Online Convex Programming and Generalized Infinitesimal Gradient Ascent

By Martin A. Zinkevich. 2003

2,812 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Adam: A Method for Stochastic Optimization (2014, neutral): “Decaying β 1 ,t towards one is important in our theoretical analysis and also matches previous emperical ﬁndings, e.g. (Sutskever et al., 2013) suggests reducing the momentum coefﬁcient in the end of training can improve convergence.”
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “…is given gradient information, the attainable optimization error / average regret is well-known: under mild conditions, it is Θ(1/ √ T ) for convex functions and Θ(1/T ) for strongly-convex functions, where T is the number of queries Zinkevich (2003); Hazan and Kale (2011); Rakhlin et al. (2012).”
Contextual Dueling Bandits (2015, methodology): “Using an analysis similar to Zinkevich (2003), but for fixed learning rate, and taking into account the errors introduced by imperfect projections, we can show the following: Lemma 5 For the algorithm described above with η = 2/(L √ Tout), we have 1 Tout Tout∑ t=1 w>t But ≥ min w∈C 1 Tout Tout∑ t=1…”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Neural Replicator Dynamics Neural Replicator Dynamics (NeuRD) [49] takes the policy gradient connection to CFR a step further: in [66], the relationship between policy gradients and CFR was possible via GIGA [77]; however, this requires `2 projections of policies after the gradient step.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “Convergence results for SG and its variants are occasionally established using regret bounds as an intermediate step [157, 138, 51].”
Adaptive Gradient-Based Meta-Learning Methods (2019, background): “While this can be viewed as a single online learning problem to determine actions it is easier to decouple φ and η by ﬁrst deﬁning two function sequences { f init t } t and { f sim t } t : We show in Theorem 3.1 that to get an adaptive algorithm it sufﬁces to specify two OCO algorithms, INIT and SIM”
Semi-Cyclic Stochastic Gradient Descent (2019, methodology): “Standard regret bounds for the latter (Zinkevich, 2003; see also Shalev-Shwartz, 2012; Hazan, 2016) imply that for any sequence z1, . . . , zT and for any ‖w?”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, neutral): “The irst dynamic regret is deined as ∑� �=1 ( �� (x� ) − �� (x∗ � ) ) subject to ∑�−1 �=1 x∗ �+1 − x∗ � ≤ � where� is a budget for the change over the reference points [49].”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “1 Privatizing unit `2 vectors with high accuracy We begin with the Euclidean case, which arises in most classical applications of stochastic gradientlike methods [71, 61, 60].”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “In general, the coeﬃcient of the dominant √ m term is proportional to an upper bound on the expected norm of the stochastic gradient (e.g., Zinkevich, 2003).”
Adaptive Bound Optimization for Online Convex Optimization (2010, methodology): “Following the arguments of Zinkevich (2003), for the remainder we restrict our attention to linear functions.”
Privacy Aware Learning (2012, background): “Such a setting is natural; indeed, many online optimization and stochastic approximation algorithms [34, 21, 1] assume that for any x ∈ X and θ ∈ Θ , if g ∈ ∂ℓ ( x, θ ) then g ≤ L for some norm k·k . allowing to so k k We may obtain privacy by a perturbation the subgradient g long as the…”
What do we need to build explainable AI systems for the medical domain? (2017, neutral): “…(1) The class probabilities modeled by the neural net are functions having a gradient, consequently a widely-used technique in AI, gradient ascent, which aims at maximizing an objec-tive function (opposite to gradient descent which aims to minimizing an objective function) (Zinkevich, 2003).”
Smoothness, Low Noise and Fast Rates (2010, background): “Comparing with the bound of O ( D 2 B 2 /n ) when the loss is D - Lipschitz rather then H -smooth [34, 22], we see the same relationship discussed above for ERM.”
Counterfactual Prediction with Deep Instrumental Variables Networks (2016, background): “Lower variance for ∇ θ L t will tend to yield faster convergence [Zinkevich, 2003] while the computational e ﬃ ciency of SGD on large datasets requires limiting the number of operations going into each gradient calculation [Bousquet and Bottou, 2008].”
Continual Few-Shot Learning for Text Classification (2021, background): “tially, where the task is the same but can exhibit concept drift (new patterns) (Zinkevich, 2003; Crammer et al., 2006; Sahoo et al., 2018; Jerfel et al., 2019; Javed and White, 2019).”
Dual Policy Iteration (2018, background): “9 and update the Lagrange multiplier µ , for example, by projected gradient ascent [40].”
Empirically Evaluating Multiagent Learning Algorithms (2014, background): “1) and strategic convergence to a Nash equilibrium when playing against GIGA (Zinkevich, 2003) in two-player two-action games.”
Multiagent Learning: Basics, Challenges, and Prospects (2012, methodology): “The IGA algorithm has been generalized into the generalized infinitesimal gradient ascent (GIGA) algorithm beyond two actions using the regret measure by Zinkevich (2003).”