Smooth strongly convex interpolation and exact worst-case performance of first-order methods
From MaRDI portal
Publication:507324
DOI10.1007/s10107-016-1009-3zbMath1359.90098arXiv1502.05666OpenAlexW1962121538MaRDI QIDQ507324
François Glineur, Adrien B. Taylor, Julien M. Hendrickx
Publication date: 3 February 2017
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.05666
semidefinite programmingrates of convergenceworst-case analysisfirst-order methodssmooth convex minimizationsmooth convex interpolation
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)
Related Items (49)
On the convergence rate of the Halpern-iteration ⋮ Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis ⋮ Optimized first-order methods for smooth convex minimization ⋮ Optimal complexity and certification of Bregman first-order methods ⋮ Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry ⋮ A frequency-domain analysis of inexact gradient methods ⋮ Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs ⋮ On the Properties of Convex Functions over Open Sets ⋮ A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives ⋮ Finitely determined functions ⋮ Generalizing the Optimized Gradient Method for Smooth Convex Minimization ⋮ Exact worst-case convergence rates of the proximal gradient method for composite convex minimization ⋮ Surrogate-based distributed optimisation for expensive black-box functions ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions ⋮ The exact worst-case convergence rate of the gradient method with fixed step lengths for \(L\)-smooth functions ⋮ Backward-forward-reflected-backward splitting for three operator monotone inclusions ⋮ An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ Accelerated gradient methods with absolute and relative noise in the gradient ⋮ Conditions for linear convergence of the gradient method for non-convex optimization ⋮ A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ Unnamed Item ⋮ An elementary approach to tight worst case complexity analysis of gradient based methods ⋮ Principled analyses and design of first-order methods with inexact proximal operators ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA) ⋮ Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation ⋮ Efficient first-order methods for convex minimization: a constructive approach ⋮ Halting time is predictable for large models: a universality property and average-case analysis ⋮ Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection ⋮ Accelerated methods for saddle-point problem ⋮ A generic online acceleration scheme for optimization algorithms via relaxation and inertia ⋮ Tight Sublinear Convergence Rate of the Proximal Point Algorithm for Maximal Monotone Inclusion Problems ⋮ Accelerated proximal point method for maximally monotone operators ⋮ On the convergence analysis of the optimized gradient method ⋮ Analysis of biased stochastic gradient descent using sequential semidefinite programs ⋮ Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions ⋮ Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems ⋮ Bounds for the tracking error of first-order online optimization methods ⋮ Data-Driven Nonsmooth Optimization ⋮ Analysis of optimization algorithms via sum-of-squares ⋮ New analysis of linear convergence of gradient-type methods via unifying error bound conditions ⋮ On the oracle complexity of smooth strongly convex minimization ⋮ Finding the forward-Douglas-Rachford-forward method ⋮ Solving inverse problems using data-driven models ⋮ Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Optimized first-order methods for smooth convex minimization
- On the convergence analysis of the optimized gradient method
- Introductory lectures on convex optimization. A basic course.
- Performance of first-order methods for smooth convex minimization: a novel approach
- Lectures on Modern Convex Optimization
- Double Smoothing Technique for Large-Scale Linearly Constrained Convex Optimization
- Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
- Variational Analysis
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Semidefinite Programming
- Equivalent Subgradient Versions of Hamiltonian and Euler–Lagrange Equations in Variational Analysis
- Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems
- Quadratic Matrix Programming
- Convex analysis and monotone operator theory in Hilbert spaces
This page was built for publication: Smooth strongly convex interpolation and exact worst-case performance of first-order methods
