Excessive Gap Technique in Nonsmooth Convex Minimization

By Yurii E. Nesterov. SIAM Journal on Optimization, 2005

301 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/8cd1b5c73b6254ccd95bbb2daff8723f85b6deb1

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 Computational Theory and Mathematics

Citations in the corpus

First-order methods of smooth convex optimization with inexact oracle (2013, background): “Interest into these methods has been renewed recently with development of smoothing techniques for non-smooth convex problems (see [15,16,17,4]), where FGMs are used to minimize a smooth approximation of a non-smooth objective function.”
Computer poker: A review (2011, methodology): “[30] present an adapted version of Nesterov’s excessive gap technique [60] that has been specialised for twoperson, zero-sum imperfect information games.”
Heads-up limit hold’em poker is solved (2015, methodology): “Another notable algorithm to emerge from the Annual Computer Poker Competition is an application of Nesterov’s excessive gap technique (51) to solving extensive-form games (52).”
Hankel Matrix Rank Minimization with Applications to System Identification and Realization (2013, unknown): “, [41–44,54]).”
Deterministic and Stochastic Primal-Dual Subgradient Algorithms for Uniformly Convex Minimization (2014, background): “However, because of the immediate lack of application and, more importantly, due to new first order methods based on smoothing of structured problems with better complexity characteristics which were developed in [11, 12] at that time, the authors got an impression that new non-Euclidean algorithms ”
Dual extrapolation and its applications to solving variational inequalities and related problems (2007, background): “5 Bilinear matrix games Let us compare our results with the efficiency estimates of the smoothing technique [4, 5] as applied to the following problem instance.”
Libratus: The Superhuman AI for No-Limit Poker (2017, methodology): “Recent work suggests that subgame solving could be even faster by leveraging warm starting [Brown and Sandholm, 2016b], new pruning techniques [Brown and Sandholm, 2017a], or first-order methods [Nesterov, 2005; Kroer et al., 2017].”
Dynamic Thresholding and Pruning for Regret Minimization (2017, methodology): “We focus on Hedge (Freund and Schapire 1997; Littlestone and Warmuth 1994), also known as the exponentially-weighted forecaster, which is the most popular regret-minimizing algorithm in domains other than extensive-form game solving, on RM, and on the Excessive Gap Technique (EGT) (Nesterov 2005; Gi”
Accelerated training of max-margin Markov networks with kernels (2011, background): “Therefore to reduce the duality gap and dual gap below , it suffices to take 2 + max i,y ∥∥ψiy∥∥2 √ 6 log |Y| λ and max i,y ∥∥ψiy∥∥2 √ 6KL(α∗||α0) λ (22) steps respectively.”
Safe and Nested Endgame Solving for Imperfect-Information Games (2017, methodology): “In order to use iterative algorithms such as the Excessive Gap Technique (Nesterov 2005; Gilpin, Pe˜na, and Sandholm 2012) or Counterfactual Regret Minimization (CFR) (Zinkevich et al. 2007), one can use the gadget game described by Moravcik et al. (2016).”
Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games (2007, methodology): “Our approach is based on modern smoothing techniques for saddle-point problems [17].”
Solving variational inequalities with Stochastic Mirror-Prox algorithm (2008, background): “…therein) with the guaranteed rate of convergence O (1) L + M + N √ t and extra-gradient-type algorithms for solving deterministic monotone v.i.’s with Lip-schitz continuous operators (see [6, 9, 10, 11]), which attains the accuracy O (1) in the case of M = N = 0 or O (1) M √ t when L = N = 0.”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, methodology): “If the input (µX, µY, x, y) to algorithm 3 satisfies equation 5, then so does (µ+X, µY, x +, y+) as long as t satisfies t2/(1 − t ) ≤ µX µY sX sY /||A|| 2 (Nesterov 2005a).”
Trace Norm Regularization: Reformulations, Algorithms, and Multi-Task Learning (2010, background): “Such a duality gap bound, shown originally by Nesterov for related methods [37,38], is a special property of these accelerated methods.”