Meta-Learning Adversarial Bandits
- URL: http://arxiv.org/abs/2205.14128v1
- Date: Fri, 27 May 2022 17:40:32 GMT
- Title: Meta-Learning Adversarial Bandits
- Authors: Maria-Florina Balcan, Keegan Harris, Mikhail Khodak, Zhiwei Steven Wu
- Abstract summary: We study online learning with bandit feedback across multiple tasks, with the goal of improving average performance across tasks if they are similar according to some natural task-similarity measure.
As the first to target the adversarial setting, we design a meta-algorithm that setting-specific guarantees for two important cases: multi-armed bandits (MAB) and bandit optimization (BLO)
Our guarantees rely on proving that unregularized follow-the-leader combined with multiplicative weights is enough to online learn a non-smooth and non-B sequence.
- Score: 49.094361442409785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning with bandit feedback across multiple tasks, with the
goal of improving average performance across tasks if they are similar
according to some natural task-similarity measure. As the first to target the
adversarial setting, we design a unified meta-algorithm that yields
setting-specific guarantees for two important cases: multi-armed bandits (MAB)
and bandit linear optimization (BLO). For MAB, the meta-algorithm tunes the
initialization, step-size, and entropy parameter of the Tsallis-entropy
generalization of the well-known Exp3 method, with the task-averaged regret
provably improving if the entropy of the distribution over estimated
optima-in-hindsight is small. For BLO, we learn the initialization, step-size,
and boundary-offset of online mirror descent (OMD) with self-concordant barrier
regularizers, showing that task-averaged regret varies directly with a measure
induced by these functions on the interior of the action space. Our adaptive
guarantees rely on proving that unregularized follow-the-leader combined with
multiplicative weights is enough to online learn a non-smooth and non-convex
sequence of affine functions of Bregman divergences that upper-bound the regret
of OMD.
Related papers
- LoRA-Ensemble: Efficient Uncertainty Modelling for Self-attention Networks [52.46420522934253]
We introduce LoRA-Ensemble, a parameter-efficient deep ensemble method for self-attention networks.
By employing a single pre-trained self-attention network with weights shared across all members, we train member-specific low-rank matrices for the attention projections.
Our method exhibits superior calibration compared to explicit ensembles and achieves similar or better accuracy across various prediction tasks and datasets.
arXiv Detail & Related papers (2024-05-23T11:10:32Z) - Continual-MAE: Adaptive Distribution Masked Autoencoders for Continual Test-Time Adaptation [49.827306773992376]
Continual Test-Time Adaptation (CTTA) is proposed to migrate a source pre-trained model to continually changing target distributions.
Our proposed method attains state-of-the-art performance in both classification and segmentation CTTA tasks.
arXiv Detail & Related papers (2023-12-19T15:34:52Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
We study online meta-learning with bandit feedback.
We learn to tune online mirror descent generalization (OMD) with self-concordant barrier regularizers.
arXiv Detail & Related papers (2023-07-05T13:52:10Z) - Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
We consider the average of a very large number of smooth possibly non-size functions, and we use two widely minibatch frameworks to tackle this problem.
We define ease-controlled modifications of IG/RR schemes, which require a light additional computational effort.
We prove our implementation with both a full batch gradient (i.e. L-BFGS) and an implementation of IG/RR methods, proving that algorithms require a similar computational effort.
arXiv Detail & Related papers (2022-12-04T15:26:36Z) - Minimum-Delay Adaptation in Non-Stationary Reinforcement Learning via
Online High-Confidence Change-Point Detection [7.685002911021767]
We introduce an algorithm that efficiently learns policies in non-stationary environments.
It analyzes a possibly infinite stream of data and computes, in real-time, high-confidence change-point detection statistics.
We show that (i) this algorithm minimizes the delay until unforeseen changes to a context are detected, thereby allowing for rapid responses.
arXiv Detail & Related papers (2021-05-20T01:57:52Z) - Semi-Supervised Learning with Variational Bayesian Inference and Maximum
Uncertainty Regularization [62.21716612888669]
We propose two generic methods for improving semi-supervised learning (SSL)
The first integrates weight perturbation (WP) into existing "consistency regularization" (CR) based methods.
The second method proposes a novel consistency loss called "maximum uncertainty regularization" (MUR)
arXiv Detail & Related papers (2020-12-03T09:49:35Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
We propose a novel design-based algorithm to minimize regret in online linear and bandits.
We provide state-of-the-art finite time regret guarantees and show that our algorithm can be applied in both the bandit and semi-bandit feedback regime.
arXiv Detail & Related papers (2020-11-01T17:59:19Z) - Meta-learning with Stochastic Linear Bandits [120.43000970418939]
We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector.
We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
arXiv Detail & Related papers (2020-05-18T08:41:39Z) - PAC-Bayes meta-learning with implicit task-specific posteriors [37.32107678838193]
We introduce a new and rigorously-formulated PAC-Bayes meta-learning algorithm that solves few-shot learning.
We show that the models trained with our proposed meta-learning algorithm are well calibrated and accurate.
arXiv Detail & Related papers (2020-03-05T06:56:19Z)
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.