Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions

Introduction

In this work, we consider the optimization problem

The proximal subgradient method is perhaps the simplest algorithm for the problem (1.1). Given a current iterate $x_{t}$, the method repeats the steps

It has been known since that the (stochastic) subgradient method with $r=0$ generates an iterate sequence that subsequentially converges to a stationary point of the problem. A long standing open question in this line of work is to determine the “rate of convergence” of the basic (stochastic) subgradient method and of its proximal extensions.

An immediate difficulty in addressing this question is that it is not a priori clear how to measure the progress of the algorithm. Indeed, neither the functional suboptimality gap, $\varphi(x_{t})-\min\varphi$, nor the stationarity measure, ${\rm dist}(0;\partial\varphi(x_{t}))$, necessarily tend to zero along the iterate sequence. Instead, recent literature has identified a different measure of complexity of minimizing weakly convex functions, based on smooth approximations. The key construction we use is the Moreau envelope:

where $\lambda>0$. Standard results show that as long as $\lambda<\rho^{-1}$, the envelope $\varphi_{\lambda}$ is $C^{1}$-smooth with the gradient given by

Thus a small gradient $\|\nabla\varphi_{\lambda}(x)\|$ implies that $x$ is near some point $\hat{x}$ that is nearly stationary for (1.1). For a longer discussion of near-stationarity, see or [7, Section 4.1].

In this paper, we show that under an appropriate choice of the control sequence $\alpha_{t}$, the subgradient method will generate a point $x$ satisfying $\|\nabla\varphi_{1/2\rho}(x)\|\leq\varepsilon$ after at most $O(\varepsilon^{-4})$ iterations. A similar guarantee was recently established for the proximally guided projected subgradient method . This scheme proceeds by directly applying the gradient descent method to the Moreau envelope $\varphi_{\lambda}$, with each proximal point ${\rm prox}_{\lambda\varphi}(x)$ approximately evaluated by a convex subgradient method. In contrast, we show here that the basic subgradient method, without any modification or parameter tuning, already satisfies the desired convergence guarantees. This is perhaps surprising, since neither the Moreau envelope $\varphi_{\lambda}(\cdot)$ nor the proximal map ${\rm prox}_{\lambda\varphi}(\cdot)$ explicitly appear in the definition of the subgradient method.

Though our results appear to be new even in this rudimentary deterministic set up, the argument we present applies much more broadly to stochastic proximal subgradient methods, in which only stochastic estimates of $\zeta_{t}$ are available. This is the setting of the paper. In this regard, we improve in two fundamental ways on the results in the seminal papers : first, we allow $g$ to be nonsmooth and second, we do not require the variance of our stochastic estimator for $\zeta_{t}$ to decrease as a function of $t$. The second contribution removes the well-known “mini-batching” requirements common to , while the first significantly expands the class of functions for which the rate of convergence of the stochastic proximal subgradient method is known. It is worthwhile to mention that our techniques crucially rely on convexity of $r$, while makes no such assumption.

There is an extensive literature on stochastic subgradient methods in convex optimization, which we will not detail here; instead, we refer the interested reader to the seminal works . An in-depth summary of recent work for nonconvex problems appears in .

The outline of the paper is as follows. In the Section 2.1, we present a simplified argument for the case in which $r$ is the indicator function of a closed convex set and the stochastic estimator has finite second moment. In this section, we also comment on improved rates in the convex setting. In Section 2.2, we prove convergence of the stochastic proximal subgradient method in full generality. In Section 2.3, we modify the results of the previous section to the case in which $g$ is smooth and the stochastic estimator has finite variance.

Convergence guarantees

It is possible to generate i.i.d. realizations $\xi_{1},\xi_{2},\ldots\sim dP$.

Weak convexity automatically guarantees that subgradients of $g$ satisfy the much stronger property [27, Theorem 12.17]:

One important consequence we will use is the hypo-monotonicity inequality:

The three assumption (A1), (A2), (A3) are standard in the literature on stochastic subgradient methods. Indeed, assumptions (A1) and (A2) are identical to assumptions (A1) and (A2) in , while Assumption (A3) is the same as the assumption listed in [15, Equation (2.5)].

In this work, we investigate the efficiency of the proximal stochastic subgradient method, described in Algorithm 1.

Our analysis of Algorithm 1 is shorter and more transparent when $r$ is the indicator function of a closed, convex set $\mathcal{X}$. This is not surprising, since projected subgradient methods are typically much easier to analyze than their proximal extensions (e.g. ). Note that (1.1) then reduces to the constrained problem

Let $x_{t^{*}}$ be the point returned by Algorithm 1. Then in terms of any constant $\hat{\rho}>\rho$, the estimate holds:

Using the law of total expectation to unfold this recursion yields:

Lower-bounding the left-hand side by $\min\varphi$ and rearranging, we obtain the bound:

where the last equality follows from (1.3). Using this estimate to lower bound the left-hand-side of (2.7) completes the proof. ∎

In particular, using the constant stepsize $\alpha$ on the order of $\frac{1}{\sqrt{T+1}}$ yields the following complexity guarantee.

Fix an index $T>0$ and set the constant steplength $\alpha=\frac{\gamma}{\sqrt{T+1}}$ for some real $\gamma>0$. Then the point $x_{t^{*}}$ returned by Algorithm 1 satisfies:

This follows immediately from Theorem 2.1 by setting $\hat{\rho}=2\rho$. ∎

This complexity in $\varepsilon$ matches the guarantees of the stochastic gradient method for finding an $\varepsilon$-stationary point of a smooth function [9, Corollary 2.2].

This complexity can be improved slightly by first regularizing the problem. We will only outline the procedure here, since the details are standard and easy to verify. Define the function $\widehat{\varphi}:=\varphi+\frac{\mu}{2}\|\cdot-x_{\rm c}\|^{2}$, for some $\mu>0$ and arbitrary $x_{\rm c}\in\mathcal{X}$. We will apply optimization algorithms to $\widehat{\varphi}$ instead of $\varphi$, and therefore we must relate their Moreau envelopes. Fixing an arbitrary $\lambda>0$, it is straightforward to verify the following equality by completing the square in the Moreau envelope:

Thus, supposing $\varepsilon\leq 2\rho D$, we may set $\mu=\frac{\varepsilon}{2D}$ and $\lambda=2\rho-\frac{\varepsilon}{2D}$, obtaining the estimate

2 Proximal stochastic subgradient method

We next move on to convergence guarantees of Algorithm 1 in full generality – the main result of this work. To this end, in this section, in addition to assumptions (A1), (A2), and (A3) we will also assume that $g$ is $L$-Lipschitz.

For each index $t\geq 0$, equality holds:

By the definition of $\hat{\zeta}_{t}$, we have

where the last equivalence follows from the optimality conditions for the proximal subproblem. This completes the proof. ∎

The next lemma establishes a crucial descent property for the iterates.

Suppose $\hat{\rho}\in(\rho,2\rho]$ and we have $\alpha_{t}\leq{\hat{\rho}}^{-1}$ for all indices $t\geq 0$. Then the inequality holds:

where (2.12) follows from Lemma 2.3, the inequality (2.13) uses that ${\rm prox}_{\alpha_{t}r}(\cdot)$ is $1$-Lipschitz [27, Proposition 12.19], and (2.15) follows from the inequality (2.2). The result now follows from the assumed inequality $\hat{\rho}\leq 2\rho$. ∎

With Lemma 2.4 proved, we can now establish convergence guarantees of Algorithm 1 in full generality.

Fix a real $\hat{\rho}\in(\rho,2\rho]$ and a stepsize sequence $\alpha_{t}\in(0,\hat{\rho}^{-1}]$. Then the point $x_{t^{*}}$ returned by Algorithm 1 satisfies:

where the first inequality follows directly from the definition of the proximal map and the second follows from Lemma 2.4.

Using the law of total expectation to unfold this recursion yields:

Next using the inequality $\varphi_{1/\hat{\rho}}(x_{T+1})\geq\min\varphi$ and rearranging, we obtain the bound:

In particular, using the constant stepsize $\alpha$ on the order of $\frac{1}{\sqrt{T+1}}$ yields the following complexity guarantee.

Fix a constant $\gamma\in(0,\tfrac{1}{2\rho}]$ and an index $T>0$, and set the constant steplength $\alpha=\frac{\gamma}{\sqrt{T+1}}$. Then the point $x_{t^{*}}$ returned by Algorithm 1 satisfies:

This follows immediately from Theorem 2.5 by setting $\hat{\rho}=2\rho$. ∎

3 Proximal stochastic gradient for smooth minimization

Let us now look at the consequences of our results in the setting when $g$ is $C^{1}$-smooth with $\rho$-Lipschitz gradient. Note, that then $g$ is automatically $\rho$-weakly convex. In this smooth setting, it is common to replace assumption (A3) with the finite variance condition:

Henceforth, let us therefore assume that $g$ is $C^{1}$-smooth with $\rho$-Lipschitz gradient and Assumptions (A1), (A2), and $\overline{\rm(A3)}$ hold.

All of the results in Section 2.2 can be easily modified to apply to this setting. In particular, Lemma 2.3 holds verbatim, while Lemma 2.4 extends as follows.

Fix a real $\hat{\rho}>\rho$ and a sequence $\alpha_{t}\in(0,\hat{\rho}^{-1}]$. Then the inequality holds:

By the same argument as in Lemma 2.7, we arrive at the inequality (2.14) with ${\hat{\zeta}}_{t}=\nabla g({\hat{x}}_{t})$. Adding and subtracting $\nabla g(x_{t})$, we successively deduce

We can now state the convergence guarantees of the proximal stochastic gradient method. The proof is completely analogous to that of Theorem 2.5, with Lemma 2.7 playing the role of Lemma 2.4.

Fix a real $\hat{\rho}>\rho$ and a stepsize sequence $\alpha_{t}\in(0,\hat{\rho}^{-1}]$. Then the point $x_{t^{*}}$ returned by Algorithm 1 satisfies:

In particular, setting $\alpha=\frac{\gamma}{\sqrt{T+1}}$ for some real $\gamma\in(0,\frac{1}{2\rho}]$ yields the guarantee

It is worth noting that in this smooth setting, the norm $\|\nabla\varphi_{\lambda}(x)\|$ is closely related to the magnitude of the prox-gradient mapping

This stationarity measure typically appears when analyzing proximal gradient methods (e.g. ). It is straightforward to see that this measure is proportional to the norm of the gradient of the Moreau envelope, the quantity we have been using [6, Theorem 3.5]:

Hence, the convergence guarantees of Corollary 2.8 can be immediately translated in terms of $\|\mathcal{G}_{1/(2\rho)}(x_{t}^{*})\|$, allowing for a direct comparison with previous results.

References