Online Gradient Descent

OGD processes data one sample at a time, computing the gradient of the loss function and updating weights immediately. This contrasts with batch gradient descent, which requires the full dataset, and mini-batch, which uses subsets.

• Update rule: w_{t+1} = w_t - η ∇L(w_t, x_t, y_t)
• Each step uses only the current observation (x_t, y_t)
• No requirement to store historical data for training
• Naturally handles streaming data pipelines and unbounded datasets

OGD is theoretically analyzed through regret, which measures the cumulative loss of the online algorithm compared to the best fixed parameter vector in hindsight.

• Regret bound: For convex losses, OGD achieves O(√T) regret over T rounds
• Guarantees that the average performance converges to that of the optimal batch solution
• Strongly convex loss functions yield tighter O(log T) regret bounds
• Provides mathematical assurance that online learning is not arbitrarily worse than batch training

Modern OGD implementations use adaptive step sizes that adjust per-parameter based on historical gradient information, improving convergence on sparse or non-stationary data.

• AdaGrad: Scales learning rates inversely with the sum of squared past gradients, effective for sparse features
• RMSProp: Uses exponentially decaying average of squared gradients to handle non-stationary objectives
• Adam: Combines momentum and adaptive learning rates, widely used in online deep learning
• Adaptive methods automatically decay the learning rate for frequently updated parameters

When parameters must satisfy constraints (e.g., L2 norm bounds, probability simplex), OGD uses a projection step after each gradient update to map weights back into the feasible set.

• Projected OGD: w_{t+1} = Π_Ω(w_t - η ∇L_t) where Π_Ω projects onto constraint set Ω
• Common in online SVM and bounded-regret portfolio optimization
• Enforces structural constraints like non-negativity or sparsity budgets
• Projection guarantees the updated model remains within the valid parameter space

OGD is closely related to Stochastic Gradient Descent (SGD) but differs in its data model. OGD assumes an adversarial or arbitrary data stream, while SGD assumes i.i.d. samples from a fixed distribution.

• OGD makes no statistical assumptions about data order or distribution
• SGD's convergence guarantees rely on independent, identically distributed samples
• In practice, OGD and SGD with a batch size of 1 are algorithmically identical
• OGD's adversarial framework provides stronger worst-case guarantees for concept drift scenarios

OGD is the canonical algorithm in the broader field of Online Convex Optimization (OCO), which models learning as a repeated game between a learner and an environment.

• At each round t: learner chooses w_t, environment reveals convex loss f_t(w_t)
• Learner suffers loss and updates strategy for the next round
• OGD with appropriate step size achieves sublinear regret in this framework
• Forms the mathematical basis for real-time bidding, dynamic pricing, and online portfolio selection

The foundational optimization algorithm from which Online Gradient Descent derives. While standard SGD processes data in mini-batches, Online Gradient Descent operates on a single sample per update, making it suitable for streaming environments. The key distinction is that SGD typically requires multiple passes (epochs) over a static dataset, whereas Online Gradient Descent processes each data point exactly once as it arrives, never revisiting past examples.

A critical hyperparameter strategy that controls how aggressively model weights are updated with each gradient step. In online settings, a decaying learning rate is essential for convergence—starting larger to quickly adapt to new patterns, then shrinking to fine-tune. Common schedules include:

• Time-based decay: α = α₀ / (1 + k·t)
• Step decay: Reduce by factor every N samples
• Adaptive methods: AdaGrad, RMSprop, Adam, which adjust per-parameter rates based on gradient history

The theoretical framework for evaluating online learning algorithms. Regret measures the cumulative difference between the algorithm's performance and the best fixed-in-hindsight decision. Online Gradient Descent achieves sublinear regret—meaning the average regret per round approaches zero as the number of rounds increases. This provides a mathematical guarantee that the algorithm will eventually perform as well as the optimal static strategy, even as the environment shifts.

The choice of loss function directly shapes how Online Gradient Descent interprets prediction errors. Common options include:

• Mean Squared Error (MSE): For regression tasks, penalizes large errors quadratically
• Log Loss (Cross-Entropy): For binary classification, heavily penalizes confident misclassifications
• Hinge Loss: For maximum-margin classifiers, only penalizes predictions on the wrong side of the decision boundary
• Huber Loss: Combines MSE and absolute error, providing robustness to outliers in noisy streaming data

Online Gradient Descent's primary advantage is its inherent ability to track concept drift—changes in the relationship between features and targets over time. Unlike batch-trained models that grow stale, the algorithm continuously adjusts its decision boundary. However, the learning rate creates a fundamental trade-off: a high rate enables rapid adaptation to genuine drift but risks overfitting to noise, while a low rate provides stability but may fail to track legitimate shifts in the data distribution.

Online Gradient Descent is highly sensitive to feature magnitudes. Without proper scaling, features with larger ranges dominate the gradient updates, slowing convergence. In streaming contexts, where the full data distribution is unknown upfront, running statistics are essential:

• Running mean and variance: Continuously updated with each new sample
• Online standardization: (x - μ_running) / σ_running
• Min-max scaling with bounds: Track running min/max with periodic resets to handle distribution shifts