Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems

Introduction

where $z_{1},\ldots,z_{t},\ldots$ are IID and $\alpha_{t}$ is an appropriate control sequence. For nonsmooth $f(\cdot,z_{t})$, sample subgradients are simply replaced by sample subgradients $v_{t}\in\partial f(x_{t},z_{t})$, where $\partial f(x_{t},z_{t})$ denotes the subdifferential in the sense of convex analysis .

The complexity of minimizing (1) is directly related to the regularity of $f(\cdot,z)$. For example, for convex functions $f(\cdot,z)$ the stochastic subgradient method attains expected functional accuracy $\varepsilon$ with after $O(\varepsilon^{-2})$ stochastic subgradient evaluations. For strongly convex losses, the number of stochastic subgradient evaluations drops to $O(\varepsilon^{-1}).$ The interested reader may turn to the seminal work for an in-depth investigation of these methods and for information-theoretic lower bounds showing such rates are unimprovable without further assumptions.

For convex functions, complexity theory does not favor smooth losses over nonsmooth losses. For nonconvex problems, the situation is less clear. In the smooth case, the seminal work of Ghadimi, Lan, and Zhang develops a variant of the stochastic projected gradient method and establishes that the expected norm of the projected gradient

a natural measure of stationarity, tends to zero at a controlled rate. Namely, with $O(\varepsilon^{-2})$ stochastic gradient evaluations, the algorithm produces a point with expected projected gradient norm squared less than $\varepsilon$.

In contrast to subgradient-based methods, the “usual criteria” is meaningful for the proximal point method , which constructs a sequence $x_{t}$ of approximate minimizers through the recursion

The search for an appropriate class of functions $F$ for which each proximal subproblem may be (approximately) executed naturally leads us to the deceptively simple, yet surprisingly broad class of $\rho$-weakly convex functions. This is the class of functions that become convex after adding the quadratic $\frac{\rho}{2}\|\cdot\|^{2}$. For example, any $C^{2}$ function on a compact, convex set becomes convex after adding the quadratic $\tfrac{|\lambda_{+}|}{2}\|\cdot\|^{2}$, where $\lambda$ is the minimal eigenvalue of its Hessian across all points in the set. In the nonsmooth setting, this class includes all convex composite losses

where $h$ is convex and $L$-Lipschitz and $c$ is $C^{1}$ with $\beta$-Lipschitz Jacobian; such functions are known to be $\beta L$-weakly convex [13, Lemma 4.2]. The additive composite class is another widely used, much studied class of weakly convex functions, formed from all sums

where $r$ is closed and convex and $g$ is $C^{1}$ with $\beta$-Lipschitz gradient; such functions are known to be $\beta$-weakly convex. For further examples of weakly convex functions, see [9, Section 2.1], which includes formulations of robust phase retrieval, covariance matrix estimation, blind deconvolution, sparse dictionary learning, robust principal component analysis, and conditional value at risk. We provide several further examples in Section 2.1. It is important to note that none of these applications are covered by the seminal work of Ghadimi, Lan, and Zhang , which assumes an additive composite objective form.

Contributions. In this paper, we develop the first known complexity guarantees for a subgradient-based method for a general class of nonsmooth nonconvex losses in stochastic optimization. The guarantees in this paper apply to $\rho$-weakly convex losses $F$. Our algorithm, called the Proximally Guided stochastic Subgradient Method (PGSG) (Algorithm 2), follows an inner-outer loop strategy that may be compactly and informally summarized

The outer loop of PGSG is governed by the approximate proximal point method applied to the population risk $F$. Due to $\rho$-weak convexity of $F$, the inner loop subproblem is a strongly convex stochastic optimization problem. Thus, by classical complexity theory, approximate solutions to the inner loop subproblems may be quickly found. When both inner and outer loops are coupled together appropriately, we establish that this method produces a point $\bar{x}$ that is $\varepsilon$-close in expectation to the set of $\varepsilon$-critical points after $O(\varepsilon^{-2})$ stochastic subgradient evaluations, meaning,

Having established expectation guarantees, we turn our attention to probabilistic guarantees. Namely, following (which considers the smooth case), we say a (random) point $\bar{x}$ is an $(\varepsilon,\Lambda)$-solution if

Markov’s inequality shows that PGSG finds an $(\varepsilon,\Lambda)$-solution $\bar{x}$ after

stochastic subgradient evaluations. To improve this complexity, we introduce a 2-phase algorithm, called 2PGSG, which produces an $(\varepsilon,\Lambda)$-solution after

stochastic subgradient evaluations, substantially reducing the variance of our solution estimate. The technique for achieving this improvement is somewhat different than what proposes in the smooth case. The challenge in establishing the result is that we no longer have unbiased estimates of subgradients at nearly stationary points. Indeed, the iterates produced by subgradient methods are only nearby nearly stationary points and are not nearly stationary themselves.

Finally, we turn our attention to a more practical variant of PGSG, which does not assume that the weak convexity constant $\rho$ is known. In this setting, a simple idea—letting the outer loop stepsize tend to infinity—results in a point $\bar{x}$, which satisfies (4) after $O(\varepsilon^{2/(1-\beta)})$ stochastic subgradient evaluations, where $\beta\in(0,1)$ is a user defined meta-parameter. We mention that the seminal work of Ghadimi, Lan, and Zhang also assumes knowledge of the weak convexity constant $\rho$; in their setting $\rho$ is simply the Lipschitz constant of the gradient.

We validate our results with some preliminary numerical experiments on the population objective of a robust real phase retrieval problem. We also discuss several more examples of Weakly convex functions in Section 2.1.

The convergence rates presented in match known rates for the stochastic gradient method in nonconvex optimization . There, the standard stochastic gradient method may be used without modification. Interestingly, recent work has developed methods, which converge at the improved rate of $O(\varepsilon^{-3/2})$ , showing a surprising gap between smooth and nonsmooth nonconvex optimization not present in the convex case.

Stochastic Proximal-Gradient Methods

Stochastic Methods for Convex Composite

Recently proposed a method for finding stationary points of the convex composite problem in which $f(x,z)=h(c(x,z),z)$. The first method adapts the prox-linear algorithm to the stochastic setting: given $x_{t}$, sample $z_{t}$ and form $x_{t+1}$ as the solution to the convex problem:

where $\gamma_{t}=\theta(1/\sqrt{t})$. The second proposed method is a straightforward application of the stochastic projected subgradient method . Both methods are shown to almost surely converge to stationary points, but no rates of convergence are given.

We remark that the convergence proof presented in is complex, being based on the highly nontrivial theory of nonconvex differential inclusions. We believe there is a benefit to having a simple proof of convergence, albeit for a slightly different subgradient method, which is what we provide in this paper.

Inexact Proximal Point Methods in Nonconvex Optimization

The idea of using the inexact proximal point method to guide a nonconvex optimization algorithm to stationary points is not new. For example, Hare and Sagastizabal propose a method for computing inexact proximal points, which then enables the analysis of a nonconvex bundle method. The more recent work exploits linearly convergent algorithms for solving the proximal subproblems. In contrast for the subproblems considered in this work, there are no linearly convergent stochastic subgradient algorithms capable of minimizing the proximal point step.

Subgradient Methods for Weakly Convex Problems

This paper is not the first to consider subgradient methods under weak convexity. For example, the early work proves subsequential convergence of the (non projected) subgradient method for weakly convex deterministic problems. However, no rates were given in that work.

Almost Sure Convergence of Stochastic Subgradient Methods for Nonconvex Problems

Convergence to stationary points of stochastic subgradient methods in nonsmooth, nonconvex optimization has previously been attained under several different scenarios, some of which are more general than the scenario considered in Problem (1) . No rates of convergence were given in these works. In contrast, the novelty of the proposed approach lies in the attained rate of convergence, which matches the best known rates of convergence for smooth, nonconvex stochastic optimization .

Rates of Convergence in Stochastic Weakly Convex Optimization

Since the first draft of this paper appeared on arXiv in July 2017, several works appearing in 2018 have established convergence of the standard stochastic projected subgradient method under weak convexity . The obtained rates (in expectation) are essentially the same as those obtained in this paper, namely they are of the form presented in equation (4). The authors of do not provide any probabilistic guarantees.

2 Outline

Section 2 presents notation and several basic results used in this paper, as well as further examples of weakly convex functions. Section 3 presents our convergence analysis under the assumption that $\rho$ is known. Section 3.2 presents our probabilistic guarantees. Section 3.3 presents our convergence analysis when $\rho$ is unknown. Section 4 preliminary presents numerical results obtained on a robust phase retrieval problem.

Notation and Basic Results

For the class of weakly convex functions, all elements of the subdifferential generate quadratic underestimators of the function $F$, as the following proposition shows. The equivalences are based on [8, Theorem 3.1].

$F$ is $\rho$-weakly convex. That is, $F+\frac{\rho}{2}\|\cdot\|^{2}$ is convex.

As stated in the introduction, the class of weakly convex functions is broad. In the nonsmooth setting, this class includes all convex composite losses

where $h$ is convex and $L$-Lipschitz and $c$ is $C^{1}$ with $\beta$-Lipschitz Jacobian; such functions are known to be $\beta L$-weakly convex [13, Lemma 4.2]. Several popular weakly convex formulations are presented in [9, Section 2.1]. We now discuss several further examples.

The censored block model is a variant of the standard stochastic block model , which seeks to detect two communities in a partially observed graph. Mathematically, we encode such communities by forming the “community matrix” $M=\bar{\theta}\bar{\theta}^{T}\in\{-1,1\}^{d}$, where $\bar{x}\in\{-1,1\}^{d}$ is a membership vector in which $\bar{x}_{i}=1$ if node $i$ is in the first community, and $\bar{x}_{i}=-1$ otherwise. In the censored block model, we observe a randomly corrupted version $\hat{M}$ of the matrix $M$

Then our task is to recover $M$ given only $\hat{M}$. We may formulate this problem in the following form convex, composite form:

Notice that absolute value function encourages the matrix to $xx^{T}$ agree with $\hat{M}$ in most of its nonzero entries—the bulk of which are equal to $M_{ij}$—due to the sparsity promoting behavior of the nonsmooth absolute value function.

Notice that this nonsmooth objective is given in convex composite form, and therefore, it is weakly convex.

One can see that for fixed $x$, the only objective values that contribute to the sum are those that are among the $h$-minimal elements of the set $\{f_{1}(x),\ldots,f_{n}(x)\}$. In the Appendix, we provide a short proof that this objective is weakly convex. Notice that it is in general nonconvex, despite each $f_{i}$ begin convex.

Proximally Guided Stochastic Subgradient Method

In this section, we formalize the proposed algorithm. First we slightly generalize the problem considered in the introduction, namely we assume that

strongly convex. Next we introduce a stochastic subgradient oracle and a basic assumption on $F$.

It is possible to generate IID realizations $z_{1},z_{2},\ldots$ from $P$.

Assumption A is standard in the literature on stochastic subgradient methods. In particular, assumptions (A1) and (A2) are identical to assumptions (A1) and (A2) in , while assumption (A3) is identical to [29, Equation (2.5)]. A useful consequence of (A3) is that $f$ itself is Lipschitz.

Suppose that assumption (A3) holds. Then $f$ is $L$-Lipschitz continuous on U.

Before introducing the Proximally Guided stochastic Subgradient (PGSG) method, we introduce two necessary algorithm parameters:

As stated in the introduction PGSG employs an inner-outer loop strategy, which is shown in Algorithm 2. The outer loop executes $T-1$ approximate proximal point steps, resulting in the iterates $\{x_{t}\}$. The inner loop, shown in Algorithm 1, approximately solves the proximal point subproblem, which is now strongly convex, using a stochastic subgradient method for strongly convex optimization . Beyond its use in governing the outer loop dynamics of PGSG, the proximal point subproblems also lead to a natural measure of stationarity.

Note that $\hat{x}_{t}$ exists and is unique by the $\mu$-strong convexity of the proximal subproblem. We stress that this point, although in principle obtainable via convex optimization, is never computed. Instead it is only used to formulate convergence guarantees. To that end, the following Lemma shows that the gap $\gamma^{-1}\|x_{t}-\hat{x}_{t}\|$ is a natural measure of stationarity.

Based on this Lemma, the iterate $x_{t}$ is $\varepsilon$-close to an $\varepsilon$-stationary point in expectation whenever

Establishing this fact is the main technical goal of the following theorem.

In particular, given $\Delta\geq F(x_{0})-\inf F$, and setting

The total number of stochastic oracle evaluations required to compute this point is bounded by $j_{t}\cdot T=O(\Delta L^{2}\varepsilon^{-2})$.

As stated, the theorem indicates that $x_{R}$ is nearby a nearly stationary point. The proof of Lemma 10 shows that one can in principle obtain the nearly stationary point $\hat{x}_{R}$ by solving the strongly convex stochastic optimization problem

Throughout the proof we will need the following bound on the proximal point step:

Let $\gamma>0$, $x\in{\mathcal{X}}$, and suppose that

where Lipschitz continuity follows from Lemma 3.1. Divide both sides of the inequality by $\tfrac{1}{2}\|x-\hat{x}\|$ to get the result.

We now analyze one inner loop of Algorithm 2. This inner loop may be interpreted as a variant of the stochastic projected subgradient method applied to the strongly convex optimization problem,

We note that the following proof is similar in outline to , but the results of that work are not sufficient for our purposes.

On the other hand, if $0<\alpha_{j}\leq 2\gamma$ for all $j$, but $\{\alpha_{j}\}$ and $\gamma$ are otherwise unconstrained, we have

To proceed further, we must bound $\|v_{t,j}\|^{2}$. To that end, recall that $F_{y}$ is $\mu$-strongly convex. Therefore, for any $x\in{\mathcal{X}}$,

where the first inequality follows from Jensen’s inequality, the second inequality uses (A3) twice and Lemma 3.6, and the third inequality follows from the strong convexity.

Multiplying by $(j+1)/\alpha_{j}$, we find that

By our choice of $\alpha_{j}$, we have $(j+1)\alpha_{j}^{-1}=(j+2)(\alpha_{j+1}^{-1}-\mu)$. Therefore, summing the previous inequality, we have

Therefore, noting that $\sum_{j=0}^{j_{t}-1}(j+1)\alpha_{j}\leq 2j_{t}/\mu$ and $\alpha_{0}^{-1}-\mu=18/(\gamma^{4}\mu^{3})$, and using the convexity of $F_{y}$, we deduce

The first distance bound then follows as a direct consequence of the strong convexity of $F_{y}$, while the second follows from the convexity of $\|\cdot\|^{2}$.

By the strong convexity of the proximal point subproblem, we have

Then by Proposition 3.8, we have the following bound:

as desired. To complete the proof, apply Lemma 3.2.

2 Probabilistic Guarantees

In the previous section, we developed expected complexity results, which describe the average behavior of the PGSG over multiple runs. We are also interested in the behavior of a single run of the PGSG algorithm. Thus, in this section we recall the notion of an $(\varepsilon,\Lambda)$-solution given in the introduction: a random variable $\bar{x}$ is called an $(\varepsilon,\Lambda)$-solution if

Theorem 3.4 together with Markov’s inequality implies that $x_{R}$, generated with

where $\Delta\geq F(x_{0})-\inf F$, is an $(\varepsilon,\Lambda)$-solution after

stochastic oracle evaluations. In this section, we develop a two stage algorithm that significantly improves the dependence on $\Lambda$ in this bound.

Before we introduce the algorithm, let us define three parameters

where $\Delta\geq F(x_{0})-\inf F$. The algorithm now follows.

Let $x_{R^{s}}$ be generated as in Algorithm 3. Then

By Proposition 3.8 and Theorem 3.4, the bound holds:

On the other hand, Proposition 3.8 and Theorem 3.4 imply that

which proves the second bound and completes the proof.

We now state the convergence guarantees for Algorithm.

Notice that by Markov’s inequality, independence, and Proposition 3.11, we have:

On the other hand, by Markov’s inequality, a union bound, and Proposition 3.11, we have

which shows that $x^{\ast}$ is an $(\varepsilon,\Lambda)$-solution.

When the second term in (15) is dominating, the obtained bound (15) is $\log_{2}(2/\Lambda)/\varepsilon\Lambda$ times smaller than the bound (13) obtained by the PGSG algorithm.

3 PGSG with Unknown Weak Convexity Constant

Algorithm 2 requires that the parameters $\varepsilon$, $L$, and $\rho$ are known. In practice, computing $L$ and $\rho$ may be nontrivial. In this section we show that a simple strategy—letting $j_{t}$ tend to infinity and $\gamma_{t}$ tend to zero—results in a sublinear convergence rate without knowledge of any problem parameters. We formalize this procedure in Algorithm 4 using the following parameters: fix a hyper-parameter $0<\beta<1$, and define

In the following, we establish convergence guarantees for the parameter free variant of PGSG. The proof splits the analysis of PFPGSG into two parts. In the first part, $\gamma_{t}\geq 1/\rho$. In this setting, the analysis of the previous section does not apply. Thus, we show that that the iterates do not wander very far. In the second part, $\gamma_{t}\leq 1/\rho$, and an argument similar to the one presented in Theorem 3.4 applies. Combining these results then leads to the theorem. To that end, we address the first part now.

Let $T_{0}=\lceil(2\rho)^{1/\beta}\rceil$. Then

We now address the second part of the argument, and with it, deduce the following theorem. At first glance, the presented rate appears to be better than the rate obtained by Algorithm 2, which requires knowledge of $\rho$. However, it is not because the factor $\gamma_{R}^{-2}=(R+1)^{2\beta}$ is no longer a constant. Instead, the convergence rate of Algorithm 4 is on the order of $O(T^{1-\beta})$ in the worst case.

Suppose that $t\geq T_{0}$ and notice this ensures $\gamma_{t}\in(0,1/\rho)$. Following an argument nearly identical to the proof of Theorem 3.4, we find that for all $t\geq T_{0}$, we have

Therefore, $1-\gamma_{t}\rho\geq 1/2$, which leads to the claimed inequality: $12/(1-\gamma_{t}\rho)^{2}\leq 44\leq j_{t}$.

Using the lower bound $\mu_{t}\geq 1/(2\gamma_{t})$ (which follows because $t\geq T_{0}$), we thus find

We would like to extend the sum on the left hand side of the previous inequality to all $t$ between and $T-1$. To that end, we bound the excess terms

Therefore, using the bounds $\sum_{t=T_{0}}^{\infty}\gamma_{t}/(j_{t}+1)\leq\sum_{t=T_{0}}^{\infty}t^{-1-\beta}=C<\infty$ and $\sum_{t=0}^{T-1}\gamma_{t}^{-1}\geq\int_{-1}^{T-1}(t+1)^{\beta}dt=T^{1+\beta}/(1+\beta)$, we have,

as desired. To complete the proof, apply Lemma 3.2.

Experimental Results

where $a,\delta,$ and $\xi$ are independent random variables satisfying the following assumptions

$\delta$ is a $\{0,1\}$-random variable with $P(\delta=1)=0.25$;

$\xi$ is a zero mean Laplace random variable with scale parameter $1$.

In this setting, it is possible to show that the only minimizers of $F(x)$ are $\pm\bar{x}$ [11, Lemma B.8]. In Lemma B.1, we show that this function is 2-weakly convex.

Implementation. Each step of PGSG and the stochastic subgradient method requires access to a subgradient of a random function of the form

It is a straightforward exercise to show that $G$ satisfies assumption A on any bounded set ${\mathcal{X}}$. For our purposes we choose ${\mathcal{X}}$ to be a closed ball with a large radius, $r=10^{6}$. In our experiments, we never had to explicitly enforce this constraint.

Experiment 1: Sensitivity to Stepsize. In the first experiment we compare the performance of PGSG to the stochastic subgradient method, which possessed no complexity guarantees at the time of writing this manuscript. In the stochastic subgradient method, we choose stepsizes of the form $\gamma/(t+10)^{\beta}$ for varying $\gamma>0$ and $\beta\in\{1/2,1\}$. For PGSG, we chose varying values of $\gamma>0$ and then set $\alpha_{j}$ by (9), $j_{t}=250$, and $\mu=1/2\gamma$. Figure 1 shows the result of running these two methods to solve robust real phase retrieval problems with $d=50$.

Based on the results of Experiment 1, we set $\gamma=2^{-6}$ for the PGSG and 2-PGSG algorithms. We furthermore set $\alpha_{j}$ by (9) and let $\mu=1/2\gamma$. For both methods, we consider two different selections for the number of inner iterations $j_{t}\in\{10^{3},10^{4}\}$. These choices determine the level of stationarity reached by the algorithm. For 2PGSG, we fix $S=5$ and $J=5T$. For PFPGSG, we set $\beta=1/2$, $\gamma_{t}=(t+1)^{-\beta}/10$ (which differs from (16) by a factor of ten), $j_{t}$ as in (17), and $\alpha_{j}$ as in (18).

Table 1 lists the mean and variance of the stationarity measures averaged over $50$ trials. Each sub column shows the performance of the target algorithm as the computational budget increases. We find that with $j_{t}=10^{3}$, both PGSG and 2PGSG quickly converge to a region of stationarity and then do not improve. With $j_{t}=10^{4}$, both of these methods reach a level of stationarity an order of magnitude smaller than with the choice $j_{t}=10^{3}$. Under sufficiently large computational budget ($2500000$ stochastic subgradient evaluations), the variance of the stationarity reported by 2PGSG is consistently lower than that of PGSG as expected from Theorem 3.13. Finally, we note that the performance of PFPGSG is similar to PGSG in most regimes.

Appendix A Trimmed Estimation

Appendix B Weak Convexity of Robust Phase Retrieval

The robust phase retrieval loss defined in (20) is $2$-weakly convex.

Therefore, by Proposition 2.1, $F$ is $2$-weakly convex.

Acknowledgments

We thank Dmitriy Drusvyatskiy, George Lan, and the two anonymous reviewers for helpful comments.

References