Introductory Lectures on Convex Optimization

By Y. Nesterov, I. Nesterov. 2003

935 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, 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 Theory and Mathematics

In Mathematical Optimization

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, positive): “Moreover, for convex F ( y , ξ ) Assumption 1a implies Assumption 1b (Nesterov, 2004).”
Privacy Amplification by Iteration (2018, positive): “The following is a standard result in convex optimization [37].”
Hyperparameter optimization with approximate gradient (2016, positive): “This implies the following inequality for any pair of values α, β ∈ D : This is a classical result on quadratic upper bounds for L -smooth functions (see e.g. (Nesterov, 2004, Lemma 1.2.3)).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, neutral): “A trivial benchmark for solving problems of structure (1) is Gradient Descent (GD) in the case when functions fi are smooth (or Subgradient Descent for non-smooth functions) [69].”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “3 in Nesterov [Nes04]) yields the upper bound ψ∗ α(z + g) ≤ ψ∗ α(z) + 〈g,∇ψ∗ α(z)〉 + 1 2 α ‖g‖2∗ .”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “Here, the performance of SGD depends on the second moment The precise iteration complexity depends on whether the objective is strongly convex or whether x ⋆ is bounded, but in either case depends linearly on G 2 (see e.g. [32, 43]).”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, neutral): “Finally, we remark that although there are well-understood lower bounds on the number of iterations required to achieve an ǫ -optimal solution in the context of centralized convex optimization [31], [95], much less is understood about the fundamental limits of distributed optimization.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, neutral): “The best condition number of a function is when its level sets are spherical; the analog in term of the constraint sets is actually the regular simplex, which has the maximum width-to-diameter ratio amongst all simplices [see Corollary 1 in 2].”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, neutral): “We use the same notations than the proof of Theorem 1, and the same proof principle: (a) splitting the contributions of the initial conditions and the noise, (b) providing a direct argument for the initial condition, and (c) performing an expansion for the noise contribution.”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, positive): “We believe that the algorithm can be modified to remove the large sample condition T ≥ 2L/μ, that the convergence proof can be extended to the proximal setting, and that it is possible to use acceleration techniques in the sense of Nesterov [44].”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, positive): “t stays away from the problematic points allows us to show that ‘(w) has a Lipschitz continuous gradient on the line between w t and w t+1, with constant L= O~(1).9 By standard optimization analysis (Nesterov, 2004) it follows that after T = O( 1 2 ) iterations we will have krl(w t)kO() for some 0 t”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, positive): “The forward-backward algorithm may be accelerated by a simple extrapolation step, similar to Nesterov’s acceleration for convex minimization [21].”
Scalable Semi-Supervised Learning by Efficient Anchor Graph Regularization (2016, methodology): “algorithm named local anchor embedding, which employs Nesterovs method [28] to accelerate the gradient descent.”
Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials (2010, neutral): “…in Log-Linear Models: Beyond Pairwise Potentials The SPG algorithm may be useful for other problems with overlapping group 1 -regularization, while Dykstra's algorithm could alternately be used within the optimal method of Nesterov (2003) or projected quasi- Newton methods (Schmidt et al., 2009).”
Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results (2011, neutral): “…stronger assumptions on the objective than in the global convergence results, we obtain an upper bound on the total number of iterations the ARC algorithm takes to drive the norm of the gradient of f below ǫ that is of order ǫ − 2 , which is the same as for the steepest descent method [23, p.29].”