Continuous Prediction with Experts' Advice
- URL: http://arxiv.org/abs/2206.00236v1
- Date: Wed, 1 Jun 2022 05:09:20 GMT
- Title: Continuous Prediction with Experts' Advice
- Authors: Victor Sanches Portella, Christopher Liaw, Nicholas J. A. Harvey
- Abstract summary: Prediction with experts' advice is one of the most fundamental problems in online learning.
Recent work has looked at online learning through the lens of differential equations and continuous-time analysis.
- Score: 10.98975673892221
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Prediction with experts' advice is one of the most fundamental problems in
online learning and captures many of its technical challenges. A recent line of
work has looked at online learning through the lens of differential equations
and continuous-time analysis. This viewpoint has yielded optimal results for
several problems in online learning.
In this paper, we employ continuous-time stochastic calculus in order to
study the discrete-time experts' problem. We use these tools to design a
continuous-time, parameter-free algorithm with improved guarantees for the
quantile regret. We then develop an analogous discrete-time algorithm with a
very similar analysis and identical quantile regret bounds. Finally, we design
an anytime continuous-time algorithm with regret matching the optimal
fixed-time rate when the gains are independent Brownian Motions; in many
settings, this is the most difficult case. This gives some evidence that, even
with adversarial gains, the optimal anytime and fixed-time regrets may
coincide.
Related papers
- Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data.
Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box.
In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
arXiv Detail & Related papers (2024-03-12T08:40:21Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
We study unconstrained Online Linear Optimization with Lipschitz losses.
Motivated by the pursuit of instance optimality, we propose a new algorithm.
Central to these results is a continuous time approach to online learning.
arXiv Detail & Related papers (2023-09-27T21:54:52Z) - Bayesian Q-learning With Imperfect Expert Demonstrations [56.55609745121237]
We propose a novel algorithm to speed up Q-learning with the help of a limited amount of imperfect expert demonstrations.
We evaluate our approach on a sparse-reward chain environment and six more complicated Atari games with delayed rewards.
arXiv Detail & Related papers (2022-10-01T17:38:19Z) - Optimal Tracking in Prediction with Expert Advice [0.0]
We study the prediction with expert advice setting, where the aim is to produce a decision by combining the decisions generated by a set of experts.
We achieve the min-max optimal dynamic regret under the prediction with expert advice setting.
Our algorithms are the first to produce such universally optimal, adaptive and truly online guarantees with no prior knowledge.
arXiv Detail & Related papers (2022-08-07T12:29:54Z) - Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses [0.0]
We study the online optimization of mixable loss functions with logarithmic static regret in a dynamic environment.
For the first time in literature, we show that it is also possible to achieve near-logarithmic regret per switch with sub-polynomial complexity per time.
arXiv Detail & Related papers (2021-09-28T15:06:31Z) - Contrastive learning of strong-mixing continuous-time stochastic
processes [53.82893653745542]
Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data.
We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
arXiv Detail & Related papers (2021-03-03T23:06:47Z) - A closer look at temporal variability in dynamic online learning [19.468067110814808]
This work focuses on the setting of dynamic regret in the context of online learning with full information.
By assuming that the sequence of loss functions does not vary much with time, we show that it is possible to incur improved regret bounds compared to existing results.
arXiv Detail & Related papers (2021-02-15T16:50:16Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions.
The goal is to design algorithms that are both consistent and robust.
We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
arXiv Detail & Related papers (2020-10-22T04:51:01Z) - Temporal Variability in Implicit Online Learning [15.974402990630402]
tightest regret analyses only show marginal improvements over Online Mirror Descent.
We prove a novel static regret bound that depends on the temporal variability of the sequence of loss functions.
We present an adaptive algorithm that achieves this regret bound without prior knowledge of the temporal variability.
arXiv Detail & Related papers (2020-06-12T22:50:34Z) - Time-varying Gaussian Process Bandit Optimization with Non-constant
Evaluation Time [93.6788993843846]
We propose a novel time-varying Bayesian optimization algorithm that can effectively handle the non-constant evaluation time.
Our bound elucidates that a pattern of the evaluation time sequence can hugely affect the difficulty of the problem.
arXiv Detail & Related papers (2020-03-10T13:28:33Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
We propose a systematic method to transform operations into operations that are differentiable and never locally constant.
Our approach relies on perturbeds, and can be used readily together with existing solvers.
We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
arXiv Detail & Related papers (2020-02-20T11:11:32Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.