Smooth Optimization with Approximate Gradient

By Alexandre d'Aspremont. 2005

215 citations recorded by the source corpus.

We show that the optimal complexity of Nesterov's smooth first-order optimization algorithm is preserved when the gradient is computed only up to a small, uniformly bounded error. In applications of this method to semidefinite programs, this means in some instances computing only a few leading eigenvalues of the current iterate instead of a full matrix exponential, which significantly reduces the method's computational cost. This also allows sparse problems to be solved efficiently using sparse maximum eigenvalue packages.

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

Hyperparameter optimization with approximate gradient (2016, methodology): “The analysis of this algorithm is inspired by the work of d’Aspremont (2008); Schmidt et al.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, neutral): “The total runtime required by accelerated Prox-SDCA to guarantee an -accurate solution with probability of at least 1− δ is O ( d √ nR2 λ γ · log ( 1 δ ) · log ( R2 λ γ n ) ( log ( R2 λγn ) + log ( P (0)−D(0) ))) .”
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (2016, background): “This rate is achieved by accelerated gradient descent (Nesterov, 1983, 2004), and is known to be 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; Devo”
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).”
Optimal Primal-Dual Methods for a Class of Saddle Point Problems (2013, unknown): “, [38, 2, 26, 10, 42, 51, 4, 25]).”
A Closer Look at Deep Policy Gradients (2018, result): “While these results might be reminiscent of the well-studied “noisy gradients” problem in supervised learning (Robbins & Monro, 1951; d’Aspremont, 2008; Kawaguchi, 2016; Safran & Shamir, 2018; Livni et al., 2014; Keskar et al., 2016; Hochreiter & Schmidhuber, 1997), we have very little…”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, result): “, 2013), and need higher accuracy of the gradients to perform well (d’Aspremont, 2008; Devolder et al., 2014) compared to standard methods like GD.”
Primal-dual first-order methods with O (1/e) iteration-complexity for cone programming. (2011, unknown): “[8], Nesterov [12] and d’Aspremont [4]).”
An optimal method for stochastic composite optimization (2011, methodology): “These first-order methods were further studied in, for example, [1,8,26,28,37,38,50], and successfully used in sparse covariance selection, rank reduction in multivariate linear regression and compressed sensing, etc.”
Accelerating Stochastic Gradient Descent (2017, methodology): “In essence, this paper presents the first known provable analysis of the claim that fast gradient methods are stable when dealing with statistical errors, in contrast to negative results in statistical and non-statistical settings (Paige, 1971; Proakis, 1974; Polyak, 1987; Greenbaum, 1989; Roy and S”
First-order methods of smooth convex optimization with inexact oracle (2013, methodology): “Fast gradient methods using inexact ﬁrst-order oracle have been recently studied in [1] and [3].”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, background): “[7, 26, 33]), the idea of exploiting this for balancing the computational cost is novel.”
Convex Optimization: Algorithms and Complexity (2014, methodology): “We describe below the SVRG (Stochastic Variance Reduced Gradient descent) algorithm from Johnson and Zhang [2013] which makes the main ideas of SAG and SDCA more transparent (see also Defazio et al. [2014] for more on the relation between these different methods).”