Fast rates for prediction with limited expert advice

• URL: http://arxiv.org/abs/2110.14485v1
• Date: Wed, 27 Oct 2021 14:57:36 GMT
• Title: Fast rates for prediction with limited expert advice
• Authors: El Mehdi Saad (CELESTE, LMO), Gilles Blanchard (LMO, DATASHAPE)
• Abstract summary: We investigate the problem of minimizing the excess generalization error with respect to the best expert prediction in a finite family under limited access to information. We show that if we are allowed to see the advice of only one expert per round for T rounds in the training phase, the worst-case excess risk is $Omega$ (1/ $sqrt$ T) with probability lower bounded by a constant. We design novel algorithms achieving this rate in this setting, and give precise instance-dependent bounds on the number of training rounds and queries needed to achieve a given generalization error precision.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of minimizing the excess generalization error with respect to the best expert prediction in a finite family in the stochastic setting, under limited access to information. We assume that the learner only has access to a limited number of expert advices per training round, as well as for prediction. Assuming that the loss function is Lipschitz and strongly convex, we show that if we are allowed to see the advice of only one expert per round for T rounds in the training phase, or to use the advice of only one expert for prediction in the test phase, the worst-case excess risk is $\Omega$(1/ $\sqrt$ T) with probability lower bounded by a constant. However, if we are allowed to see at least two actively chosen expert advices per training round and use at least two experts for prediction, the fast rate O(1/T) can be achieved. We design novel algorithms achieving this rate in this setting, and in the setting where the learner has a budget constraint on the total number of observed expert advices, and give precise instance-dependent bounds on the number of training rounds and queries needed to achieve a given generalization error precision.

Related papers

• Proper losses regret at least 1/2-order [1.7986307635828565]
  We show that the strict properness of a loss is necessary and sufficient to establish a non-vacuous surrogate regret bound. We also show that the order of convergence in p-norm cannot be faster than the $1/2$-order of surrogate regrets for a broad class of strictly proper losses.
  arXiv  Detail & Related papers  (2024-07-15T03:46:15Z)
• Loss Shaping Constraints for Long-Term Time Series Forecasting [79.3533114027664]
  We present a Constrained Learning approach for long-term time series forecasting that respects a user-defined upper bound on the loss at each time-step. We propose a practical Primal-Dual algorithm to tackle it, and aims to demonstrate that it exhibits competitive average performance in time series benchmarks, while shaping the errors across the predicted window.
  arXiv  Detail & Related papers  (2024-02-14T18:20:44Z)
• Inverse Reinforcement Learning with Sub-optimal Experts [56.553106680769474]
  We study the theoretical properties of the class of reward functions that are compatible with a given set of experts. Our results show that the presence of multiple sub-optimal experts can significantly shrink the set of compatible rewards. We analyze a uniform sampling algorithm that results in being minimax optimal whenever the sub-optimal experts' performance level is sufficiently close to the one of the optimal agent.
  arXiv  Detail & Related papers  (2024-01-08T12:39:25Z)
• Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
  We consider the problem of ranking n experts based on their performances on d tasks. We make a monotonicity assumption stating that for each pair of experts, one outperforms the other on all tasks.
  arXiv  Detail & Related papers  (2023-06-05T06:55:39Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times) The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
  arXiv  Detail & Related papers  (2023-03-03T04:39:53Z)
• On Second-Order Scoring Rules for Epistemic Uncertainty Quantification [8.298716599039501]
  We show that there seems to be no loss function that provides an incentive for a second-order learner to faithfully represent its uncertainty. As a main mathematical tool to prove this result, we introduce the generalised notion of second-order scoring rules.
  arXiv  Detail & Related papers  (2023-01-30T08:59:45Z)
• Constant regret for sequence prediction with limited advice [0.0]
  We provide a strategy combining only p = 2 experts per round for prediction and observing m $ge$ 2 experts' losses. If the learner is constrained to observe only one expert feedback per round, the worst-case regret is the "slow rate" $Omega$($sqrt$ KT)
  arXiv  Detail & Related papers  (2022-10-05T13:32:49Z)
• 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)
• Memory Bounds for the Experts Problem [53.67419690563877]
  Online learning with expert advice is a fundamental problem of sequential prediction. The goal is to process predictions, and make a prediction with the minimum cost. An algorithm is judged by how well it does compared to the best expert in the set.
  arXiv  Detail & Related papers  (2022-04-21T01:22:18Z)
• No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling [12.933990572597583]
  We focus on the fundamental and practical aggregation method known as logarithmic pooling. We consider the problem of learning the best set of parameters in an online adversarial setting. We present an algorithm that learns expert weights in a way that attains $O(sqrtT log T)$ expected regret.
  arXiv  Detail & Related papers  (2022-02-22T22:27:25Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  We consider a prediction problem with two experts and a forecaster. We assume that one of the experts is honest and makes correct prediction with probability $mu$ at each round. The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster.
  arXiv  Detail & Related papers  (2020-03-18T20:12:08Z)

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.