Semi-stochastic coordinate descent

DOI10.1080/10556788.2017.1298596MaRDI QIDQ4594842zbMATH OpenOpenAlexFDO

Authors Jakub Konečný, Zheng Qu, Peter Richtárik

Publication date 24 November 2017

Published in Optimization Methods \& Software (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1412.6293

zbMATH Keywords

coordinate descentempirical risk minimizationstochastic gradient

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Stochastic programming (90C15)

Abstract: We propose a novel stochastic gradient method---semi-stochastic coordinate descent (S2CD)---for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: $f(x)=frac1nsu{m}_i{f}_i(x)$. Our method first performs a deterministic step (computation of the gradient of $f$ at the starting point), followed by a large number of stochastic steps. The process is repeated a few times, with the last stochastic iterate becoming the new starting point where the deterministic step is taken. The novelty of our method is in how the stochastic steps are performed. In each such step, we pick a random function $f_i$ and a random coordinate $j$---both using nonuniform distributions---and update a single coordinate of the decision vector only, based on the computation of the $j^{th}$ partial derivative of $f_i$ at two different points. Each random step of the method constitutes an unbiased estimate of the gradient of $f$ and moreover, the squared norm of the steps goes to zero in expectation, meaning that the stochastic estimate of the gradient progressively improves. The complexity of the method is the sum of two terms: $O(nlog(1/epsilon))$ evaluations of gradients $abla{f}_i$ and $O(hatkappalog(1/epsilon))$ evaluations of partial derivatives $abl{a}_j{f}_i$, where $hatkappa$ is a novel condition number.

Recommendations

• Efficiency of coordinate descent methods on huge-scale optimization problems
• Minimizing finite sums with the stochastic average gradient
• Accelerated, parallel, and proximal coordinate descent
• Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
• A flexible coordinate descent method

Cited in

(21)

• Projected semi-stochastic gradient descent method with mini-batch scheme under weak strong convexity assumption
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Non-stationary grid generation algorithm for deformed volumes of revolution
• Proximal average approximated incremental gradient descent for composite penalty regularized empirical risk minimization
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods
• On optimal probabilities in stochastic coordinate descent methods
• scientific article; zbMATH DE number 6982318 (Why is no real title available?)
• Online learning in optical tomography: a stochastic approach
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Multilevel stochastic gradient methods for nested composition optimization
• A Stochastic Proximal Alternating Minimization for Nonsmooth and Nonconvex Optimization
• Adaptivity of stochastic gradient methods for nonconvex optimization
• Stochastic reformulations of linear systems: algorithms and convergence theory
• Minimizing finite sums with the stochastic average gradient
• Stochastic sub-sampled Newton method with variance reduction
• Inexact SARAH algorithm for stochastic optimization
• A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
• An aggressive reduction on the complexity of optimization for non-strongly convex objectives
• An overview of stochastic quasi-Newton methods for large-scale machine learning
• Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: application to stochastic coordinate descent

This page was built for publication: Semi-stochastic coordinate descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594842)