Semi-stochastic coordinate descent

By Jakub Konecný, Zheng Qu, Peter Richtárik. 2014

94 citations recorded by the source corpus.

We propose 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: . 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 and a random coordinate j—both using non-uniform distributions—and update a single coordinate of the decision vector only, based on the computation of the jth partial derivative of 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 computational complexity of the method is the sum of two terms: evaluations of gradients and evaluations of partial derivatives , where is a novel condition number.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Minimizing finite sums with the stochastic average gradient (2013, background): “Konečnỳ et al. [2014] recently proposed an SVRG algorithm of this flavour.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Although these works highlight some interesting theoretical properties, the algorithms do not seem to be practical at the moment; more work is needed in this area.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “127] SGD O(Cgrad=) [196, 162] CD O(nCpdlog(1=)) [129, 148] SDCA O((n+ )Cgradlog(1=)) [163, 201, 143] SVRG/S2GD O((nCgrad+ Cgrad)log(1=)) [80, 187, 89] S2CD O((nCgrad+ ^Cpd)log(1=)) this work [84] Table 3.1: Runtime complexity of various algorithms. We use Cgradto denote the the evaluation cost of th”
Federated Learning over Wireless Networks: Optimization Model Design and Analysis (2019, background): “Denote the time of one local iteration by Tcmp, then the computation time in one global iteration is v log(1/θ)Tcmp for some positive constant v that depends on the data size and condition number of the local problem [10].”
Adaptive Sampling for SGD by Exploiting Side Information (2016, methodology): “, 2013), (Konečnỳ & Richtárik, 2013; Defazio et al., 2014; Johnson & Zhang, 2013; Konečnỳ et al., 2014) where the descent direction uses some momentum from past gradients.”
Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses (2015, methodology): “eas can lead to algorithms which are far superior to SGD in both theory and practice. The methods that belong to this category include SAG [2], SDCA [3], SVRG [4], S2GD [5], mS2GD [6], SAGA [7], S2CD [8], QUARTZ [9], ASDCA [10], prox-SDCA [11], IPROX-SDCA [12], A-PROX-SDCA [13], AdaSDCA [14], SDNA [”
Importance Sampling for Minibatches (2016, background): “In terms of theory, as in the case of minibatching, this strategy leads to the improvement of the leading constant in the complexity estimate, typically via replacing the maximum of certain data-dependent quantities by their average [24, 12, 40, 23, 19, 2, 3].”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, methodology): “These include primal methods such as SAG (Schmidt et al., 2013), SVRG (Johnson & Zhang, 2013), S2GD (Konečný & Richtárik, 2014), SAGA (Defazio et al., 2014), mS2GD (Konečný et al., 2014a) and MISO (Mairal, 2014).”
Coordinate Descent Face-Off: Primal or Dual? (2016, methodology): “Recently, a variety of novel primal methods for ERM have been designed, including SAG [21], SVRG [5], S2GD [8], proxSVRG [25], mS2GD [6], SAGA [2], MISO [10] and S2CD [7].”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, background): “Keywords: coordinate descent; accelerated coordinate descent; arbitrary sampling; complexity analysis”
A Crowdsourcing Framework for On-Device Federated Learning (2019, background): “where γk > 0 is a parameter choice of client k that depends on the data size and condition number of the local subproblem [42].”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, unknown): “…& Richtárik, 2014), proxSVRG (Xiao & Zhang, 2014), MISO (Mairal, 2014), SAGA (Defazio et al., 2014), minibatch S2GD (Konečný et al., 2014a), S2CD (Konečný et al., 2014b), and iii) variants of stochastic dual coordinate ascent (Shalev-Shwartz & Zhang, 2013d; Zhao & Zhang, 2014; Takáč…”