PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic algorithms with geometric step decay converge linearly on sharp functions

Damek Davis, Dmitriy Drusvyatskiy, Vasileios Charisopoulos

arXiv:1907.09547v1math.OCcs.LGstat.ML

TL;DR

Classical polynomial step decay yields sublinear rates, and geometric step decay had improved rates for sharp convex problems, leaving its effectiveness on sharp nonconvex problems open. The paper applies geometric step decay to stochastic algorithms and establishes local linear convergence guarantees for a large class of such problems.

  • Problem

    Whether geometric step decay can give stochastic algorithms linear convergence on sharp nonconvex problems remained open, where the convergence region is local.

    Source: §1 · pp. 1–2, §3.2 · p. 12

  • Method

    The paper applies geometric step decay to stochastic algorithms, including a restart strategy for stochastic model-based methods.

    Source: §1 · p. 2, §2.2 · p. 9

  • Results

    A geometric step decay schedule gives a local linear rate to global minimizers for a large class of stochastic, sharp, nonsmooth, nonconvex problems.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The guarantees extend linear convergence results to stochastic sharp nonconvex problems with a local convergence region.

    Source: §1 · p. 2, §3.2 · p. 12

    For arbitrary sets S, repeated runs of Algorithm 2 do not permit selecting the best iterate without increasing sample complexity.

    Source: §2.2 · p. 9

Abstract

from arXiv · show

Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called \emph{geometric step decay} and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of \emph{sharp} convex functions. In this work, we ask whether geometric step decay similarly improves stochastic algorithms for the class of sharp nonconvex problems. Such losses feature in modern statistical recovery problems and lead to a new challenge not present in the convex setting: the region of convergence is local, so one must bound the probability of escape. Our main result shows that for a large class of stochastic, sharp, nonsmooth, and nonconvex problems a geometric step decay schedule endows well-known algorithms with a local linear rate of convergence to global minimizers. This guarantee applies to the stochastic projected subgradient, proximal point, and prox-linear algorithms. As an application of our main result, we analyze two statistical recovery tasks---phase retrieval and blind deconvolution---and match the best known guarantees under Gaussian measurement models and establish new guarantees under heavy-tailed distributions.

1 Introduction

Classical polynomial step decay yields sublinear rates, while geometric step decay has improved rates for sharp convex problems; whether it could do so for sharp nonconvex problems remained open. This work establishes local linear convergence guarantees for stochastic algorithms and applies them to statistical recovery tasks.

1 Introduction

  • Sharp nonconvex recovery problems pose an open question: whether stochastic algorithms with geometric step decay can converge linearly, despite the local convergence region.Sharpness is associated with strong identifiability in statistical recovery problems.Source: §1 · p. 2
  • The main result gives a local linear convergence rate to global minimizers for a large class of stochastic, sharp, nonsmooth, nonconvex problems using geometric step decay.The guarantee applies to stochastic projected subgradient, proximal point, and prox-linear algorithms.Source: §1 · p. 2
  • Phase retrieval and blind deconvolution match the best known guarantees under Gaussian measurements and establish new guarantees under heavy-tailed distributions.Source: §1 · p. 2

Related work

  • Prior work [66] established linear convergence with geometric step decay for sharp convex functions, assuming convexity and uniformly bounded stochastic subgradients; this work assumes neither condition.The paper instead assumes stochastic subgradients have a finite second moment.Source: §1 · p. 2, Related work · p. 3
  • Bounding the probability that iterates leave the local convergence region is a technical contribution to analyzing stochastic restarts in nonconvex problems.Source: Related work · p. 3

2 Algorithms, assumptions, and main results

The paper combines stochastic model-based algorithms with geometric step decay to obtain local linear convergence guarantees for sharp nonconvex problems. Its assumptions cover sharp growth toward a closed set and locally accurate, convex models, while the results include a repeated-run ensemble strategy for stronger probability and initialization guarantees.

Sharp Growth

  • Under sharp growth toward a closed set S containing X*, the algorithm converges linearly to S, which may be an active manifold rather than the minimizer set.When S differs from X*, convergence to S does not necessarily imply convergence to a global minimizer.Source: Sharp Growth · p. 5

Accuracy and Regularity

  • The stochastic models are assumed to be convex and to under-approximate the loss up to quadratic error, with one-sided accuracy and convexity conditions.These model conditions imply weak convexity; the paper also notes that its results hold under a weaker assumption.Source: Accuracy and Regularity · p. 6

Lipschitz continuity

  • The model Lipschitz condition is local to a tube around S, where the algorithms are initialized and remain, rather than global.The paper identifies this local condition as important for phase retrieval and blind deconvolution, where global Lipschitz continuity does not hold.Source: Lipschitz continuity · p. 7

2 Algorithms, assumptions, and main results

  • The restart strategy halves the step size across outer iterations and applies stochastic model-based updates, improving sublinear guarantees to local linear rates with high probability.The results include a strategy converging linearly to a general set S and a nested ensemble/proximal-point strategy for S = X* with improved dependence on failure probability.Source: §2 · p. 5, §2.2 · p. 7

2.2 Algorithms and results

  • The nested ensemble strategy applies repeated model-based runs to quadratically regularized problems with unique solutions, then updates the regularization in a proximal-point scheme.This construction addresses the singleton-set restriction of the basic ensemble method, relevant when recovery problems have uncountably many solutions.Source: §2.2 · p. 9
  • The proximal-point ensemble guarantee reaches ε-distance from X* with probability at least 1−δ and resolves the earlier strategy’s initialization and sample-complexity issues.It assumes only a local second-moment bound, whereas the cited convex result of Xu et al. [66] requires almost surely bounded stochastic subgradients.Source: §2.2 · p. 10

3 Proofs of main results

The proofs establish linear convergence guarantees for stochastic model-based algorithms, first in the convex setting and then in nonconvex settings where the convergence region is local. A high-probability strategy boosts inner-loop success at logarithmic cost.

3 Proofs of main results

  • The section establishes linear-convergence guarantees for Algorithms 2 and 5 under Assumptions (A1)–(A5).The stated guarantees cover settings beyond weakly convex problems when the two-point accuracy assumption replaces (A3).Source: §3 · p. 10, §3.2 · pp. 13–14

3.1 Warm-up: convex setting

  • The convex warm-up proves convergence to within ε of the solution set with probability at least 1 − δ under the stated assumptions.The proof repeatedly applies a sublinear convergence guarantee, choosing parameters to reduce the error by a fixed fraction; Markov's inequality handles the random inner-loop output.Source: §3.1 · p. 11

3.2 Nonconvex setting

  • The nonconvex proof uses a stopping-time argument to keep iterates inside the local convergence region while establishing linear convergence.The guarantee's initialization quality and sample complexity depend on the success-probability parameter.Source: §3.2 · pp. 12–13

3.3 Convergence with high probability

  • The high-probability strategy boosts inner-loop success at logarithmic cost and yields a linear-convergence guarantee for Algorithm 5.The proof applies the inner-loop guarantee conditionally and uses the ensemble technique to raise its success probability.Source: §3.3 · pp. 14–16

4 Consequences for statistical recovery problems

The paper applies its convergence results to robust phase retrieval and blind deconvolution. Under Gaussian measurements, the analyses match the best known sample-complexity guarantees up to logarithmic factors, and the results extend to heavy-tailed distributions.

4 Consequences for statistical recovery problems

  • The section presents phase retrieval and blind deconvolution as sharp, weakly convex statistical recovery problems addressed by linearly convergent streaming algorithms.The phase-retrieval solution set is {±x̄}; blind deconvolution has a solution set parameterized by a scaling factor.Source: §4 · p. 16, §4.1 · p. 17, §4.2 · p. 19

4.1 Robust Phase retrieval

  • For Gaussian robust phase retrieval, combining spectral initialization with Algorithm 5 matches the best known sample complexity up to logarithmic factors.The convergence guarantee applies to subgradient, clipped subgradient, and prox-linear models when initialized within constant relative error; the section also extends beyond Gaussian measurements to heavy-tailed distributions.Source: §4.1 · pp. 17–18

4.2 Robust blind deconvolution

  • For Gaussian robust blind deconvolution, combining spectral initialization with Algorithm 5 matches the best known sample complexity up to logarithmic factors.The convergence guarantee applies to subgradient, clipped subgradient, and prox-linear models when initialized within constant relative error; the section also states that results extend to heavy-tailed distributions.Source: §4.2 · pp. 19–20

5 Numerical Experiments

The experiments test geometric step decay on phase retrieval, blind deconvolution, and sparse logistic regression, examining convergence, step-size sensitivity, and convergence to an active set. The recovery experiments broadly match the predicted linear behavior, while the logistic-regression experiment distinguishes Algorithm 2's linear support-set convergence from sublinear function-value convergence.

5 Numerical Experiments

  • The study evaluates convergence, step-size sensitivity, and active-manifold convergence on recovery tasks and sparse logistic regression, using Algorithm 2 and four models for the recovery losses.Algorithms 2 and 5 performed similarly in preliminary testing, so Algorithm 5 was not evaluated.Source: §5 · p. 20

5.1 Convergence behavior

  • With noise, phase retrieval and blind deconvolution converge linearly at the predicted rate; without noise, all but the subgradient method reach an exact solution in fewer iterations.The finite-sample and streaming plots average 10 runs for d = 100.Source: §5.1 · p. 21, Figure 2 · p. 22, Figure 3 · p. 23
  • In finite-sample tests, the recovery problems use m = 8·d measurements; streaming tests draw a new i.i.d. sample each iteration, with corruption probability pfail.The phase retrieval and blind deconvolution experiments use d = 100 and initialize at a fixed distance from ground truth.Source: §5.1 · pp. 20–21, Figure 2 · p. 22, Figure 3 · p. 23

5.2 Sensitivity to step size

  • Algorithm 2 performs as predicted even when its initial step size is misspecified by a few orders of magnitude.The sensitivity experiments cover phase retrieval and blind deconvolution with d = 100 and pfail in {0, 0.2}.Source: §5.2 · p. 21, Figure 4 · p. 24, Figure 5 · p. 25
  • The prox-linear, proximal point, and clipped models perform similarly; a much larger proximal-point step size produces different iterates but fails to reach the specified accuracy.The prox-linear and clipped methods produce the same iterates, while the proximal-point and prox-linear iterates are practically indistinguishable at the tested settings.Source: §5.2 · pp. 21–22

5.3 Activity identification

  • The sparse logistic regression experiment applies stochastic proximal gradient to identify the active set defined by coefficients exceeding a numerical threshold.The target is a sparse classifier for distinguishing MNIST digits 6 and 7.Source: §5.3 · pp. 22–24

5.3.1 Evaluation

  • Algorithm 2's iterates converge linearly to the sparse logistic regression support set, while function values converge sublinearly; RDA's iterates converge sublinearly on both metrics.Figure 6 reports function-value gap and distance to the support set and the proximal-gradient solution.Source: §5.3.1 · p. 26, Figure 6 · p. 26

A Proofs from Section 3.2

This proof section supplies an elementary lemma under Assumptions (A4) and (A5). Its proof uses a minimal-norm subgradient inequality and Cauchy–Schwarz.

A Proofs from Section 3.2

  • The section presents the lemma as an elementary ingredient for subsequent arguments.Source: A Proofs from Section 3.2 · p. 31
  • Lemma A.1 applies for any γ in (0, 2), y in Tγ, and x in R^d, under Assumptions (A4) and (A5).The excerpt introduces an estimate for these points.Source: A Proofs from Section 3.2 · p. 31
  • The proof selects a minimal-norm subgradient at y and applies its defining inequality before invoking Cauchy–Schwarz.The argument also refers to inequality (2.5).Source: A Proofs from Section 3.2 · p. 31

A.1 Proof of Lemma 3.3

The proof of Lemma 3.3 uses a stopping time to analyze the probability that the iterates remain in the relevant region. It combines a bound on expected distance with a bound on the probability of staying in that region.

A.1 Proof of Lemma 3.3

  • The proof seeks a lower bound on the probability that the iterate at the stopping index is within ε, using the event that the process has not exited the region.It defines D_k as the distance from y_k to S and introduces a stopping time τ.Source: §A.1 · p. 31
  • One proposition bounds the expected distance to S on the event of remaining in the region, by iterating an inequality for the proximal update.The argument conditions on the algorithm history and uses the event sequence A_k.Source: §A.1 · pp. 32–33
  • A second proposition bounds the probability of remaining in the region by analyzing a stopped process and combining expectation estimates.The proof uses the decomposition of the target event and Markov's inequality.Source: §A.1 · p. 33

B.1 Proof of Lemma 3.5

The proof of Lemma 3.5 establishes that a minimizer of the proximal subproblem lies in the solution set when the base point is in the local tube. It uses weak convexity and sharpness to constrain the proximal minimizer.

B.1 Proof of Lemma 3.5

  • Weak convexity makes the proximal subproblem strongly convex with constant ρ − η for γ in (0, 2) and y in Tγ.The proof also invokes Assumptions (A4) and (A5).Source: §B.1 · p. 34
  • Sharpness and weak convexity yield a lower bound on subgradients of the extended-valued objective away from the solution set.The proof considers subgradients of f plus the normal cone to X.Source: §B.1 · p. 34
  • The proximal minimizer remains in the tube and the argument concludes it belongs to X* under the stated parameter condition.The proof compares its distance to the base point with the tube radius and derives a contradiction if it is outside X*.Source: §B.1 · p. 34

B.2 Proof of Lemma 3.6

The proof controls the algorithm’s stopped process using conditional-expectation estimates while iterates remain in the local region. It combines bounds on expected distance and on the probability of remaining in that region to establish the proposition.

B.2 Proof of Lemma 3.6

  • Conditional-expectation estimates apply when the iterate lies in Tγ, using the algorithm’s history and a stopping-time construction.The proof defines conditional expectation with respect to the history through iteration k and introduces the events A_k = {τ > k}.Source: §B.2 · pp. 35–36
  • Two propositions establish an upper bound on expected squared distance and a lower bound on the probability of the event A_K.The proof identifies these as the two ingredients needed for the result.Source: §B.2 · pp. 35, 37
  • The proof iterates the conditional estimate using the tower rule, then combines the resulting bounds with the initial condition y0 ∈ Tγ.The final step also uses dist²(y0, X*) = 0.Source: §B.2 · pp. 36–37

B.3 The ensemble method

The ensemble method aggregates independent vectors that individually satisfy an accuracy condition. With high probability, it identifies an index whose vector is within 3ε of the target.

B.3 The ensemble method

  • For independent vectors satisfying the stated estimate, the ensemble lemma guarantees an index meeting condition (B.8) with high probability.The proof invokes Chernoff’s bound to control how many vectors satisfy the estimate.Source: §B.3 · pp. 37–38
  • Any index satisfying (B.8) has vector distance at most 3ε from the target vector.The proof finds another vector within ε of the target and within 2ε of the selected vector, then applies the triangle inequality.Source: §B.3 · pp. 37–38

C.1 Proof of Theorem 4.1

The phase-retrieval proof establishes the minimizer set and sharpness for the outlier-free objective, then bounds model parameters. Across the three models, the noise parameter satisfies η = 2˜η.

C.1 Proof of Theorem 4.1

  • The minimizers are exactly {±x̄}, with sharpness parameter μ = (1 − 2p_fail)˜μ||x̄||.The proof derives these properties for the outlier-free phase-retrieval loss.Source: §C.1 · p. 38
  • For all three models, the noise parameter satisfies η = 2˜η.The proof analyzes the models separately after deriving a common inequality.Source: §C.1 · pp. 38–39
  • Each model’s subgradient norm has a bound in terms of the loss-scale quantity L(x, z).The proof uses the form of the model subgradients to establish the bound.Source: §C.1 · p. 39

C.2 Proof of Theorem 4.1

The blind-deconvolution proof establishes sharpness for the outlier-free objective and then estimates the model parameters. Across the three models, it obtains η = ˜η.

C.2 Proof of Theorem 4.1

  • The proof establishes sharpness for the blind-deconvolution objective.It defines an outlier-free objective and uses a bound to prove sharpness.Source: §C.2 · p. 39
  • For all three models, the noise parameter satisfies η = ˜η.The proof applies the derived inequality to each model.Source: §C.2 · pp. 39–40
  • The proof bounds model subgradient norms using a quantity L((x, y), z).The bound follows from the stated form of the model subgradients.Source: §C.2 · p. 40

D Sharpness and identifiability

This section relates local sharp growth away from a closed set to that set being an identifiable, or active, manifold. Under stated local conditions, each property implies the other.

D Sharpness and identifiability

  • For f(x, y) = x^2 + |y|, the x-axis is sharply growing away from and active, although it is not the minimizer set.The passage presents sharp growth away from the set and uniformly nonzero subgradients outside it as the two geometric properties.Source: D Sharpness and identifiability · p. 40
  • An identifiable manifold is C2-smooth, f is C2-smooth on it, and convergent limiting-subgradient sequences eventually lie in it.These are the smoothness and finite-identification conditions in the paper’s definition.Source: D Sharpness and identifiability · p. 41
  • At a critical point, identifiability implies local sharp growth under a mild condition on f.The theorem states this direction for a closed function and an identifiable manifold at the critical point.Source: D Sharpness and identifiability · p. 41
  • Under prox-regularity and local sharp growth away from S, limiting-subgradient sequences converging to the critical point eventually lie in S.The sharp-growth condition bounds f(x) below by the best value on the projection of x onto S plus a positive multiple of dist(x, S).Source: D Sharpness and identifiability · p. 42

Related papers

Loading 1907.09547v1…