Stochastic Methods for Composite and Weakly Convex Optimization Problems

John Duchi; Feng Ruan

Source-linked AI summary

Stochastic Methods for Composite and Weakly Convex Optimization Problems

John Duchi, Feng Ruan

arXiv:1703.08570v3Mar 24, 2017math.OCmath.ST

TL;DR

The paper addresses stochastic composite and weakly convex optimization when full prox-linear updates are computationally difficult. It develops stochastic model-based methods, including prox-linear and subgradient procedures, and proves convergence under technical conditions; experiments on robust nonsmooth phase retrieval indicate practical advantages for stochastic procedures, while convergence rates are not provided.

Problem
Full prox-linear iterations can be prohibitively expensive for large finite sums and infeasible when the distribution is continuous, unknown, or accessible only through samples.
Method
The paper develops stochastic model-based algorithms, including stochastic prox-linear and stochastic subgradient methods that use individual samples at each iteration.
Results
Under boundedness, coercivity, and moment conditions, the stochastic methods converge to stationary values or stationary points of potentially nonsmooth, nonconvex objectives.
Takeaways & Limitations
Robust nonsmooth phase-retrieval experiments indicate advantages for stochastic over deterministic procedures on some problems and suggest greater robustness for stochastic prox-linear methods than stochastic subgradient methods.
Takeaways & Limitations
The paper's stochastic convergence results do not provide rates of convergence, and the reported robustness advantage of stochastic prox-linear methods is not explained by the theory.

Abstract

from arXiv · show

We consider minimization of stochastic functionals that are compositions of a (potentially) non-smooth convex function $h$ and smooth function $c$ and, more generally, stochastic weakly-convex functionals. We develop a family of stochastic methods---including a stochastic prox-linear algorithm and a stochastic (generalized) sub-gradient procedure---and prove that, under mild technical conditions, each converges to first-order stationary points of the stochastic objective. We provide experiments further investigating our methods on non-smooth phase retrieval problems; the experiments indicate the practical effectiveness of the procedures.

1. Introduction.

The paper develops stochastic model-based methods for composite and weakly convex optimization when deterministic prox-linear subproblems are expensive or infeasible. Under technical conditions, the methods converge to stationary values or stationary points, while phase-retrieval experiments investigate their practical behavior.

1. Introduction.: The prox-linear models are convex and second-order accurate under Lipschitz conditions, motivating iterative minimization around the current iterate.For sufficiently small stepsizes, the iterates decrease the composite objective and converge to stationary points in the deterministic setting.
1. Introduction.: The paper develops stochastic linear proximal and stochastic subgradient procedures for stochastic composite and weakly convex objectives.These methods are presented as examples of a broader stochastic model-based framework.
1. Introduction.: Stochastic model-based methods use individual samples per iteration, making composite optimization computationally simpler than solving full deterministic prox-linear subproblems.The stochastic prox-linear method substitutes a sampled component h_i0 and c_i0 for the full composite functions, provided individual prox-linear steps are available.
1. Introduction.: Under bounded-iterate, coercivity, and second-moment conditions, appropriate model-based strategies have limit points whose objective values are stationary values.With an additional density condition on non-critical objective values, the methods converge to stationary points.
1. Introduction.: The numerical study uses robust nonsmooth phase retrieval to compare stochastic and deterministic procedures, finding advantages for stochastic methods on some problems.The experiments also indicate that stochastic prox-linear methods may be more robust than stochastic subgradient methods, although the theory does not explain this effect.
1. Introduction.: The paper does not provide convergence rates for the stochastic procedures, motivating numerical simulations to investigate their properties.Subsequent work supplied non-asymptotic guarantees for variants of these methods.

2. Algorithms and Main Convergence Result.

The paper develops model-based stochastic algorithms for composite and weakly convex objectives, including subgradient, prox-linear, and proximal-point variants. Under stated regularity, boundedness, and stepsize conditions, these methods converge to stationary values, with stronger assumptions yielding stationary cluster points and objective-value convergence.

General model-based strategy: The model-based update uses convex local models that match the instantaneous objective at the current iterate and locally almost underestimate it.The required model conditions also include a quantitative local approximation guarantee.
Examples: The framework includes stochastic subgradient, stochastic prox-linear, stochastic proximal-point, and guarded stochastic proximal-point methods.The prox-linear variant linearizes the smooth inner mapping while retaining the outer convex function.
Main convergence result: The main convergence theorem applies to model-based stochastic updates under local Lipschitzian and weak-convexity assumptions, bounded iterates, and suitable stepsizes.Its conclusion places limiting objective values in the image of the stationary set.
Main convergence result: For composite objectives, integrability of local smoothness and outer-function Lipschitz parameters supplies sufficient conditions for the required assumptions.Specifically, finite E[γ_ε(x; S)β_ε(x; S)] yields the needed weak-convexity and model-approximation bounds.
Main convergence result: With Assumption C, objective values converge and every cluster point of the iterates is stationary; without it, iterate convergence is not guaranteed.The weaker theorem still constrains cluster-point objective values to stationary values.

3. Convergence Analysis of the Algorithm.

The convergence analysis interprets stochastic model updates as asymptotic approximations to a differential inclusion. Set-valued analysis establishes trajectory regularity, Lyapunov behavior, and the functional convergence needed to connect the discrete algorithms to stationary points.

Stochastic approximation and differential inclusions: As stepsizes vanish, the stochastic iterations asymptotically track solution paths of a differential inclusion involving the mean subgradient, regularizer, and constraint normal cone.The paper proves this limiting equivalence rather than using it only as a heuristic.
Preliminaries: The analysis establishes existence and uniqueness properties for the limiting differential inclusion through outer semicontinuity, compactness, and one-sided growth conditions.A stated lemma gives uniqueness under the relevant inner-product bound.
Preliminaries: A Lyapunov argument supplies trajectories with nonincreasing behavior and an integral decrease condition for the differential inclusion.The sufficient conditions require an admissible velocity satisfying a directional Lyapunov inequality.
Analytic properties: Under the paper’s assumptions, the subgradient mappings are closed, compact-convex valued, and outer semicontinuous, while the regularizer preserves these properties in the combined mapping.These properties support the limiting dynamical-system analysis.
Functional convergence: The generic stochastic update is shown to satisfy the functional-convergence theorem’s requirements, including bounded iterates, stepsize conditions, weighted-error convergence, and a distance condition.This connects the model-based algorithms to the appropriate differential inclusion.

3.2. Functional convergence of the iteration path.

The stochastic iterations are represented as stochastic approximation processes whose interpolated paths asymptotically follow a differential inclusion. Under boundedness, stepsize, noise, and mapping conditions, this framework applies to the paper’s model-based updates.

Stochastic approximation framework: The update xk+1 = xk + αk[yk + ξk+1] is analyzed through the linear interpolation of its iterates and time-shifted paths.The interpolation is absolutely continuous and satisfies a differential relation almost everywhere.
Stochastic approximation framework: The general convergence theorem requires bounded iterates and update directions, suitable stepsizes, convergent weighted noise, and a closed-valued limiting mapping.These conditions support relative compactness of shifted interpolated paths and identification of their limits.
Model-based updates: The model-based update conditions yield locally bounded gradient mappings and establish the technical properties needed for the limiting inclusion.The construction uses local Lipschitz bounds, model continuity, and monotonicity of subgradients.
Model-based updates: The stochastic updates admit a mean-progress plus zero-mean noise decomposition, covering stochastic proximal point, prox-linear, and subgradient methods.The noise is a square-integrable martingale difference sequence with bounded second moments under the stated assumptions.
Functional convergence: With probability one, shifted interpolated paths are relatively compact, and every limit point satisfies the differential inclusion associated with the stochastic model-based method.The result applies to stochastic subgradient, prox-linear, and proximal point examples.

3.3. Properties of the limiting differential inclusion.

The limiting differential inclusion has well-behaved trajectories: a Lyapunov function decreases along them, trajectories exist globally, and their cluster points are stationary under the stated assumptions.

Lyapunov analysis: The Lyapunov-like function V decreases in the minimal-subgradient direction according to V′(x; −g⋆(x)) ≤ −∥g⋆(x)∥2.The minimal subgradient supplies the descent direction used in the trajectory analysis.
Trajectory properties: The coercivity assumption makes F + I_X coercive, ensuring compact sublevel sets for the objective over X.This assumption supports boundedness and global extension of differential-inclusion trajectories.
Trajectory properties: Solutions to the differential inclusion exist for all t ≥ 0, remain in X, are bounded, and are Lipschitz in time.These properties are established under Assumptions A, B, and E.
Stationarity of trajectories: If the objective value remains unchanged over an interval, the minimal subgradient vanishes throughout that interval.The result first obtains almost-everywhere vanishing and then extends it using continuity and outer semicontinuity.
Stationarity of trajectories: Every cluster point of a trajectory solving the limiting inclusion is stationary, meaning g⋆(x∞) = 0.The proof combines repeated visits near the cluster point, small minimal subgradients, and outer semicontinuity.

3.4. Almost sure convergence to stationary points.

Under the paper’s assumptions, the stochastic iterates converge almost surely in objective value, and under an additional weak Sard-type condition, all cluster points are stationary.

Main convergence result: The main theorem establishes almost-sure convergence behavior for stochastic model-based iterations under Assumptions A, B, D, and E.The proof uses properties of the interpolated path and the limiting differential inclusion.
Main convergence result: With probability one, the iterates have stationary cluster points and the objective values F(xk) converge under Assumptions A–E and the weak Sard-type condition.This is the stated stationary-set convergence corollary.
Boundedness conditions: A finite second moment of the local Lipschitz parameter guarantees bounded iterates with probability one under the stated conditions.This provides one sufficient route to the boundedness assumption required by the convergence theorems.
Boundedness conditions: Regularizers with suitable coercive growth also guarantee bounded iterates when the sample objectives have controlled local Lipschitz growth.The sufficient condition requires ν < β − 1 for a (β, λ)-coercive regularizer.
Proof of convergence: If a nonstationary cluster point existed, the interpolated objective trajectory would produce infinitely many strict decreases across an objective-level interval.The upcrossing argument combines strict decreases near nonstationary points with a bound on how quickly the interpolated path can move.

4. Experiments.

The experiments evaluate stochastic prox-linear, stochastic subgradient, and deterministic prox-linear methods on robust phase retrieval under noise, corruption, conditioning, row-norm irregularity, and stepsize variation. Stochastic methods converge quickly to reasonably accurate solutions, while stochastic prox-linear is generally more robust to conditioning and stepsize choices.

4.1. Performance for well-conditioned problems: After a few data passes, stochastic methods reach approximately 10^-4 accuracy, whereas deterministic prox-linear eventually achieves substantially better accuracy but often progresses more slowly.Results use median excess gaps with 10% and 90% confidence intervals over 100 tests.
4.1. Performance for well-conditioned problems: Stochastic prox-linear converges substantially faster than stochastic subgradient on noiseless and corrupted observations, while their behavior is similar under Laplacian noise.The paper heuristically attributes the noiseless advantage to more precise updates; under continuous noise, that precision is less necessary.
4.2. Problem conditioning and observation irregularity: As the condition number increases, all methods degrade, but stochastic subgradient degrades substantially more quickly than the other methods.With noisy observations, subgradient performance improves relative to the other methods; with noiseless observations, its relative performance is worse.
4.2. Problem conditioning and observation irregularity: With row norms varying by approximately a factor of 10, stochastic prox-linear performs better in both noiseless and noisy experiments.The paper connects this behavior to the scaling robustness of its linearized updates.
4.3. Stepsize sensitivity: Stochastic prox-linear and proximal-point methods tolerate broad choices of often-large initial stepsizes, whereas stochastic subgradient performs well only in a relatively narrow stepsize range.The prox-linear and proximal-point methods are also less sensitive to the stepsize decay parameter β.

Appendix A. Proof of Theorem 3.7.

The proof establishes convergence by relating interpolated stochastic iterates to limiting differential inclusions. Relative compactness yields convergent subsequences, and weak-convergence arguments identify the limiting dynamics.

Part I: Relative compactness: The proof first establishes relative compactness of the time-shifted trajectories using uniform equicontinuity and pointwise boundedness.The Arzelà-Ascoli theorem supplies relative compactness in C(R+, R^d).
Part II: Limiting differential inclusion: Noise and discretization effects become asymptotically negligible, allowing the interpolated stochastic sequence to inherit the limiting trajectory behavior.The proof controls interpolation errors using boundedness, the stepsize-noise condition, and convergence of shifted trajectories.
Part II: Limiting differential inclusion: Any convergent subsequence of shifted interpolants is shown to satisfy the limiting differential inclusion through weak convergence and Banach-Saks subsequences.The argument passes to weak limits of the interpolated driving terms and verifies membership in the limiting set-valued map.
Part II: Limiting differential inclusion: Closedness of the limiting set-valued map then yields inclusion membership almost everywhere, completing the theorem for arbitrary finite time horizons.The conclusion follows after modifying the limiting function on a null set and observing that the horizon T is arbitrary.

Appendix B. Technical Proofs and Results.

The appendix sets up a technical result for points y and z lying within ε of x, together with a vector v satisfying a norm bound.

The technical setup fixes s ∈ S and abbreviates h(·; s) and c(·; s) as h and c.
The result considers points y and z satisfying ∥y − x∥ ≤ ε and ∥z − x∥ ≤ ε.
It also assumes a vector v whose norm is bounded by βε ∥y − z∥^2 / 2.

B.1. Proof of Claim 1.

The proof establishes local weak convexity of each composite sample function by adding a sufficiently large quadratic regularizer. The required curvature bound is obtained from local Lipschitz and smoothness parameters.

B.1. Proof of Claim 1: Choosing λ ≥ γ_ϵ(x)β_ϵ(x) makes the locally regularized composite function convex, so h(c(·;s)) is λ(s,x)-weakly convex near x.The proof uses local Lipschitz continuity of h and c's gradient, together with subdifferentiability of h.
B.1. Proof of Claim 1: The local model error is bounded by γ_ϵ(x;s)β_ϵ(x;s), reflecting the product of the local Lipschitz parameters for h and the gradient of c.This bound is stated for y in an ϵ-neighborhood of x.

B.2. Proof of Lemma 3.6.

The proof establishes directional-derivative and subdifferential properties for weakly convex sample functions, then derives compactness and semicontinuity results for the associated stochastic subdifferential.

Subdifferential representation: The stochastic subdifferential is represented by integrating sample subdifferentials, and it is compact.The representation follows from an argument parallel to standard measurable-subdifferential results.
Convexification: Adding the quadratic regularization produces a convex continuous function near x, enabling the directional-derivative arguments used in the proof.The regularization uses the integrable weak-convexity parameter λ(s).
Directional derivatives: The directional derivative of each weakly convex sample function exists and equals the support function of its Fréchet subdifferential.The argument uses local weak convexity and passage to the limit in directional difference quotients.
Regularity: The auxiliary quantity L_ε(x;s) is finite because the relevant subdifferential sum consists of compact convex subdifferentials.This finiteness supports the subsequent regularity analysis.

B.3. Proof of Lemma 3.9.

The proof establishes upper semicontinuity of the local Lipschitz bound L_ε first pointwise and then after taking expectation, using subdifferential semicontinuity, an integrable envelope, and Fatou’s lemma.

Pointwise bound: Upper semicontinuity of L_ε(·;s) follows by contradiction, boundedness of selected subgradients, and outer semicontinuity of weakly convex subdifferentials.A convergent subsequence yields limiting subgradients at a nearby point, contradicting the assumed discontinuity.
Expected bound: The expected bound L_ε(·) is upper semicontinuous after constructing an integrable local-Lipschitz envelope and applying Fatou’s lemma.The envelope is obtained from the assumed M_ε(x;s)-local Lipschitz continuity.

B.4. Proof of Observation 2.

The proof analyzes a stochastic recursion using normalized products and martingale convergence, concluding that the iterates’ norms have a finite asymptotic upper bound.

Martingale argument: L2-martingale convergence yields M_k divided by its normalizing product converging almost surely to E[Z_k].The martingale is built from the i.i.d., mean-zero variables ξ_i.
Iterate control: lim sup_k ∥x_k∥ ≤ lim sup_k Z_k, so the auxiliary sequence provides an asymptotic norm bound for the iterates.This transfers the stochastic recursion control to the iterate sequence.

B.5. Proof of Observation 3.

The proof bounds the iterates by showing that either the regularizer decreases or the next iterate remains within a fixed ball, then uses induction to obtain a uniform regularizer bound.

Growth comparison: The local Lipschitz assumption bounds the stochastic subgradient by L(1 + ∥x_k∥^ν), while coercivity controls subgradients outside the ball of radius B.The proof compares these growth rates using β − 1 > ν.
One-step stability: ϕ(x_k+1) ≤ ϕ(x_k) or ∥x_k+1∥ ≤ B, yielding the key one-step stability alternative.The alternative follows from the coercivity and regularity assumptions on ϕ together with the stochastic subgradient bound.
Inductive bound: A uniform bound ϕ(x_k+1) ≤ B′ follows inductively from the stability alternative and continuity of the convex regularizer.B′ is chosen to dominate ϕ on the ball of radius B and can be enlarged to include ϕ(x_1).