Source-linked AI summary
Subgradient methods for sharp weakly convex functions
Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, Courtney Paquette
TL;DR
The paper asks whether subgradient methods can provide linear local search for nonsmooth, nonconvex problems. It analyzes standard subgradient methods for sharp weakly convex functions with suitably initialized iterates, and reports essentially the convex-case linear rate under that condition.
Problem
The paper asks whether a generic gradient-based local search procedure can converge linearly on nonsmooth, nonconvex problems under standard regularity conditions.
Source: §1 · p. 1Method
Results
With initialization in a slight contraction of the tube, the methods retain essentially the convex-case linear rate, while ρ determines the initialization condition.
Source: §1 · p. 2Takeaways & Limitations
For statistical and signal-processing problems with good initialization, subgradient methods offer inexpensive local search, illustrated on phase retrieval and covariance estimation.
Source: §1 · pp. 1–2The guarantee for measurements corrupted by gross outliers is outside this work's scope.
Source: §2.1 · p. 5
Abstract
from arXiv · showhide
Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A variety of statistical and signal processing tasks come equipped with good initialization, and provably lead to formulations that are both weakly convex and sharp. Therefore, in such settings, subgradient methods can serve as inexpensive local search procedures. We illustrate the proposed techniques on phase retrieval and covariance estimation problems.
1 Introduction
The introduction asks whether a generic gradient-based local search procedure can converge linearly on nonsmooth, nonconvex problems. It extends sharp-function subgradient guarantees to weakly convex functions when initialization lies in a suitable tube around the solution set.
1 Introduction
- The motivating gap is whether a generic gradient-based local search procedure can converge linearly on nonsmooth, nonconvex problems under standard regularity conditions.Statistics and signal-processing workflows often first obtain a moderately accurate estimate, then refine it iteratively.Source: §1 · p. 1
- Sharpness, equivalently a global error bound, is the regularity condition under which a judicious stepsize choice gives subgradient methods a linear rate on the convex problem.The introduction identifies the minimizers as X* and states that the iterates converge to that set.Source: §1 · p. 2
- Weakly convex functions need not be smooth or convex, yet sharpness and weak convexity together imply a tube around X* with no extraneous stationary points.This supplies a neighborhood in which local convergence analysis can avoid other stationary points.Source: §1 · p. 2
- Standard linearly convergent subgradient methods extend to sharp, weakly convex functions when initialized within a slight contraction of tube T.The weak-convexity constant ρ determines the initialization condition, while the methods retain essentially the convex-case linear rate.Source: §1 · p. 2
- The paper studies Polyak, geometrically decaying, and constant stepsizes, and illustrates the methods on phase retrieval and covariance estimation.It contrasts its locally linear convergence under sharpness with prior global sublinear convergence for any weakly convex function [9].Source: §1 · p. 2
2 Notation
The section establishes notation and describes weakly convex functions, including composite functions and statistical examples. It then specifies sharpness assumptions and a tube around the solution set that contains no extraneous stationary points.
2 Notation
- Euclidean distance and projection are defined, and the indicator δX is zero on X and +∞ outside it.The notation also fixes the inner product and induced norm.Source: §2 · p. 3
2.1 Weakly convex functions
- Weak convexity makes a function convex after a quadratic perturbation, and the generalized subdifferential constructions coincide for weakly convex functions.For the composite class F(x) = h(c(x)), F is Lβ-weakly convex; this is a worst-case estimate, and its subdifferential follows by a chain rule.Source: §2.1 · p. 3
- The phase-retrieval formulation is weakly convex under mild measurement assumptions and sharp under an appropriate noise model, with recovery identified up to sign.The measurements are unchanged by replacing x with −x.Source: §2.1 · p. 4
- Covariance estimation is a higher-rank phase-retrieval variant whose formulation is sharp and weakly convex under appropriate measurement assumptions.Sharpness under gross outliers is mentioned but is outside this work's scope.Source: §2.1 · pp. 4–5
2.2 Setting of the paper
- The setting assumes weak convexity and sharpness; within the resulting tube Tγ for γ ∈ (0, 2], there are no extraneous stationary points.The sharpness constant µ and local subgradient bound L define τ = µ/L, with τ ∈ [0, 1].Source: §2.2 · pp. 5–6
3 Polyak subgradient method
The Polyak subgradient method retains a linear convergence guarantee for weakly convex functions when initialized within a tube around the solution set. Numerical illustrations show linear convergence in nearly all reported experiments, with stagnation when the measurement count is too small for the initialization to lie in the basin of attraction.
3 Polyak subgradient method
- The Polyak method requires knowing the optimal value min g, while later sections consider methods that do not require it.The optimal value can be reasonable to know in settings such as exact penalty methods for solving nonlinear equations.Source: §3 · p. 6
- Q-linear convergence to X∗ holds for the Polyak method when initialized at any point in Tγ, for γ ∈ (0, 1).The proof keeps iterates in the tube by non-increase of their distance to X∗.Source: §3 · p. 7
- Linear convergence is observed in all but two illustrated experiments; those two stagnate when m is too small to place x0 in the basin of attraction.The observed rate improves monotonically as the number of measurements m increases.Source: §3 · p. 7
4 Subgradient method with constant step-size
The constant-step subgradient method avoids needing the optimal value but requires estimates of problem parameters. With suitable initialization, its distance to the solution set decreases linearly up to a fixed threshold.
4 Subgradient method with constant step-size
- With suitable initialization, the constant-step method makes dist(x_k; X*) decrease linearly up to a fixed threshold.The guarantee applies when the initial point lies in the specified tube around the solution set.Source: §4 · pp. 8, 10
- The method is agnostic to the optimal value but requires estimates of µ, ρ, and L; the authors note constant-step schemes are often chosen in practice.The Polyak method, by contrast, relies on knowing the minimal objective value.Source: §4 · pp. 7–8
- As E_k falls toward E*, the contraction factors shrink; as the step size tends to zero, the limiting linear rate is 1 − τ^2.The iterates decrease linearly to a value below E*, and subsequent values stay close to that threshold.Source: §4 · p. 10
- In Figure 2's corrupted-set-up experiments, the lower curves correspond to smaller constant step sizes in phase retrieval and covariance estimation.The compared step sizes are α ∈ {1, 1/3, 1/9}.Source: Figure 2 · p. 10
5 Geometrically decaying step
To reach the true solution set, the paper replaces the constant step with a geometrically decreasing one. With initialization in a specified tube, the method converges linearly, and experiments show better performance than the constant-step scheme.
5 Geometrically decaying step
- As E_k tends to zero Q-linearly, the geometrically scheduled steps α_k tend to zero R-linearly.The authors implement this schedule in Algorithm 3 and prove linear convergence.Source: §5 · p. 12
- For Algorithm 3, the paper states linear convergence in Theorem 5.1; its setup includes initialization at x0 ∈ Tγ, but this excerpt omits the theorem’s full parameter conditions.Source: §5 · p. 12
- In experiments, the method converged linearly in all cases, and smaller chosen rates q improved convergence; it outperformed the constant-step scheme but not the Polyak scheme.The reported comparisons use the paper's phase retrieval and covariance estimation examples.Source: §5 · p. 13