Subgradient Methods for Sharp Weakly Convex Functions

By Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, Courtney Paquette. 2018

140 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “The classical Polyak stepsize [25] has been successfully used in the analysis of deterministic subgradient methods in different settings [5, 7, 18].”
The importance of better models in stochastic optimization (2019, neutral): “In this case, an integration argument [9] guarantees that 〈F ′(x), x− x〉 ≥ λ ‖x− x‖2 ‖x+ x ‖2 − ρ 2 ‖x− x‖22 .”
Stochastic model-based minimization of weakly convex functions (2018, methodology): “and exact penalty formulations of nonlinear programs [14, Section 17.2] are classical examples, while notable contemporary instances include robust phase retrieval [6,9], covariance matrix estimation [3,5], and matrix factorization problems such as NMF [11,12]. The subgradient and the prox-linear me”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “In the deterministic setting Polyak’s results have been been successfully extended and used for solving weakly convex and smooth problems (Boyd et al., 2003; Davis et al., 2018; Hazan & Kakade, 2019).”