Primal-dual subgradient methods for convex problems

2007/06/18 by Yurii Nesterov · 861 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Convex optimization #Dual (grammatical number) #Interior point method #Mathematical optimization #Mathematics #Minimax #Regular polygon #Saddle point #Sequence (biology) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Subgradient method #Variational inequality

paper · doi:10.1007/s10107-007-0149-x

published in Mathematical Programming 120(1), 221-259 (Springer Science+Business Media)

openalex publication_date 2007/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• Smooth minimization of non-smooth functions

Cited by

• Sample size selection in optimization methods for machine learning
• Are Statistical Methods Obsolete in the Era of Deep Learning? A Study of ODE Inverse Problems
• An Isotropic Approach to Efficient Uncertainty Quantification with Gradient Norms
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Online AUC Optimization for Sparse High-Dimensional Datasets
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• On the robustness of learning in games with stochastically perturbed payoff observations
• Generalized-Hukuhara Subgradient Method for Optimization Problem with Interval-valued Functions and its Application in Lasso Problem
• On the convergence of single-call stochastic extra-gradient methods
• Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise
• Nonlinear stochastic multiarmed bandit problems with inexact oracle
• A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds
• On the Last Iterate Convergence of Momentum Methods
• On the convergence of dynamic implementations of Hamiltonian Monte Carlo and no U-turn samplers
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• Robust equilibria in continuous games: From strategic to dynamic robustness
• Multi-agent learning under uncertainty: Recurrence vs. concentration
• Distributed Delayed Stochastic Optimization
• Bayesian Bridge Gaussian Process Regression
• Online Distributed ADMM on Networks
• Adaptive extra-gradient methods for min-max optimization and games
• Online convex optimization and no-regret learning: Algorithms, guarantees and applications
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Gossip Dual Averaging for Decentralized Optimization of Pairwise\n Functions
• GenAI vs. Human Creators: Procurement Mechanism Design in Two-/Three-Layer Markets
• Minimax Theorems for Possibly Nonconvex Functions
• Frank-Wolfe variants for minimization of a sum of functions
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Entropy-based adaptive Hamiltonian Monte Carlo
• Federated Composite Optimization
• Online and stochastic Douglas-Rachford splitting method for large scale machine learning
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Dual subgradient algorithms for large-scale nonsmooth learning problems
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• Modeling and Analysis of Energy Harvesting and Smart Grid-Powered Wireless Communication Networks: A Contemporary Survey
• Communication-Efficient Algorithms For Distributed Optimization
• Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments
• Online Learning: A Comprehensive Survey
• Universal similar triangulars method for searching equilibriums in traffic flow distribution models
• A regret minimization approach to fixed-point iterations
• Online and Stochastic Universal Gradient Methods for Minimizing Regularized Hölder Continuous Finite Sums
• Convex Optimization without Projection Steps
• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• Extragradient method with variance reduction for stochastic variational inequalities
• Searching of equilibriums in hierarchical congestion population games
• Learned convex regularizers for inverse problems
• Sparse Q-learning with Mirror Descent
• Online Learning: A Modern Introduction Using Convex Optimization
• Balancing Communication and Computation in Distributed Optimization
• Convergence Rates of Subgradient Methods for Quasi-convex Optimization Problems
• Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems
• Iteratively reweighted ℓ ₁ ℓ 1 algorithms with extrapolation
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• No-regret learning and mixed Nash equilibria: They do not mix
• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications
• Towards an O((1)/(t)) convergence rate for distributed dual averaging
• A Rank-1 Sketch for Matrix Multiplicative Weights
• Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms
• Universal gradient descent
• In an Uncertain World: Distributed Optimization in MIMO Systems with Imperfect Information
• Adaptive Subgradient Methods for Online AUC Maximization
• Distributed Convex Optimization With Limited Communications
• The Power of Factorial Powers: New Parameter settings for (Stochastic)\n Optimization
• On the convergence of gradient-like flows with noisy gradient input
• Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence
• Training Sparse Neural Networks using Compressed Sensing
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k²) Rate on Squared Gradient Norm
• Subsampling Algorithms for Semidefinite Programming
• Asynchronous stochastic convex optimization
• Optimization Methods for Large-Scale Machine Learning
• Data Dependent Convergence for Distributed Stochastic Optimization
• Subgradient Projection Operators
• Time-Average Stochastic Optimization with Non-convex Decision Set and its Convergence
• Large-scale Unit Commitment under uncertainty
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• A Gradient Sampling method based on Ideal direction for solving nonsmooth nonconvex optimization problems: convergence analysis and numerical experiments
• Distributed Equilibrium-Learning for Power Network Voltage Control With a Locally Connected Communication Network
• The Confluence of Networks, Games and Learning
• The Generalization Ability of Online Algorithms for Dependent Data
• Least Squares Revisited: Scalable Approaches for Multi-class Prediction
• Pricing Mechanism for Resource Sustainability in Competitive Online Learning Multi-Agent Systems
• Conservative quantum offline model-based optimization
• Gradient-free prox-methods with inexact oracle for stochastic convex optimization problems on a simplex
• A new boosting algorithm based on dual averaging scheme
• A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication Networks
• Minimizing Regret on Reflexive Banach Spaces and Learning Nash Equilibria in Continuous Zero-Sum Games
• Optimal Distributed Online Prediction using Mini-Batches
• Glocal Smoothness: Line search and adaptive step sizes can help in theory too!
• Demystifying and Generalizing BinaryConnect
• Variance Regularization for Accelerating Stochastic Optimization
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Cost-Efficient Throughput Maximization in Multi-Carrier Cognitive Radio Systems
• Online Market Equilibrium with Application to Fair Division
• Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization
• Bethe Projections for Non-Local Inference
• On optimizing low SNR wireless networks using network coding
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• On the convergence of mirror descent beyond stochastic convex programming
• On Stochastic Subgradient Mirror-Descent Algorithm with Weighted\n Averaging
• Smoothed Gradients for Stochastic Variational Inference
• Flexible Bayesian Dynamic Modeling of Correlation and Covariance Matrices
• Stabilized Sparse Online Learning for Sparse Data
• Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization
• Stochastic Optimization for Machine Learning
• Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters
• Sampling from Conditional Distributions of Simplified Vines
• Multi-cut stochastic approximation methods for solving stochastic convex composite optimization
• Primal-Dual Sequential Subspace Optimization for Saddle-point Problems
• Optimistic and Adaptive Lagrangian Hedging
• Layer-wise Quantization for Quantized Optimistic Dual Averaging
• A Survey of Distributed Optimization Methods for Multi-Robot Systems
• About accelerated randomized methods
• A Subgradient Method for Free Material Design
• Weighted iteration complexity of the sPADMM on the KKT residuals for convex composite optimization
• Online Classification Using a Voted RDA Method
• Searching equillibriums in large transport networks
• Learning by mirror averaging
• Linear convergence of SDCA in statistical estimation
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Comparing different subgradient methods for solving convex optimization\n problems with functional constraints
• Realizing Quantum Wireless Sensing Without Extra Reference Sources: Architecture, Algorithm, and Sensitivity Maximization
• Learning to Optimize by Differentiable Programming
• Hamiltonian Monte Carlo for (Physics) Dummies
• Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions
• A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method
• Dynamic sampling schemes for optimal noise learning under multiple\n nonsmooth constraints
• Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses
• Stochastic Optimization with Optimal Importance Sampling
• Sparse Online Relative Similarity Learning
• Finding Equilibria in the Traffic Assignment Problem with Primal-Dual Gradient Methods for Stable Dynamics Model and Beckmann Model
• Dual Averaging With Non-Strongly-Convex Prox-Functions: New Analysis and Algorithm
• Variational Online Mirror Descent for Robust Learning in Schrödinger Bridge
• Incorporating the ChEES Criterion into Sequential Monte Carlo Samplers
• Stochastic Mirror Descent Dynamics and Their Convergence in Monotone Variational Inequalities. [europepmc]
• An incremental mirror descent subgradient algorithm with random sweeping and proximal step. [europepmc]
• Performance of Hamiltonian Monte Carlo and No-U-Turn Sampler for estimating genetic parameters and breeding values. [europepmc]
• Parallel residual projection: a new paradigm for solving linear inverse problems. [europepmc]
• Flexible Bayesian Dynamic Modeling of Correlation and Covariance Matrices. [europepmc]
• Low-dimensional encoding of decisions in parietal cortex reflects long-term training history. [europepmc]
• Subgradient ellipsoid method for nonsmooth convex problems. [europepmc]
• Primal Subgradient Methods with Predefined Step Sizes. [europepmc]