Survey of algorithms to correct past mistakes in prediction.
problem Improving prediction accuracy by correcting past errors.
method Defensive Forecasting as a sequential game theory approach to minimize prediction metrics.
result Simple, near-optimal algorithms for various prediction tasks.
We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to …
LatentTrack generates model parameters online for nonstationary data.
problem Online probabilistic prediction under nonstationary dynamics.
method Sequential neural architecture with latent filtering and amortized inference.
result Consistently lower negative log-likelihood and mean squared error than baselines.
New algorithms for fast online decision making using neural networks and martingale posteriors.
problem Online sequential decision making under uncertainty.
method Martingale posterior neural networks for fast online learning and decision making.
result Achieves competitive performance-speed trade-offs in non-stationary contextual bandits and Bayesian optimization.
A novel online GP model captures long-term memory in sequential data.
problem Capturing long-term memory in sequential data online.
method Integrates HiPPO framework into interdomain GP, leveraging time-varying orthogonal projections as inducing variables.
result OHSVGP outperforms existing online GP methods in predictive performance, long-term memory preservation, and computational efficiency.
A new framework predicts hidden Markov model regimes online.
problem Efficiently identify hidden Markov model regimes in streaming data.
method Develops a predictive-first optimisation framework for streaming HMMs, approximating the full posterior predictive distribution.
result The method provides competitive prequential performance compared to Online EM and Sequential Monte Carlo.
Develops a framework to control risk in online learning models.
problem Rigorous uncertainty quantification for online learning models.
method A framework for constructing uncertainty sets that provably control risk.
result Guarantees risk control at any user-specified level even with distribution shifts.
Adaptive Bayesian learning aggregates experts to improve performance.
problem Bayesian online learning's performance depends on inferential choices.
method Treat Bayesian update rules as experts and aggregate them based on sequential predictive losses.
result The aggregate competes with the best expert in hindsight at a low aggregation cost.
Algorithm learns data structure in real-time with outliers and change points.
problem Sequential online prediction in the presence of outliers and change points.
method INTEL algorithm using WGPs and POE model for real-time structure learning.
result Significantly better performance than benchmarks in real datasets.
Online prediction improves with abstention, reducing regret to a fixed bound.
problem Sequential prediction with expert advice.
method Introducing abstention with a cost smaller than 0.5, achieving independent regret bounds.
result Achieves expected regret bounds independent of time horizon, with bounds of order log(N)/(1-2c).
Many kinds of data can be represented as a network or graph. It is crucial to infer the latent structure underlying such a network and to predict unobserved links in the network. Mixed Membership Stochastic Blockmodel (MMSB) is a promising model for network data. Latent variables and unknown parameters in MMSB have bee…
Paper proposes AdaBoost-assisted ELM for efficient online sequential classification.
problem Efficient online sequential classification with improved accuracy and stability.
method Utilizes AdaBoost for cost-sensitive learning and forgetting mechanism for stability.
result Achieves 94.41% accuracy on MNIST dataset with reduced standard deviation.
Bayesian framework reduces online optimization regret.
problem Sequential optimization in dynamic environments with bounded losses.
method PAC-Bayes theory and Bayesian updating principles.
result Achieves O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret for bounded losses. The paper addresses errors in online selective conformal prediction and proposes new strategies to ensure valid inference.
problem Online selective conformal prediction's exchangeability issues and false coverage rate control problems.
method Evaluation and correction of existing calibration selection strategies, proposing new ones that preserve exchangeability.
result Novel calibration selection strategies ensure both selection-conditional coverage and FCR control.
Proposes online conformal prediction method with adversarial semi-bandit feedback.
problem Online uncertainty quantification with adversarial semi-bandit feedback.
method Formulates online conformal prediction as an adversarial bandit problem and uses regret minimization.
result Achieves long-run coverage guarantee with adversarial semi-bandit feedback.
Majorizing measures control sequential complexities for online learning.
problem Extending classical empirical processes theory to sequential cases.
method Generic chaining, majorizing measures, fractional covering numbers.
result Sharp control of worst-case sequential Rademacher complexity.
Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.
problem Online convex optimization with adversarial constraints.
method Improved algorithm using accurate predictions of loss and constraint functions.
result Improved bounds on regret and cumulative constraint violations.
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the function class, the minimax rates depend on both the curvature of the loss function and the sequential complexities of the class. Above this…
Hybrid model for online nonlinear prediction using LSTM and soft GBDT.
problem Online nonlinear prediction with manual feature selection and model selection issues.
method End-to-end architecture with LSTM for feature extraction and soft GBDT for regression, jointly optimized.
result Significant performance improvements over conventional methods on real datasets.
IE-GP framework learns sequentially arriving data with adaptive kernels.
problem Sequential data adaptation in Gaussian process models.
method Incremental ensemble of Gaussian process learners with adaptive weights.
result IE-GP framework effectively learns and adapts to sequential data.
Adaptive algorithm minimizes online prediction errors for irregular data.
problem Online adversarial regression with highly irregular prediction rules.
method Adaptive wavelet-based algorithm for Besov space regression.
result Minimax-optimal regret bounds in adversarial settings.
BONG optimizes Bayesian inference online with natural gradient descent.
problem Sequential Bayesian inference in online settings.
method Bayesian online natural gradient (BONG) approach based on variational Bayes.
result BONG outperforms other online VB methods in non-conjugate settings.
Proposes methods for online conformal prediction with nested prediction sets across multiple confidence levels.
problem Need for uncertainty quantification with multiple confidence levels in diverse applications.
method Online optimization perspective to enforce nestedness of prediction sets while controlling quantile estimation error.
result Achieves stable coverage across all levels, strictly nested prediction sets, and improved efficiency.
Due to the popularity of the Internet and smart mobile devices, more and more financial transactions and activities have been digitalized. Compared to traditional financial fraud detection strategies using credit-related features, customers are generating a large amount of unstructured behavioral data every second. In …
Bayesian neural networks learn weights with closed-form updates.
problem Efficiently learning Bayesian neural networks with closed-form updates.
method Closed-form Bayesian inference for online learning of Gaussian-weighted BNNs.
result Closed-form expressions for sequential/online training of BNNs.
Study online monotone density estimation with expert aggregation and log-optimal calibration.
problem Online monotone density estimation and log-optimal calibration.
method Proposed two online estimators: Grenander estimator and expert aggregation estimator.
result Online estimators achieve O ( n 1 / 3 ) O(n^{1/3}) O ( n 1/3 ) cumulative log-likelihood gap and n log n \sqrt{n\log{n}} n log n pathwise regret bound. Study improves neural network performance in sequential learning for image classification.
problem Improving neural network performance in sequential learning for image classification.
method Evaluation of approaches for computing prequential description lengths, proposing forward-calibration and replay-streams.
result Improved description lengths for image classification datasets, outperforming previous results.
Sequential prediction problems such as imitation learning, where future observations depend on previous predictions (actions), violate the common i.i.d. assumptions made in statistical learning. This leads to poor performance in theory and often in practice. Some recent approaches provide stronger guarantees in this se…
We study data poisoning attacks in the online setting where training items arrive sequentially, and the attacker may perturb the current item to manipulate online learning. Importantly, the attacker has no knowledge of future training items nor the data generating distribution. We formulate online data poisoning attack…
This paper discovers classification models from sequential data without prior knowledge.
problem Lack of prior knowledge in defining kernels for online classification.
method Adapts GP-based time-series structure discovery with SMC to learn new features from sequential data.
result Improves classification accuracy by 10% on real-world data.
New algorithm predicts piecewise regular functions online.
problem Online prediction of piecewise regular functions.
method Modified sleeping experts aggregation algorithm.
result Oracle risk bounds for all local regions.
The paper improves Bayesian optimization by calibrating uncertainty estimates.
problem Improper uncertainty estimates in Bayesian optimization when data is non-stationary.
method Proposes online learning algorithms to maintain calibration on non-i.i.d. data and integrates them into Bayesian optimization.
result Calibrated Bayesian optimization converges to better optima in fewer steps.
Online convex optimization is a sequential prediction framework with the goal to track and adapt to the environment through evaluating proper convex loss functions. We study efficient particle filtering methods from the perspective of such a framework. We formulate an efficient particle filtering methods for the non-st…
Novel algorithm reduces feature inclusion in online decision-making.
problem Optimizing decision-making for personalized user experiences with fairness.
method Online Batched Sequential Inclusion (OBSI) algorithm for sequential feature inclusion.
result OBSI outperforms other algorithms in terms of regret, relevance of features, and compute.
New algorithm optimizes complex metrics in online learning.
problem Optimizing non-decomposable metrics in sequential learning.
method General online algorithm for various metrics.
result Achieves O ( ln n n ) \mathcal{O}(\frac{\ln n}{n}) O ( n l n n ) regret for concave and smooth metrics. This thesis improves OCO algorithms for dynamic data environments.
problem Sequential, changing data in big data environments.
method Designing algorithms to adapt to changing environments.
result Improved algorithms for online resource allocation.
New methods improve Bayesian inference and decision-making in online learning.
problem Current Bayesian deep learning does not fully utilize joint predictives for sequential decision-making.
method Proposes new evaluation settings for active learning and active sampling, focusing on marginal and joint cross-entropies.
result Initial experiments suggest challenges in applying current BDL inference techniques in high-dimensional spaces.
Paper proposes an online sparse linear regression method for streaming data.
problem Sparse regression for variable selection and prediction accuracy.
method Online sparse linear regression framework with memory efficiency and relaxed assumptions.
result The ℓ 2 \ell_2 ℓ 2 -norm statistical error of the estimator diminishes to zero with optimal order. We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emph{regret bounds}), (ii) high-probability tail bounds for the supremum of a collection of martingales (of a specific form arising from uniform laws of large numbers for martingales), and (iii) in-expe…
This paper introduces Zap, a generic machine learning pipeline for making predictions based on online user behavior. Zap combines well known techniques for processing sequential data with more obscure techniques such as Bloom filters, bucketing, and model calibration into an end-to-end solution. The pipeline creates we…
Continuous-time algorithms improve online learning performance.
problem Online learning with sequential data and minimizing overall regret.
method Extending discrete-time algorithms to continuous-time models for online linear optimization, adversarial bandit, and adversarial linear bandit.
result Optimal regret bounds are proven for continuous-time settings.
Adaptive truncation improves privacy in online Bayesian estimation.
problem Ensuring privacy in online Bayesian estimation of a static parameter.
method Sequential Monte Carlo, adaptive truncation, Thompson sampling.
result Adaptive truncation reduces privacy-preserving noise, enabling more accurate estimation.
Adaptive online learning algorithm improves history forgetting in nonstationary environments.
problem Adversarial nonstationary environments where future data can be very different from past data.
method Discounted regret in online convex optimization, FTRL-based algorithm, adaptive learning rate.
result Improves classical gradient descent with constant learning rate in online convex optimization.
We consider online learning with linear models, where the algorithm predicts on sequentially revealed instances (feature vectors), and is compared against the best linear function (comparator) in hindsight. Popular algorithms in this framework, such as Online Gradient Descent (OGD), have parameters (learning rates), wh…
Paper introduces online tensor inference for real-time data analysis.
problem Real-time processing of high-dimensional tensor data.
method Stochastic Gradient Descent (SGD) for efficient online inference.
result Establishes non-asymptotic convergence and optimal estimation error rate.
We present a new method for online prediction and learning of tensors ( N N N -way arrays, N > 2 N >2 N > 2 ) from sequential measurements. We focus on the specific case of 3-D tensors and exploit a recently developed framework of structured tensor decompositions proposed in [1]. In this framework it is possible to treat 3-D tensors …
New UCB algorithm for learning PSRs with tractable computation and accuracy.
problem Learning predictive state representations in sequential decision-making problems.
method Proposes a novel UCB-type algorithm with a bonus term to estimate PSRs accurately and efficiently.
result First known UCB-type approach for PSRs with guaranteed model accuracy and computational tractability.
New method constructs confidence sets for GLMs via game theory.
problem Developing reliable confidence intervals for GLM parameters.
method Reduction to sequential prediction games with low regret.
result Online-to-confidence-set conversions provide new types of intervals.