2019/01/22 by Lam M. Nguyen, Nguyen, Lam M., Marten van Dijk +9
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1901.07648
openalex publication_date 2019/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The total complexity (measured as the total number of gradient computations) of a stochastic first-order optimization algorithm that finds a first-order stationary point of a finite-sum smooth nonconvex objective function F(w)=(1)/(n) ∑i=1n fi(w) has been proven to be at least Ω(√(n)/ε) for n ≤ O(ε-2) where ε denotes the attained accuracy 𝔼[ ‖∇ F(w)‖2] ≤ ε for the outputted approximation w (Fang et al., 2018). In this paper, we provide a convergence analysis for a slightly modified version of the SARAH algorithm (Nguyen et al., 2017a;b) and achieve total complexity that matches the lower-bound worst case complexity in (Fang et al., 2018) up to a constant factor when n ≤ O(ε-2) for nonconvex problems. For convex optimization, we propose SARAH++ with sublinear convergence for general convex and linear convergence for strongly convex problems; and we provide a practical version for which numerical experiments on various datasets show an improved performance.