Semi-stochastic coordinate descent

Summary

A novel stochastic gradient method—semi-stochastic coordinate descent—for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: .

Keywords

Mathematics, Nabla symbol, Combinatorics, Regular polygon, Stochastic gradient descent

References

Semi-Stochastic Gradient Descent MethodsJakub Konečný, Peter Richtárik — 2013
S2CD: Semi-stochastic coordinate descentJakub Konečný, Zheng Qu, Peter Richtárik — 2014
Minimizing finite sums with the stochastic average gradientMark Schmidt, Nicolas Le Roux, Francis Bach — 2013
Randomized Dual Coordinate Ascent with Arbitrary SamplingZheng Qu, Peter Richtárik, Tong Zhang — 2014
Accelerated, Parallel, and Proximal Coordinate DescentOlivier Fercoq, Peter Richtárik — 2013
Fast distributed coordinate descent for non-strongly convex lossesOlivier Fercoq, Zheng Qu, Peter Richtárik — 2014
Robust Stochastic Approximation Approach to Stochastic ProgrammingArkadi Nemirovski, Anatoli Juditsky, Guanghui Lan — 2008
A Stochastic Approximation MethodHerbert Robbins, Sutton Monro — 1951
Parallel coordinate descent methods for big data optimizationPeter Richtárik, Martin Takáč — 2012
A Proximal Stochastic Gradient Method with Progressive Variance ReductionLin Xiao, Tong Zhang — 2014
Solving large scale linear prediction problems using stochastic gradient descent algorithmsTong Zhang — 2004
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization ProblemsYu. Nesterov — 2012
Accelerating Stochastic Gradient Descent using Predictive Variance ReductionRie Johnson, Tong Zhang — 2013
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionPeter Richtárik, Martin Takáč — 2011
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimizationShai Shalev‐Shwartz, Tong Zhang — 2013
Introductory Lectures on Convex Optimization - A Basic CourseYurii Nesterov — 2014
On optimal probabilities in stochastic coordinate descent methodsPeter Richtárik, Martin Takáč — 2013
Distributed Coordinate Descent Method for Learning with Big DataPeter Richtárik, Martin Takáč — 2013
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite ObjectivesAaron Defazio, Francis Bach, Simon Lacoste-Julien — 2014
Smooth minimization of nonsmooth functions with parallel coordinate descent methodsFercoq, Olivier, Richtárik, Peter — 2013

Cited by

Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex LossesDominik Csiba, Peter Richtárik — 2015
Minimizing finite sums with the stochastic average gradientMark Schmidt, Nicolas Le Roux, Francis Bach — 2013
Stochastic Dual Coordinate Ascent with Adaptive ProbabilitiesDominik Csiba, Zheng Qu, Peter Richtárik — 2015
SMART: The Stochastic Monotone Aggregated Root-Finding AlgorithmDamek Davis — 2016
Doubly Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization with Factorized DataAdams Wei Yu, Qihang Lin, Tianbao Yang — 2015
Doubly Stochastic Primal-Dual Coordinate Method for Empirical Risk Minimization and Bilinear Saddle-Point ProblemAdams Wei Yu, Qihang Lin, Tianbao Yang — 2015
Accelerated Stochastic Block Coordinate Descent with Optimal SamplingAston Zhang, Quanquan Gu — 2016
Adaptive Sampling for SGD by Exploiting Side InformationSiddharth Gopal — 2016
Federated Optimization: Distributed Machine Learning for On-Device IntelligenceJakub Konečný, H. Brendan McMahan, Daniel Ramage — 2016
Federated Learning: Strategies for Improving Communication EfficiencyJakub Konečný, H. Brendan McMahan, Felix X. Yu — 2016
Practical Efficiency of Asynchronous Stochastic Gradient DescentOnkar Bhardwaj, Guojing Cong — 2016
Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex OptimizationJinghui Chen, Quanquan Gu — 2016
Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point ProblemAdams Wei Yu, Qihang Lin, Tianbao Yang — 2015
Stochastic, Distributed and Federated Optimization for Machine LearningJakub Konečný — 2017
Inefficiency of stochastic gradient descent with larger mini-batches (and more learners)Onkar Bhardwaj, Guojing Cong — 2017
Online learning in optical tomography: a stochastic approachKe Chen, Qin Li, Jian-Guo Liu — 2017
Big Data techniques for Solar Power ForecastingRui Miguel da Cunha Nunes — 2017
Analyzing intentions from big data traces of human activitiesAston Zhang — 2017
Data sampling strategies in stochastic algorithms for empirical risk minimizationDominik Csiba — 2018
A Joint Row and Column Action Method for Cone-Beam Computed TomographyYushan Gao, Thomas Blumensath — 2018

Related papers

Accelerating Stochastic Gradient Descent using Predictive Variance ReductionRie Johnson, Tong Zhang — 2013
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionPeter Richtárik, Martin Takáč — 2011
A Proximal Stochastic Gradient Method with Progressive Variance ReductionLin Xiao, Tong Zhang — 2014
Semi-Stochastic Gradient Descent MethodsJakub Konečný, Peter Richtárik — 2013
Rates of convergence of semi-stochastic approximation procedures for solving stochastic optimization problems 1K. Marti, Erich Fuchs — 1986
Tight Analyses for Non-Smooth Stochastic Gradient DescentNicholas J. A. Harvey, Christopher Liaw, Yaniv Plan — 2018
Stochastic Nested Variance Reduced Gradient Descent for Nonconvex OptimizationDongruo Zhou, Pan Xu, Quanquan Gu — 2018
Stochastic Nested Variance Reduction for Nonconvex OptimizationDongruo Zhou, Pan Xu, Quanquan Gu — 2018
Introductory Lectures on Convex Optimization: A Basic CourseЮ Е Нестеров — 2014
On optimal probabilities in stochastic coordinate descent methodsPeter Richtárik, Martin Takáč — 2013