2022/11/03 by Ali Kavis, Stratis Skoulakis, Kavis, Ali +7 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2211.01851
openalex publication_date 2022/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fairly distinct, adaptive step-size schedule with the recursive stochastic path integrated estimator proposed in [Fang et al., 2018]. To our knowledge, Adaspider is the first parameter-free non-convex variance-reduction method in the sense that it does not require the knowledge of problem-dependent parameters, such as smoothness constant L, target accuracy ε or any bound on gradient norms. In doing so, we are able to compute an ε-stationary point with O(n + √(n)/ε2) oracle-calls, which matches the respective lower bound up to logarithmic factors.