Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems

By Yurii E. Nesterov. 2012

1,532 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

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 Numerical Analysis

In Optimization & Training

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “The non-uniform sampling techniques used in the work of Nesterov (2012); Needell et al. (2014); Zhao & Zhang (2015) use Lipschitz constants of partial derivatives to obtain the sampling probabilities.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, background): “in machine learning, and also sparked new theoretical results such as (Nesterov, 2010).”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “Alternative methods have also been proposed in which, in each iteration, the index ik is chosen randomly with probabilities proportional to Li or according to the largest ratio |∇iF (wk)|/ √ Li [91, 109].”
Minimizing finite sums with the stochastic average gradient (2013, neutral): “Algorithm 1 Basic SAG method for minimizing 1n ∑n i=1 fi (x) with step size α. d = 0, yi = 0 for i = 1, 2, . . . , n for k = 0, 1, . . . do Sample i from {1, 2, . . . , n} d = d − yi + f ′i (x) yi = f ′i (x) x = x − αn d end for”
Federated Learning: Collaborative Machine Learning without Centralized Training Data (2022, neutral): “One of these is randomized coordinate descent (RCD) [18].”
A Theory of Multiple-Source Adaptation with Limited Target Labeled Data (2020, methodology): “It is known that the above algorithm converges to the global optimum (Nesterov, 2012).”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “simplicity and effectiveness, CD can be chosen over GD in such applications [19].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “The algorithm consists of three sequences (wk, ζk, vk) updated in each iteration [24].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “Although the idea of coordinate descent has been around for several decades in various contexts (and for quadratic functions dates back even much further, to works on the Gauss-Seidel methods), it came to prominence in machine learning and optimization with the work of Nesterov [67] which equipped t”
Stochastic dual coordinate ascent methods for regularized loss (2012, neutral): “In addition, [17], and later [12] have analyzed randomized versions of coordinate descent for unconstrained and constrained minimization of smooth convex functions.”
Evolution Strategies as a Scalable Alternative to Reinforcement Learning (2017, methodology): “Derivative free optimization methods have also been analyzed in the convex setting Duchi et al. [2015], Nesterov [2012].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “But importance sampling has also been considered in stochastic coordinate-descent methods [33, 40].”
Coordinate descent algorithms (2015, methodology): “The accelerated randomized algorithm, specified here as Algorithm 4, was proposed by Nesterov [37].”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “Such weighted sampling schemes have also been proposed for the Prox-SDCA method [35], as well as for coordinate descent methods [24, 26, 18].”