Subgradient Methods for Saddle-Point Problems

By Angelia Nedić, Asuman E. Ozdaglar. 2009

516 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Networks and Communications, Numerical Analysis

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Numerical Analysis

Citations in the corpus

Stochastic Primal-Dual Q-Learning (2018, positive): “If the discounted MDP model is known, then it can be solved by using the (deterministic) primal-dual algorithm (Nedi´c and Ozdaglar, 2009) where the gradients of L M with respect to the primal variables, Q, V , and the dual variables, λ, µ , are where We introduce the matrices, N, H , to radomize…”
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms (2013, background): “More recently, reference [40] studies similar algorithms for a wide class of non-differentiable (in general) cost functions and gives sub-linear rates to a neighborhood of a saddle point (The sub-linear rate is due to the wide function class assumed).”
On Distributed Convex Optimization Under Inequality and Equality Constraints (2010, unknown): “We here make the following assumptions on the network communication graphs, which are standard in the analysis of average consensus algorithms; e.g., see [18], [19], and distributed optimization in [15], [17].”
Regularized Off-Policy TD-Learning (2012, methodology): “Assumption 3 (Subgradient Boundedness)[12]: Assume for the bilinear convex-concave loss function defined in (14), the sets X, Y are closed compact sets.”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, methodology): “When the set-valued mapping F is monotone, many eﬃcient algorithms with non-asymptotic convergence guarantee have been developed for a VI problem itself or under the setting of a min-max problem [43, 65, 41, 55, 8, 53, 51, 50, 9].”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, methodology): “Non-asymptotical Convergence An explicit convergence rate for the subgradient method with a constant stepsize was proved in [30] for reaching an approximate saddle point, as opposed to asymptotically exact solutions.”
Generative Modeling Using the Sliced Wasserstein Distance (2018, background): “Special techniques, e.g ., [24, 23] are generally necessary but practically not used.”
Scalable Learning of Non-Decomposable Objectives (2016, background): “An important consequence of the above derivation is that we can just as easily optimize for AUCROC and AUCPR in some limited range, e.g. for precision greater than some desired threshold.”
Stability of primal-dual gradient dynamics and applications to network optimization (2010, background): “Other related work in the optimization literature can be found in Nedic and Ozdaglar (2009) and references therein.”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, methodology): “hm can be viewed as an extension of the Arrow-Hurwitz method which performs alternating subgradient steps with respect to the primal and dual variables in order to solve the saddle point problem (12) [41]. Two step-sizesτ and σ and relaxation factors (λn)n∈N are involved in Algorithm 2, which can be”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, methodology): “ stepsize ρ > 0). The GPDA is closely related to the classical Uzawa primal-dual method [28], which has been utilized to solve convex saddle point problems and linearly constrained convex problems [29]. It is also related to the proximal method of multipliers (Prox-MM) ﬁrst developed by Rockafell”
On stochastic gradient and subgradient methods with adaptive steplength sequences (2011, methodology): “rmore, Ais a symmetric matrix whose entries are A ij= i+ j 1 2n 1 1 i;jn: (49) Problem (48) a saddle point problem. Solving saddle point problems by SA algorithm has been discussed extensively (cf. [72]). The gradient and its sampled variant to be employed in algorithm (3) are given by: g(x;y) = ATy”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “By contrast, the extragradient method (extrapolated gradient) does not require any averaging to converge for monotone operators (in the batch setting), and can even converge at the faster O (1 /t ) rate (Nesterov, 2007).”
Stochastic Primal-Dual Q-Learning Algorithm For Discounted MDPs (2019, methodology): “If the DMDP model is known, then it can be solved by using the primal-dual algorithm [30].”
Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, methodology): “The D-GPDA is closely related to many classical primal-dual methods, such as the Uzawa method [42] (which has been recently utilized to solve linearly constrained convex problems [43]), and the proximal method of multipliers (prox-MM) [44, 45].”
Proximity Without Consensus in Online Multiagent Optimization (2016, methodology): “The convergence of recursively averaged saddle point iterates with constant step-size has appeared in the deterministic setting in [17] and in the context of regret for online learning in [30].”