2024/06/27 by Yue Xie, Xie, Yue, Jiawen Bi +3
Computer Science · Engineering · Mathematics · #90C06 #90C15 #90C26 #90C30 #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2406.19475
openalex publication_date 2024/06/27 · openalex created_date 2024/07/02 · openalex updated_date 2026/07/28
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.