Online Convex Programming and Generalized Infinitesimal Gradient Ascent

Martin A. Zinkevich

article2003ICML2,834 citationsClassic Paper Prize

Introduces online convex programming alongside a projected gradient descent algorithm that guarantees $O(\sqrt{T})$ regret against arbitrary sequences of convex cost functions and proves universal consistency in repeated games.

Listen

The article addresses online optimization problems where a decision maker must repeatedly choose a point inside a known convex feasible set before observing the convex cost function for that round. Such settings arise in production planning, resource allocation, and repeated games, where future costs or payoffs remain unknown at decision time. The work introduces online convex programming to capture these repeated decisions and develops a practical algorithm to keep long-run average performance close to the best fixed choice that could have been made with full hindsight.

The article sets out to design and analyze a gradient-based method that works for arbitrary sequences of convex cost functions and to show that the method generalizes infinitesimal gradient ascent to establish universal consistency in repeated games. It defines the Greedy Projection algorithm, which performs a gradient step and then projects the result back onto the feasible set. The analysis compares performance against the single best fixed point in hindsight and derives explicit regret bounds under standard assumptions of bounded diameter and bounded gradients.

When the learning rate is set to the square root of the inverse time step, the cumulative regret grows at most on the order of the square root of the time horizon. Consequently, the average regret per round tends to zero. The same framework yields a lazy-projection variant with comparable guarantees and a dynamic-regret bound that remains controlled when the comparator sequence changes slowly. The approach is then specialized to repeated games, producing the Generalized Infinitesimal Gradient Ascent (GIGA) algorithm that inherits the regret bound and is proven universally consistent even against adaptive opponents.

These results matter because they supply a simple, widely understood technique—gradient descent with projection—that solves a broader class of online problems than traditional experts algorithms and can achieve tighter bounds when the geometry of the feasible set is favorable. The work also clarifies how experts methods can be converted into online linear-programming solvers, though the resulting bounds may be weaker. Decision makers gain a concrete, implementable procedure that guarantees sublinear regret without requiring advance knowledge of the cost sequence.

The article recommends extending the method to non-Euclidean geometries and stronger adaptive schemes such as WoLF. Further empirical validation on larger repeated games and industrial planning instances would strengthen before widespread deployment. The main limitations are the assumptions of a closed bounded feasible set, differentiable costs, and known gradient oracles; performance guarantees weaken when these conditions are relaxed or when gradient norms are large.

Carnegie Mellon University nonconvex programming languages stochastic gradient descent online convex programming generalized infinitesimal gradient ascent online linear programming problem

Zinkevich (2003).pdf

Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). This seminal work establishes the foundational Hedge algorithm and regret-minimization framework for online learning with expert advice that the source generalizes to continuous convex sets.
Paper: Markov Games as a Framework for Multi-Agent Reinforcement Learning, M. Littman (1994). This paper formalizes repeated competitive games and minimax learning, providing the game-theoretic context in which the source analyzes universal consistency and GIGA.
Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). This work develops finite-time cumulative regret bounds in sequential decision-making, introducing key no-regret evaluation techniques fundamental to online learning analysis.

Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). This monograph provides a comprehensive modern survey of the online convex optimization paradigm, directly building upon and expanding the projected gradient descent framework founded in the source.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). This paper extends online gradient descent and online convex programming by introducing adaptive, coordinate-specific learning rates via the AdaGrad algorithm.
Paper: A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning, Stephane Ross et al. (2010). This work applies no-regret online convex learning guarantees to solve sequential imitation learning and structured prediction via the DAgger algorithm.
Paper: Online Passive-Aggressive Algorithms, K. Crammer et al. (2003). This paper presents the Passive-Aggressive algorithm family, applying online convex optimization and projection-based updates to real-time classification and regression tasks.
Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). This work advances online and stochastic gradient optimization by introducing predictive variance reduction techniques to achieve linear convergence on convex objectives.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). This paper builds on the foundations of sequential convex optimization and confidence-directed exploration to develop improved algorithms for linear stochastic bandits.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). This survey provides an extensive treatment of first-order stochastic gradient methods and computational tradeoffs for large-scale convex and non-convex machine learning.

Cover for Online Convex Programming and Generalized Infinitesimal Gradient Ascent

Abstract

Convex programming involves a convex set F ⊆ ℝⁿ and a convex function c : F → ℝ. The goal of convex programming is to find a point in F which minimizes c. In this paper, we introduce online convex programming. In online convex programming, the convex set is known in advance, but in each step of some repeated optimization problem, one must select a point in F before seeing the cost function for that step. This can be used to model factory production, farm production, and many other industrial optimization problems where one is unaware of the value of the items produced until they have already been constructed. We introduce an algorithm for this domain, apply it to repeated games, and show that it is really a generalization of infinitesimal gradient ascent, and the results here imply that generalized infinitesimal gradient ascent (GIGA) is universally consistent.

Topics

nonconvex programming languages stochastic gradient descent

Keywords

online convex programming generalized infinitesimal gradient ascent online linear programming problem greedy projection algorithm dynamic regret relative loss bounds computational learning theory gradient dynamics experts algorithms

1 Introduction
2 Online Convex Programming
2.1 Analyzing the Performance of the Algorithm
2.2 Regret Against a Dynamic Strategy
2.3 Lazy Projection
3 Generalized Infinitesimal Gradient Ascent
3.1 Repeated Games
3.2 Oblivious Deterministic Environments
3.3 Formulating a Repeated Game as an Online Linear Program
3.4 Self-Oblivious Behavior
3.5 Lazy Projection and Fictitious Play
4 Converting Old Algorithms
4.1 Formal Definitions
4.2 Converting an OLPA to an Online Convex Programming Algorithm
5 Related Work
6 Conclusions and Future Work
Acknowledgements
References
A Proof of Dynamic Bounds
B Proof of Lazy Projection
B.1 A Motivating Example
B.2 Geometric Lemmas
B.3 Completing the Proof
C Proof of Universal Consistency

Knowls

Knowl 1 — Online Convex Programming and Regret
definition
An online convex programming (OCP) problem is defined over a non-empty, closed, and bounded convex feasible set $F \subset \mathbb{R}^n$ with Euclidean diameter: $\|F\| = \max_{x,y \in F} \|x - y\|_2$

The optimization proceeds in discrete rounds $t = 1, 2, \dots$ :
1. At each step $t$ , the online algorithm selects a vector $x^t \in F$ .
2. The environment subsequently reveals a convex cost function $c^t : F \to \mathbb{R}$ , which is differentiable with bounded gradient norm $\|\nabla c^t(x)\|_2 \le \|\nabla c\| = \sup_{x \in F, t \ge 1} \|\nabla c^t(x)\|_2$ (or subdifferentiable with a computable subgradient $g^t$ ).
3. The algorithm incurs cost $c^t(x^t)$ .
The total cost incurred by an algorithm $A$ up to time horizon $T$ is: $C_A(T) = \sum_{t=1}^T c^t(x^t)$

The cost of any fixed static comparator $x \in F$ is $C_x(T) = \sum_{t=1}^T c^t(x)$ .

The regret (static regret) of algorithm $A$ with respect to the optimal single static decision in hindsight is: $R_A(T) = C_A(T) - \min_{x \in F} C_x(T) = \sum_{t=1}^T c^t(x^t) - \min_{x \in F} \sum_{t=1}^T c^t(x)$ An algorithm is no-regret (or Hannan consistent) if $\limsup_{T \to \infty} \frac{R_A(T)}{T} \le 0$ .
Knowl 2 — Static Regret Bound for Greedy Projection
theoretical result
Let $F \subset \mathbb{R}^n$ be a closed, bounded, non-empty convex feasible set with diameter $\|F\| = \max_{x,y \in F} \|x - y\|_2$ , and let $\{c^1, c^2, \dots\}$ be an arbitrary sequence of convex cost functions with gradient norms bounded by $\|\nabla c\| = \sup_{x \in F, t \ge 1} \|\nabla c^t(x)\|_2$ .

If the Greedy Projection algorithm is executed with step sizes $\eta_t = t^{-1/2}$ for $t \ge 1$ , then for any time horizon $T \ge 1$ , the static regret $R_G(T) = \sum_{t=1}^T c^t(x^t) - \min_{x^* \in F} \sum_{t=1}^T c^t(x^*)$ is bounded by: $R_G(T) \le \frac{\|F\|^2 \sqrt{T}}{2} + \left(\sqrt{T} - \frac{1}{2}\right) \|\nabla c\|^2$

As a consequence, the average regret approaches zero: $\limsup_{T \to \infty} \frac{R_G(T)}{T} \le 0$ yielding a worst-case regret of order $O(\sqrt{T})$ against an arbitrary sequence of convex cost functions.
Knowl 3 — Greedy Projection Algorithm for Online Convex Programming
algorithm
The Greedy Projection algorithm (online projected gradient descent) updates its decision at each round by performing a gradient step along the cost function revealed at that round and projecting the updated vector back onto the feasible set.

Let $F \subset \mathbb{R}^n$ be a closed convex set and $P: \mathbb{R}^n \to F$ be the Euclidean projection operator defined by $P(y) = \arg\min_{x \in F} \|x - y\|_2$ .
Input: Feasible convex set $F$ , sequence of learning rates $\{\eta_t\}_{t \ge 1}$
Output: Decisions $x^t \in F$ at each time step $t$
Initialize $x^1 \in F$ arbitrarily
for $t = 1, 2, \dots$ do
    Play $x^t$
    Receive convex cost function $c^t$ (or its gradient $\nabla c^t(x^t)$ )
    Compute $x^{t+1} = P(x^t - \eta_t \nabla c^t(x^t))$
end for
At each step $t$ , the algorithm takes the gradient $\nabla c^t(x^t)$ , steps by $-\eta_t \nabla c^t(x^t)$ , and projects the resulting point back onto $F$ using Euclidean projection.
Knowl 4 — Dynamic Regret Bound for Greedy Projection
theoretical result
The performance of Greedy Projection can be bounded against a time-varying sequence of decisions. For any sequence of vectors $(x^1, \dots, x^T) \in F^T$ , its path length is: $\text{PathLength}(x^1, \dots, x^T) = \sum_{t=1}^{T-1} \|x^t - x^{t+1}\|_2$ Let $\mathcal{A}(T, L)$ be the set of comparator sequences of length $T$ with path length at most $L$ : $\mathcal{A}(T, L) = \left\{ (z^1, \dots, z^T) \in F^T \;\middle|\; \sum_{t=1}^{T-1} \|z^t - z^{t+1}\|_2 \le L \right\}$ The dynamic regret of an algorithm $A$ against $\mathcal{A}(T, L)$ is: $R_A(T, L) = \sum_{t=1}^T c^t(x^t) - \min_{(z^1, \dots, z^T) \in \mathcal{A}(T, L)} \sum_{t=1}^T c^t(z^t)$

If the Greedy Projection algorithm is run with a fixed learning rate $\eta > 0$ , its dynamic regret satisfies: $R_G(T, L) \le \frac{7\|F\|^2}{4\eta} + \frac{L \|F\|}{\eta} + \frac{T \eta \|\nabla c\|^2}{2}$ where $\|F\| = \max_{x,y \in F} \|x - y\|_2$ and $\|\nabla c\| = \sup_{x \in F, t \ge 1} \|\nabla c^t(x)\|_2$ .
Knowl 5 — Regret Bound and Universal Consistency of GIGA
theoretical result
In a repeated normal-form game with player action set $A = \{1, \dots, n\}$ , opponent action set $Y$ , and utility function $u : A \times Y \to \mathbb{R}$ , define the utility span: $|u| = \max_{(a,y) \in A \times Y} u(a, y) - \min_{(a,y) \in A \times Y} u(a, y)$ The simplex feasible set $F = \Delta(A)$ has diameter $\|F\| \le \sqrt{2}$ , and the utility gradient norm satisfies $\|\nabla c\| \le \sqrt{|A|}|u|$ .

When Generalized Infinitesimal Gradient Ascent (GIGA) uses step sizes $\eta_t = t^{-1/2}$ , its expected regret with respect to any fixed pure action $a \in A$ against any oblivious deterministic environment $\rho : H \to \Delta(Y)$ over $T$ rounds is bounded by: $\mathbb{E}_{h \in \mathcal{F}_{\sigma, \rho}} [R^{* \to a}(h|T)] \le \sqrt{T} + \left(\sqrt{T} - \frac{1}{2}\right) |A| |u|^2$

Because GIGA is a self-oblivious behavior (meaning its mixed strategy at round $t$ depends strictly on the opponent's historical action sequence and not on its own past sampled actions), achieving sublinear expected regret against oblivious deterministic environments guarantees that GIGA is universally consistent: for every $\epsilon > 0$ , there exists $T$ such that against any (including arbitrary and adaptive) environment $\rho$ : $\Pr_{h \in \mathcal{F}_{\sigma, \rho}}\left[ \forall t > T, \; \frac{R(h|t)}{t} > \epsilon \right] < \epsilon$
Knowl 6 — Generalized Infinitesimal Gradient Ascent (GIGA) for Repeated Games
algorithm
The Generalized Infinitesimal Gradient Ascent (GIGA) algorithm applies online convex optimization to repeated games with arbitrary finite action sets.

Let $A = \{1, \dots, n\}$ be the player's action set, $Y$ be the opponent's action set, and $u: A \times Y \to \mathbb{R}$ be the utility function. The mixed strategy space is the $(n-1)$ -dimensional simplex $F = \Delta(A) = \{x \in \mathbb{R}^n \mid x_i \ge 0, \sum_{i=1}^n x_i = 1\}$ . The projection operator is $P(y) = \arg\min_{x \in \Delta(A)} \|x - y\|_2$ .
Input: Action set $A = \{1, \dots, n\}$ , sequence of step sizes $\{\eta_t\}_{t \ge 1}$
Output: Action choices $a_t \in A$ at each round $t$
Initialize $x^1 \in \Delta(A)$ arbitrarily
for $t = 1, 2, \dots$ do
    Sample and play action $i \in A$ with probability $x^t_i$
    Observe opponent action $h_{t,2} \in Y$
    for each $i \in A$ do
         $y^{t+1}_i = x^t_i + \eta_t u(i, h_{t,2})$
    end for
    Compute $x^{t+1} = P(y^{t+1})$
end for
GIGA uses gradient ascent on the linear utility function induced by the opponent's observed action, followed by Euclidean projection onto the probability simplex.
Knowl 7 — Lazy Projection Algorithm for Online Convex Programming
algorithm
The Lazy Projection algorithm maintains an unconstrained state vector $y^t \in \mathbb{R}^n$ that accumulates negative gradient steps directly in Euclidean space without intermediate projections, mapping to the feasible set $F$ only when outputting the current decision.

Let $F \subset \mathbb{R}^n$ be a closed convex set and $P(y) = \arg\min_{x \in F} \|x - y\|_2$ be the Euclidean projection operator.
Input: Feasible convex set $F$ , sequence of learning rates $\{\eta_t\}_{t \ge 1}$
Output: Decisions $x^t \in F$ at each time step $t$
Initialize $x^1 \in F$ arbitrarily, and set $y^1 = x^1$
for $t = 1, 2, \dots$ do
    Play $x^t$
    Receive convex cost function $c^t$ (or its gradient $\nabla c^t(x^t)$ )
    Compute $y^{t+1} = y^t - \eta_t \nabla c^t(x^t)$
    Compute $x^{t+1} = P(y^{t+1})$
end for
Unlike Greedy Projection, the unprojected vector $y^t$ does not restart from the boundary projection $x^t$ on each round.
Knowl 8 — Regret Bound for Lazy Projection
theoretical result
Let $F \subset \mathbb{R}^n$ be a closed, bounded, non-empty convex feasible set with diameter $\|F\| = \max_{x,y \in F} \|x - y\|_2$ , and let $\{c^1, c^2, \dots\}$ be an arbitrary sequence of convex cost functions with $\|\nabla c\| = \sup_{x \in F, t \ge 1} \|\nabla c^t(x)\|_2$ .

When Lazy Projection is run with a fixed learning rate $\eta > 0$ , its static regret $R_L(T) = \sum_{t=1}^T c^t(x^t) - \min_{x^* \in F} \sum_{t=1}^T c^t(x^*)$ satisfies: $R_L(T) \le \frac{\|F\|^2}{2\eta} + \frac{T \eta \|\nabla c\|^2}{2}$

Choosing $\eta = \frac{\|F\|}{\|\nabla c\|\sqrt{T}}$ minimizes the bound to: $R_L(T) \le \|F\| \|\nabla c\| \sqrt{T}$
Knowl 9 — Z Fictitious Play
algorithm
The Z Fictitious Play algorithm is an application of Lazy Projection to repeated matrix games, providing a smooth alternative to standard fictitious play.

Let $A = \{1, \dots, n\}$ be the player's action set, $Y$ be the opponent's action set, and $u : A \times Y \to \mathbb{R}$ be the utility function. At step $t$ , the algorithm maintains the cumulative historical payoff for each action and projects this vector onto the probability simplex $\Delta(A) = \{x \in \mathbb{R}^n \mid x_i \ge 0, \sum_{i=1}^n x_i = 1\}$ .
Input: Action set $A = \{1, \dots, n\}$ , learning parameter $\eta > 0$
Output: Mixed strategy $x^t \in \Delta(A)$ at each round $t$
for $t = 1, 2, \dots$ do
    for each action $i \in A$ do
        Compute $y^t_i = \sum_{j=1}^{t-1} \eta u(i, h_{j,2})$
    end for
    Compute $x^t = \arg\min_{x \in \Delta(A)} \|x - y^t\|_2$
    Sample and play action according to distribution $x^t$
    Observe opponent action $h_{t,2}$
end for
Knowl 10 — Online Convex Programming via Online Linear Programming and Sampling
model/method
An online linear programming algorithm (OLPA) outputting distributions $D^t \in \Delta(F)$ over a convex feasible set $F$ can be converted into an online convex programming (OCP) algorithm against convex cost functions $c^t$ :
1. Exact Conversion: At round $t$ , play the expected vector $x^t = \mathbb{E}_{X \sim D^t}[X] \in F$ and pass the cost vector $\nabla c^t(x^t)$ to the OLPA. Because the function is convex, $\mathbb{E}_{X \sim D^t}[c^t(X)] \ge c^t(x^t)$ , guaranteeing that the linear cost linearization bounds the convex regret.
2. Approximate Conversion (Sampling): When the expected vector $x^t$ cannot be computed in closed form, sample $s_t$ points $X_1, \dots, X_{s_t} \sim D^t$ independently, play the empirical mean $z^t = \frac{1}{s_t} \sum_{i=1}^{s_t} X_i$ , and feed $\nabla c^t(z^t)$ to the OLPA.
Setting the number of samples to $s_t = t$ per round yields an expected regret bound of: $\mathbb{E}[R_{\text{Approx}}(T)] \le R_{\text{Exact}}(T) + \|\nabla c\| \|F\| (2\sqrt{T} - 1)$ where $\|F\| = \max_{x,y \in F} \|x - y\|_2$ and $\|\nabla c\| = \sup_{x \in F, t \ge 1} \|\nabla c^t(x)\|_2$ .

Coverage note — Algorithm 5 (the naive reduction from expert algorithms to online linear programs by assigning one expert per polytope vertex) and supporting geometric lemmas (Lemmas 4–7, Azuma's lemma, and Doob's decomposition) were omitted as they are standard background or proof apparatus for the main results.

References

1.S. Amari. Natural gradient works efficiently in learning. Neural Computation, 10:251–276, 1998.
2.N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Online oblivious routing. Submitted, 2003.
3.D. Blackwell. An analog of the minimax theorem for vector payoffs. South Pacific J. of Mathematics, pages 1–8, 1956.
4.M. Bowling and M. Veloso. Convergence of gradient dynamics with a variable learning rate. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 27–34, 2001.
5.N. Cesa-Bianchi, P. Long, and M. K. Warmuth. Worst-case quadratic bounds for on-line prediction of linear functions by gradient descent. IEEE Transactions on Neural Networks, 7:604–619, 1994.
6.S. Della Pietra, V. Della Pietra, and J. Lafferty. Duality and auxilary functions for Bregman distances. Technical Report CMU-CS-01-109, Carnegie Mellon University, 1999.
7.D. Foster. A proof of calibration via Blackwell's approachability theorem. In Games and Economic Behavior, volume 29, pages 73–79, 1999.
8.D. Foster and R. Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 29(1):7–35, 1999.
9.Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. In Games and Economic Behavior, volume 29, pages 79–103, 1999.
10.D. Fudenberg and D. Levine. Universal consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19:1065–1089, 1995.
11.D. Fudenberg and D. Levine. The Theory of Learning in Games. MIT Press, 1998.
12.D. Fudenberg and D. Levine. Conditional universal consistency. Games and Economic Behavior, 29, 1999.
13.C. Gentile and M. Warmuth. Proving relative loss bounds for online learning algorithms by the Bregman divergence. In The 13th Annual Conference on Computational Learning Theory, June 2000. Tutorial.
14.J. Hannan. Approximation to bayes risk in repeated play. Annals of Mathematics Studies, 39:97–139, 1957.
15.S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1127–1150, 2000.
16.S. Hart and A. Mas-Colell. A general class of adaptive strategies. Journal of Economic Theory, 98:26–54, 2001.
17.M. Herbster and M. K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1:281–309, 2001.
18.W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13–30, March 1963.
19.A. Kalai and S. Vempala. Geometric algorithms for online optimization. Technical report, MIT, 2002.
20.J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132:1–64, 1997.
21.J. Kivinen and M. Warmuth. Relative loss bounds for multidimensional regression problems. Machine Learning Journal, 45:301–329, 2001.
22.D. Levine. Personal communication, 2003.
23.N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In Proceedings of the Second Annual Conference on Computational Learning Theory, 1989.
24.R. Mahony and R. Williamson. Prior knowledge and preferential structures in gradient descent algorithms. Journal of Machine Learning Research, 1:311–355, 2001.
25.S. Singh, M. Kearns, and Y. Mansour. Nash convergence of gradient dynamics in general-sum games. In Proceedings of the Sixteenth Conference in Uncertainty in Artificial Intelligence, pages 541–548, 2000.

Citation

MLA

Zinkevich, M. “Online Convex Programming and Generalized Infinitesimal Gradient Ascent”. International Conference on Machine Learning, 2003, pp. 928–35, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9960.

APA

Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. International Conference on Machine Learning, 928–935. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9960

Chicago

Zinkevich, M. 2003. “Online Convex Programming and Generalized Infinitesimal Gradient Ascent”. International Conference on Machine Learning, 928–35. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9960.

Harvard

Zinkevich, M. (2003) “Online convex programming and generalized infinitesimal gradient ascent”, International Conference on Machine Learning, pp. 928–935. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9960.

Vancouver

1. Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. International Conference on Machine Learning 928–935

BibTeX

@article{zinkevich2003online,
  title = {Online convex programming and generalized infinitesimal gradient ascent},
  author = {Zinkevich, Martin},
  year = {2003},
  journal = {International Conference on Machine Learning},
  pages = {928-935},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9960}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Online Convex Programming and Generalized Infinitesimal Gradient Ascent

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Online Convex Programming and Regret

Knowl 2 — Static Regret Bound for Greedy Projection

Knowl 3 — Greedy Projection Algorithm for Online Convex Programming

Knowl 4 — Dynamic Regret Bound for Greedy Projection

Knowl 5 — Regret Bound and Universal Consistency of GIGA

Knowl 6 — Generalized Infinitesimal Gradient Ascent (GIGA) for Repeated Games

Knowl 7 — Lazy Projection Algorithm for Online Convex Programming

Knowl 8 — Regret Bound for Lazy Projection

Knowl 9 — Z Fictitious Play

Knowl 10 — Online Convex Programming via Online Linear Programming and Sampling

References

Citation

BibTeX

Access the Paper