Advice-efficient prediction with expert advice (in analogy to label-efficient prediction) is a variant of prediction with expert advice game, where on each round of the game we are allowed to ask for advice of a limited number out of experts. This setting is especially interesting when asking for advice of ever…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “expert advice”
Investigates fast prediction rates with limited expert advice.
problem Minimizing excess generalization error with limited expert access.
method Assumes Lipschitz and strongly convex loss, designs novel algorithms.
result Achieves fast rates of O(1/T) with optimal number of expert advices.
A new method for learning to defer decisions with expert advice improves over standard methods.
problem Learning to defer decisions with expert advice in systems where expert information can be modified after selection.
method An augmented surrogate that operates on the composite expert-advice action space, providing consistency guarantees and excess-risk bounds.
result The method improves over standard Learning-to-Defer and adapts its advice acquisition behavior to the cost regime.
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
Improved regret bounds for bandits with expert advice.
problem Optimizing decision-making in environments with expert advice.
method Proved lower and upper bounds for regret in restricted and standard feedback models.
result Proved a new upper bound of order for the worst-case regret, matching a previously known lower bound.
Improved regret bounds for bandits with fixed expert advice using information theory.
problem Optimizing regret in bandit problems with fixed expert distributions.
method Information-theoretic analysis and KL-divergence measures.
result First regret bounds for EXP4 that can get arbitrarily close to zero under certain conditions.
Conventional learning with expert advice methods assumes a learner is always receiving the outcome (e.g., class labels) of every incoming training instance at the end of each trial. In real applications, acquiring the outcome from oracle can be costly or time consuming. In this paper, we address a new problem of active…
Improved algorithm reduces regret in corrupted expert advice setting.
problem Prediction with expert advice in the presence of adversarial corruption.
method Multiplicative Weights algorithm with decreasing step sizes.
result Achieves constant regret and optimal performance in various environments.
In the framework of prediction with expert advice, we consider a recently introduced kind of regret bounds: the bounds that depend on the effective instead of nominal number of experts. In contrast to the Normal- Hedge bound, which mainly depends on the effective number of experts but also weakly depends on the nominal…
A Generalized Online Algorithm for Translation and Scale Invariant Prediction with Expert Advicecs.LG
Generalized algorithm for translation and scale-invariant prediction.
problem Sequential prediction with expert advice, focusing on translation and scale invariance.
method Designing a generalized online algorithm using the universal prediction perspective to compete against a generic class of expert selection strategies.
result No preliminary knowledge of loss sequences is required; performance bounds are stable under arbitrary scalings and translations.
We provide the first algorithm for online bandit linear optimization whose regret after T rounds is of order sqrt{Td ln N} on any finite class X of N actions in d dimensions, and of order d*sqrt{T} (up to log factors) when X is infinite. These bounds are not improvable in general. The basic idea utilizes tools from con…
A new framework uses deep RL to aggregate expert advice for better portfolio management.
problem Improving portfolio management through expert advice and deep reinforcement learning.
method Convolutional networks for signal aggregation and historical price data, Proximal Policy Optimization algorithm.
result Our framework can achieve 90% of the best expert's profit on average.
Sharp bounds found on expert error in binary advice aggregation.
problem Aggregating binary advice from conditionally independent experts.
method Sharp upper and lower bounds on optimal error probability in asymmetric case.
result Sharp bounds recover and sharpen known results in symmetric case.
New algorithms improve prediction with expert advice under local differential privacy.
problem Predicting expert advice with privacy constraints.
method Design of two new algorithms: RW-AdaBatch and RW-Meta, leveraging limited-switching behavior and random walks.
result RW-Meta outperforms classical and central DP algorithms by 1.5-3x on predicting hospital COVID patient densities.
Improves reward bounds for prediction with expert advice using abstention.
problem Prediction with expert advice under bandit feedback with abstention.
method CBA algorithm exploiting abstention to improve reward bounds.
result Achieved significant improvement in reward bounds for general confidence-rated predictors.
A simple algorithm improves model generalization in expert advice settings.
problem Improving model generalization in expert advice settings.
method A naive aggregation algorithm for point estimations of high-dimensional nonlinear functions.
result Conditions for optimal parameter estimates through sequential mixing distribution strategies.
We prove non-asymptotic lower bounds on the expectation of the maximum of independent Gaussian variables and the expectation of the maximum of independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (…
Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimalitycs.LG
We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an algorithm based on the optimistic paradigm and on the Good-Turing missing mass estimator. We prove two different regret bounds on t…
Paper studies continuous prediction with experts' advice using differential equations.
problem Continuous prediction with experts' advice in online learning.
method Continuous-time stochastic calculus and differential equations.
result Improved guarantees for quantile regret with continuous-time algorithm.
New algorithm reduces expert prediction regret for two experts.
problem Efficient prediction with two experts under fixed time constraints.
method Optimal algorithm based on stochastic calculus techniques.
result Achieves optimal regret of sqrt(T/2π) + O(1) with O(1) per-turn processing time.
Improved prediction algorithm for 'easy' sequences with reduced regret.
problem Prediction with expert advice for 'easy' sequences.
method Variant of NormalHedge algorithm using second-order -quantile regret bound.
result Second-order -quantile regret bound of for .
A key challenge in online learning is that classical algorithms can be slow to adapt to changing environments. Recent studies have proposed "meta" algorithms that convert any online learning algorithm to one that is adaptive to changing environments, where the adaptivity is analyzed in a quantity called the strongly-ad…
This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret…
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.
New algorithms reduce label collection for online prediction with expert advice.
problem Efficiently predicting binary sequences with expert advice using fewer labels.
method Adaptive selective sampling for exponentially weighted forecasters.
result Label complexity scales roughly as the square root of the number of rounds for a scenario with a strictly better expert.
Bayesian algorithms improve online learning with adversaries over infinite action spaces.
problem Online learning with adversaries over infinite action spaces.
method Developed a Thompson sampling algorithm for online learning with an adversary's prior over the space of actions.
result Thompson sampling over a Gaussian process prior achieves a rate of against a -bounded -Lipschitz adversary.
This work addresses the classic machine learning problem of online prediction with expert advice. A new potential-based framework for the fixed horizon version of this problem has been recently developed using verification arguments from optimal control theory. This paper extends this framework to the random (geometric…
Novel algorithms for online learning with uncertain feedback graphs reduce regret.
problem Uncertainty in feedback graphs hinders traditional online learning approaches.
method Developed novel online learning algorithms to handle uncertain feedback graphs.
result Proved sublinear regret under mild conditions for the proposed algorithms.
New algorithms reduce private bandit regret to nearly non-private levels.
problem Differentially private adversarial bandits and expert advice.
method Conversion of non-private algorithms to private, new algorithms for bandits and expert advice.
result Improved regret bounds for private bandits, sublinear for small ε.
For the prediction with experts' advice setting, we construct forecasting algorithms that suffer loss not much more than any expert in the pool. In contrast to the standard approach, we investigate the case of long-term forecasting of time series and consider two scenarios. In the first one, at each step the learne…
The paper extends a prediction method to curved spaces.
problem Prediction with expert advice in curved spaces.
method Geometric considerations and adaptation of online to batch conversion.
result Extension of exponentially weighted average forecaster to non-positive curvature spaces.
Improved cumulative regret for sequence prediction with limited expert advice.
problem Minimizing cumulative regret in sequence prediction with limited information.
method Convex combination of experts with limited observation, achieving constant regret.
result Strategies achieve constant regret independent of the horizon T, improving over standard bounds.
With the increasing volume of data in the world, the best approach for learning from this data is to exploit an online learning algorithm. Online ensemble methods are online algorithms which take advantage of an ensemble of classifiers to predict labels of data. Prediction with expert advice is a well-studied problem i…
New algorithm improves bandit with graph feedback by decomposing regret.
problem Improving performance in bandit problems with graph feedback.
method Partition-based algorithm framework using regret decomposition.
result Improved and optimal regret bounds on various graph families.
We investigate the adversarial bandit problem with multiple plays under semi-bandit feedback. We introduce a highly efficient algorithm that asymptotically achieves the performance of the best switching -arm strategy with minimax optimal regret bounds. To construct our algorithm, we introduce a new expert advice alg…
We consider a variation on the problem of prediction with expert advice, where new forecasters that were unknown until then may appear at each round. As often in prediction with expert advice, designing an algorithm that achieves near-optimal regret guarantees is straightforward, using aggregation of experts. However, …
The paper tackles online learning with two types of losses and shows it's impossible without certain assumptions.
problem Online learning with primary and secondary losses where the secondary loss is bounded by a linear threshold.
method Analyzes the feasibility of achieving low regret with respect to the primary loss while keeping the secondary loss within a linear threshold.
result Achieving the goal is impossible without bounded variance assumption on the secondary loss.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for -BAI.
This paper introduces a novel optimization method for differential neural architecture search, based on the theory of prediction with expert advice. Its optimization criterion is well fitted for an architecture-selection, i.e., it minimizes the regret incurred by a sub-optimal selection of operations. Unlike previous s…
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).
We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of experts. Our main contribution is to analyze the regime where the best expert makes at most mistakes and to show that when , the expected number of mistakes made by the optima…
Efficiently optimizes boolean functions using multilinear polynomials and exponential weight updates.
problem Optimizing boolean functions over the boolean hypercube with high computational cost.
method Proposes a computationally efficient algorithm using multilinear polynomials and exponential weight updates.
result Improves computational time up to several orders of magnitude compared to state-of-the-art algorithms.
The paper shows optimal robustness against adversarial corruption in sequential decision-making problems.
problem Optimal robustness to adversarial corruption in online decision-making problems.
method Investigates prediction with expert advice and multi-armed bandit problems, focusing on algorithms with decreasing learning rates and second-order regret bounds.
result Optimal robustness can be expressed by a square-root dependency on the amount of corruption, achieving -regret.
We study a variant of decision-theoretic online learning in which the set of experts that are available to Learner can shrink over time. This is a restricted version of the well-studied sleeping experts problem, itself a generalization of the fundamental game of prediction with expert advice. Similar to many works in t…
The paper explores trade-offs between regret and variance in online learning algorithms.
problem Investigating the trade-offs between regret and variance in online learning.
method Analysis of the Exponentially Weighted Average (EWA) algorithm and its variants.
result A variant of EWA either achieves negative regret or guarantees a logarithmic bound on both variance and regret.
We consider prediction with expert advice under the log-loss with the goal of deriving efficient and robust algorithms. We argue that existing algorithms such as exponentiated gradient, online gradient descent and online Newton step do not adequately satisfy both requirements. Our main contribution is an analysis of th…
A novel algorithm for actively trading stocks is presented. While traditional expert advice and "universal" algorithms (as well as standard technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirica…
Active learning aims to reduce annotation cost by predicting which samples are useful for a human teacher to label. However it has become clear there is no best active learning algorithm. Inspired by various philosophies about what constitutes a good criteria, different algorithms perform well on different datasets. Th…