On Tackling High-Dimensional Nonconvex Stochastic Optimization via Stochastic First-Order Methods with Non-smooth Proximal Terms and Variance Reduction

2025/09/17 by Yue Xie, Xie, Yue, Jiawen Bi +3 · 1 citation
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Gaussian Processes and Bayesian Inference #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2509.13992

Abstract

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. To alleviate this linear dependence, we adopt non-Euclidean settings and propose two choices of non-smooth proximal terms when taking the stochastic gradient steps. This approach leads to stronger convergence metric, incremental computational overhead, and potentially dimension-insensitive sample complexity. We also consider further acceleration through variance reduction which achieves near optimal sample complexity and, to our best knowledge, is the first such result in the ℓ₁/ℓ_∞ setting. Since the use of non-smooth proximal terms is unconventional, the convergence analysis deviates much from algorithms in Euclidean settings or employing Bregman divergence, providing tools for analyzing other non-Euclidean choices of distance functions. Efficient resolution of the subproblems in various scenarios is also discussed and simulated. We illustrate the dimension-insensitive property of the proposed methods via preliminary numerical experiments.

Citations

• PolarGrad: A Class of Matrix-Gradient Optimizers from a Unifying Preconditioning Perspective
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence
• Accelerated stochastic approximation with state-dependent noise
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization
• Lower Bounds for Non-Convex Stochastic Optimization
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Stochastic model-based minimization of weakly convex functions
• Stochastic subgradient method converges at the rate O(k^-1/4) on weakly convex functions
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
• Adam: A Method for Stochastic Optimization
• Convergence of Stochastic Proximal Gradient Algorithm
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging
• Acceleration of Stochastic Approximation by Averaging
• A Stochastic Approximation Method

Cited by

• Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential

Related

• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization
• Stochastic Variance Reduction for Nonconvex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization