Primal-dual subgradient methods for convex problems

By Yurii E. Nesterov. 2009

1,071 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “1: Initialization: θ = 0 , ¯ θ = 0 , z = 0 .”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “These methods are characterized by incremental updates based on subgradients ∂(cid:96) ( w , z i ) of individual instances, and enjoy the advantages of being highly scalable and simple to implement.”
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, methodology): “Similar techniques, based on subgradient averaging, have been proposed in [14, 16, 27].”
Distributed delayed stochastic optimization (2011, methodology): “To build intuition for the algorithms we analyze, we first describe two closely related first-order algorithms: the dual averaging algorithm of Nesterov [Nes09] and the mirror descent algorithm of Nemirovski and Yudin [NY83], which is analyzed further by Beck and Teboulle [BT03].”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “Standard dual averaging Our algorithm is based on Nesterov’s recent dual averaging algorithm [13], [14], designed for minimization of (potent ially nonsmooth) convex functionsf subject to the constraint x ∈ X .”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, background): “More recently, several mathematically motivated algorithms (Nesterov, 2009; Le Roux et al. , 2012) have been proposed that incorporate some form of momentum and that also ensure much faster convergence (linear rather than sublinear) compared to stochastic gradient descent, at least for convex…”
The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo (2011, methodology): “We also developed a method for automatically adapting the step size parameter (cid:15) shared by NUTS and HMC via an adaptation of the dual averaging algorithm of Nesterov (2009), making it possible to run NUTS with no hand tuning at all.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “This assumption is commonly used in the analysis for stochastic optimization algorithms, for example, [5]–[10], [19], [27]–[29], [41]–[43].”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, methodology): “nd global constraints [26], [36] randomly varying networks [29], [30], [31] and random gradient errors [42], [34]. A different distributed algorithm that relies on Nesterov’s dual averaging algorithm [37] for static networks has been proposed and analyzed in [11]. Such gradient 3This work is clearly”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework (2012, methodology): “Similar techniques, based on subgradient averaging, have been proposed in [13, 16, 27].”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, background): “In these applications, function F in (1.5) is assumed to be a multiple of a strongly convex prox-function (see, for example, [14]).”
Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives (2015, methodology): “The dual iterate zi(t) computed by agent i at time t will be an estimate of the “running average of the subgradients” as seen by agent i, and will constitute an approximation of the true centralized dual-averaging subgradient update of Nesterov’s algorithm.”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, neutral): “This recovers the method of [11]: #%+1 = argmin!∈' { ⟨/̄%, #⟩+ (:/ √ .”
Robust Stochastic Approximation Approach to Stochastic Programming (2008, methodology): “Close techniques, based on subgradient averaging, have been proposed in Nesterov [17] and used in [10] to solve the stochastic optimization problem (1.1).”
A distributional interpretation of robust optimization (2010, methodology): “In this case, the objective function is indeed a saddle point problem, which can be solved using, for example, the primal-dual subgradient method [24].”
Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization (2020, methodology): “We consider a fully distributed topologyand consider the problem of stochastic convex optimization via dual averaging Nesterov (2009); Xiao (2010).”
Monte Carlo sampling-based methods for stochastic optimization (2014, methodology): “Nesterov [171] proposed a primal-dual method which works in the dual space of the problem, with the goal of preventing the weights of subgradients from going to zero.”