Linear convergence of first order methods under weak nondegeneracy assumptions for convex programming
By Ion Necoara, Yurii E. Nesterov, François Glineur. 2015
9 citations recorded by the source corpus.
The standard assumption for proving linear convergence of first order methods for smooth convex optimization is the strong convexity of the objective function, an assumption which does not hold for many practical applications. In this paper, we derive linear convergence rates of several first order methods for solving smooth non-strongly convex constrained optimization problems, i.e. involving an objective function with a Lipschitz continuous gradient that satisfies some relaxed strong convexity condition. In particular, in the case of smooth constrained convex optimization, we provide several relaxations of the strong convexity conditions and prove that they are sufficient for getting linear convergence for several first order methods such as projected gradient, fast gradient and feasible descent methods. We also provide examples of functional classes that satisfy our proposed relaxations of strong convexity conditions. Finally, we show that the proposed relaxed strong convexity conditions cover important applications ranging from solving linear systems, Linear Programming, and dual formulations of linearly constrained convex problems.
Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis
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
- Peter Richtárik
- Martin Jaggi
- Virginia Smith
- Jakub Konecný
- Martin Takác
- Chenxin Ma
- Michael I. Jordan
- Sebastian U. Stich
In Computational Mechanics
- Peter Richtárik
- Martin Takác
- Martin Jaggi
- Jakub Konecný
- Virginia Smith
- Chenxin Ma
- Michael I. Jordan
- Simone Forte
In Numerical Analysis
- Martin Takác
- Martin Jaggi
- Chenxin Ma
- Virginia Smith
- Michael I. Jordan
- Rachael Tappenden
- Simone Forte
- Francis R. Bach
Citations in the corpus
- CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “…problems like the hinge-loss support vector machine that could be applied, e.g., by using error bound conditions (Necoara and Nedelcu, 2014; Wang and Lin, 2014), weak strong convexity conditions (Ma et al., 2015c; Necoara, 2015) or by considering Polyak-Łojasiewicz conditions (Karimi et al., 2016).”
- Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, methodology): “Just recently, Necoara (2015) showed that if (26) is satisfied, then (5) is satisfied with κ f = L W f 2η 2 f .”