Linear convergence of first order methods for non-strongly convex optimization
From MaRDI portal
Abstract: 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.
Recommendations
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
- Conditions for linear convergence of the gradient method for non-convex optimization
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- First-order methods for convex optimization
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
Cites work
- A unified approach to error bounds for structured convex optimization problems
- Adaptive restart for accelerated gradient schemes
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convex optimization: algorithms and complexity
- Coordinate descent algorithms
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Error bounds for solutions of linear equations and inequalities
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- scientific article; zbMATH DE number 1328979 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Randomized methods for linear constraints: convergence rates and conditioning
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
- Robust Stochastic Approximation Approach to Stochastic Programming
- Weak sharp minima revisited. III: Error bounds for differentiable convex inclusions
Cited in
(only showing first 100 items - show all)- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases
- New characterizations of Hoffman constants for systems of linear constraints
- Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
- On the linear convergence of forward-backward splitting method. I: Convergence analysis
- General convergence analysis of stochastic first-order methods for composite optimization
- The condition number of a function relative to a set
- New subspace minimization conjugate gradient methods based on regularization model for unconstrained optimization
- Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
- An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Convergence results of a nested decentralized gradient method for non-strongly convex problems
- Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)
- Inertial proximal incremental aggregated gradient method with linear convergence guarantees
- From differential equation solvers to accelerated first-order methods for convex optimization
- Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
- On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces
- Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergence
- Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Exponential convergence of distributed optimization for heterogeneous linear multi-agent systems over unbalanced digraphs
- Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry
- Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- Error bounds for non-polyhedral convex optimization and applications to linear convergence of FDM and PGM
- Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Provable accelerated gradient method for nonconvex low rank optimization
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Random minibatch subgradient algorithms for convex problems with functional constraints
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
- Inexact successive quadratic approximation for regularized optimization
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Computation of the maximal invariant set of discrete-time linear systems subject to a class of non-convex constraints
- New results on multi-dimensional linear discriminant analysis
- Quadratic growth conditions and uniqueness of optimal solution to Lasso
- Convergence rates of the heavy-ball method under the Łojasiewicz property
- A globally convergent proximal Newton-type method in nonsmooth convex optimization
- Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- Accelerating Stochastic Composition Optimization
- Global convergence rate of proximal incremental aggregated gradient methods
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Convergence rates for the stochastic gradient descent method for non-convex objective functions
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- Stochastic proximal AUC maximization
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- Exact gradient methods with memory
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- An iterative reduction FISTA algorithm for large-scale LASSO
- First-order methods for problems with \(O(1)\) functional constraints can have almost the same convergence rate as for unconstrained problems
- Convergence rates of the heavy ball method for quasi-strongly convex optimization
- Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
- First-Order Methods for Nonconvex Quadratic Minimization
- The error-feedback framework: SGD with delayed gradients
- New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
- The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth
- Accelerate stochastic subgradient method by leveraging local growth condition
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems
- Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
- An update-and-stabilize framework for the minimum-norm-point problem
- A speed restart scheme for a dynamics with Hessian-driven damping
- Conditions for linear convergence of the gradient method for non-convex optimization
- Linearly-convergent FISTA variant for composite optimization with duality
- A new Lagrangian-based first-order method for nonconvex constrained optimization
- A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
- FISTA is an automatic geometrically optimized algorithm for strongly convex functions
- Efficiency of higher-order algorithms for minimizing composite functions
- A strict complementarity approach to error bound and sensitivity of solution of conic programs
- First-order methods for convex optimization
- Local linear convergence of proximal coordinate descent algorithm
- scientific article; zbMATH DE number 7811224 (Why is no real title available?)
- Coordinate descent methods beyond smoothness and separability
- Variance reduced moving balls approximation method for smooth constrained minimization problems
- Mini-batch stochastic subgradient for functional constrained optimization
- Subgradient regularized multivariate convex regression at scale
- MGProx: a nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization
- Consensus-based optimization methods converge globally
- Interpolation conditions for linear operators and applications to performance estimation problems
- Distributed accelerated gradient methods with restart under quadratic growth condition
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Parameter-free FISTA by adaptive restart and backtracking
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Lipschitz continuity of the metric projection operator and convergence of gradient methods
- Convergence rate analysis of the gradient descent–ascent method for convex–concave saddle-point problems
- Perseus: a simple and optimal high-order method for variational inequalities
- Predefined/prescribed-time convergence algorithm of nonconvex-nonconcave min-max optimization
- Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
- An optimal lower bound for smooth convex functions
- Losing momentum in continuous-time stochastic optimisation
- On growth error bound conditions with an application to heavy ball method
- Performative prediction: past and future
- A systematic approach to general higher-order majorization-minimization algorithms for (non)convex optimization
- A geometric integration approach to smooth optimization: foundations of the discrete gradient method
This page was built for publication: Linear convergence of first order methods for non-strongly convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414900)
