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

arXiv: https://arxiv.org/abs/2406.19475 · HTML: https://mlsanity.com/paper/2406.19475/

## Key facts

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

## Builds on (most cited first, 18 of 18)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018)
- [Convergence of Stochastic Proximal Gradient Algorithm](https://mlsanity.com/paper/1403.5074/) (2014)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2002.05359/) (2020)
- [Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization](https://mlsanity.com/paper/1901.08369/) (2019)

## 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.