Online Learning: A Comprehensive Survey

Abstract

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.

arXiv comment100 pages, ~400 references

References in corpus (26)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• A Survey on Multi-view Learning
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Optimal Distributed Online Prediction using Mini-Batches
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Online Alternating Direction Method
• A Survey on Contextual Multi-armed Bandits
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• Stochastic Optimization of PCA with Capped MSG
• Online Learning to Rank in Stochastic Click Models
• Towards minimax policies for online linear optimization with bandit feedback
• Efficient Second Order Online Learning by Sketching
• On-Line Portfolio Selection with Moving Average Reversion
• Online Stochastic Linear Optimization under One-bit Feedback
• On Kernelized Multi-armed Bandits
• Active Learning with Expert Advice
• Online Convex Optimization with Unconstrained Domains and Losses
• The Scaling Limit of High-Dimensional Online Independent Component Analysis
• A Framework of Sparse Online Learning and Its Applications
• Can We Learn to Beat the Best Stock
• An Online Hierarchical Algorithm for Extreme Clustering
• SOL: A Library for Scalable Online Learning Algorithms

Cited by in corpus (38)

• A Survey on Deep Learning for Named Entity Recognition
• Malicious URL Detection using Machine Learning: A Survey
• Bio-inspired digit recognition using reward-modulated spike-timing-dependent plasticity in deep convolutional networks
• Review: Deep Learning in Electron Microscopy
• Recommender systems based on graph embedding techniques: A comprehensive review
• CRPS Learning
• Cutting-edge 3D Medical Image Segmentation Methods in 2020: Are Happy Families All Alike?
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• Tasking framework for Adaptive Speculative Parallel Mesh Generation
• Homogeneous Online Transfer Learning with Online Distribution Discrepancy Minimization
• Evaluating Online Continual Learning with CALM
• Training for the Future: A Simple Gradient Interpolation Loss to Generalize Along Time
• Understanding Continual Learning Settings with Data Distribution Drift Analysis
• Learning-based Prediction and Uplink Retransmission for Wireless Virtual Reality (VR) Network
• Online Multi-horizon Transaction Metric Estimation with Multi-modal Learning in Payment Networks
• No-regret Learning in Price Competitions under Consumer Reference Effects
• Sage: Using Unsupervised Learning for Scalable Performance Debugging in Microservices
• On-the-Fly Joint Feature Selection and Classification
• Online Multi-Agent Forecasting with Interpretable Collaborative Graph Neural Network
• Transfer Learning via ${\ell }_1$ Regularization
• Efficient Projection-Free Online Methods with Stochastic Recursive Gradient
• Personalized Online Machine Learning
• Memory Efficient Meta-Learning with Large Images
• ALE: A Simulation-Based Active Learning Evaluation Framework for the Parameter-Driven Comparison of Query Strategies for NLP
• Optimizing the Whole-life Cost in End-to-end CNN Acceleration
• Sparse Meta Networks for Sequential Adaptation and its Application to Adaptive Language Modelling
• Continual Backprop: Stochastic Gradient Descent with Persistent Randomness
• Data Analytics for Fog Computing by Distributed Online Learning with Asynchronous Update
• Online Newton Step Algorithm with Estimated Gradient
• Online learning using multiple times weight updating
• Online Passive-Aggressive Total-Error-Rate Minimization
• Modified online Newton step based on element wise multiplication
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
• Learning to Transfer: A Foliated Theory
• Fairness-Aware Online Meta-learning
• Incremental Learning Techniques for Online Human Activity Recognition
• Bilevel Online Deep Learning in Non-stationary Environment