Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods

By Angelia Nedić, Asuman E. Ozdaglar. SIAM Journal on Optimization, 2008

438 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Numerical Analysis, Transportation

View Paper: https://www.semanticscholar.org/paper/c95d9d54880f559131459722dc0e7762291b77b4

How researchers see this paper

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

In Computer Networks and Communications

In Numerical Analysis

In Transportation

Citations in the corpus

Robust Energy Management for Microgrids With High-Penetration Renewables (2012, background): “The running averages can be recursively computed as in (21), and are also guaranteed to converge to a neighborhood of the optimal solution [26].”
Introduction to dual composition for inference (2011, methodology): “22) when solving a Lagrangian relaxation using subgradient methods has been well-studied (e.g., see Anstreicher and Wolsey, 2009; Nedić and Ozdaglar, 2008; Shor et al., 1985).”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, positive): “However, more recent work [33] also provides convergence rates estimates, including per iteration estimates for the amount of feasibility violation, as well as upper and lower bounds for the primal objective function.”
1 Introduction to Dual Decomposition for Inference (2010, methodology): “22) when solving a Lagrangian relaxation using subgradient methods has been well-studied (e.g., see Anstreicher and Wolsey, 2009; Nedić and Ozdaglar, 2008; Shor et al., 1985).”
Ergodic Stochastic Optimization Algorithms for Wireless Communication and Networking (2010, background): “The operator denotes projection to the positive orthant.”
Balancing Communication and Computation in Distributed Optimization (2017, background): “A number of later contributions [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30] extended DGD to other settings, including stochastic networks, constrained problems, and noisy environments.”
Constrained Learning With Non-Convex Losses (2021, background): “This issue, known as primal recovery, is not specific to constrained learning and is a fundamental limitation of duality in general [33], [64].”
Subgradient Methods for Saddle-Point Problems (2009, methodology): “More recent literature also considered exploiting the subgradient information generated in the dual space directly to produce approximate primal solutions (see Sherali and Choi [28], Larsson, Patriksson, and Strömberg [16, 17, 18], Nesterov [26], and Nedić and Ozdaglar [23]).”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “Since calculating an approximate gradient is often cheap, recent years have witnessed the development of several variants, such as the incremental aggregated gradient method [25], stochastic average gradient method [26], [27], stochastic variance reduced gradient method [28], SAGA [29].”
On Distributed Convex Optimization Under Inequality and Equality Constraints (2010, background): “The following lemma is a direct result of Lemma 1 in [17].”
Distributed dual gradient methods and error bound conditions (2014, methodology): “All existing convergence results from the literature on dual gradient method either show sublinear convergence [1,10,13,15] or at most local linear convergence [8].”
Unsupervised Image Matching and Object Discovery as Optimization (2019, methodology): “Once the dual problem is solved, as argued by Nedić & Ozdaglar [35] and Bach [3], an approximate solution of the primal problem can be found as a running average of the primal sequence (xt, et) generated as a by-product of the sub-gradient method: x̂ = 1 T T−1∑ t=0 xt, ê = 1 T T−1∑ t=0 et (11) aft”