First-order methods of smooth convex optimization with inexact oracle

By Olivier Devolder, François Glineur, Yurii E. Nesterov. 2013

588 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “In addition to concerns of communication efficiency, because compression operators satisfying Assumption 3 are not all necessarily quantization operators, our method (in the n = 1 case) can also be seen as an analysis of fixed point methods with perturbed iterates in a similar spirit to [13], who an”
Fast Distributed Gradient Methods (2011, methodology): “Lemma 2 is similar to [[33], Theorem 5], although [33] considers a different accelerated Nesterov method.”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “Accelerated first-order methods are also known to be sensitive to inexact gradients when the gradient errors are deterministic (possibly adversarial) and bounded (d’Aspremont, 2008; Devolder et al., 2014).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In the area of deterministic algorithms, the inexact variant of the full gradient descent method, x = x −ωk[∇f(x) + ], has received a lot of attention [174, 39, 180, 59, 128].”
Accelerated Distributed Nesterov Gradient Descent (2017, methodology): “Remark 4: It is well-known Nesterov Gradient method is prone to accumulating noise and divergence [39], [40].”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “In the area of deterministic algorithms, the inexact variant of the full gradient descent method, xk+1 = xk−ωk[∇f(xk)+ k], has received a lot of attention [49, 11, 51, 16, 32].”
Distributed stochastic optimization for deep learning (thesis) (2016, unknown): “One reason is that the momentum method has an error accumulation effect [18].”
Universal gradient methods for convex optimization problems (2015, unknown): “31.0073.”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “show that in a setting where there are inexact values, an accelerated method will accumulate errors over the iterations [22], and “slow” algorithms may have better performance.”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, methodology): “We will build on the results in [18, 19] on the analysis of first-order methods with inexact oracle, and provide a set of distributed algorithms and their respective iterations complexities.”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, methodology): “, The ideas used in the proof can be found in the proofs of [17, Lemma 5.7], [40 Lemma 2], and in [18, Section 2.3].”
On Acceleration with Noise-Corrupted Gradients (2018, methodology): “More recently, (Devolder et al., 2014) proposed a more general framework that allows for larger perturbations and seems to capture the error accumulation and instability observed in practice for accelerated methods.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, methodology): “ achieve low-training error [34,38]. However, it is not clear that momentum adds stability. Indeed, in the case of convex optimization, momentum methods are less robust to noise than gradient methods [7,23]. Thus, it is possible that momentum speeds up training but adversely impacts generalization. ”
Convergence rate analysis of distributed gradient methods for smooth optimization (2012, background): “The Lemma easily follows from Theorem 2 and the result in equation (33) in [9].”
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (2016, background): “ optimal if the number of iterations n is less than the dimension d of the underlying predictors, but the algorithm is not robust to random or deterministic noise in the gradients (d’Aspremont, 2008; Devolder et al., 2014). On the other hand, the optimal variance term is proportional to σ2d n (Tsyba”
Gradient Coding (2016, background): “While we do not present any empirical results, we refer the reader to Devolder et al. (2014) for a theoretical and empirical analysis of the effect of noisy gradients in NAG.”
Accelerating Stochastic Gradient Descent (2017, methodology): “Numerous works have attempted to quantify these instabilities in the face of either statistical or non-statistical errors (Paige, 1971; Proakis, 1974; Polyak, 1987; Greenbaum, 1989; Devolder et al., 2014).”