PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning: A Comprehensive Survey

Steven C. H. Hoi, Doyen Sahoo, Jing Lu, Peilin Zhao

arXiv:1802.02871v2cs.LG

TL;DR

Batch learning can be costly to retrain as data arrives, motivating scalable incremental approaches. This survey systematically reviews online learning, organizes methods by feedback type, and focuses mainly on supervised learning while identifying open issues.

  • Problem

    Batch learning requires expensive retraining for new data, creating a need to understand incremental online learning approaches for evolving data streams.

    Source: §1 · p. 1

  • Method

    The paper systematically reviews online learning literature and categorizes methods into supervised, limited-feedback, and unsupervised learning.

    Source: §1 · p. 2, §10.1 · p. 72

  • Results

    The survey distills core ideas and key principles of online learning, focusing mainly on supervised learning while briefly covering limited-feedback and unsupervised settings.

    Source: §1 · p. 2, §10.1 · p. 72

  • Takeaways & Limitations

    Online learning provides a theory-grounded framework for updating models incrementally as new data arrives, with methods organized by the feedback available to the learner.

    Source: §1 · p. 2, §10.1 · p. 72

    The proposed taxonomy may not fully cover all existing online learning work because precise categorization is challenging.

    Source: §1.3 · p. 5

Abstract

from arXiv · show

Online learning represents an important family of machine learning algorithms, in which a learner attempts to resolve an online prediction (or any type of decision-making) task by learning a model/hypothesis from a sequence of data instances one at a time. The goal of online learning is to ensure that the online learner would make a sequence of accurate predictions (or correct decisions) given the knowledge of correct answers to previous prediction or learning tasks and possibly additional information. This is in contrast to many traditional batch learning or offline machine learning algorithms that are often designed to train a model in batch from a given collection of training data instances. This survey aims to provide a comprehensive survey of the online machine learning literatures through a systematic review of basic ideas and key principles and a proper categorization of different algorithms and techniques. Generally speaking, according to the learning type and the forms of feedback information, the existing online learning works can be classified into three major categories: (i) supervised online learning where full feedback information is always available, (ii) online learning with limited feedback, and (iii) unsupervised online learning where there is no feedback available. Due to space limitation, the survey will be mainly focused on the first category, but also briefly cover some basics of the other two categories. Finally, we also discuss some open issues and attempt to shed light on potential future research directions in this field.

1. Introduction

Online learning addresses the scalability challenges of batch machine learning by updating models incrementally as sequential data arrives. The survey organizes online learning by task feedback and supervision, reviews its applications and literature, and focuses especially on supervised and partial-feedback settings.

1. Introduction

  • Online learning updates models incrementally and efficiently as new data arrives, addressing batch learning’s costly retraining and poor scalability for large, rapidly evolving data streams.The survey describes online learning as theoretically grounded, easy to understand, and simple to implement, with rigorous regret bounds.Source: §1 · pp. 1–2
  • The survey systematically reviews online learning literature, emphasizing online supervised learning and partial-feedback learning while acknowledging that its taxonomy may not cover every existing work.Its stated goal is to distill core methodological and application ideas for primarily machine-learning audiences.Source: §1 · p. 2, §1.3 · p. 5

1.2 Tasks and Applications

  • The survey defines online learning as sequential prediction and model updating for future data, covering supervised, regression, bandit, unsupervised, recommender, ranking, and reinforcement-learning tasks.Applications include online SVM training, streaming analytics with concept drift, financial time series, portfolio selection, recommendation, and online clustering.Source: §1.1 · p. 2, §1.2 · p. 3

1.3 Taxonomy

  • The survey classifies online learning into full-feedback supervised learning, limited-feedback learning requiring exploration–exploitation tradeoffs, and unsupervised learning without labels or additional feedback.Figure 1 summarizes a taxonomy grounded in learning, optimization, and game theory; unsupervised methods include online clustering, dimension reduction, and anomaly detection.Source: §1.3 · pp. 4–5, Figure 1 · p. 4

1.4 Related Work and Further Reading

  • The survey situates itself alongside books, theses, surveys, tutorials, and open-source toolboxes covering online prediction, online convex optimization, online algorithms, and applied online learning.Referenced resources include Cesa-Bianchi and Lugosi (2006), Shalev-Shwartz (2011), LIBOL, and Vowpal Wabbit.Source: §1.4 · p. 5

2. Problem Formulations and Related Theory

This section formulates online binary classification as sequential prediction with feedback, loss measurement, and model updates, then develops statistical learning, convex optimization, and game-theoretic foundations. Its central criterion is low regret, with sublinear regret implying average performance approaching the best fixed comparator in hindsight.

2.1 Problem Settings

  • Online binary classification proceeds round by round: the learner predicts from x_t, receives y_t, measures loss, and updates its model to improve future predictions.The framework includes binary labels, classifier-based predictions, convex losses such as hinge loss, and updates when loss is nonzero.Source: §2.1 · p. 6
  • The classic online-learning objective is to minimize regret against the best fixed model in hindsight; sublinear regret R_T = o(T) makes average performance converge to that comparator.Mistakes can also be counted over T rounds, while the optimal hindsight model is only identifiable after observing all instances and labels.Source: §2.1 · pp. 6–7

2.2 Statistical Learning Theory

  • Statistical learning theory defines true risk under an unknown joint distribution, while empirical risk minimization approximates it using finite i.i.d. samples and selects a hypothesis from a class F.For linear binary classification with hinge loss, ERM yields an objective for training the best linear model.Source: §2.2.1 · p. 7

2.2.2 Error Decomposition

  • Excess risk decomposes into estimation error from finite data and approximation error from model-class restrictions, creating a tradeoff because greater model capacity can reduce approximation error while increasing estimation error.This decomposition motivates the difficulty of model selection.Source: §2.2.2 · p. 8

2.3 Convex Optimization Theory

  • Online convex optimization chooses decisions in a convex set under sequential convex losses and minimizes regret relative to the decision minimizing cumulative loss in hindsight.Online binary SVM training is an example using hinge loss and a norm-bounded feasible set.Source: §2.3 · p. 8

2.3.1 First-order Methods / 2.3.2 Second-order Methods

  • OGD uses projected first-order updates and achieves O(√T) regret, whereas ONS uses Hessian-related second-order information, costs O(n^2) rather than O(n), and achieves O(log T) regret under exp-concave losses.OGD’s projection can be computationally intensive; ONS projects under a matrix-induced norm.Source: §2.3.1 · pp. 8–9, §2.3.2 · p. 9

2.3.3 Regularization

  • Regularization stabilizes potentially high-regret FTL: FTRL generally has sublinear regret, while OMD generalizes OGD through dual-space and Bregman-divergence updates, recovering OGD or EG under specific regularizers.EG uses negative entropy on the simplex, and AdaGrad adapts the regularization over time.Source: §2.3.3 · pp. 9–10

2.4 Game Theory / 2.4.1 Game Playing and Nash Equilibrium / 2.4.2 Repeated Two-player Zero-Sum Games

  • Game theory models online prediction as repeated play between a learner and environment, including finite normal-form games, Nash equilibria, and two-player zero-sum games governed by minimax strategies.In a Nash equilibrium no player benefits from changing only its own strategy; von Neumann’s theorem equates minimax and maximin values, linking repeated game interaction to cumulative-loss minimization in online learning.Source: §2.4.1 · p. 11, Nash Equilibrium · p. 11, §2.4.2 · p. 12

3. Online Supervised Learning · 3.1 Overview

This section surveys online supervised learning algorithms and their fundamental principles, emphasizing linear methods before covering expert advice, regularization, kernel approaches, and conversion to batch learning. It frames these methods around sequentially learning hypotheses for supervised tasks.

3.1 Overview

  • The section surveys online supervised learning algorithms as foundational approaches for supervised online learning tasks.It situates the discussion within established online learning methodologies.Source: §3.1 · p. 13
  • Linear online learning methods learn target models represented as linear functions from input domain X to output domain Y.The target hypothesis is written as f : X 7→Y.Source: §3.1 · p. 13
  • For binary classification, the surveyed linear classifier predicts f(x_t; w) = sgn(w · x_t), using a weight vector w over a d-dimensional input space.The sign function outputs +1 when w · x_t > 0 and −1 otherwise.Source: §3.1 · p. 13
  • The survey distinguishes first-order and second-order online learning algorithms as two major types of linear online methods.This distinction organizes the initial treatment of linear approaches.Source: §3.1 · p. 13
  • It also reviews Prediction with expert advice and online learning with regularization.These topics follow the discussion of first-order and second-order linear methods.Source: §3.1 · p. 13
  • The nonlinear-learning portion examines kernel-based online methods, their computational challenges, and approximation strategies for efficient learning.The survey covers a variety of kernel-based approaches rather than a single method.Source: §3.1 · p. 13
  • The section concludes by discussing how online learning algorithms can be converted to learn batch models that generalize well.This connects online algorithms with batch-model learning and generalization.Source: §3.1 · p. 13

3.2 First-order Online Learning

First-order online learning algorithms exploit model first-order information, spanning additive, multiplicative, margin-based, gradient-based, and related large-margin approaches. Their guarantees and update behavior depend on assumptions such as separability, margins, feedback loss, and learning-rate choices.

3.2.1 Perceptron

  • Perceptron uses additive updates for online binary classification and has a margin-dependent mistake bound that tightens as the margin γ increases.The normalized Perceptron improves the separable-case mistake bound through normalization.Source: §3.2.1 · pp. 13–14

3.2.2 Winnow

  • Winnow uses multiplicative promotion and elimination updates for learning k-literal monotone disjunctions over binary features, with mistake bound αk(logα θ + 1) + n/θ.Here α > 1 and θ ≥1/α.Source: §3.2.2 · p. 14

3.2.3 Passive-Aggressive Online Learning (PA)

  • PA is margin-based: it stays passive when hinge loss is zero but updates aggressively for any nonzero loss, while slack variants trade passiveness against aggressiveness through C.PA assumes separable data in its regular form; the survey reports comparable theoretical mistake bounds to Perceptron and frequent empirical outperformance.Source: §3.2.3 · pp. 14–15

3.2.4 Online Gradient Descent (OGD)

  • OGD solves online convex optimization using gradient updates and projection onto a feasible set, with a learning rate ηt that is typically predefined.Compared with PA’s per-round optimal learning rate subject to C, OGD has variants including adaptive and mini-batch methods.Source: §3.2.4 · pp. 15–16

3.2.5 Other first-order algorithms

  • Other first-order algorithms include ALMA, ROMMA, and metaGrad, covering large-margin methods and automatic learning-rate adaptation for faster convergence.ALMA is a large-margin variant of the p-norm Perceptron algorithm.Source: §3.2.5 · p. 16

3.3 Second-Order Online Learning

Second-order online learning combines first- and second-order information to accelerate convergence, typically at higher computational cost. The section presents algorithms that exploit data geometry, feature confidence, adaptive regularization, and extensions to broader online tasks.

3.3 Second-Order Online Learning

  • Second-order algorithms use first- and second-order information to accelerate optimization convergence, but often incur higher computational complexity.Source: §3.3 · p. 16

3.3.1 Second Order Perceptron (SOP)

  • SOP exploits data geometry by approximating the correlation matrix from previously seen instances, adapting the whitened Perceptron to online learning.Whitening reduces transformed-instance correlations and can substantially improve the Perceptron mistake bound; a positive parameter ensures matrix invertibility.Source: §3.3.1 · pp. 16–17

3.3.2 Confidence Weighted Learning (CW)

  • CW models classifier weights and prediction confidence as Gaussian distributions, updating them through KL-regularized optimization to enforce a target correct-classification probability.Its hard probability constraint can make CW sensitive to noise and difficult to generalize beyond Gaussian-distributed constraints.Source: §3.3.2 · pp. 17–18

3.3.3 Adaptive Regularization of Weight Vectors (AROW)

  • AROW extends CW to non-separable data by balancing parameter stability, squared-hinge loss, and growing confidence through adaptive regularization.It is robust to noisy data and readily generalizes to tasks including online collaborative filtering and second-order feature selection.Source: §3.3.3 · p. 18

3.3.4 Soft Confidence weighted Learning (SCW)

  • SCW handles non-separable data while preserving CW’s adaptive-margin property by assigning different margins through a probability formulation.SCW provides two soft-margin formulations, SCW-I and SCW-II, controlled by an aggressiveness parameter C.Source: §3.3.4 · pp. 18–19

3.3.5 Other second-order algorithms

  • Confidence-weighted methods extend to multi-class classification, active learning, and structured prediction, while other approaches include IELLIP, NAROW, NHERD, and Sketched Online Newton.Sketched Online Newton improves the speed of second-order online learning.Source: §3.3.5 · p. 19

3.4 Prediction with Expert Advice

Prediction with expert advice is identified as an important online learning subject, framed around choosing among N experts by assigning weights over them at each time step.

Prediction with Expert Advice

  • Prediction with expert advice is described as an important online learning subject (Roughgarden and Schrijvers, 2017).Source: §3.4 · p. 19
  • The setting gives a learner N experts and requires choosing a nonnegative distribution p_t over experts 1, ..., N at each time step.The weight p_t,i represents the learner’s assigned weight to expert i.Source: applications · p. 19

applications.

This section frames online prediction with expert advice as minimizing regret against individual experts, targeting vanishing per-round regret, and reviews representative algorithms from weighted voting to parameter-free methods.

applications.

  • Online prediction with expert advice minimizes the learner’s regret relative to each expert and seeks vanishing per-round regret, known as Hannan-consistency.Expert losses are aggregated according to the learner’s chosen distribution, and losses are typically assumed bounded in [0, 1].Source: applications · pp. 19–20

3.4.1 Weighted Majority Algorithms

  • Weighted Majority makes binary predictions from expert advice, initializes equal expert weights, and discounts the weights of experts that make mistakes.The discount rate β is user specified and lies in (0, 1).Source: §3.4.1 · p. 20

3.4.2 Randomized Multiplicative Weights Algorithms

  • Randomized multiplicative-weights methods address binary expert advice while producing randomized predictions.The supplied passage identifies this setting as sharing the assumption that expert advice is binary.Source: §3.4.2 · p. 20

3.4.3 Hedge Algorithm

  • Hedge generalizes Weighted Majority by normalizing nonnegative expert weights into prediction probabilities and updating them multiplicatively according to incurred losses.Its initial weights can encode a prior, and theory proves Hedge is Hannan consistent (Freund and Schapire, 1997; Littlestone and Warmuth, 1994, 1989).Source: §3.4.3 · p. 20

3.4.4 EWAF Algorithms

  • EWAF uses exponentially weighted expert losses but evaluates loss between the forecaster’s prediction and the true label, unlike Hedge’s distribution-loss inner product.The distinction matters because prediction-label loss can be more complex than the loss used by Hedge.Source: §3.4.4 · p. 21

3.4.5 Parameter-free Online Learning

  • Parameter-free online learning removes the need to specify a learning rate, with early methods matching optimally tuned regret bounds and later work deriving data-dependent bounds.Chaudhuri et al. (2009) proposed a learning-rate-free Hedge variant; Chernov and Vovk (2010) improved the bound, while later extensions included Luo and Schapire (2015) and Koolen and Van Erven (2015).Source: §3.4.5 · p. 21

3.5 Online Learning with Regularization

Regularization makes online learning more scalable for high-dimensional data by inducing sparse classifiers, primarily through ℓ1-based methods and related truncation, projection, averaging, and adaptive-geometry strategies.

3.5 Online Learning with Regularization

  • Sparse online learning addresses the computational cost of dense classifiers by exploiting high-dimensional data sparsity; ℓ1 regularization induces sparsity without explicitly fixing the number of nonzero weights.An ℓ0 regularizer imposes a hard nonzero-count constraint but is difficult to optimize, motivating the more common ℓ1 alternative.Source: §3.5 · p. 22

3.5.1 Truncated Gradient Descent

  • Truncated Gradient Descent reduces small coefficients toward zero less aggressively than direct rounding, achieving time and space complexity linear in nonzero features and independent of dimensionality d.Direct rounding can discard useful low-frequency features; TGD addresses this limitation through controlled truncation.Source: §3.5.1 · p. 22

3.5.2 Forward Looking Subgradients (FOBOS)

  • FOBOS combines an online gradient step with projection under a sparsity-inducing regularizer, and its ℓ1 version is a special case of TGD with θ = ∞ and K = 1.The projection keeps the solution close to the interim vector while exploiting the regularizer’s low complexity.Source: §3.5.2 · p. 23

3.5.3 Regularized Dual Averaging (RDA)

  • RDA averages gradients and uses a global proximal function, producing a more aggressive constant-λ truncation than FOBOS and usually significantly sparser solutions.Its design differs from FOBOS through averaged rather than current gradients, global rather than local geometry, and distinct truncation coefficients.Source: §3.5.3 · p. 23

3.5.4 Adaptive Regularization

  • Adaptive regularization replaces fixed auxiliary geometry with a data-driven temporal function that accumulates second-order information, yielding Ada-RDA and Ada-FOBOS; Ht is approximated diagonally for tractability.The approximation avoids computationally impractical matrix-root calculations in high-dimensional data.Source: §3.5.4 · p. 24

3.5.5 Online Feature Selection

  • Online feature selection differs from sparse learning by imposing a hard constraint on the number of nonzero classifier elements rather than minimizing an ℓ1-regularized loss, although both use truncation and projection.Both approaches target efficient classifiers for very high-dimensional data.Source: §3.5.5 · p. 24

3.5.6 Others

  • SCD and SMIDAS address ℓ1-regularized minimization but depend on dimensionality d and assume batch access to all instances, while later methods combine sparsity, second-order learning, and cost-sensitive classification for scalable imbalanced tasks.SMIDAS performs truncation in dual space using mirror descent.Source: §3.5.6 · p. 24

3.6 Online Learning with Kernels

Online kernel learning uses kernels to learn nonlinear classifiers sequentially, with regret as the objective. The survey covers kernel methods, budget maintenance, functional approximation, and online multiple-kernel learning.

3.6 Online Learning with Kernels

  • Kernel online learning predicts nonlinear binary labels with f(x) in an RKHS, using sgn(f(x)) for classification and |f(x)| as confidence.Its objective is to minimize online regret over cumulative classification losses.Source: §3.6 · p. 25, §3.6.1 · p. 25

3.6.1 Online Kernel Methods

  • Kernelized Perceptron and OGD extend linear online updates through the kernel trick, representing predictions as weighted sums over support vectors.The kernel trick replaces inner products with κ(x_i, x_j), while nonzero coefficients identify support vectors; this representation creates computational and scalability challenges.Source: §3.6.1 · pp. 26–27

3.6.2 Scalable Online Kernel Learning via Budget Maintenance

  • Budget online kernel learning bounds the support-vector set to B using removal, projection, or merging strategies to control computation and memory.Removal trades simplicity and efficiency against accuracy, projection approximates discarded vectors using a base set, and merging replaces two vectors with one; exhaustive pair search for merging costs O(B^2).Source: §3.6.2 · pp. 27–29

3.6.3 Scalable Online Kernel Learning via Functional Approximation

  • Functional approximation scales online kernel learning by mapping inputs to finite-dimensional features, converting the kernel problem into linear online classification.FOGD uses random Fourier features, NOGD uses Nyström approximation, and Dual Space Gradient Descent combines an RBP model with an FOGD model built from discarded support vectors.Source: §3.6.3 · p. 30

3.6.4 Online Multiple Kernel Learning

  • Online multiple-kernel learning avoids fixing one kernel by combining or selecting predefined kernel classifiers online, while jointly learning classifiers and combination weights.Perceptron learns per-kernel classifiers and Hedge combines them; stochastic selection and budgeting improve efficiency, with extensions to regression, time-sensitive patterns, and imbalanced streams.Source: §3.6.4 · p. 31

3.7 Online to Batch Conversion

Online-to-batch conversion connects an online algorithm’s regret to the generalization performance of a batch model. The section develops a strongly convex conversion theory and reviews sharper alternatives for general convex losses.

3.7 Online to Batch Conversion

  • Online-to-batch conversion relates sequential regret minimization to the excess risk and generalization ability of a model under an unknown data distribution.The online learner receives examples sequentially and incurs convex loss, whereas batch learning seeks a model with small excess risk.Source: §3.7 · p. 32

3.7.1 A General Conversion Theory

  • Under Lipschitz and strongly convex bounded losses with i.i.d. data, a high-probability theorem converts an online learner’s performance into a generalization guarantee.The analysis uses conditional expectations and Freedman’s inequality, with the guarantee stated relative to the population-risk minimizer.Source: §3.7.1 · pp. 32–33
  • For the strongly convex setting, Online Gradient Descent has regret at most L^2(1 + ln T)/(2λ), yielding a high-probability guarantee for the averaged iterate.The averaged model is ¯w_T = 1/T Σ_t w_t, and the stated simplification uses (1 + ln T)/(2T) ≤ ln T/T for T ≥ 3.Source: §3.7.1 · p. 33

3.7.2 Other Conversion Theories

  • For general convex losses, prior work derives generalization bounds, while exponential-moment and Bernstein-based analyses provide sharper concentration under losses bounded by 1 [Cesa-Bianchi et al., 2004; Zhang, 2005; Cesa-Bianchi and Gentile, 2008].The Bernstein-based approach selects an iterate by minimizing a penalized empirical risk and achieves a rate O(ln T^2/T) when the stated bounded-loss condition holds.Source: §3.7.2 · p. 33

4. Applied Online Learning for Supervised Learning

This section surveys applied online learning methods for supervised tasks across specialized learning settings and applications, including cost-sensitive, multi-task, multi-view, transfer, metric learning, collaborative filtering, ranking, distributed computation, neural networks, portfolio selection, and time-series prediction. It covers their update mechanisms, assumptions, limitations, benchmark strategies, adaptive methods, and emerging studies.

4.1 Overview

  • The section’s overview frames these methods as responses to sequential problem settings and applications where conventional supervised online algorithms cannot be applied directly.Its scope includes cost-sensitive, multi-task, multi-view, transfer, metric, collaborative-filtering, structured-prediction, distributed, neural-network, and portfolio-selection methods.Source: §4.1 · p. 34

4.2 Cost-Sensitive Online Learning

  • Cost-sensitive online learning addresses misleading accuracy under class imbalance by modeling unequal errors, with CSOGD directly optimizing weighted sensitivity-specificity or misclassification-cost objectives.PAUM and CPA adjust updates for class-dependent costs but do not directly optimize predefined cost-sensitive measures; online AUC methods use reservoir sampling to control memory growth.Source: §4.2 · pp. 34–36

4.3 Online Multi-task Learning

  • Online multi-task learning solves related tasks in parallel as instances arrive sequentially, using task relationships through learned matrices or shared-and-individual model structures.The multitask Perceptron uses inter-task relationships, while other methods learn time-varying relationships or impose structure regularization.Source: §4.3 · p. 37

4.4 Online Multi-view Learning

  • Online multi-view learning combines classifiers from multiple feature views, adding an agreement term to passive-aggressive optimization while retaining a closed-form update.Two-view PA predicts with sign(wA · xA + wB · xB) and extends online learning to complementary similarity and distance-metric tasks.Source: §4.4 · pp. 37–38

4.5 Online Transfer Learning

  • Online transfer learning adapts a source classifier to sequential target data in homogeneous or heterogeneous feature spaces, using weighted ensembles or co-regularized classifiers.The surveyed extensions address multiple sources, negative transfer, imbalanced distributions, and unlabeled target instances.Source: §4.5 · pp. 38–39

4.6 Online Metric Learning

  • Online metric learning learns a positive semidefinite Mahalanobis metric from pairwise or triple feedback by minimizing accumulated online loss.Evaluation after online-to-batch conversion can use mean average precision or precision-at-top-k, while POLA applies a passive-aggressive update to pairwise data.Source: §4.6 · p. 40
  • OASIS learns a bilinear similarity matrix from triplets, avoiding positive-semidefinite projection and potentially simplifying data collection compared with prior metric-learning methods.It uses a bilinear similarity measure and does not require W to be positive semi-definite, saving projection cost; triplets may be easier to collect.Source: §4.6 · p. 41

4.7 Online Collaborative Filtering

  • Online collaborative filtering predicts each incoming user–item rating from previous ratings, then updates after the true rating is revealed, optimizing RMSE or MAE.Model-based methods use low-dimensional user and item vectors, while improved updates target faster adaptation to rapidly changing user preferences.Source: §4.7 · pp. 42–43

4.8 Online Learning to Rank

  • Online learning to rank processes instances sequentially and includes pointwise and pairwise approaches, with Prank minimizing accumulated rank loss and OAP-BPM improving its generalization.Prank maintains perceptron weights and ordered thresholds; OAP-BPM averages diverse Prank-based solutions, while pairwise methods learn score functions from preference pairs.Source: §4.8 · pp. 44–45

4.9 Distributed Online Learning

  • Distributed online learning processes instances across nodes whose local models communicate for consistency, balancing computational speed, accuracy, communication load, and network robustness.Centralized networks use a master node, whereas decentralized networks communicate between neighbors; synchronization improves theoretical bounds, while asynchrony increases processing speed.Source: §4.9 · pp. 45–46

4.10 Online Learning with Neural Networks

  • Online neural-network learning includes sequential training methods, but many approaches lack theoretical guarantees, rely on heuristics, incur high computational cost, or are adaptations of batch learning.Examples include recurrent networks, resource-allocating networks, ARTMAP, OS-ELM, Learning++, and Hedge Backpropagation, with scalability and direct online optimization remaining concerns.Source: §4.10 · pp. 46–47

4.11 Online Portfolio Selection

  • Online portfolio selection updates portfolio allocations each period using historical price relatives to optimize metrics such as cumulative wealth and risk-adjusted returns.Common assumptions include no transaction costs, perfect liquidity, and no market impact; strategies include Follow-the-winner, Follow-the-loser, Pattern Matching, and Meta-Learning.Source: §4.11 · p. 47
  • Portfolio-selection benchmarks include Buy and Hold, Best Stock, and Constant Rebalanced Portfolio, although Best Stock and Best-CRP require hindsight.BAH equally invests across assets without rebalancing; CRP maintains a fixed allocation and rebalances each period.Source: §4.11 · p. 47
  • Follow-the-winner methods increase allocations to historically successful stocks, whereas mean-reversion methods follow losers based on expected price reversion.Representative methods include Universal Portfolios, Exponential Gradient, PAMR (Li et al., 2012), OLMAR (Li and Hoi, 2012; Li et al., 2015), and RMR (Huang et al., 2013).Source: §4.11 · p. 48
  • Pattern-matching methods seek sequential decision patterns, while meta-learning combines expert portfolio advice and other methods optimize returns while accounting for transaction costs.Pattern-matching approaches are generally non-parametric, and meta-learners typically follow the winner among experts.Source: §4.11 · p. 48
  • Online time-series prediction receives observations sequentially and predicts future values, with recent studies exploring online algorithms alongside linear, nonlinear, univariate, multivariate, and sliding-window formulations.Emerging online studies include Anava et al. (2013) and Liu et al. (2016a).Source: §4.11 · p. 48

5. Bandit Online Learning

This section introduces bandit online learning as sequential decision-making under partial feedback, focusing on exploration–exploitation and regret minimization across stochastic, Bayesian, adversarial, linear, combinatorial, contextual, Markovian, infinitely many-armed, and continuum-armed settings. It surveys representative algorithms, alternatives, and stated regret guarantees, including epsilon-greedy, UCB, Thompson Sampling, Exp3, COMBAND, Banditron, and Exp4.

5.1 Overview

  • Bandit learning selects one of K actions per round, observes only the chosen action’s payoff or loss, and balances exploration against exploitation to minimize cumulative regret.The survey distinguishes stochastic i.i.d. environments from adversarial environments whose losses may adapt to past decisions.Source: §5.1 · p. 49

5.2.1 Stochastic Multi-armed Bandit

  • In stochastic bandits, epsilon-greedy explores randomly with probability ϵ, while UCB uses shrinking confidence bounds to combine exploration with exploitation.Constant ϵ causes linear regret, whereas epsilon-decreasing exploration can achieve O(ln T); UCB is described as having logarithmic expected-regret bounds.Source: §5.2.1 · pp. 50–51

5.2.2 Bayesian Bandits

  • Thompson Sampling maintains Beta posteriors for Bernoulli-arm means, samples from them, and selects an arm according to the sampled means’ largest value.The method extends to arbitrary unknown reward distributions on [0, 1] and contextual bandits, with a stated stochastic-bandit expected-regret result.Source: §5.2.2 · p. 52

5.3 Adversarial Bandits

  • Adversarial bandits allow losses to depend on previous actions, so randomized policies compare their expected loss with the best fixed action in hindsight.Exp3 applies exponential weights with exploration and achieves regret O(√(TK ln K)); Exp3.P and Exp3.M address high-probability bounds and multiple plays, respectively.Source: §5.3 · p. 52, §5.3.1 · p. 53

5.3.2 Linear Bandit and Combinatorial Bandit

  • Linear bandits reveal only the selected action’s linear loss, while combinatorial bandits restrict actions to binary-hypercube subsets and may be stochastic or adversarial.COMBAND estimates losses from sampled actions, controls exploration and exploitation, and achieves a regret bound better than O(√(T d ln |S|)) for several action sets.Source: §5.3.2 · p. 54

5.4 Contextual Bandits

  • Contextual bandits associate contexts with arms and define regret against the best policy mapping contexts to actions rather than against a single best arm.The survey highlights personalized recommendation as an application and focuses on multiclass classification and expert-advice settings.Source: §5.4 · p. 55

5.4.1 The Multiclass Setting.

  • Banditron is a multiclass contextual-bandit algorithm and Perceptron variant that maintains a linear model, explores labels probabilistically, receives correctness feedback, constructs an update, and updates the model.Source: §5.4.1 · pp. 55–56

5.4.2 The Expert Setting.

  • Exp4 handles contextual bandits with expert advice by weighting experts’ arm recommendations and comparing performance with the expert achieving the highest expected cumulative reward.Each expert supplies a distribution over arms, and the algorithm forms arm-selection probabilities from the weighted advice.Source: §5.4.2 · p. 56
  • Exp4 balances exploitation and exploration with γ, samples arms from p_i,t, uses unbiased reward estimates, and updates weights by expected reward.Its regret is O(√(TK ln N)), with tighter bounds also established.Source: §5.4.2 · p. 57
  • Epoch-greedy is computationally efficient with an oracle optimizer but has O(T^2/3) regret, while LinUCB and LinREL maximize contextual upper-confidence bounds.LinUCB uses arm feature vectors and LinREL differs through its regularization term.Source: §5.4.2 · p. 57

5.5 Other Bandit Variants

  • Markovian bandits model arms as Markov reward processes, and Gittins (1979) gives an efficiently computable optimal greedy policy; Bayesian bandits use known parameter priors.Bayesian-bandit regret averages over parameters drawn from those priors.Source: §5.5 · p. 57
  • Infinitely many-armed bandits allow more arms than experiments or even infinitely many, while continuum-armed bandits place arms in metric spaces with smooth mean-reward functions.Continuum-armed bandits are also called Lipschitz Bandits when the reward function is Lipschitz.Source: §5.5 · p. 57

6. Online Active Learning

Online active learning selectively queries labels for incoming unlabeled instances, updating the model only when feedback is obtained. The section reviews selective-sampling algorithms, including first- and second-order methods, alternative RLS-based approaches, and expert-advice frameworks.

6.1 Overview

  • Online active learning queries labels selectively to reduce costly or uninformative feedback, leaving the prediction model unchanged when labels are not requested.The learner observes each unlabeled instance, predicts, decides whether to query its label, and updates only after queried feedback.Source: §6.1 · p. 58
  • The section distinguishes selective sampling from online active learning with expert advice; both query labels conditionally, while expert-based methods aggregate predictions from a pool of experts.Selective sampling adapts classical online learning, whereas expert advice adapts prediction with expert advice; applications include crowdsourcing (Hao et al., 2015a).Source: §6.1 · p. 58, §6.2 · p. 58, §6.3 · pp. 62–63

6.2.1 First-order Selective Sampling Algorithms

  • Selective-sampling Perceptron methods use randomized confidence-dependent querying and retain Perceptron-style mistake guarantees, with separable data recovering the familiar Perceptron bound.The query rate is controlled by δ, and adaptive parameter variants adjust sampling using observed instance norms (Cesa-Bianchi et al., 2006).Source: §6.2.1 · p. 59

6.2.2 Second-order Selective Sampling Algorithms

  • Second-order selective-sampling Perceptron algorithms transform predictions using correlation information while applying randomized label querying, yielding bounds involving the random correlation matrix.Cesa-Bianchi et al. (2006) also modify the sampling probability to incorporate second-order information.Source: §6.2.2 · pp. 60–61

6.2.3 Other Selective Sampling Approaches

  • Other selective-sampling methods use RLS-based classifiers, including BBQ and improved variants, but their batch-like updates can become inefficient or non-scalable with many queried examples.These approaches include Cesa-Bianchi et al. (2009), Orabona and Cesa-Bianchi (2011), and Dekel et al. (2010).Source: §6.2.3 · p. 61

6.3 Online Active Learning with Expert Advice

  • Expert-advice approaches query labels when expert predictions are insufficiently confident, using disagreement to determine when feedback can be skipped.For Zhao et al. (2013), if all expert predictions differ by at most δ, the forecaster’s prediction and its estimated counterpart differ by at most δ.Source: §6.3 · pp. 62–63

7. Online Semi-supervised Learning

Online semi-supervised learning combines online prediction with labeled and unlabeled data, encompassing online manifold regularization and transductive online learning. The section emphasizes scalable approximations for manifold methods and the limited, theoretically informative scope of transductive settings.

7.1 Overview

  • Online semi-supervised learning has two branches: adapting batch methods to labeled and unlabeled data streams, and studying online learning when unlabeled instances are available in advance; online active learning is a special case of the former.Source: §7.1 · p. 63

7.2 Online Manifold Regularization

  • Online manifold regularization minimizes labeled-data loss, supervised regularization, and prediction differences between similar unlabeled instances on the manifold.Source: §7.2 · pp. 63–64
  • The online objective can be optimized with Online Gradient Descent in O(T 2) time, but its manifold term requires storing all instances and comparing each incoming instance with them.Source: §7.2 · p. 64
  • Sparse approximations retain either the newest τ instances or s cluster centers found by a random projection tree, while incremental k-center quantization constructs reduced similarity graphs for harmonic solutions.Source: §7.2 · p. 64
  • Online active semi-supervised learning extends active learning, including OASIS, which applies a general online Bayesian learning framework.Source: §7.2 · p. 64

7.3 Transductive Online Learning

  • Transductive online learning assumes all unlabeled instances are available before learning, uses random playout and randomized rounding for efficient prediction with expert advice, and remains niche because this assumption may be unrealistic despite theoretical links to batch learning.Source: §7.3 · p. 64

8. Online Unsupervised Learning

The survey reviews online unsupervised learning from unlabeled streams without explicit feedback, organizing key ideas into clustering, dimension reduction, density estimation, and anomaly detection while providing only a focused overview.

8.1 Overview

  • Online unsupervised learning is organized into four areas: clustering, dimension reduction, anomaly detection, and density estimation, with coverage limited to key ideas.The literature is too broad for comprehensive treatment, so the survey emphasizes areas closely related to online learning.Source: §8.1 · p. 65

8.2 Online Clustering

  • Online clustering primarily studies partition-based and density-based methods, while also addressing hierarchical, projected, categorical, text, uncertain, graph, and distributed streams.Partition methods include k-MEANS, k-MEDOIDS, STREAM, sampling, and StreamKM++; density methods use micro-clusters or grids to handle arbitrary shapes, unknown cluster counts, and outliers under streaming constraints.Source: §8.2 · pp. 65–66

8.3 Online Dimension Reduction

  • Online dimension reduction learns lower-dimensional representations through subspace or manifold learning, with research emphasizing online PCA and also covering ICA, Kernel-PCA, ISOMAP, and LLE.Dimension reduction improves efficiency, compression, visualization, and applicability; manifold methods preserve global or local properties of nonlinear data structure.Source: §8.3 · pp. 66–67

8.4 Online Density Estimation

  • Online density estimation commonly uses KDE, but its kernelization cost grows with all observed points, motivating memory-bounded merging and sampling approaches.Merging combines similar kernels under a storage budget, whereas sampling retains selected points while targeting accuracy; newer methods address bandwidth selection and distributional change.Source: §8.4 · pp. 67–68

8.5 Online Anomaly Detection

  • Online unsupervised anomaly detection identifies abnormal behavior in streams using distance-, density-, clustering-, statistical-, subspace-, and one-class methods, although many approaches are not purely online machine learning.Sliding-window distance methods dominate reviewed stream approaches, alongside one-class detectors and online clustering, so this survey keeps the discussion brief.Source: §8.5 · p. 68

9. Related Areas and Other Terminologies

This section distinguishes online learning from related terms whose meanings can vary by context. It characterizes overlaps and boundaries involving incremental, sequential, stochastic, adaptive, interactive, reinforcement, and continual learning.

9.1 Overview

  • The relationships among these terms are context-dependent, and some may be used interchangeably.The section presents these distinctions as partly subjective rather than universally fixed.Source: §9.1 · p. 69

9.2 Incremental Learning

  • Incremental learning updates models from streams under limited space and computation, and is a branch of online learning that can also use batch updates.Incremental SVM illustrates adding or removing one instance per model update while approximating batch learning (Poggio, 2001).Source: §9.2 · p. 69

9.3 Sequential Learning

  • Sequential learning exploits correlations in ordered data to predict structured outputs, can use batch or online algorithms, and includes sequence classification as a simpler special case.Examples include sliding windows, recurrent models, hidden Markov models, conditional random fields, and graph transformer networks.Source: §9.3 · pp. 69–70

9.4 Stochastic Learning

  • Stochastic learning commonly processes randomly selected instances or mini-batches to accelerate scalable optimization, making it a special family of online learning rather than its full scope.Stochastic Gradient Descent is also called Online Gradient Descent in online-learning terminology, whereas mini-batch SGD processes small batches.Source: §9.4 · p. 70

9.5 Adaptive Learning

  • Adaptive learning modifies models for changing environments, but often relies on heuristics rather than online-learning theory and therefore lacks theoretical performance guarantees.These methods resemble online learning through dynamic adaptation but are not necessarily based on online algorithms.Source: §9.5 · p. 70

9.6 Interactive Learning

  • Interactive learning places users or domain experts in the loop, where online methods can support informative sampling, sequential updates, and exploration–exploitation decisions.Its benefits include integrating domain knowledge, improving communication, and continuously improving learning efficacy.Source: §9.6 · pp. 70–71

9.7 Reinforcement Learning

  • Reinforcement learning learns policies through actions and cumulative rewards, can be batch or online, and is more general than bandit learning for complex interactive environments.Both fields balance exploration and exploitation, while RL commonly addresses sequential dynamics and objective optimization (Kaelbling et al., 1996).Source: §9.7 · p. 71

9.8 Continual Learning

  • Continual learning addresses sequentially arriving tasks while retaining prior knowledge, but most existing studies train each task in batches and therefore are not online learning.A central challenge is catastrophic forgetting, especially in neural-network-based continual learning (Parisi et al., 2018).Source: §9.8 · p. 71

10. Conclusions

The survey categorizes online learning by feedback into supervised, limited-feedback, and unsupervised methods, while emphasizing supervised learning and identifying greater challenges in the other two categories. It highlights future directions spanning non-stationarity, scale, data variety and veracity, online deep learning, and continual learning.

10.1 Concluding Remarks

  • The survey groups online learning into supervised methods with full feedback, limited-feedback methods requiring exploration–exploitation tradeoffs, and unsupervised methods without feedback.Supervised learning includes linear, nonlinear, and non-traditional tasks; unsupervised examples include online clustering, representation learning, and anomaly detection.Source: §10.1 · p. 72
  • Supervised online learning receives greater emphasis because it extends batch supervised learning to real-time data streams, whereas limited-feedback and unsupervised learning remain more challenging.The survey argues that these latter categories should attract more future research effort.Source: §10.1 · p. 72

10.2 Future Directions

  • Concept drift in non-stationary streams remains unresolved because existing approaches rely on restricted assumptions and lack general theoretical frameworks for arbitrary drift.The challenge concerns target concepts changing over time in unforeseeable ways.Source: §10.2 · pp. 72–73
  • Large-scale online learning must address extremely high data volume and velocity through parallel and distributed methods using high-performance, cloud, and IoT computing resources.Although online learning offers efficiency and scalability advantages over batch learning, real-world big-data analytics remains non-trivial.Source: §10.2 · p. 73
  • Online learning must address data variety across multiple sources and structured, semi-structured, and unstructured modalities through multi-source and multi-modal learning.Existing work, including online multiple kernel learning, has not fully resolved these challenges.Source: §10.2 · p. 73
  • Data veracity is an important open issue because noise, missing values, and incomplete feedback can reduce efficacy, motivating more robust online learning algorithms.Many existing studies implicitly assume perfect-quality data and feedback, an assumption that often fails in real-time analytics.Source: §10.2 · p. 73
  • Online deep learning remains challenging because it must balance accuracy, computational efficiency, scalability, and model complexity when learning neural networks from streams.The survey identifies online deep learning as an emerging topic following the success of deep learning techniques (Sahoo et al., 2018).Source: §10.2 · p. 73
  • Online continual learning is a promising direction for streaming existing and novel tasks, with catastrophic forgetting across tasks as its key challenge.This direction extends traditional continual learning to pure online-learning settings, potentially drawing on progress in online deep learning.Source: §10.2 · p. 73

Related papers

Loading 1802.02871v2…