Optimization methods & software · 2016 · 76 citations · 40 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationConvex AnalysisConvex OptimizationLinear ProgrammingNonlinear ProgrammingOptimization For Machine LearningRandomized ComplexityComplexity AnalysisCoordinate DescentGradient DescentRandomized OptimizationSample ComplexitySample Complexity AnalysisStochastic Convex OptimizationStochastic Gradient Descent
We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a very flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent—both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.
40
Robust Stochastic Approximation Approach to Stochastic Programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan et al. · SIAM Journal on Optimization · 2009 · 2.1K citations
Pegasos: primal estimated sub-gradient solver for SVM
Shai Shalev‐Shwartz, Yoram Singer, Nathan Srebro et al. · Mathematical Programming · 2010 · 1.5K citations
Stephen J. Wright · Mathematical Programming · 2015 · 1.4K citations