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

• An Adversarial Analysis of Thompson Sampling for Full-information Online Learning: from Finite to Infinite Action Spaces [54.37047702755926]
  We develop an analysis of Thompson sampling for online learning under full feedback. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret.
  arXiv  Detail & Related papers  (2025-02-20T18:10:12Z)
• Learning to Partially Defer for Sequences [17.98959620987217]
  We present an L2D setting for sequence outputs where the system can defer specific outputs of the whole model prediction to an expert. We also empirically demonstrate that such granular deferrals achieve better cost-accuracy tradeoffs than whole deferrals on Traveling salesman solvers and News summarization models.
  arXiv  Detail & Related papers  (2025-02-03T15:50:11Z)
• Rethinking Early Stopping: Refine, Then Calibrate [49.966899634962374]
  We show that calibration error and refinement error are not minimized simultaneously during training. We introduce a new metric for early stopping and hyper parameter tuning that makes it possible to minimize refinement error during training. Our method integrates seamlessly with any architecture and consistently improves performance across diverse classification tasks.
  arXiv  Detail & Related papers  (2025-01-31T15:03:54Z)
• 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)
• 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.