You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'This paper presents an algorithm for efficient training of sparse linear models with elastic net regularization. Extending previous work on delayed updates, the new algorithm applies stochastic gradient updates to non-zero features only, bringing weights current as needed with closed-form updates. Closed-form delayed updates for the $\ell_1$, $\ell_{\infty}$, and rarely used $\ell_2$ regularizers have been described previously. This paper provides closed-form updates for the popular squared norm $\ell^2_2$ and elastic net regularizers. We provide dynamic programming algorithms that perform each delayed update in constant time. The new $\ell^2_2$ and elastic net methods handle both fixed and varying learning rates, and both standard [stochastic gradient descent]{} (SGD) and [forward backward splitting (FoBoS)]{}. Experimental results show that on a bag-of-words dataset with $260,941$ features, but only $88$ nonzero features on average per training example, the dynamic programming method trains a logistic regression classifier with elastic net regularization over $2000$ times faster than otherwise.'
author:
- |
    Zachary C. Lipton Charles Elkan\
    University of California, San Diego\
    `{zlipton, <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>`
bibliography:
- 'lazy\_updates\_arxiv.bib'
date: 'May 27th, 2015'
title: |
    Efficient Elastic Net Regularization\
    for Sparse Linear Models
---

Introduction {#section:introduction}
============

For many applications of linear classification or linear regression, training and test examples are sparse, and with appropriate regularization, a final trained model can be sparse and still achieve high accuracy. It is therefore desirable to be able to train linear models using algorithms that require time that scales only with the number of non-zero feature values.

Incremental training algorithms such as stochastic gradient descent (SGD) are widely used to learn high-dimensional models from large-scale data. These methods process each example one at a time or in small batches, updating the model on the fly. When a dataset is sparse and the loss function is not regularized, this sparsity can be exploited by updating only the weights corresponding to non-zero feature values for each example. However, to prevent overfitting to high-dimensional data, it is often useful to apply a regularization penalty, and specifically to impose a prior belief that the true model parameters are sparse and small in magnitude. Unfortunately, widely used regularizers such as $\ell_1$ (lasso), $\ell_2^2$ (ridge), and elastic net ($\ell_1 + \ell_2^2)$ destroy the sparsity of the stochastic gradient for each example, so they seemingly require most weights to be updated for every example.

This paper builds upon methods for delayed updating of weights first described by [@carpenter2008lazy], [@singer2009efficient], and [@langford2009sparse]. As each training example is processed, the algorithm updates only those weights corresponding to non-zero feature values in the example. The model is brought current as needed by first applying closed-form constant-time delayed updates for each of these weights. For sparse data sets, the algorithm runs in time independent of the nominal dimensionality, scaling linearly with the number of non-zero feature values per example.

To date, constant-time delayed update formulas have been derived only for the $\ell_1$ and $\ell_{\infty}$ regularizers, and for the rarely used $\ell_2$ regularizer. We extend previous work by showing the proper closed form updates for the popular $\ell^2_2$ squared norm regularizer and for elastic net regularization. When the learning rate varies (typically decreasing as a function of time), we show that the elastic net update can be computed with a dynamic programming algorithm that requires only constant-time computation per update.[^1]

A straightforward experimental implementation of the proposed methods shows that on a representative dataset containing the abstracts of a million articles from biomedical literature, we can train a logistic regression classifier with elastic net regularization over $2000$ times faster than using an otherwise identical implementation that does not take advantage of sparsity. Even if the standard implementation exploits sparsity when making predictions during training, additionally exploiting sparsity when doing updates, via dynamic programming, still makes learning $1400$ times faster.

Background and Definitions {#section:background}
==========================

We consider a data matrix $X \in \mathbbm{R^{n \times d}}$ where each row $\boldsymbol{x_i}$ is one of $n$ examples and each column, indexed by $j$, corresponds to one of $d$ features. We desire a linear model parametrized by a weight vector $\boldsymbol{w} \in \mathbbm{R^d}$ that minimizes a convex objective function $F(\boldsymbol{w})$ expressible as $\sum_{i=1}^{n} F_i (\boldsymbol{w})$, where $F$ is the loss with respect to the entire dataset $X$ and $F_i$ is the loss due to example $\boldsymbol{x}_i$.

In many datasets, the vast majority of feature values $x_{ij}$ are zero. The-bag-of-words representation of text is one such case. We say that such datasets are [sparse]{}. When features correspond to counts or to binary values, as in bag-of-words, we sometimes say say that a zero-valued entry $x_{ij}$ is [absent]{}. We use $p$ to refer to the average number of nonzero features per example. Naturally, when a dataset is sparse, we prefer algorithms that take time $O(p)$ per example to those that require time $O(d)$.

Regularization {#section:background-regularization}
--------------

To prevent overfitting, regularization restricts the freedom of a model’s parameters, penalizing their distance from some prior belief. Widely used regularizers penalize large weights with an objective function of the form $$\label{eqn:objective-function}
F(\boldsymbol{w}) = {L}(\boldsymbol{w}) + R(\boldsymbol{w}).$$ Many commonly used regularizers $R(\boldsymbol{w})$ are of the form $\lambda||\boldsymbol{w}||$ where $\lambda$ determines the strength of regularization and the $\ell_0$, $\ell_1$, $\ell^2_2$, or $\ell_{\infty}$ norms are common choices for the penalty function. The $\ell_1$ regularizer is popular owing to its tendency to produce sparse models. In this paper, we focus on elastic net, a linear combination of $\ell_1$ and $\ell^2_2$ regularization that has been shown to produce comparably sparse models to $\ell_1$ while often achieving superior accuracy [@zou2005regularization].

Stochastic Gradient Descent {#section:background-optimization}
---------------------------

Gradient descent is a common strategy to learn optimal parameter values $\boldsymbol{w}$. To minimize $F(\boldsymbol{w})$, a number of steps $T$, indexed by $t$, are taken in the direction of the negative gradient: $$\boldsymbol{w}^{(t+1)} := \boldsymbol{w}^{(t)} - \eta \sum_{i=1}^{n} \nabla F_i(\boldsymbol{w})$$ where the learning rate $\eta$ may be a function of time $t$. An appropriately decreasing $\eta$ ensures that the algorithm will converge to a vector $\boldsymbol{w}$ within distance $\epsilon$ of the optimal vector for any small value $\epsilon$ [@carpenter2008lazy].

Traditional (or “batch") gradient descent requires a pass through the entire dataset for each update. [Stochastic gradient descent]{} (SGD) circumvents this problem by updating the model once after visiting each example. With SGD, examples are randomly selected one at a time or in small so-called mini-batches. For simplicity of notation, without loss of generality we will assume that examples are selected one at a time. At time $t+1$ the gradient $\nabla F_i(\boldsymbol{w}^{(t)})$ is calculated with respect to the selected example $\boldsymbol{x_i}$, and then the model is updated according to the rule $$\boldsymbol{w}^{(t+1)} := \boldsymbol{w}^{(t)} - \eta \nabla F_i(\boldsymbol{w}^{(t)}).$$ Because the examples are chosen randomly, the expected value of this noisy gradient is identical to the true value of the gradient taken with respect to the entire corpus.

Given a continuously differentiable convex objective function $F(\boldsymbol{w})$, stochastic gradient descent is known to converge for learning rates $\eta$ that satisfy $\sum_t \eta_t = \infty$ and $\sum_t \eta_t^2 < \infty$ [@bottou2012stochastic]. Learning rates $\eta_i \propto {1}/{t}$ and $\eta_i \propto {1}/{\sqrt {t}}$ both satisfy these properties.[^2] For many objective functions, such as those of linear or logistic regression without regularization, the noisy gradient $\nabla F_i(\boldsymbol{w})$ is sparse when the input is sparse. In these cases, one needs only to update the weights corresponding to non-zero features in the current example $\boldsymbol{x}_i$. These updates require time $O(p)$, where $p \ll d$ is the average number of nonzero features in an example.

Regularization, however, can ruin the sparsity of the gradient. Consider an objective function as in Equation (\[eqn:objective-function\]), where $R(w) = ||\boldsymbol{w}||$ for some norm $|| \cdot ||$. In these cases, even when the feature value $x_{ij} = 0$, the partial derivative $(\partial / \partial w_j) F_i$ is nonzero owing to the regularization penalty if $w_j$ is nonzero. A simple optimization is to update a weight only when either the weight or feature is nonzero. Given feature sparsity and persistent model sparsity throughout training, not updating $w_j$ when $w_j = 0$ and $x_{ij} = 0$ provides a substantial benefit. But such an approach still scales with the size of the model, which may be far larger than $p$. In contrast, the algorithms below scale in time complexity $O(p)$.

Forward Backward Splitting {#section:background-fobos}
--------------------------

Proximal algorithms are an approach to optimization in which each update consists of solving a convex optimization problem [@parikh2013proximal]. Forward Backward Splitting (FoBoS) [@singer2009efficient] is a proximal algorithm that provides a principled approach to online optimization with non-smooth regularizers. We first step in the direction of the negative gradient of the differentiable unregularized loss function. We then update the weights by solving a convex optimization problem that simultaneously penalizes distance from the new parameters and minimizes the regularization term. In FoBoS, first a standard unregularized stochastic gradient step is applied: $$\boldsymbol{w}^{(t+\frac{1}{2})} = \boldsymbol{w}^{(t)} - \eta^{(t)} \nabla {L}_i(\boldsymbol{w}^{(t)}).$$ Note that if $(\partial / \partial w_j) L_i = 0$ then $w_j^{(t+\frac{1}{2})} = w_j^{(t)}$. Then a convex optimization is solved, applying the regularization penalty. For elastic net the problem to be solved is $$\boldsymbol{w}^{(t+1)} = \operatorname{argmin}_w \left( \frac{1}{2} || \boldsymbol{w}-\boldsymbol{w}^{(t+\frac{1}{2})} ||_2^2 
    + \eta^{t}\lambda_1 ||\boldsymbol{w}||_1 + \frac{1}{2} \eta^{t} \lambda_2 ||\boldsymbol{w}||_2^2 \right).
\label{eqn:fobos-update}$$ The problems corresponding to $\ell_1$ or $\ell_2^2$ separately can be derived by setting the corresponding $\lambda$ to $0$.

Lazy Updates {#section:lazy-updates}
============

The idea of lazy updating was introduced in [@carpenter2008lazy], [@langford2009sparse], and [@singer2009efficient]. This paper extends the idea for the cases of $\ell_2^2$ and elastic net regularization. The essence of the approach is given in Algorithm (\[alg:lazy\]). We maintain an array $\boldsymbol{\psi} \in \mathbbm{R}^d$ in which each $\psi_j$ stores the index of the last iteration at which the value of weight $j$ was current. When processing example $\boldsymbol{x}_i$ at time $k$, we iterate through its nonzero features $x_{ij}$. For each such nonzero feature, we lazily apply the $k-\psi_j$ delayed updates collectively in constant time, bringing its weight $w_j$ current. Using the updated weights, we compute the prediction $\hat{y}^{(k)}$ with the fully updated relevant parameters from $\boldsymbol{w}^{(k)}$. We then compute the gradient and update these parameters.

When training is complete, we pass once over all nonzero weights to apply the delayed updates to bring the model current. Provided that we can apply any number $k-\psi_j$ of delayed updates in $O(1)$ time, the algorithm processes each example in $O(p)$ time regardless of the dimension $d$.

\[alg:lazy\]

To use the approach with a chosen regularizer, it remains only to demonstrate the existence of constant time updates. In the following subsections, we derive constant-time updates for $\ell_1$, $\ell_2^2$ and elastic net regularization, starting with the simple case where the learning rate $\eta$ is fixed during each epoch, and extending to the more complicated case when the learning rate is decreased every iteration as a function of time.[^3]

Prior Work {#section:prior-work}
==========

Over the last several years, a large body of work has advanced the field of online learning. Notable contributions include ways of adaptively decreasing the learning rate separately for each parameter such as AdaGrad [@duchi2011adaptive] and AdaDelta [@zeiler2012adadelta], using small batches to reduce the variance of the noisy gradient [@li2014efficient], and other variance reduction methods such as Stochastic Average Gradient (SAG) [@schmidt2013minimizing] and Stochastic Variance Reduced Gradient (SVRG) [@johnson2013accelerating].

In 2008, Carpenter described an idea for performing lazy updates for stochastic gradient descent [@carpenter2008lazy]. With that method, we maintain a vector $\boldsymbol{\psi} \in \mathbbm{N}^d$, where each $\psi_i$ stores the index of the last epoch in which each weight was last regularized. We then perform periodic batch updates. However, as the paper acknowledges, the approach described results in updates that do not produce the same result as applying an update after each time step.

Langford *et al.* concurrently developed an approach for lazily updating $\ell_1$ regularized linear models [@langford2009sparse]. They restrict attention to $\ell_1$ models. Additionally, they describe the closed form update only when the learning rate $\eta$ is constant, although they suggest that an update can be derived when $\eta_t$ decays as $t$ grows large. We derive constant-time updates for $\ell_2^2$ and elastic net regularization. Our algorithms are applicable with both fixed and varying learning rates.

In 2008 also, as mentioned above, Duchi and Singer described the FoBoS method [@duchi2008efficient]. They share the insight of applying updates lazily when training on sparse high-dimensional data. Their lazy updates hold for norms $\ell_q$ for $q \in \{1,2,\infty \}$, However they do not hold for the commonly used $\ell^2_2$ squared norm. Consequently they also do not hold for mixed regularizers involving $\ell^2_2$ such as the widely used elastic net $(\ell_1 + \ell^2_2)$.

Constant-Time Lazy Updating for SGD {#section:lazy-attenuated}
===================================

In this section, we derive constant-time stochastic gradient updates for use when processing examples from sparse datasets. Using these, the lazy update algorithm can train linear models with time complexity $O(p)$ per example. For brevity, we describe the more general case where the learning rate is varied. When the learning rate is constant the algorithm can be easily modified to have $O(1)$ space complexity.

Lazy $\ell_1$ Regularization with Decreasing Learning Rate {#section:lazy-lasso-attenuated}
----------------------------------------------------------

The closed-form update for $\ell_1$ regularized models is [@singer2009efficient] $$w_j^{(k)} = \operatorname{sgn}(w_j^{(\psi_j)}) \left[ |w_j^{(\psi_j)}| -   \lambda_1  \left( S(k-1) - S(\psi_j -1) \right) \right]_+
\label{eq:l1_lazy_update}$$ where $S(t)$ is a function that returns the partial sum $ \sum_{\tau=0}^{t} \eta^{(\tau)}$. The sum $\sum_{\tau=t}^{t+n-1} \eta^{(\tau)}$ can be computed in constant time using a caching approach. On each iteration $t$, we compute $S(t)$ in constant time given its predecessor as $S(t) = \eta^{(t)} + S(t-1)$. The base case for this recursion is $S(0) = \eta^{(0)}$. We then cache this value in an array for subsequent constant time lookup.

When the learning rate decays with $1/t$, the terms $\eta ^ {(\tau)}$ follow the harmonic series,. Each partial sum of the harmonic series is a harmonic number $H(t) = \sum_{i=1}^{t} {1}/{t}$. Clearly $$\sum_{\tau =t}^{t+n-1} \eta^{(\tau)} = \eta^{(0)} \left( H(t+n) - H(t) \right)$$ where $H_\tau$ is the $\tau_{th}$ harmonic number. While there is no closed-form expression to calculate the $\tau_{th}$ harmonic number, there exist good approximations.

The $O(T)$ space complexity of this algorithm may seem problematic. However, this problem is easily dealt with by bringing all weights current after each epoch. The cost to do so is amortized across all iterations and is thus negligible.

Lazy $\ell_2^2$ Regularization with Decreasing Learning Rate {#section:lazy-ridge-attenuated}
------------------------------------------------------------

For a given example $\boldsymbol{x}_i$, if the feature value $x_{ij} = 0$ and the learning rate is varying, then the stochastic gradient update rule for an $\ell^2_2$ regularized objective is $$\label{}
w_j^{(t+1)} = w_j^{(t)} - \eta^{(t)} \lambda_2 w_j^{(t)}.$$ The decreasing learning rate prevents collecting successive updates as terms in a geometric series, as we could if the learning rate were fixed. However, we can employ a dynamic programming strategy.

For SGD with $\ell_2^2$ regularization, the constant-time lazy update to bring a weight current from iteration $\psi_j$ to $k$ is $$w_j^{(k)} = w_j^{(\psi_j)} \frac{P(k-1)}{P(\psi_j -1)}$$ where P(t) is the partial product $\prod_{\tau=0}^{t} (1- \eta^{(\tau)} \lambda_2).$

Rewriting the multiple update expression yields $$\label{}
\begin{split}
    w_j^{(t+1)}     & = w_j^{(t)} ( 1 - \eta^{(t)} \lambda_2 ) \\
        w_j^{(t+n)} & = w_j^{(t)} ( 1 - \eta^{(t)} \lambda_2 )( 1 - \eta^{(t+1)} \lambda_2 )
                    \cdot ... \cdot
                    (1 - \eta^{(t+n-1)} \lambda_2).
\end{split}$$ The products $P(t) = \prod_{\tau=0}^{t}  (1 - \eta^{(\tau)} \lambda_2) \ $ can be cached on each iteration in constant time using the recursive relation $$P(t)=(1-\eta^{(t)}\lambda_2)P(t-1).$$ The base case is $P(0) = a_0 = (1-\eta_0 \lambda_2).$ Given cached values $P(0),...,P(t+n)$, it is then easy to calculate the exact lazy update in constant time: $$w_j^{(t+n)} = w_j^{(t)} \frac{P(t+n-1)}{P(t-1)}.$$ The claim follows.

As in the case of $\ell_2^2$ regularization with fixed learning rate, we need not worry that the regularization update will flip the sign of the weight $w_j$, because $P(t) >0$ for all $t \geq 0$.

Lazy Elastic Net Regularization with Decreasing Learning Rate {#section:lazy-elastic-attenuated}
-------------------------------------------------------------

Next, we derive the constant time lazy update for SGD with elastic net regularization. Recall that a model regularized by elastic net has an objective function of the form $$F(w) = {L}(w) + \lambda_1 ||w ||_1 + \frac{\lambda_2}{2} ||w||_2^2.$$ When a feature $x_j = 0$, the SGD update rule is $$\label{eqn:elastic-attenuated-update}
\begin{split}
w_j^{(t+1)} & = \operatorname{sgn}(w_j^{(t)}) \left[| w_j^{(t)}| -
                \eta^{(t)} \lambda_1 -\eta^{(t)} \lambda_2 |w_j^{(t)}| \right]_+ \\
            & =  \operatorname{sgn}(w_j^{(t)}) \left[(1 - \eta^{(t)} \lambda_2)| w_j^{(t)}| -
                \eta^{(t)} \lambda_1 \right]_+
\end{split}$$

To bring the weight $w_j$ current from time $\psi_j$ to time $k$ using repeated Equation (\[eqn:elastic-attenuated-update\]) updates, the constant time update is $$w_j^{(k)} = \operatorname{sgn}(w_j^{(\psi_j)}) \left[ |w_j^{(\psi_j)}| \frac{P(k-1)}{P(\psi_j -1)}  -
             P(k-1) \cdot \left( B(k-1) - B(\psi_j -1) \right) \right]_+$$ where $P(t) = (1-\eta^{(t)} \lambda_2) \cdot P(t-1)$ with base case $P(-1) = 1$ and $B(t) = \sum_{\tau = 0}^{t} {\eta^{(\tau)}}/{P(\tau - 1) }$ with base case $B(-1) = 0$.

The time-varying learning rate prevents us from working out a simple expansion. Instead, we can write the following inductive expression for consecutive terms in the sequence: $$\begin{split}
    w_j^{(t+1)} & =\operatorname{sgn}(w_j^{(t)}) \left[ (1- \eta^{(t)} \lambda_2) |w_j^{(t)}| - \eta^{(t)} \lambda_1   \right]_+ \\
\end{split}$$ Writing $a_{\tau} = (1- \eta^{(\tau)} \lambda_2)$ and $b_{\tau} = -\eta^{(\tau)} \lambda_1$ gives $$\begin{split}
    w^{(t+1)} & = \operatorname{sgn}(w_j^{(t)}) \left[ a_t |w^{(t)}| + b_t \right]_+ \\
            & ... \\
    w^{(t+n)}   & = \operatorname{sgn}(w_j^{(t)}) \left[
        a_{(t+n-1)} ( ... a_{(t+1)} \left( a_{t} w^{t} - b_t \right) - b_{(t+1)} ... ) - b_{(t+n-1)}
        \right]_+ \\
    & = \operatorname{sgn}(w_j^{(t)}) \left[ |w_j^{(t)}| \prod_{\tau=t}^{t+n-1} a_{\tau}
        + \sum_{\tau= t}^{t+n-2} b_i \left( \prod_{q=\tau}^{t+n-2} a_q \right) + b_{(t+n-1)}
        \right]_+
\end{split}$$ The leftmost term $\prod_{\tau=t}^{t+n-1} a_{\tau}$ can be calculated in constant time as $P(t+n-1)/P(t-1)$ using cached values from the dynamic programming scheme discussed in the previous section. To cache the remaining terms, we group the center and rightmost terms and apply the simplification $$\sum_{\tau= t}^{t+n-2} b_i \left( \prod_{q=\tau}^{t+n-2} a_q \right) + b_{t+n-1}$$ $$\begin{split}
    & = b_{t} \frac{P(t+n-2)}{P(t-1)} + b_{t+1} \frac{P(t+n-2)}{P(t)} + ... + b_{t+n-1} \frac{P(t+n-2)}{P(t+n-2)} \\
        & =     - \lambda_1 P(t+n-2) \left( \frac{\eta^{(t)}}{P(t-1) }
            +  \frac{\eta^{(t+1)}}{P(t)} +  ... + \frac{\eta^{(t+n-1)}}{P(t+n-2)} \ \ \right).
\end{split}$$

We now add a new layer to the dynamic programming formulation. In addition to precalculating all values $P(t)$ as we go, we define a partial sum over inverses of partial products $$B(t) = \sum_{\tau = 0}^{t} \frac{\eta^{(\tau)}}{P(\tau - 1) }.$$ Given that $P(t-1)$ can be accessed in constant time at time $t$, $B(t)$ can now be cached in constant time. With the base case $B(-1) = 0$, the dynamic programming here depends upon the recurrence relation $$B(t) = B(t-1) + \frac{\eta^{(t)}}{P(t - 1) } .$$

Then, for SGD elastic net with decreasing learning rate, the update rule to apply any number $n$ of consecutive regularization updates in constant time to weight $w_j$ is $$\begin{split}
w^{(t+n)} & = \operatorname{sgn}(w_j^{(t)}) \left[
        |w_j^{(t)}| \frac{P(t+n-1)}{P(t -1)}  - \lambda_1 P(t+n-1) \left( B(t+n-1) - B(t -1) \right)
    \right]_+
\end{split}$$

Lazy Updates for Forward Backward Splitting {#section:lazy-fobos}
===========================================

Here we turn our attention to FoBoS updates for $\ell^2_2$ and elastic net regularization. For $\ell_2^2$ regularization, to apply the regularization update we solve the problem from Equation (\[eqn:fobos-update\]) with $\lambda_1$ set to $0$. Solving for $\boldsymbol{w}^*$ gives the update $$w_j^{(t+1)} = \frac{w_j^{(t)}}{1+ \eta^{(t)} \lambda_2}$$ when $x_{ij} = 0$. Note that this differs from the standard stochastic gradient descent step. We can store the values $\Phi(t) = \prod_{\tau=0}^{t} \frac{1}{1+\eta^{t}\lambda_2}$. Then, the constant time lazy update for FoBoS with $\ell_2^2$ regularization to bring a weight current at time $k$ from time $\psi_j$ is $$w_j^{(k)} = w_j^{(\psi_j)} \frac{\Phi(k-1)}{\Phi(\psi_j-1)}$$ where $\Phi(t) = (1+\eta^{(t)} \lambda_2)^{-1} \cdot \Phi(t-1)$ with base case $\Phi(0) = \frac{1}{1+\eta^{0}\lambda_2}$.

Finally, in the case of elastic net regularization via forward backward splitting, we solve the convex optimization problem from Equation (\[eqn:fobos-update\]). This objective also comes apart and can be optimized for each $w_j$ separately. Setting the derivative with respect to $w_j$ to zero yields the solution $$w_j^{(t+1)} = \operatorname{sgn}(w^{(t)}_j) \left[ \frac{|w_j^{(t)}| - \eta^{(t)}\lambda_1}{\eta^{t} \lambda_2 + 1} \right]_+$$

A constant-time lazy update for FoBoS with elastic net regularization and decreasing learning rate to bring a weight current at time $k$ from time $\psi_j$ is $$w_j^{(k)} = \operatorname{sgn}(w_j^{(\psi_j)}) \left[ |w_j^{(\psi_j)}| \frac{\Phi(k-1)}{\Phi(\psi_j-1)}
- \Phi(k-1)\cdot \lambda_1   \left( \beta(k-1)- \beta(\psi_j-1) \right) \right]_+$$ where $\Phi(t)=\Phi(t-1) \cdot \frac{1}{1+\eta^{t} \lambda_2}$ with base case $\Phi(-1) = 1$ and $\beta(t) = \beta(t-1) + \frac{\eta^{(t)}}{\Phi(t-1)}$ with base case $\beta(-1) = 0$.

Write $a_{t} = (\eta^{(t)}\lambda_2+1)^{-1}$ and $b_t=-\eta^{(t)} \lambda_1$. Note that neither $a_t$ nor $b_t$ depends upon $w_j$. Consider successive updates: $$\begin{split}
w_j^{(t+1)}     & = \operatorname{sgn}(w_j^{(t)}) \left[ a_t(|w_j^{(t)}| +b_t) \right]_+ \\
w_j^{(t+n)}     &= \operatorname{sgn}(w_j^{(t)}) \left[ |w_j^{(t)}| \prod_{\beta=t}^{t+n-1} a_{\beta} +
\sum_{\tau=t}^{t+n-1} \left( b_{\tau} \prod_{\alpha = \tau}^{t+n-1} a_{\alpha} \right) \right]_+.
\end{split}$$ Inside the square brackets, $\frac{\Phi(t+n-1)}{\Phi(t-1)}$ can be substituted for $\prod_{\beta=t}^{t+n-1} a_{\beta}$ and the second term can be expanded as $$\begin{split}
\sum_{\tau=t}^{t+n-1} \left( b_{\tau} \prod_{\alpha = \tau}^{t+n-1} a_{\alpha} \right) &=
\sum_{\tau=t}^{t+n-1} \left( b_{\tau} \frac{\Phi(t+n-1)}{\Phi(\tau-1)} \right) \\
        &= - \Phi(t+n-1)\cdot  \lambda_1  \sum_{\tau=t}^{t+n-1} \left( \frac{\eta^{(\tau)}}{\Phi(\tau-1)} \right)   \\
\end{split}$$ Using the dynamic programming approach, for each time $t$, we calculate $$\beta(t) = \beta(t-1) + \frac{\eta^{(t)}}{\Phi    (t-1)}$$ with the base cases $\beta(0) = \eta^{(0)}$ and $\beta(-1) = 0$. Then $$w_j^{(t+n)} = \operatorname{sgn}(w_j^{(t)}) \left[ |w_j^{(t)}| \frac{\Phi(t+n-1)}{\Phi(t-1)}
- \Phi(t+n-1)\cdot \lambda_1   \left( \beta(t+n-1)- \beta(t-1) \right) \right]_+$$

Experiments {#section:experiments}
===========

The usefulness of logistic regression with elastic net regularization is well-known. To confirm the correctness and speed of the dynamic programming algorithm just presented, we implemented it and tested it on a bag-of-words representation of abstracts from biomedical articles indexed in Medline as described in [@lipton2014optimal]. The dataset contains exactly $10^6$ examples, $260,941$ features and an average of $88.54$ nonzero features per document.

We implemented algorithms in Python. Datasets are represented by standard sparse SciPy matrices. We implemented both standard and lazy FoBoS for logistic regression regularized with elastic net. We confirmed on a synthetic dataset that the standard FoBoS updates and lazy updates output essentially identical weights. To make a fair comparison, we also report results where the non-lazy algorithm exploits sparsity when calculating predictions. Even when both methods exploit sparsity to calculate $\hat{y}$, lazy updates lead to training over $1400$ times faster. Note that sparse data structures must be used even with dense updates, because a dense matrix to represent the input dataset would use an unreasonable amount of memory.

Logistic regression with lazy elastic net regularization runs approximately $2000$ times faster than with dense regularization updates for both SGD and FoBoS. In the absence of overhead, exploiting sparsity should yield a $2947\times$ speedup. Clearly the additional dynamic programming calculations do not erode the benefits of exploiting sparsity. While the dynamic programming strategy consumes space linear in the number of iterations, it does not present a major time penalty. Concerning space, storing two floating point numbers for each time step $t$ is a modest use of space compared to storing the data itself. Further, if space ever were a problem, all weights could periodically be brought current. The cost of this update would be amortized across all iterations and thus would be negligible.

           **Lazy Updates**   Dense Updates   Dense with Sparse Predictions
  ------- ------------------ --------------- -------------------------------
    SGD       **.0102**          21.377                  14.381
   FoBoS      **.0120**          22.511                  16.785

  : Average time in seconds for each algorithm to process one example.

\[table:speed\]

Discussion {#section:discussion}
==========

Many interesting datasets are high-dimensional, and many high-dimensional datasets are sparse. To be useful, learning algorithms should have time complexity that scales with the number of non-zero feature values per example, as opposed to with the nominal dimensionality. This paper provides algorithms for fast training of linear models with $\ell_2^2$ or with elastic net regularization. Experiments confirm the correctness and empirical benefit of the method. In future work we hope to use similar ideas to take advantage of sparsity in nonlinear models, such as the sparsity provided by rectified linear activation units in modern neural networks.

### Acknowledgments {#acknowledgments .unnumbered}

This research was conducted with generous support from the Division of Biomedical Informatics at the University of California, San Diego, which has funded the first author via a training grant from the National Library of Medicine. Galen Andrew began evaluating lazy updates for multilabel classification with Charles Elkan in the summer of 2014. His notes provided an insightful starting point for this research. Sharad Vikram provided invaluable help in checking the derivations of closed form updates.

[^1]: The dynamic programming algorithms below for delayed updates with varying learning rates use time O(1) per update, but have space complexity $O(T)$ where $T$ is the total number of stochastic gradient updates. If this space complexity is too great, that problem can be solved by allotting a fixed space budget and bringing all weights current whenever the budget is exhausted. As the cost of bringing weights current is amortized across many updates, it adds negligibly to the total running time.

[^2]: Some common objective functions, such as those involving $\ell_1$ regularization, are not differentiable when weights are equal to zero. However, forward backward splitting (FoBoS) offers a principled approach to this problem [@singer2009efficient].

[^3]: The results hold for schedules of weight decrease that depend on time, but cannot be directly applied to AdaGrad [@duchi2011adaptive] or RMSprop, methods where each weight has its own learning rate which is decreased with the inverse of the accumulated sum (or moving average) of squared gradients with respect to that weight.