mlsanityData to 7 Oct 2026

Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization

arXiv 2406.19475 ↗First posted 27 Jun 2024math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

When the nonconvex problem is complicated by stochasticity, the sample complexity of stochastic first-order methods may depend linearly on the problem dimension, which is undesirable for large-scale problems. In this work, we propose dimension-insensitive stochastic first-order methods (DISFOMs) to address nonconvex optimization with expected-valued objective function. Our algorithms allow for non-Euclidean and non-smooth distance functions as the proximal terms. Under mild assumptions, we show that DISFOM using minibatches to estimate the gradient enjoys sample complexity of O ( (log d) / ε4 ) to obtain an ε-stationary point. Furthermore, we prove that DISFOM employing variance reduction can sharpen this bound to O ( (log d)2/3/ε10/3 ), which perhaps leads to the best-known sample complexity result in terms of d. We provide two choices of the non-smooth distance functions, both of which allow for closed-form solutions to the proximal step. Numerical experiments are conducted to illustrate the dimension insensitive property of the proposed frameworks.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 35 references that are in the map. First posted on arXiv 27 Jun 2024.

Builds on

18 of 35 references.

References · 18

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  3. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  4. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  5. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  6. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  7. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  8. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  9. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  10. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 37
  11. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  12. 2017Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applicationscited by 29
6 more
  1. 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
  2. 2018On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimizationcited by 18
  3. 2014Convergence of Stochastic Proximal Gradient Algorithmcited by 17
  4. 2018Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergencecited by 16
  5. 2020Adaptivity of Stochastic Gradient Methods for Nonconvex Optimizationcited by 16
  6. 2019Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimizationcited by 3

Built on by

Not cited yet.