Gradient methods for minimizing composite objective function

By Yurii E. Nesterov. 2007

1,290 citations recorded by the source corpus.

Subfields: 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 Optimization & Training

In Mathematical Optimization

Citations in the corpus

Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification (2019, methodology): “In experiments, we use Nesterov accelerated gradient [Nesterov, 2007] with momentum β ∈ { 0 , 0 .”
Differentially Private Distributed Optimization (2014, methodology): “We study iterative distributed algorithms for solving this problem in which agents exchange information about their current estimates for the optimal point and then update their estimates based on the information received from their neighbors.”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “In practice, these methods are augmented with some form of momentum or acceleration [20, 18] that results in faster empirical convergence [28].”
Generalized Sparse Additive Models (2019, methodology): “(cid:28) The algorithm can also take advantage of Nesterov-style acceleration [Nesterov, 2007], which improves the worst-case convergence rate after k steps from An important special case is the least squares loss − ( y, θ ) = ( y − θ ) 2 .”
Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, methodology): “3 Comparison with Nesterov’s Accelerated Gradient Method Ji and Ye (2009) proposed a first-order algorithm based on Nesterov’s acceleration scheme (Nesterov, 2007), for nuclear norm minimization for a generic multi-task learning problem (Argyriou et al.”
On the Convergence of Decentralized Gradient Descent (2013, background): “From the classic analysis of gradient descent iteration in [1] and [21], [x(i)(k)], and hence x(i)(k), will converge to a certain point when α ≤ (1 + λn(W ))/Lh.”
A reliable effective terascale linear learning system (2011, neutral): “hybrid approach is at most T hybrid = 1 + O c0 log 1 log n ; (7) for some c0. For instance, gradient descent guarantees c0 = and Nesterov’s accelerated gradient method gives c0= O( p ) (Nesterov, 2007). For the L-BFGS method, the constant c0depends on the type of line search used (Liu and Noce”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “Then, f admits the following majorizing surrogate in S 2 L ( f, κ ), or in S 2 L,L ( f, κ ) when f 2 is convex: The approximation error g − f is indeed the same as in Section 2.3.1 and thus, Minimizing g amounts to performing one step of the proximal gradient algorithm [3, 40, 48].”
Optimization with Sparsity-Inducing Penalties (2011, background): “, with rates in O(Ct) for some constant C < 1; see [89]).”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “Following Nesterov [17], we apply a “smoothing” technique.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Acc-Prox-SVRG incorporates both mini-batch scheme and Nesterov’s acceleration method [27], [28]; however, the author claims that when b < db0e, with the threshold b0 defined as 8 √ κn √ 2p(n−1)+8 √ κ , the overall complexity is O (( n+ n− b n− 1 κ ) log(1/ ) ) ;”
Accelerated Mini-Batch Stochastic Dual Coordinate Ascent (2013, methodology): “In particular, Nesterov [2007] proposed an accelerated gradient descent (AGD) method for solving (1).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “6 Comparison with Acc-Prox-SVRG The Acc-Prox-SVRG [132] method of Nitanda, which was not available online before the first version of this work appeared on arXiv, incorporates both a mini-batch scheme and Nesterov’s acceleration [127, 128].”
Online Learning for Matrix Factorization and Sparse Coding (2009, positive): “For instance, it allows us to use the fast algorithm of Nesterov (2007) for solving the more general fused lasso problem (Tibshirani et al., 2005).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “Furthermore, it is possible to guarantee convergence rates for the function values [172, 20], and after t iterations, the precision be shown to be of order O(1/t), which should contrasted with rates for the subgradient case, that are rather O(1/ √ t).”