Linear convergence of first order methods for non-strongly convex optimization

By Ion Necoara, Yurii E. Nesterov, François Glineur. 2015

409 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “We say that a function f : R d → R is µ –strongly quasi-convex [Karimi et al., 2016, Necoara et al., 2018] if there is µ > 0 such that: for all x ∈ d .”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Lemma D.1 (Necoara et al. (2018)) .”
SGD: General Analysis and Improved Rates (2019, background): “Further, we assume that f has a unique1 global minimizer x∗ and is μ–strongly quasi-convex (Karimi et al., 2016; Necoara et al., 2018):”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “Nesterov (1998) shows that GD finds an -first-order stationary point in O(1/ 2) steps.”
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods (2016, background): “Discussion of recent related work There have been a number of closely related manuscripts circulating shortly before or concurrently with the initial version of our manuscript [22], namely [8, 30, 39, 54, 55].”
Better Theory for SGD in the Nonconvex World (2020, background): “There are only a handful of results under QFG (Drusvyatskiy & Lewis, 2018; Necoara et al., 2019; Grimmer, 2019) and only one applies to our setting (Grimmer, 2019).”
Unified Optimal Analysis of the (Stochastic) Gradient Method (2019, background): “(Necoara et al., 2019)) and denote by x a minimizer of f in R.”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, background): “Lemma 5 (Necoara et al. (2019), Theorem 10) Consider a problem of the following form where g is strongly convex with any feasible initial point α 0 .”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, neutral): “Assumption 3 implies (Hazan and Kale, 2011) λ 2 ‖w −w∗‖(2) ≤ F (w)− F (w∗), ∀w ∈ W (5) which is referred to as the quadratic growth condition (Necoara et al., 2019).”
The Physical Systems Behind Optimization Algorithms (2016, methodology): “We study the convergence of VGD for two classes of functions: (1) General convex function — Nesterov (2013) has shown that VGD achieves O(L/k) convergence for general convex functions; (2) A class of functions satisfying the Polyak-Łojasiewicz (PŁ) condition, which is defined as follows (Polyak, 196”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “We refer the interested reader to [92] and [129] for more details on these conditions and how they are related to each other.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “…[2016], PL condition is weaker, or not stronger, than other well-known conditions that guarantee linear convergence for gradient descent, such as error bounds (EB) [Luo and Tseng, 1993], weak strong convexity (WSC) [Necoara et al., 2018] and restricted secant inequality (RSI) [Zhang and Yin, 2013].”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “Our definition is slightly less general than the notion of quasi-convexity introduced in (Necoara et al., 2019), as we choose a particular minimizer x⋆, the “quasar-convex point” and do not e.g. use projection on the set of minimizers as in (Necoara et al., 2019).”