Online Convex Optimization

Imagine choosing a portfolio every morning before the markets open. You pick your weights, the prices move, and only then do you see how costly your choice was. Tomorrow you must choose again — still blind to what the next loss function will be.

This is the setting of online convex optimization (OCO). At each round $t = 1, 2, \dots, T$ you choose a point $x_t$ from a convex set $\mathcal{K}$. An adversary then reveals a convex loss function $f_t$, and you pay $f_t(x_t)$. You never see $f_t$ before committing.

The goal is not to minimize total loss — the adversary can always make that large. The goal is to minimize regret: the extra cost you pay compared to the single best fixed point $x^*$ in hindsight,

$$\text{Regret}_T = \sum_{t=1}^{T} f_t(x_t) - \min_{x \in \mathcal{K}} \sum_{t=1}^{T} f_t(x).$$

A regret that grows only as $O(\sqrt{T})$ means your average extra cost per round vanishes — you are essentially as good as the best fixed strategy, without ever knowing the future.

The demo below runs Online Gradient Descent (OGD) against a sequence of quadratic loss functions $f_t(x) = (x - c_t)^2$ on the interval $[-1, 1]$. Each round, a new center $c_t$ is revealed after you (OGD) have already committed to $x_t$.

<!-- {{c_demo_title}} -->
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="rounds-label">{{label_rounds}}: <strong id="round-num">0</strong></span>
</div>
<canvas id="chart" width="560" height="200" aria-label="{{aria_chart}}"></canvas>
<div class="legend">
  <span class="dot ogd"></span> {{legend_ogd}}
  <span class="dot fixed"></span> {{legend_fixed}}
  <span class="dot rand"></span> {{legend_rand}}
</div>
<div class="stats" id="stats">{{hint_start}}</div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.rounds-label { font-size: .88rem; color: #555; margin-left: auto; }
canvas { display: block; width: 100%; border: 1px solid #d0d7de; border-radius: 8px;
         background: #f8fafc; max-width: 560px; }
.legend { display: flex; gap: 1rem; font-size: .8rem; color: #444; margin: .4rem 0; flex-wrap: wrap; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; margin-right: 4px; vertical-align: middle; }
.dot.ogd   { background: #2563eb; }
.dot.fixed { background: #dc2626; }
.dot.rand  { background: #16a34a; }
.stats { font-size: .88rem; color: #333; min-height: 2.4em; line-height: 1.5; }
@media (prefers-color-scheme: dark) {
  body { color: #e2e8f0; }
  canvas { background: #1e293b; border-color: #334155; }
  .legend { color: #94a3b8; }
  .stats { color: #cbd5e1; }
  .rounds-label { color: #94a3b8; }
  button.ghost { background: #1e293b; color: #93c5fd; border-color: #93c5fd; }
}

// Code not found

Watch the cumulative regret curve. It grows, but notice how the average regret (regret divided by round number) steadily falls toward zero. That is the sublinear guarantee in action: $O(\sqrt{T})$ total regret means $O(1/\sqrt{T})$ per round.

Compare OGD against a fixed strategy that never updates, and against a random player that picks a fresh point each round. OGD wins cleanly over time.

How good can an online algorithm be? The answer depends on what you know about the loss functions.

Online Gradient Descent (OGD), proposed by Zinkevich in 2003, is the simplest algorithm: after paying $f_t(x_t)$, compute the gradient $g_t = \nabla f_t(x_t)$ and update

$$x_{t+1} = \Pi_{\mathcal{K}}\!\left(x_t - \eta\, g_t\right),$$

where $\Pi_{\mathcal{K}}$ projects back onto $\mathcal{K}$ and $\eta > 0$ is the step size. With step size $\eta = D / (G\sqrt{T})$ (where $D$ is the diameter of $\mathcal{K}$ and $G$ bounds the gradient norm), this achieves

$$\text{Regret}_T \le \frac{DG\sqrt{T}}{2} = O(\sqrt{T}).$$

• Is $O(\sqrt{T})$ tight? Yes. A simple adversary — alternating the loss between two shapes — forces any deterministic algorithm to pay $\Omega(\sqrt{T})$ regret, so OGD is minimax optimal.
• Strongly convex losses let you do better: if every $f_t$ is $\lambda$-strongly convex, a logarithmic step schedule achieves $O(\log T)$ regret.
• Exp-concave losses (e.g., log loss in prediction) admit $O(d \log T)$ regret via the ONS (Online Newton Step) algorithm of Hazan et al. (2007).
• The connection to PAC learning: in the batch setting you minimize average loss over a fixed distribution; OCO is the adversarial, sequential version of the same idea — and many PAC guarantees follow by reducing to OCO.

"Make a decision, then see the cost" is the hidden shape of an enormous number of real problems:

• Adaptive optimizers in deep learning: AdaGrad, Adam, and RMSProp are all instances of OCO algorithms. Their $1/\sqrt{T}$ per-coordinate learning-rate decay is the OCO $O(\sqrt{T})$ regret bound in disguise.
• Online portfolio management: the Cover (1991) universal portfolio and its OCO descendants rebalance daily with $O(\log T)$ regret against the best fixed mixture of assets.
• Ad auction bidding: each impression is a round; OCO-based bidders adjust bids to maximize revenue under budget constraints, with sublinear regret against any fixed bidding strategy.
• Routing and scheduling: packets, jobs, and vehicles arrive sequentially; OCO methods adapt routing weights round by round without knowing future demand.
• Recommendation and ranking: each query is a round with a convex surrogate loss; online updates beat fixed ranking functions over long horizons.

Understand OCO and you understand the theoretical backbone of most modern adaptive learning algorithms — including the ones training the neural networks behind every large language model.

Online convex optimization captures something deep: even when an adversary picks the losses after watching your strategy, a simple gradient update keeps you competitive with the best fixed choice — the gap grows only as $O(\sqrt{T})$, vanishing on a per-round basis.

That guarantee is not just theoretical elegance. It is why AdaGrad converges, why online portfolios do not catastrophically underperform, and why sequential bidding systems remain profitable over millions of auctions.

The next time you see a learning-rate schedule decay as $1/\sqrt{t}$, you are looking at OCO theory made practical — proof that deciding before you know the cost is a solvable problem, with a tight and beautiful answer.