Introduction to Optimization
By Xin-She Yang, J. Kiusalaas, Xing He. 2015
2,855 citations recorded by the source corpus.
Plain gradient descent (2:1) Stepsize and step direction as core issues (2:2) Stepsize adaptation (2:4) Backtracking (2:5) Line search (2:5) Wolfe conditions (2:7) Gradient descent convergence (2:8) Steepest descent direction (2:11) Covariant gradient descent (2:13) Newton direction (2:14) Newton method (2:15) Gauss-Newton method (2:20) Quasi-Newton methods (2:23) Broyden-Fletcher-Goldfarb-Shanno (BFGS) (2:25) Conjugate gradient (2:28) Rprop (2:35)
Subfields: Numerical Analysis, Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Numerical Analysis
- Nicolas Loizou
- Peter Richtárik
- Simon Lacoste-Julien
- Issam Hadj Laradji
- Sebastian U. Stich
- Ernö Robert Csetnek
- Sharan Vaswani
- Jakub Konecný
In Optimization & Training
- Nicolas Loizou
- Peter Richtárik
- Simon Lacoste-Julien
- Sebastian U. Stich
- Jakub Konecný
- Martin Jaggi
- Francis R. Bach
- Sashank J. Reddi
Citations in the corpus
- Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “The classical Polyak stepsize [25] has been successfully used in the analysis of deterministic subgradient methods in different settings [5, 7, 18].”
- Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “An analysis of several stochastic optimization methods under the assumption of PL condition (Polyak, 1987) was recently proposed in Karimi et al. (2016).”
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “We first focus on a special class of non-convex functions that satisfy the Polyak-Lojasiewicz (PL) condition (Polyak, 1987).”
- A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “This point of view was presented in Polyak (1987); Bertsekas (1999) and recently used in Arjevani et al. (2016); Mescheder et al. (2017); Gidel et al. (2019b) for instance.”
- Counterfactual Normalization: Proactively Addressing Dataset Shift and Improving Reliability Using Causal Mechanisms (2018, methodology): “We first fit the structural equation for Y using maximum likelihood estimation, optimized using BFGS (Chong and Zak, 2013).”
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “To the best of our knowledge, no convergence analysis of mRK exists in the literature (Polyak’s momentum).”
- Vision-Based Pose Estimation From Points With Unknown Correspondences (2014, methodology): “The comparison results of run time of SI, SoftSI, SoftPOSIT and some PnP methods (POSIT [2], OI [4], LM [10]) are shown in Fig.”
- A strong convergence result involving an inertial forward–backward algorithm for monotone inclusions (2017, methodology): “In [4], Alvarez and Attouch translated the idea of the heavy ball method in [51,52] to the setting of a general maximal monotone operator using the framework of the proximal point algorithm.”
- Convergence results of two-step inertial proximal point algorithm (2022, background): “Polyak [46] also discussed that the multi-step inertial methods can boost the speed of optimization methods even though neither the convergence nor the rate result of such multi-step inertial methods is established in [46].”
- L4: Practical loss-based stepsize adaptation for deep learning (2018, result): “ion for line search is, of course, not novel, as witnessed for example by the Armijo-Wolfe line search [16]. Also, and more notably, our motivation is identical to the one of the Polyak’s update rule [17], where the loss-linearization (Eq. 2) is already proposed in a deterministic setting as well as”
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, neutral): “Stochastic gradient methods are classical, beginning with the development by Robbins and Monro [48] in the 1950s [46, 47, 65, 42, 64, 30].”
- Fast optimization via inertial dynamics with closed-loop damping (2020, background): “Polyak [83, 84] and further studied by Attouch–Goudou–Redont [27] (exploration of local minima), Alvarez [7] (convergence in the convex case), Haraux-Jendoubi [69, 70] (convergence in the analytic case), Bégout–Bolte–Jendoubi [43] (convergence based on the KurdykaLojasiewicz property), to cite part ”
- Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games (2020, methodology): “…in depth the stochastic gradient feedback case, where each player adopts OGD in λ -cocoercive games, with gradient corrupted by a zero-mean, martingale-difference noise, whose variance is proportional to current gradient norm squared as assumed in the relative random noise model [Polyak, 1987].”
- Stochastic Polyak Stepsize with a Moving Target (2021, methodology): “2 and finally 3) motivated through star-convexity in Section G which is closely related to Polyak’s original motivation [Pol87].”
- Learning in games with continuous action sets and unknown payoff functions (2016, background): “At the other end of the spectrum, if players only have access to their realized, ingame payoffs, they would need to reconstruct their individual payoff gradients via a suitable single-shot estimator (Polyak, 1987; Flaxman et al., 2005).”
- A Fast Proximal Point Method for Computing Wasserstein Distance (2018, neutral): “From [21, Section 2.2], we guarantee that { D h ( x ∗ , x ( t ) ) } converges to 0 ≤ d ( x ∗ ) ∞ .”
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “The convergence of (stochastic) gradient descent with compressed gradients has been studied in various communities, and results for unbiased compression (perturbations) can be tracked back to e.g. (Polyak, 1987).”