PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic model-based minimization of weakly convex functions

Damek Davis, Dmitriy Drusvyatskiy

arXiv:1803.06523v3math.OCcs.LG

TL;DR

The paper addresses missing sample-complexity guarantees for stochastic optimization on broad nonsmooth, nonconvex problems. It analyzes stochastic model-based algorithms through Moreau-envelope smoothing and establishes O(ε^-4) worst-case complexity, including guarantees for several proximal methods and projected stochastic optimization.

  • Problem

    Sample complexity was unknown for stochastic subgradient methods across reasonably broad nonsmooth and nonconvex problem classes, despite their widespread use.

  • Method

    The paper analyzes algorithms that repeatedly sample and minimize stochastic models, interpreting their updates as approximate descent on the Moreau envelope.

  • Results

    O(ε^-4) worst-case complexity holds for a broad family of stochastic model-based algorithms, including stochastic subgradient, prox-linear, and proximal-point methods.

  • Takeaways & Limitations

    The analysis supplies complexity guarantees for popular stochastic proximal algorithms and addresses the previously elusive complexity of stochastic subgradient and proximal extensions.

  • Takeaways & Limitations

    Improving beyond O(ε^-4) remains open for the nonsmooth weakly convex setting considered here.

Abstract

from arXiv · show

We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate $O(k^{-1/4})$. As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss-Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set.

1. Introduction.

The paper addresses missing sample-complexity guarantees for widely used stochastic methods on nonsmooth, nonconvex problems. It introduces a stationarity measure suitable for analyzing such methods and targets proximal subgradient, proximal point, and related algorithms.

  • Motivation: Sample complexity for stochastic subgradient methods remains unknown beyond smooth or convex problems, despite their widespread use.The gap concerns reasonably broad nonsmooth and nonconvex problem classes.
  • Contribution: The paper provides first sample-complexity bounds for several popular stochastic algorithms on a broad class of nonsmooth, nonconvex problems.The analyzed methods include proximal stochastic subgradient, proximal point, and regularized Gauss–Newton methods.
  • The search for stationary points: Stationarity means 0 ∈∂ϕ(x), while dist(0; ∂ϕ(x)) ≤ε expresses approximate first-order stationarity.Under mild conditions, the distance measure also characterizes directional-derivative behavior.
  • The search for stationary points: Progress is difficult to measure because neither functional suboptimality nor dist(0; ∂ϕ(x_t)) necessarily tends to zero for these problems.The paper motivates using a continuous stationarity measure instead of the discontinuous subdifferential-based measure.

Weak convexity and the Moreau envelope.

Weakly convex objectives include convex, smooth, and important composite functions that may be neither smooth nor convex. The Moreau envelope provides a smooth implicit measure of stationarity whose small gradient certifies proximity to a nearly stationary point.

  • Weak convexity: Weakly convex functions include all convex functions and smooth functions with Lipschitz continuous gradients.A function is ρ-weakly convex when adding ρ/2∥x∥^2 makes it convex.
  • Weak convexity: Composite functions h(c(x)) with h convex and Lipschitz and c having Lipschitz Jacobian are weakly convex, although they need not be smooth or convex.This class includes examples such as nonlinear least squares and phase retrieval.
  • The Moreau envelope: For a ρ-weakly convex objective and λ < ρ^-1, the Moreau envelope ϕ_λ is C1-smooth.Its gradient therefore supplies a continuous stationarity measure for the original objective.
  • The Moreau envelope: The Moreau-envelope gradient connects to familiar measures: for smooth objectives it is proportional to the true gradient or proximal-gradient step.These correspondences depend on the presence or absence of a regularizer.
  • The Moreau envelope: ∥∇ϕ_λ(x)∥ controls proximity to a point that is nearly stationary for ϕ.Specifically, the associated point ˆx satisfies ∥ˆx − x∥ = λ∥∇ϕ_λ(x)∥ and dist(0; ∂ϕ(ˆx)) ≤∥∇ϕ_λ(x)∥.
  • Complexity guarantee: The proximal stochastic subgradient method reaches E∥∇ϕ_1/(2ρ)(x)∥≤ε within O(ε^-4) iterations under weak convexity and mild Lipschitz conditions.The Moreau envelope and proximal map do not explicitly appear in the algorithm’s definition.

Contributions.

The paper unifies stochastic optimization methods through stochastic one-sided models and proves complexity guarantees under approximation and weak-convexity conditions. These results cover proximal subgradient, prox-linear, proximal-point, and related composite optimization methods.

  • General guarantees: Stochastic one-sided models lower-bound f in expectation up to a quadratic error while agreeing with f at the base point.This model framework controls approximation quality for sampled objective surrogates.
  • General guarantees: O(ε−4) iterations suffice to find x with E∥∇ϕ1/2ρ(x)∥≤ ε under mild Lipschitz conditions and ρ-weak convexity of each model plus regularizer.The analysis interprets the algorithm as approximate descent on the Moreau envelope.
  • Convex special cases: In the convex setting, true under-estimator models give O(ε−2) complexity in function value, improving to O(1/µε) under µ-strong convexity.The convex-model guarantees include nonclassical applications such as minimizing Conditional Value-at-Risk.
  • Algorithms: The framework encompasses stochastic proximal subgradient, stochastic prox-linear, and stochastic proximal-point methods for stochastic composite minimization.Linear models yield proximal subgradient updates, prox-linear models yield a Gauss–Newton variant, and two-sided models yield proximal-point updates.
  • Convex special cases: The proximal stochastic subgradient guarantees are new even for smooth losses with convex-set constraints and nonsmooth losses with exact subgradients.These specialize the broader theory to two classical settings.

Context and related literature.

The paper positions its results against prior Moreau-envelope, stochastic proximal-gradient, composite-optimization, and convex-rate analyses. It broadens the supported nonsmooth weakly convex setting while leaving accelerated rates in that setting open.

  • Prior methods: The basic fully proximal stochastic subgradient method achieves the desired convergence guarantees without modification or parameter tuning.Earlier work directly descended on the Moreau envelope while approximately evaluating each proximal point.
  • Advances over prior work: The analysis allows nonsmooth f(·, ξ) and does not require stochastic-gradient variance to decrease over iterations.The latter removes mini-batching requirements common in earlier smooth proximal-gradient results.
  • Open question: Whether accelerated rates are possible for nonsmooth weakly convex problems remains an open question.Existing accelerated results exploit finite-sum structure or higher-order smoothness in smooth nonconvex problems.
  • Composite optimization: The stochastic one-sided-model framework is new and complements prior results establishing almost-sure stationarity of limit points for related composite methods.The paper also makes no assumption that the entire composite function is convex or smooth.
  • Convex rates: The convex-setting function-value rates strengthen prior proximal stochastic subgradient results by excluding regularizer-subgradient norms from one bound and extending nonuniform averaging to the fully proximal setting.These claims are presented through Theorems 4.1 and 4.2.

2. Basic notation and preliminaries.

The paper develops notation for weakly convex objectives, their applications, subdifferentials, and Moreau-envelope stationarity. Weak convexity covers composite and several structured data-science problems.

  • Weak convexity: A function is ρ-weakly convex when adding ρ/2∥x∥^2 makes it convex.This class includes lower-semicontinuous extended-real-valued functions.
  • Weak convexity: Composite functions with convex Lipschitz h and smooth c are Lβ-weakly convex.Here c has a β-Lipschitz continuous Jacobian.
  • Applications: Applications include robust phase retrieval, covariance estimation, blind deconvolution, sparse dictionary learning, robust PCA, and conditional value-at-risk.The examples use structured penalties or factorizations to model sparse, low-rank, robust, or tail-risk objectives.
  • Subdifferentials: The subdifferential generalizes gradients and convex subgradients, while weak convexity admits equivalent secant, subgradient, and hypomonotonicity characterizations.For smooth functions, the subdifferential reduces to the singleton containing the gradient.
  • Moreau envelope: A small Moreau-envelope gradient places the iterate near a point that is nearly stationary for the original objective.The envelope gradient also directly relates to the prox-gradient mapping in additive composite minimization.

3. Proximal stochastic subgradient method.

The proximal stochastic subgradient method is analyzed for weakly convex objectives accessed through stochastic subgradient oracles. Its guarantees use Moreau-envelope stationarity and include the projected special case.

  • Setup: The oracle generates i.i.d. samples and unbiased stochastic subgradients with a uniformly bounded second moment.The objective is a sum of a closed convex regularizer and a weakly convex function.
  • Algorithm: The method repeatedly samples a stochastic subgradient and applies a proximal update, then returns an iterate sampled according to stepsize weights.The iterate-selection rule assigns probability proportional to αt.
  • Projected specialization: For a closed convex constraint set, the proximal map becomes the nearest-point projection.This yields the stochastic projected subgradient specialization.
  • Guarantee: O(ε^-4) iterations suffice to find x with E∥∇ϕ1/(2ρ)(x)∥≤ε under mild Lipschitz and weak-convexity conditions.The guarantee is obtained by bounding a Moreau-envelope stationarity measure.
  • Guarantee: The projected method’s ε-complexity matches the stochastic gradient guarantee for ε-stationarity in smooth minimization.The comparison concerns the dependence on ε.

Improved complexity under convexity.

Under convexity, the paper improves the projected-method complexity by reducing the initial objective gap before applying the main stochastic scheme. The general proximal-subgradient analysis establishes matching convergence guarantees.

  • Convexity improvement: A two-round scheme reduces the initial gap with a subgradient method before applying the stochastic method.The construction uses a separate first round to obtain a smaller gap parameter Δ.
  • Convexity improvement: O(L^2(ρD)^2/3 ε^8/3) iterations are sufficient for E∥∇ϕ1/(2ρ)(x)∥≤ε in the stated bounded-diameter Lipschitz setting.The bound follows from the optimized two-round construction.
  • Convexity improvement: A separate logarithmic-round procedure further improves the ε-complexity using quadratically regularized subgradient problems.Its detailed procedure and analysis are placed in an independent technical report.
  • General proximal method: The proximal stochastic subgradient analysis assumes ρ-weak convexity, mild Lipschitz conditions, and stepsizes αt≤1/¯ρ.Theorem 3.4 gives both iterate and returned-point guarantees.
  • General proximal method: The proof derives convergence by combining proximal-map identities, a descent inequality, conditional expectations, and an unfolded recursion.The final guarantee follows after setting ¯ρ=2ρ and using constant stepsizes.

Proximal stochastic gradient for smooth minimization.

For smooth minimization with a convex regularizer, the same framework yields stochastic prox-gradient guarantees under finite variance. The results extend the O(ε^-4) complexity established for proximal stochastic subgradient methods.

  • Smooth setting: In the smooth setting, f is C1-smooth with ρ-Lipschitz gradient, and finite variance replaces the bounded-second-moment condition.The resulting assumptions retain weak convexity and the regularizer framework.
  • Analysis: The analysis extends the proximal descent lemma using unbiased stochastic gradients, variance control, and Lipschitz continuity of ∇f.The key inequality is the smooth analogue of the nonsmooth proximal-subgradient argument.
  • Guarantee: The complexity estimate can be translated directly into a bound on the prox-gradient mapping.This enables comparison with prior additive-composite minimization results.
  • Guarantee: O(ε^-4) complexity persists for the stochastic proximal-gradient method in the broader smooth composite setting.The result is stated through Corollary 3.6 and its returned-iterate guarantee.

4. Stochastic model-based minimization.

The paper analyzes stochastic model-based minimization under one-sided approximation, weak-convexity, and Lipschitz assumptions. Its convergence analysis establishes stationarity and function-value guarantees, including convex and strongly convex cases.

  • Assumptions: The stochastic one-sided model assumes i.i.d. sampling, one-sided accuracy, weak convexity of each model plus r, and a Lipschitz property.These conditions imply that the objective ϕ is (τ + η)-weakly convex and that f is L-Lipschitz on U.
  • Algorithm: Algorithm 4.1 samples a stochastic model, minimizes a regularized model, and uses a nondecreasing βt inversely proportional to αt.The analysis also samples an output iterate t∗ from a discrete distribution.
  • Nonconvex convergence: Theorem 4.3 gives convergence guarantees for the iterates and the randomly returned point under βt > ρ̄ > τ + η.A constant parameter βt = ρ̄ + γ^-1√(T + 1) yields the specialized guarantee (4.16).
  • Convex convergence: Under convexity, the expected function gap converges at the rates O(1/√t) for μ = 0 and O(1/(μt)) for μ > 0.The convex result uses αt = βt^-1, while the strongly convex result uses βt = μ(t + 1).
  • Applications: The framework yields complexity guarantees for stochastic proximal point, prox-linear, and proximal subgradient methods by verifying the model assumptions.The paper identifies these methods as instances of Algorithm 4.1 and applies Theorem 4.3 to them.

Stochastic proximal point.

The stochastic proximal point method is represented as Algorithm 4.1 using stochastic models satisfying assumptions on sampling, unbiasedness, weak convexity, and Lipschitz behavior.

  • Assumptions: The proximal point setting assumes i.i.d. samples, stochastic models whose expectations equal f, ρ-weak convexity, and a Lipschitz bound.These are assumptions (C1)–(C4).
  • Method: The stochastic proximal point method is Algorithm 4.1 with models fx(y, ξ), and assumptions (B1)–(B4) hold with τ = 0 and η = ρ.Its complexity guarantees therefore follow from Theorem 4.3.

Stochastic proximal subgradient.

The stochastic proximal subgradient method fits the stochastic model framework even when both the objective term and regularizer can be weakly convex.

  • Assumptions: The method allows f and r to be weakly convex, with assumptions controlling stochastic subgradients and their second moments.The framework permits r to be nonconvex under these relaxed assumptions.
  • Method: Linear stochastic models produce the proximal subgradient method and satisfy the model conditions with τ = ρ1 and η = ρ2.The Lipschitz-model condition follows from the assumed bound involving L.
  • Related model: The framework also introduces stochastic prox-linear models under convexity and smoothness assumptions on h and c.The assumptions require h to be Lipschitz, c to be C1-smooth with Lipschitz Jacobian, and r to be weakly convex.

Expectation of convex monotone compositions.

The paper applies stochastic model-based minimization to expectations of convex monotone compositions, including settings where the inner map is not smooth.

  • Scope: A broader example permits convex h and c with monotone h even when c is not smooth, so it lies outside the smooth composite framework.The stochastic update samples ξt, selects a subgradient, and performs a simple update.
  • Assumptions: The considered composition has convex h and c, with h also nondecreasing, and assumes measurable stochastic mappings and Lipschitz bounds.These are conditions (F1)–(F4).
  • Guarantee: The assumptions imply the stochastic model conditions with τ = 0, η = 0, and L = √Eξ[M(ξ)^2].The resulting model-based algorithm therefore receives the framework’s expected function-value guarantee.
  • Guarantee: The algorithm has an O(1/√t) convergence guarantee in expected function-value gap for this composition class.The paper illustrates the result using the Conditional Value-at-Risk problem and discusses phase retrieval and blind deconvolution experiments.

5. Numerical Illustrations.

Numerical experiments on phase retrieval and blind deconvolution compare stochastic subgradient, prox-linear, and proximal point methods across problem sizes and step sizes. The prox-linear and proximal point methods perform better and are more robust to step-size choice, despite essentially identical theoretical worst-case complexity and comparable computational cost.

  • Computational cost: The three algorithms have essentially the same computational cost per update, while stochastic prox-point and prox-linear subproblems have closed-form solutions.Each method uses one data point at a time.
  • Complexity: Theoretical guarantees imply essentially the same worst-case complexity for stochastic subgradient, prox-linear, and proximal point algorithms.
  • Experimental setup: The experiments compare stochastic subgradient, prox-linear, and proximal point methods on phase retrieval and blind deconvolution.Phase retrieval uses (d, m) = (10, 30), (50, 150), and (100, 300); blind deconvolution uses (d1, d2, m) = (10, 10, 30), (50, 50, 200), and (100, 100, 400).
  • Blind deconvolution: For blind deconvolution, candidate solutions for the proximal point subproblem can be obtained by solving a system that leads to a quartic polynomial.There are at most four points satisfying the relevant critical-point condition.
Loading 1803.06523v3…