Introduction to optimization

By B. T. Poli︠a︡k. 1987

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

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “1 The Polyak step-size Before explaining the proposed stochastic Polyak step-size, we first present the deterministic variant by Polyak (Polyak, 1987).”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “oint iterations. Seeing optimization algorithms as the repeated applicationof someoperatorallows us to deducetheirconvergencepropertiesfromspectrumofthis operator. This point of view was presented in Polyak (1987); Bertsekas (1999) and recently used in Arjevani et al. (2016); Mescheder et al. (2017)”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “that will be less than one and uand vwill actually shrink closer to one another. The majority of the following results can be found in several textbooks and monographs. Notable references are Polyak [34] and Nesterov [30]. We include proofs in the appendix for completeness. Lemma 3.7. Assume that fi”
Optimal Distributed Online Prediction Using Mini-Batches (2010, methodology): “many diﬀerent parameter setting, during the initial stage when we tuned the parameters on a held-out set. Similar transient behaviors also exist for multi-step stochastic gradient methods (see, e.g., Polyak, 1987, Section 4.3.2), where the multi-step interpolation of the gradients also gives the smo”
Distributed delayed stochastic optimization (2011, background): “Classical stochastic gradient algorithms [18, 16] iteratively update a parameter x(t) ∈ X by sampling ξ ∼ P , computing g(t) = ∇F (x(t); ξ), and performing the update x(t + 1) = ΠX (x(t) − α(t)g(t)), where ΠX denotes projection onto the set X and α(t) ∈ R is a stepsize.”
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization (2008, neutral): “2, [37]).”
Coordinate descent algorithms (2015, methodology): “e of step | the search direction combines new gradient information with the previous search direction | these methods are also related to such other classical techniques as the heavy-ball method (see [43]) and conjugate gradient methods. Nesterov [37, Theorem 6] proves the following convergence resu”
Distributed optimization over time-varying directed graphs (2013, neutral): “t step will be to establish two lemmas pertaining to the convergence of a scalar sequence. The ﬁrst is a deterministic counterpart of the well-known supermartingale convergence result ([26]; see also [21], Lemma 11, Chapter 2.2). Lemma 11 Let {vt} be a non-negative scalar sequence such that vt+1 ≤ (”
Learning in games with continuous action sets and unknown payoff functions (2016, methodology): “. At the other end of the spectrum, if players only have access to their realized, ingame payoﬀs, they would need to reconstruct their individual payoﬀ gradients via a suitable single-shot estimator (Polyak, 1987; Flaxman et al., 2005). We believe our convergence analysis can be extended to this cas”
First-order methods of smooth convex optimization with inexact oracle (2013, unknown): “[21, 20, 2, 10] for subgradient methods, and [2, 7, 8] for proximal point and bundle methods).”
On stochastic gradient and subgradient methods with adaptive steplength sequences (2011, methodology): “[2], [3], [4], [5], [16], [40], [14], [17], [15]), the almost-sure convergence of such methods is guaranteed assuming that the stepsize is diminishing but not too rapidly, i.”
Error Bounds: Necessary and Sufficient Conditions (2010, background): “The concept of weak sharp minima [7–9,46,49], very important in numerics, can be considered as another interpretation of the error bound property.”
Optimization of Convex Functions with Random Pursuit (2011, background): “Polyak [28] describes step size rules for the closely related randomized gradient descent scheme:”
Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming (2006, background): “7) happen to be useful to derive efficient necessary conditions for sharp minimizers in the sense of Polyak [9] and in some other settings.”
On Perturbed Proximal Gradient Algorithms (2014, methodology): “ study the behavior of the sequence the perturbed proximal gradient algorithm is the following elementary lemma which might be seen as a deterministic version of the Robbins-Siegmund lemma (see e.g. (Polyak, 1987, Lemma 11, Chapter 2)). It replaces in our analysis (Combettes, 2001, Lemma 3.1) for qu”