Stochastic model-based minimization of weakly convex functions

By Damek Davis, Dmitriy Drusvyatskiy. 2018

473 citations recorded by the source corpus.

We consider an algorithm that successively samples and minimizes stochastic models of the objective function. We show that under weak-convexity and Lipschitz conditions, the algorithm drives the expected norm of the gradient of the Moreau envelope to zero at the rate $O(k^{-1/4})$. Our result yields new complexity guarantees for the stochastic proximal point algorithm on weakly convex problems and for the stochastic prox-linear algorithm for minimizing compositions of convex functions with smooth maps. Moreover, our result also recovers the recently obtained complexity estimate for the stochastic proximal subgradient method on weakly convex problems.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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 Numerical Analysis

Citations in the corpus

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “An alternative is to use stochastic proximal-point-type updates [10, 46, 44, 15, 24], which update Transmission of privatized updates After completing the local update to θ i , we deﬁne the local diﬀerence ∆ i = θ i − θ and transmit this to the aggregator using a separated mechanism (Deﬁnition 2.2).”
The importance of better models in stochastic optimization (2019, positive): “Adopting the techniques Davis and Drusvyatskiy (5) pioneer for weakly convex problems, we rely on the Moreau envelope’s connections to (near) stationarity:”
A Sufficient Condition for Convergences of Adam and RMSProp (2018, background): “(1)The gradient Lipschtiz continuity of f could be possibly weaken to weakly convexity as [8], i.”
Square Attack: a query-efficient black-box adversarial attack via random search (2019, background): “4 Nonconvex constrained optimization under noisy oracles is notoriously harder [22].”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Instead of considering a min-max problem, most of them contribute to the non-convex minimization problem [29, 70, 30, 63, 61, 44, 1, 2, 25, 24, 72, 24].”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, unknown): “ Section5, we present representative non-asymptotic convergence guarantees. Any aProx method (4) recovers standard convergence guarantees of stochastic gradient and proximal point methods [42,7] (see [14] for the basic convergence guarantee). We show how stochastic proximal point methods enjoy fast ”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, unknown): “of updates, which include projected stochastic gradient as a special case, known as the aProx (approximate proximal point) family [5,6]; several authors present convergence analyses for these methods [21,15,6,5]. These methods iteratively build a model of the loss at the current iterate and minimize”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, background): “Since the objective function is non-convex and not necessarily smooth, they consider a convergence measure for weakly convex function, i.e., nearly stationary solution [34].”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “An alternative criterion based on the Moreau envelope of Φ has been recognized as standard when Φ is weakly convex [10].”