A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Online learning is a sequential prediction framework where a learner makes decisions one at a time, observes a loss after each decision, and aims to minimize cumulative regret — the difference between the learner's total loss and the total loss of the best fixed strategy in hindsight. Unlike PAC learning, online learning makes no distributional assumptions: the sequence of examples can be adversarially chosen. The fundamental result is that O(sqrt(T)) regret is achievable and optimal for many problems, meaning the learner's average loss converges to the best fixed strategy's loss at rate 1/sqrt(T). This framework unifies prediction, optimization, and game theory.
PAC learning assumes data is drawn i.i.d. from a fixed distribution — a strong assumption that may not hold in practice. Online learning drops this assumption entirely, operating in a sequential, potentially adversarial setting. The learner and the environment take turns: at each round t, the learner chooses an action (prediction, hypothesis, or strategy), the environment reveals a loss, and the learner updates. There are no distributional assumptions — the environment can be an adversary that chooses the worst possible sequence for the learner.
The performance measure in this adversarial setting cannot be absolute loss, because a sufficiently malicious adversary can impose high loss on any learner. Instead, the learner is measured by regret: the difference between its cumulative loss and the cumulative loss of the best fixed action in hindsight. Formally, Regret(T) = sum_{t=1}^{T} loss(learner_t) - min_{h in H} sum_{t=1}^{T} loss(h_t). The comparator is the single best fixed hypothesis over the entire sequence — the learner does not need to beat every hypothesis, just approach the best one's performance.
The central result is that O(sqrt(T)) regret is achievable for a wide class of problems. For prediction with expert advice (choosing among N experts each round), the Hedge algorithm achieves regret O(sqrt(T * ln N)). For online convex optimization (choosing a point in a convex set, then observing a convex loss), online gradient descent achieves regret O(sqrt(T)). These bounds hold against any adversary — no distributional assumption is needed. The sqrt(T) rate is also optimal: for most problems, no algorithm can achieve o(sqrt(T)) regret in the worst case.
The implications extend far beyond sequential prediction. Online learning algorithms can be converted to batch learning algorithms (online-to-batch conversion), providing an alternative route to generalization bounds that does not require uniform convergence. The regret framework also connects to game theory — no-regret strategies correspond to Nash equilibria in repeated games — and to optimization, where online gradient descent is the template for stochastic gradient descent. The framework's generality and adversarial robustness make it a cornerstone of modern theoretical machine learning, complementing the distributional assumptions of PAC learning with guarantees that hold in the worst case.