2020/03/30 by Andrei Pătraşcu, Patrascu, Andrei, Ciprian Păduraru +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2003.13332
openalex publication_date 2020/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Stochastic optimization lies at the core of most statistical learning models.\nThe recent great development of stochastic algorithmic tools focused\nsignificantly onto proximal gradient iterations, in order to find an efficient\napproach for nonsmooth (composite) population risk functions. The complexity of\nfinding optimal predictors by minimizing regularized risk is largely understood\nfor simple regularizations such as \ℓ1/\ℓ2 norms. However, more complex\nproperties desired for the predictor necessitates highly difficult regularizers\nas used in grouped lasso or graph trend filtering. In this chapter we develop\nand analyze minibatch variants of stochastic proximal gradient algorithm for\ngeneral composite objective functions with stochastic nonsmooth components. We\nprovide iteration complexity for constant and variable stepsize policies\nobtaining that, for minibatch size N, after\n\O(\(1)/(N\ε)) iterations \ε-suboptimality is\nattained in expected quadratic distance to optimal solution. The numerical\ntests on \ℓ2-regularized SVMs and parametric sparse representation\nproblems confirm the theoretical behaviour and surpasses minibatch SGD\nperformance.\n