Gradient methods for minimizing composite functions

By Yurii E. Nesterov. 2012

1,559 citations recorded by the source corpus.

Subfields: Computational Mechanics, Mathematical Physics, Numerical Analysis, 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 Computational Mechanics

In Mathematical Physics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “In contrast to the above mentioned work, we first show that the strong growth condition (SGC) [32] implies that SGD with a constant step-size and Nesterov momentum [25] achieves the accelerated convergence rate of the deterministic setting for both strongly-convex and convex functions (Section 3).”
Convex-constrained Sparse Additive Modeling and Its Extensions (2017, methodology): “…permute 15 r← r− Z.j // add component back Since the proximal map Pηλd‖·‖tv can be computed in linear time using the algorithm in Davies & Kovac (2001), we can solve (15) hence Pλd‖·‖DCj (rj) iteratively using the accelerated proximal gradient algorithm (Beck & Teboulle, 2009; Nesterov, 2013).”
A Universal Catalyst for First-Order Optimization (2015, methodology): “Most of the algorithms we consider here, namely the proximal gr dient method [4, 19], SAGA [6], (Prox)-SVRG [27], can handle compo site objectives with a regularization penaltyψ that admits a proximal operator p oxψ, defined for anyz as proxψ(z) , argmin y∈Rp { ψ(y) + 1 2 ‖y − z‖(2) } .”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, background): “Suppose our distributed computing system consists of m machines, and each has access to n samples zi,1, . . . , zi,n, for i = 1, . . . ,m.”
DiSCO: Distributed Optimization for Self-Concordant Empirical Loss (2015, methodology): “For AFG, we used an adaptive line search scheme (Nesterov, 2013) to speed up its convergence.”
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints (2014, background): “This is to be expected because it is known that the proximal gradient and accelerated methods achieves the same worst-case convergence rates as their unconstrained counterparts [1, 25, 40].”
Accelerated Mirror Descent in Continuous and Discrete Time (2015, methodology): “Nesterov’s accelerated method [22] has been applied to many problems and extended in a number of ways, see for example [23, 20, 21, 4].”
A unified approach to error bounds for structured convex optimization problems (2015, background): “Moreover, the O (1 /k 2 ) convergence rate is optimal when the functions f and P are given by ﬁrst-order oracles [22].”
The Cyclic Block Conditional Gradient Method for Convex Optimization Problems (2015, background): “We focus on programs for which the geometry of the non-smooth part exhibits such a degree of complexity that proximal-based methods [5, 6, 24] do not constitute a viable alternative.”