First-order methods of smooth convex optimization with inexact oracle

2013/06/13 by Olivier Devolder, François Glineur, Yurii Nesterov · 442 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Applied mathematics #Computer science #Context (archaeology) #Convex analysis #Convex function #Convex optimization #First order #Mathematical optimization #Mathematics #Oracle #Proximal Gradient Methods #Proximal gradient methods for learning #Regular polygon #Regularization (linguistics) #Smoothing #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · doi:10.1007/s10107-013-0677-5

published in Mathematical Programming 146(1-2), 37-75 (Springer Science+Business Media)

openalex publication_date 2013/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Citations

• Smooth minimization of non-smooth functions

Cited by

• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Non-smooth Variable Projection
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• A perturbed preconditioned gradient descent method for the unconstrained minimization of composite objectives
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• OFF (Proximal) Newton-type Methods with Inexact Derivatives for Unconstrained Optimization
• Generalization of Silver Stepsize Schedule to Stochastic Optimization
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
• Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Target Propagation via Regularized Inversion
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian\n Monte Carlo
• Iteration complexity of first-order augmented Lagrangian methods for convex conic programming
• Subgradient Methods for Nonsmooth Convex Functions with Adversarial Errors
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Communication-Efficient Algorithms For Distributed Optimization
• Improving Fast Dual Ascent for MPC - Part I: The Distributed Case
• Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization
• Truncated Inference for Latent Variable Optimization Problems: Application to Robust Estimation and Learning
• Выпуклая оптимизация
• Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
• Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
• Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples
• Langevin Monte Carlo without smoothness
• Convergence and Stability of the Stochastic Proximal Point Algorithm\n with Momentum
• Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
• Complexity of first order inexact Lagrangian and penalty methods for conic convex programming
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• From Infinite to Finite Programs: Explicit Error Bounds with\n Applications to Approximate Dynamic Programming
• Distributed Fixed Point Methods with Compressed Iterates
• On the Convergence of SGD with Biased Gradients
• Global convergence of the Heavy-ball method for convex optimization
• Improved Adversarial Learning for Fair Classification
• Online First-Order Framework for Robust Convex Optimization
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization
• OSGA: A fast subgradient algorithm with optimal complexity
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Fast Equivariant Imaging: Accelerating Unsupervised Learning and Model Adaptation via Inexact Splitting
• Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization
• Robust Regression Revisited: Acceleration and Improved Estimation Rates
• Perturbed Gradient Descent Algorithms are Small-Disturbance Input-to-State Stable
• Train faster, generalize better: Stability of stochastic gradient descent
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Partial Uncertainty and Applications to Risk-Averse Valuation
• Distributed stochastic optimization for deep learning (thesis)
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions
• Improper Learning for Non-Stochastic Control
• Acceleration with a Ball Optimization Oracle
• Optimal subgradient algorithms with application to large-scale linear inverse problems
• On Corruption-Robustness in Performative Reinforcement Learning
• Tight analyses of first-order methods with error feedback
• Inexact projected preconditioned gradient methods with variable metrics: a Lyapunov convergence theory (extended version)
• Proximal bundle algorithms for nonsmooth convex optimization via fast gradient smooth methods
• Accelerating Gradient Boosting Machine
• A New Complexity Result for Strongly Convex Optimization with Locally α-Hölder Continuous Gradients
• Inexact JKO and proximal-gradient algorithms in the Wasserstein space
• Optimization for deep learning: theory and algorithms
• Quantization Design for Distributed Optimization
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization
• Primal-dual ε-Subgradient Method for Distributed Optimization
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
• Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization
• An Inexact Interior-Point Lagrangian Decomposition Algorithm with Inexact Oracles
• Algorithmic Instabilities of Accelerated Gradient Descent
• Convergence Analysis of Dual Decomposition Algorithm in Distributed Optimization: Asynchrony and Inexactness
• (Bandit) Convex Optimization with Biased Noisy Gradient Oracles
• Frank-Wolfe Methods in Probability Space
• Smoothness of the Augmented Lagrangian Dual in Convex Optimization
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
• Convex programming in optimal control and information theory
• Real-time Distributed MPC for Multiple Underwater Vehicles with Limited Communication Data-rates
• Robust Accelerated Dynamics for Subnetwork Bilinear Zero-Sum Games with Distributed Restarting
• Active Robust Learning