Section 3.1: Stochastic Gradient Descent

Let us consider the following standard stochastic optimization problem:

\[\begin{align}\label{eqn:so} \min_{\mathbf{w}}g(\mathbf{w}) := \mathbb{E}_{\zeta}[g(\mathbf{w}; \zeta)]. \end{align}\]

If \(g\) is differentiable, the stochastic gradient descent (SGD) method takes the following update:

\[\begin{align}\label{eqn:sgd} \mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \nabla g(\mathbf{w}_t; \zeta_t), \end{align}\]

where \(\zeta_t\) is a random sample. If \(g\) is non-differentiable, we use a stochastic subgradient \(\mathcal{G}(\mathbf{w}; \zeta)\) to update the model parameter:

\[\begin{align}\label{eqn:sgd-ns} \mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \mathcal{G}(\mathbf{w}_t; \zeta_t). \end{align}\]

The key assumption regarding the stochastic gradient or subgradient is the following.

When SGD is applied to solving ERM, \(\zeta_t\) could represent one randomly sampled data with an index from \(\{1,\ldots,n\}\) or a mini-batch of random data.

Below, we present the convergence analysis for smooth and non-smooth, convex and non-convex objective functions.

3.1.1 Smooth Convex Functions

For a point \(\mathbf{w}\), convergence is typically measured by the objective gap: \[ g(\mathbf{w}) - \min_{\mathbf{w}} g(\mathbf{w}) = g(\mathbf{w}) - g(\mathbf{w}_*), \] where \(\mathbf{w}_*\) denotes a global optimal solution. A convergence analysis aims to show that after \(T\) iterations of updates, we can obtain a solution \(\hat{\mathbf{w}}_T\) such that the expected objective gap is bounded by \[ \mathbb{E}\left[g(\hat{\mathbf{w}}_T) - g(\mathbf{w}_*)\right] \leq O\left(\frac{1}{T^{\alpha}}\right), \] for some \(\alpha > 0\). The term \(1/T^\alpha\) is referred to as the convergence rate. Accordingly, to guarantee a small objective gap \(\mathbb{E}[g(\hat{\mathbf{w}}_T) - g(\mathbf{w}_*)] \leq \epsilon\) for some \(\epsilon \ll 1\), the bound implies that \(T = O\left(\frac{1}{\epsilon^{1/\alpha}}\right)\), which is known as the iteration complexity.

Let us first assume that \(g\) is smooth and its stochastic gradient \(\nabla g(\mathbf{w}; \zeta)\) satisfies the following assumption.

The following lemma is useful for convergence analysis.

■

The following lemma shows one-step objective gap bound.

Proof.
From Lemma 3.1, we have

\[\begin{equation}\label{eqb:sgd-sm-1} \begin{aligned} \nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_{t+1} - \mathbf{w})\leq & \frac{1}{2\eta_t}\|\mathbf{w} - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w} - \mathbf{w}_{t+1}\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2\\ & +(\nabla g(\mathbf{w}_t)- \nabla g(\mathbf{w}_t; \zeta_t))^{\top}(\mathbf{w}_{t+1} - \mathbf{w}). \end{aligned} \end{equation}\]

By the smoothness and convexity of \(g\), we have

\[\begin{equation}\label{eqn:scg-cross} \begin{aligned} g(\mathbf{w}_{t+1})&\leq g(\mathbf{w}_t) +\nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_{t+1} - \mathbf{w}_t) + \frac{L}{2}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2\\ &\leq g(\mathbf{w}) + \nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_ t- \mathbf{w})+\nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_{t+1} - \mathbf{w}_t) + \frac{L}{2}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2\\ &\leq g(\mathbf{w})+\nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_{t+1} - \mathbf{w}) + \frac{L}{2}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2. \end{aligned} \end{equation}\]

Combining this with (\(\ref{eqb:sgd-sm-1}\)), we have

\[\begin{equation}\label{eqn:sgd-sm-1} \begin{aligned} g(\mathbf{w}_{t+1}) -g(\mathbf{w})\leq & \frac{1}{2\eta_t}\|\mathbf{w} - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w} - \mathbf{w}_{t+1}\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2 \\ & + \frac{L}{2}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2 +(\nabla g(\mathbf{w}_t)- \nabla g(\mathbf{w}_t; \zeta_t))^{\top}(\mathbf{w}_{t+1} - \mathbf{w}). \end{aligned} \end{equation}\]

Then if \(\eta_t\leq 1/L\) and plugging \(\mathbf{w}=\mathbf{w}_*\), we have \[\begin{align*} g(\mathbf{w}_{t+1}) -g(\mathbf{w}_*)\leq & \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_{t+1}\|_2^2 \\ &+(\nabla g(\mathbf{w}_t)- \nabla g(\mathbf{w}_t; \zeta_t))^{\top}(\mathbf{w}_{t+1} - \mathbf{w}_*). \end{align*}\]

To bound the last term, we introduce \[ \hat{\mathbf{w}}_{t+1} = \arg\min_{\mathbf{w}} \nabla g(\mathbf{w}_t)^{\top}(\mathbf{w} - \mathbf{w}_t) + \frac{1}{2\eta_t}\|\mathbf{w} - \mathbf{w}_t\|_2^2. \] Note that \(\hat{\mathbf{w}}_{t+1}\) is independent of \(\zeta_t\). Then \(\mathbb{E}_{\zeta_t}[(\nabla g(\mathbf{w}_t)- \nabla g(\mathbf{w}_t; \zeta_t))^{\top}(\hat{\mathbf{w}}_{t+1} - \mathbf{w}_*)]=0\). Thus, we have \[\begin{align*} \mathbb{E}[g(\mathbf{w}_{t+1}) -g(\mathbf{w}_*)]\leq & \mathbb{E}\left[\frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_{t+1}\|_2^2\right] \\ &+\mathbb{E}[(\nabla g(\mathbf{w}_t)- \nabla g(\mathbf{w}_t; \zeta_t))^{\top}(\mathbf{w}_{t+1} - \hat{\mathbf{w}}_{t+1})]. \end{align*}\]

■

Proof.

If \(\eta_t=\eta\), summing the inequalities in Lemma 3.1 over \(t=1,\ldots,T\), we have \[ \begin{align*} \mathbb{E}\bigg[\sum_{t=1}^T(g(\mathbf{w}_{t+1})-g(\mathbf{w}_*))\bigg] \leq &\ \mathbb{E}\left[\sum_{t=1}^T\frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_t\|_2^2-\frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_{t+1}\|_2^2\right] \\ &+T\eta\sigma^2. \end{align*} \]

The first term in \([\cdot]\) is a telescoping series, \[ \begin{align*} &\sum_{t=1}^T\frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_t\|_2^2-\frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_{t+1}\|_2^2 \leq \frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_1\|_2^2-\frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_{T+1}\|_2^2 \\ &\leq \frac{1}{2\eta}\|\mathbf{w}_*-\mathbf{w}_1\|_2^2. \end{align*} \]

As a result, \[ \begin{align*} \mathbb{E}\bigg[\frac{1}{T}\sum_{t=1}^T(g(\mathbf{w}_{t+1})-g(\mathbf{w}_*))\bigg] \leq &\ \frac{1}{2\eta T}\|\mathbf{w}_*-\mathbf{w}_1\|_2^2+\eta\sigma^2, \end{align*} \] which concludes the proof of the first part of the theorem.

For the second part, optimizing the upper bound over \(\eta\) gives \(\eta_*=\frac{\|\mathbf{w}_1-\mathbf{w}_*\|_2}{\sqrt{2T}\sigma}\). If \(\eta_*\leq 1/L\), i.e., \(T\geq\frac{\|\mathbf{w}_1-\mathbf{w}_*\|_2^2L^2}{2\sigma^2}\), we set \(\eta=\eta_*\), then \[ \mathbb{E}\left[g(\bar{\mathbf{w}}_{T})-g(\mathbf{w}_*)\right] \leq \frac{2\sigma\|\mathbf{w}_1-\mathbf{w}_*\|_2}{\sqrt{2T}}. \]

If \(\eta_*>1/L\), i.e., \(\sigma^2\leq\frac{\|\mathbf{w}_1-\mathbf{w}_*\|_2^2L^2}{2T}\), we set \(\eta=1/L\), then \[ \mathbb{E}\left[g(\bar{\mathbf{w}}_{T})-g(\mathbf{w}_*)\right] \leq \frac{L\|\mathbf{w}_1-\mathbf{w}_*\|_2^2}{2T}+\frac{L\|\mathbf{w}_1-\mathbf{w}_*\|_2^2}{2T} =\frac{L\|\mathbf{w}_1-\mathbf{w}_*\|_2^2}{T}. \]

■

3.1.2 Non-smooth Convex Functions

Now, let us consider the SGD update (\(\ref{eqn:sgd-ns}\)) for non-smooth convex functions under the following assumption.

Proof.
From Lemma 3.1, we have

\[\begin{equation}\label{eqb:sgd-nsm-1} \begin{aligned} \mathcal{G}(\mathbf{w}_t; \zeta_t)^{\top}(\mathbf{w}_{t} - \mathbf{w}_*)&\leq \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_{t+1}\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_{t+1} - \mathbf{w}_t\|_2^2\\ & +\mathcal{G}(\mathbf{w}_t; \zeta_t)^{\top}(\mathbf{w}_{t+1} - \mathbf{w}_t)\\ & \leq \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_{t+1}\|_2^2 +\frac{\eta_t}{2}\|\mathcal{G}(\mathbf{w}_t; \zeta_t)\|_2^2, \end{aligned} \end{equation}\]

where the last inequality uses Young’s inequality. Taking expectation on both sides, we have

\[\begin{equation}\label{eqb:sgd-nsm-2} \begin{aligned} \mathbb{E}[\mathcal{G}(\mathbf{w}_t; \zeta_t)^{\top}(\mathbf{w}_{t} - \mathbf{w}_*)]\leq \mathbb{E}\left[\frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_t\|_2^2 - \frac{1}{2\eta_t}\|\mathbf{w}_* - \mathbf{w}_{t+1}\|_2^2\right] +\frac{\eta_t}{2}G^2. \end{aligned} \end{equation}\]

■

■

3.1.3 Smooth Non-Convex Functions

For a non-convex function, it is generally NP-hard to find a global optimal solution. Hence, our goal here is to establish the complexity of SGD for finding an \(\epsilon\)-stationary solution with \(\epsilon\ll 1\), as defined below.

Proof.

For brevity of notation, we let \(\nabla g_t(\mathbf{w}_t)=\nabla g(\mathbf{w}_t;\zeta_t)\). Due to the \(L\)-smoothness of \(g\), we have \[ \begin{align*} &g(\mathbf{w}_{t+1})\leq g(\mathbf{w}_t)+\nabla g(\mathbf{w}_t)^{\top}(\mathbf{w}_{t+1}-\mathbf{w}_t)+\frac{L}{2}\|\mathbf{w}_{t+1}-\mathbf{w}_t\|_2^2\\ &=g(\mathbf{w}_t)-\eta_t\nabla g(\mathbf{w}_t)^{\top}\nabla g_t(\mathbf{w}_t)+\frac{\eta_t^2L}{2}\|\nabla g_t(\mathbf{w}_t)\|_2^2\\ &=g(\mathbf{w}_t)-\eta_t\|\nabla g(\mathbf{w}_t)\|_2^2+\eta_t\nabla g(\mathbf{w}_t)^{\top}(\nabla g(\mathbf{w}_t)-\nabla g_t(\mathbf{w}_t))+\frac{\eta_t^2L}{2}\|\nabla g_t(\mathbf{w}_t)\|_2^2\\ &=g(\mathbf{w}_t)-\eta_t\|\nabla g(\mathbf{w}_t)\|_2^2+\eta_t\nabla g(\mathbf{w}_t)^{\top}(\nabla g(\mathbf{w}_t)-\nabla g_t(\mathbf{w}_t))\\ &\quad+\frac{\eta_t^2L}{2}\|\nabla g_t(\mathbf{w}_t)-\nabla g(\mathbf{w}_t)+\nabla g(\mathbf{w}_t)\|_2^2\\ &=g(\mathbf{w}_t)-\left(\eta_t-\frac{\eta_t^2L}{2}\right)\|\nabla g(\mathbf{w}_t)\|_2^2+(\eta_t-\eta_t^2L)\nabla g(\mathbf{w}_t)^{\top}(\nabla g(\mathbf{w}_t)-\nabla g_t(\mathbf{w}_t))\\ &\quad+\frac{\eta_t^2L}{2}\|\nabla g_t(\mathbf{w}_t)-\nabla g(\mathbf{w}_t)\|_2^2. \end{align*} \]

Taking expectation over \(\zeta_t\) given \(\mathbf{w}_t\) on both sides, we have

\[ \begin{align}\label{eq:ncvx_base} \mathbb E_{\zeta_t}\left[g(\mathbf{w}_{t+1})\right] \leq g(\mathbf{w}_t)-\left(\eta_t-\frac{\eta_t^2L}{2}\right)\|\nabla g(\mathbf{w}_t)\|_2^2+\frac{\eta_t^2L}{2}\sigma^2. \end{align} \]

Telescoping this from \(t=1\) to \(T\) gives \[ \begin{align*} \mathbb E\left[\sum_{t=1}^T\left(\eta_t-\frac{\eta_t^2L}{2}\right)\|\nabla g(\mathbf{w}_t)\|_2^2\right] \leq g(\mathbf{w}_1)-g(\mathbf{w}_*)+\sum_{t=1}^T\frac{\eta_t^2L}{2}\sigma^2. \end{align*} \]

As a result, \[ \begin{align*} \mathbb E\left[\|\nabla g(\mathbf{w}_{\tau})\|_2^2\right] \leq \frac{g(\mathbf{w}_1)-g(\mathbf{w}_*)}{\sum_{t=1}^T\left(\eta_t-\frac{\eta_t^2L}{2}\right)} +\frac{\sum_{t=1}^T\eta_t^2L}{2\sum_{t=1}^T\left(\eta_t-\frac{\eta_t^2L}{2}\right)}\sigma^2. \end{align*} \]

Plugging the value \(\eta_t=\min\left(\frac{1}{L},\frac{D}{\sigma\sqrt{T}}\right)\), we have \[ \begin{align*} &\mathbb E\left[\|\nabla g(\mathbf{w}_{\tau})\|_2^2\right] \leq \frac{g(\mathbf{w}_1)-g(\mathbf{w}_*)}{T\left(\eta_1-\frac{\eta_1^2L}{2}\right)} +\frac{T\eta_1^2L}{2T\left(\eta_1-\frac{\eta_1^2L}{2}\right)}\sigma^2\\ &\leq \frac{2(g(\mathbf{w}_1)-g(\mathbf{w}_*))}{T\eta_1}+\eta_1L\sigma^2\\ &\leq \max\left(\frac{2L(g(\mathbf{w}_1)-g(\mathbf{w}_*))}{T}, \frac{2(g(\mathbf{w}_1)-g(\mathbf{w}_*))\sigma}{D\sqrt{T}}\right) +\frac{D\sigma L}{\sqrt{T}}\\ &\leq \frac{2L(g(\mathbf{w}_1)-g(\mathbf{w}_*))}{T} +\left(\frac{2(g(\mathbf{w}_1)-g(\mathbf{w}_*))}{D}+DL\right)\frac{\sigma}{\sqrt{T}}. \end{align*} \]

If we set \(\eta_t=\min\left(\frac{1}{L},\frac{D}{\sigma\sqrt{t}}\right)\), then \(\sum_{t=1}^T\eta_t\geq\Omega(\sqrt{T})\) and \(\sum_{t=1}^T\eta_t^2\leq O(\log T)\), hence \(\mathbb E\left[\|\nabla g(\mathbf{w}_{\tau})\|_2^2\right]\leq O(\log T/T)\).

■

3.1.4 Non-smooth Weakly Convex Functions

Next, let us extend the analysis to non-smooth non-convex functions. Consider a function \(g: \mathbb{R}^d\mapsto \mathbb{R}\) and a point \(\mathbf{w}\in\mathbb{R}^d\) with \(g(\mathbf{w})\) finite. The Fréchet subdifferential of \(g\) at \(\mathbf{w}\), denoted \(\partial g(\mathbf{w})\), consists of all vectors \(\mathbf{v}\) satisfying \[ g(\mathbf{w}) \geq g(\mathbf{w}') + \mathbf{v}^{\top}(\mathbf{w} -\mathbf{w}') + o(\|\mathbf{w} - \mathbf{w}'\|_2) \text{ as } \mathbf{w} \rightarrow \mathbf{w}'. \] We consider a family of non-convex functions, namely weakly convex functions. A lower semi-continuous function \(g\) is called \(\rho\)-weakly, if there exists \(\rho>0\) such that: \[\begin{align*} g(\mathbf{w}) \geq g(\mathbf{w}') + \mathbf{v}^{\top}(\mathbf{w - \mathbf{w}'}) - \frac{\rho}{2}\|\mathbf{w - \mathbf{w}'}\|_2^2,\quad \forall \mathbf{w}, \mathbf{w}', \mathbf{v}\in\partial g(\mathbf{w}'). \end{align*}\] It is easy to show that if \(g\) is \(\rho\)-weakly convex, then \(g(\mathbf{w}) + \frac{\rho}{2}\|\mathbf{w}\|_2^2\) is a convex function of \(\mathbf{w}\). A smooth function is weakly convex, but the reverse is not necessarily true.

Examples of Example

Example 1: Compositional functions

Let \(F(\mathbf{x}) = f(g(\mathbf{x}))\). If \(f\) is convex and \(G_1\)-Lipschitz continuous and \(g(\mathbf{x})\) is \(L_2\)-smooth, then \(F\) is \(\rho\)-weakly convex for some \(\rho>0\). We will prove this in Section 5.3. The OCE risk is a special case when \(\phi^*\) is non-smooth and the loss function \(\ell(\mathbf{w}; \mathbf{z})\) is smooth non-convex.

Example 2: Compositional functions

Let \(F(\mathbf{x}) = f(g(\mathbf{x}))\). If \(f\) is \(L_1\)-smooth and monotonically non-decreasing and \(g(\mathbf{x})\) is non-smooth convex and \(G_2\)-Lipschitz continuous, then \(F\) is \(\rho\)-weakly convex for some \(\rho>0\).

Let us prove it. Since \(f(g)\) is \(L_1\)-smooth, for any \(\mathbf{w},\mathbf{v}\in\mathbb{R}^d\), \[ f(g(\mathbf{v})) + f'(g(\mathbf{v}))(g(\mathbf{w})-g(\mathbf{v})) - \frac{L_1}{2}|g(\mathbf{w})-g(\mathbf{v})|^2 \leq f(g(\mathbf{w})). \] Since \(g\) is convex, \(g(\mathbf{w}) \geq g(\mathbf{v}) + \partial g(\mathbf{v})^\top (\mathbf{w} - \mathbf{v})\), then \[\begin{align*} f(g(\mathbf{w})) - f(g(\mathbf{v})) \geq & f'(g(\mathbf{v}))\partial g(\mathbf{v})^\top (\mathbf{w} - \mathbf{v}) - \frac{L_1}{2}|g(\mathbf{w})-g(\mathbf{v})|^2\\ \geq & f'(g(\mathbf{v}))\partial g(\mathbf{v})^\top (\mathbf{w} - \mathbf{v}) - \frac{G_2^2L_1}{2}\|\mathbf{w}-\mathbf{v}\|_2^2, \end{align*}\] where the first inequality uses \(f'(g(\mathbf{v}))\geq 0\), and the second uses \(\|\partial g(\mathbf{w})\|_2 \leq G_2\). That is, \(f(g(\mathbf{w}))\) is \(G_2^2L_1\)-weakly convex.

An important application of this function in machine learning is optimizing the truncation of a convex loss \(g(\mathbf{w})=\ell(\mathbf{w}; \mathbf{z})\geq 0\) with a smooth truncation function \(f(\ell(\mathbf{w}; \mathbf{z})) =\alpha \log(1+ \frac{\ell(\mathbf{w}; \mathbf{z})}{\alpha})\) for some \(\alpha>0\), which is useful for tackling heavy-tailed data distribution.

Nearly \(\epsilon\)-stationary solution

When \(g(\cdot)\) is non-smooth, finding an \(\epsilon\)-stationary solution such that \(\|\nabla g(\mathbf{w})\|_2\leq \epsilon\) is difficult even for a convex function. Consider \(\min_{w}|w|\): the only stationary point is \(w_*=0\), and any \(w\neq 0\) is not an \(\epsilon\)-stationary solution (\(\epsilon<1\)) no matter how close \(w\) is to \(0\). To address this issue, we introduce a weak notion of \(\epsilon\)-stationary solution, termed nearly \(\epsilon\)-stationary solution.

A useful tool for deriving a nearly \(\epsilon\)-stationary solution is the Moreau envelope of \(g\):

\[\begin{align}\label{eqn:moreau} g_{\lambda}(\mathbf{w}) &:= \min_{\mathbf{u}} g(\mathbf{u}) + \frac{1}{2\lambda}\|\mathbf{u} - \mathbf{w}\|_2^2. \end{align}\]

Define \[\begin{align} \mathrm{prox}_{\lambda g}(\mathbf{w}) := \arg\min_{\mathbf{u}} g(\mathbf{u}) + \frac{1}{2\lambda}\|\mathbf{u} - \mathbf{w}\|_2^2. \end{align}\]

An example of a weakly convex function and its Moreau envelope is illustrated in Figure 3.1.

■

With the Moreau envelope, we can use the norm of its gradient to measure the convergence for optimizing the original function.

■

Convergence Analysis

Proof.
We have \[\begin{align*} g_{\lambda}(\mathbf{w}_{t+1})& = g(\hat{\mathbf{w}}_{t+1}) + \frac{1}{2\lambda}\|\hat{\mathbf{w}}_{t+1} - \mathbf{w}_{t+1}\|_2^2 \leq g(\hat{\mathbf{w}}_{t}) + \frac{1}{2\lambda}\|\hat{\mathbf{w}}_{t} - \mathbf{w}_{t+1}\|_2^2\\ & = g(\hat{\mathbf{w}}_{t}) + \frac{1}{2\lambda}\|\hat{\mathbf{w}}_{t} - \mathbf{w}_{t}\|_2^2- \frac{1}{2\lambda}\|\hat{\mathbf{w}}_{t} - \mathbf{w}_{t}\|_2^2 + \frac{1}{2\lambda}\|\hat{\mathbf{w}}_{t} - \mathbf{w}_{t+1}\|_2^2. \end{align*}\] Merging the first two terms we get \(g_\lambda(\mathbf{w}_{t})\), and using the three-point equality \(2(a-b)(b-c) = \|a-c\|_2^2 - \|a-b\|_2^2 - \|b - c\|_2^2\) to merge the last two terms we get \[\begin{align*} g_{\lambda}(\mathbf{w}_{t+1})& = g_{\lambda}(\mathbf{w}_t) + \frac{1}{\lambda}(\hat{\mathbf{w}}_t - \mathbf{w}_t)^{\top}(\mathbf{w}_t - \mathbf{w}_{t+1}) + \frac{1}{2\lambda}\|\mathbf{w}_t - \mathbf{w}_{t+1}\|_2^2\\ & = g_{\lambda}(\mathbf{w}_t) + \frac{1}{\lambda}(\hat{\mathbf{w}}_t - \mathbf{w}_t)^{\top}\eta_t\mathbf{z}_t + \frac{\eta_t^2}{2\lambda}\|\mathbf{z}_t \|_2^2. \end{align*}\]

■

■

■

← Go Back