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

2018/01/22 by Ion Necoara, I. Necoara, Yu. Nesterov +2 · 32 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Applied mathematics #Convergence (economics) #Convex function #Convex optimization #Convexity #Linear programming #Lipschitz continuity #Mathematical analysis #Mathematical optimization #Mathematics #Regular polygon #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · open access · doi:10.1007/s10107-018-1232-1

published in Mathematical Programming 175(1-2), 69-107 (Springer Science+Business Media)

openalex publication_date 2018/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Cited by

• Characterizations, Dynamical Systems and Gradient Methods for Strongly Quasiconvex Functions
• Distributed Nonlinear Equality-Constrained Optimization via Feedback Linearization and Singular Perturbation
• Optimal Subgradient Methods for Lipschitz Convex Optimization with Error Bounds
• The Physical Systems Behind Optimization Algorithms
• Strong Global Convergence of the Consensus-Based Optimization Algorithm
• On the Tension Between Optimality and Adversarial Robustness in Policy Optimization
• Combinatorial Preconditioners for Proximal Algorithms on Graphs
• Accelerated Alternating Direction Method of Multipliers: an Optimal O(1/K) Nonergodic Analysis
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Optimization in Theory and Practice
• Geometric Convergence Analysis of Variational Inference via Bregman Divergences
• Semi-infinite Nonconvex Constrained Min-Max Optimization
• Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• Proximal gradient methods in Banach spaces
• Regularized Overestimated Newton
• Time-Varying Convex Optimization via Time-Varying Averaged Operators
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case
• Efficient Rank Minimization via Solving Non-convexPenalties by Iterative Shrinkage-Thresholding Algorithm
• On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs
• From Sublinear to Linear: Fast Convergence in Deep Networks via Locally Polyak-Lojasiewicz Regions
• Numerical Design of Optimized First-Order Algorithms
• Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings
• On the Linear Convergence of the Cauchy Algorithm for a Class of Restricted Strongly Convex Functions
• First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
• Heavy-ball dynamics with Hessian-driven damping for non-convex optimization under the Łojasiewicz condition
• Towards faster first order methods: A continuous-time model to interpolate between speed and function value restart
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
• A Stochastic Gradient Descent Method for Globally Minimizing Nearly Convex Functions
• Gradient Methods with Online Scaling Part I. Theoretical Foundations
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• Hidden Star-Convexity in Policy Optimization for Gain-Scheduled LQR: Extended Version
• Revisiting Decomposition-Invariant Conditional Gradient Methods for Polytopes
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Primal-Dual Rates and Certificates
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
• Relaxed Weak Accelerated Proximal Gradient Method: a Unified Framework for Nesterov's Accelerations
• A first order method for linear programming parameterized by circuit imbalance. [europepmc]