summaries: This paper focus on the performance of the Thompson sampling algorithm under the misspecification of the prior distribution. The authors propose a general family of n-Monte Carlo algorithm, which contains the canonical TS algorithm as a special case. The authors then proceed to show that the regret difference of a misspecified prior up to horizon H of an n-MC algorithm is of order H^2*eps, where eps is the amount of misspecification measured by the total variation distance. The results are applied to the meta-learning setting, in which one also aims to learn the prior. The paper concludes by a synthetic numerical experiment to show the benefit of meta-learning.

summaries: The paper establishes the theory for quantifying the sensitivity of a class of Bayesian bandit algorithms under misspecified prior, with Thompson sampling being a special case. It is also shown that the sensitivity bound is tight in the worst-case sense. Using the sensitivity analysis, the paper studies the sample complexity of Bayesian meta-learning in two special cases (Beta prior+Bernoulli reward and Gaussian prior+Gaussian reward). Finally, the aforementioned theory is generalized to the more general setting, the Bayesian POMDPs.

summaries: In this paper, the authors study how prior mis-specification would impact the performance of bayesian bandit algorithms. In particular, the authors provide an upper and a lower bound for a wide class of algorithms, which include Thompson sampling algorithms as a special case. The results are complemented by applications in meta learning and numerical experiments.

summaries: This paper studies the effect of prior misspecification in Thompson sampling (TS) and related posterior sampling bandit algorithms. They are able to show that the regret due to such algorithms using a misspecified prior incurs additional regret that is linear in the total variation distance between the improper and true prior.  Additionally, the paper considers estimating such priors in a meta-learning setting, where an agent interacts sequentially with multiple bandit instances whose model parameters are sampled from the same unknown prior. The authors provide bounds on the total variation distance for the estimated priors when the prior is Beta or Gaussian.

summaries: This article presents some very nice results on posterior-sampling-based bandit algorithms with mis-specified priors. The algorithms are those like Thompson sampling, in which the actions selected are functions of draws from the posterior distribution to date (an approximation of knowledge gradient is also analysed as part of a wider class of posterior-sample-based decision algorithms, and this is shown to be an improvement on TS). Results apply both to standard bandit settings and to meta-learning settings in which a series of short episodes are attempted. Theory and experiments are impressive.

abstractText: Thompson sampling and other Bayesian sequential decision-making algorithms are among the most popular approaches to tackle explore/exploit trade-offs in (contextual) bandits. The choice of prior in these algorithms offers flexibility to encode domain knowledge but can also lead to poor performance when misspecified. In this paper, we demonstrate that performance degrades gracefully with misspecification. We prove that the expected reward accrued by Thompson sampling (TS) with a misspecified prior differs by at most Õ(Hε) from TS with a well-specified prior, where ε is the total-variation distance between priors and H is the learning horizon. Our bound does not require the prior to have any parametric form. For priors with bounded support, our bound is independent of the cardinality or structure of the action space, and we show that it is tight up to universal constants in the worst case. Building on our sensitivity analysis, we establish generic PAC guarantees for algorithms in the recently studied Bayesian meta-learning setting and derive corollaries for various families of priors. Our results generalize along two axes: (1) they apply to a broader family of Bayesian decision-making algorithms, including a MonteCarlo implementation of the knowledge gradient algorithm (KG), and (2) they apply to Bayesian POMDPs, the most general Bayesian decision-making setting, encompassing contextual bandits as a special case. Through numerical simulations, we illustrate how prior misspecification and the deployment of one-step look-ahead (as in KG) can impact the convergence of meta-learning in multi-armed and contextual bandits with structured and correlated priors.

authors:
Shipra Agrawal
Navin Goyal

title: Analysis of thompson sampling for the multi-armed bandit problem

venue: Conference on Learning Theory,

authors:
Marc Abeille
Alessandro Lazaric

title: Linear thompson sampling revisited

venue: International Conference on Artificial Intelligence and Statistics,

title: Improved regret bounds for thompson sampling in linear quadratic control problems

venue: International Conference on Machine Learning,

authors:
Mohammad Gheshlaghi Azar
Alessandro Lazaric
Emma Brunskill

title: Sequential transfer in multi-armed bandit with finite set of models

venue: Advances in Neural Information Processing Systems,

authors:
Yasin Abbasi-Yadkori
Csaba Szepesvári

title: Bayesian optimal control of smoothly parameterized systems

venue: Conference on Uncertainty in Artificial Intelligence,

authors: Jonathan Baxter. Theoretical models of learning to learn

title: In Learning to learn

venue: Springer,

title: A model of inductive bias learning

venue: Journal of Artificial Intelligence Research,

authors:
Omar Besbes
Yonatan Gur
Assaf Zeevi

title: Stochastic multi-armed-bandit problem with non-stationary rewards

authors:
Arindam Banerjee
Srujana Merugu
Inderjit S Dhillon
Joydeep Ghosh
John Lafferty

title: Clustering with bregman divergences

venue: Journal of Machine Learning Research,

title: Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory

venue: Institute of Mathematical Statistics,

authors:
Hamsa Bastani
David Simchi-Levi
Ruihao Zhu

title: Meta dynamic pricing: Transfer learning across experiments

venue: Available at SSRN 3334629,

authors:
Leonardo Cella
Alessandro Lazaric
Massimiliano Pontil

title: Meta-learning with stochastic linear bandits

authors:
Wang Chi Cheung
David Simchi-Levi
Ruihao Zhu

title: Hedging the drift: Learning to optimize under non-stationarity

venue: Available at SSRN 3261050,

authors:
Simon S Du
Sham M Kakade
Ruosong Wang

title: and Lin F Yang

venue: Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations,

authors:
Yan Duan
John Schulman
Xi Chen
Peter L Bartlett
Ilya Sutskever
Pieter Abbeel

title: RL2: Fast reinforcement learning via slow reinforcement learning

authors:
Dylan J Foster
Claudio Gentile
Mehryar Mohri
Julian Zimmert

title: Adapting to misspecification in contextual bandits

authors:
Anupam Gupta
Tomer Koren
Kunal Talwar

title: Better algorithms for stochastic bandits with adversarial corruptions

authors:
Aurélien Garivier
Eric Moulines

title: On upper-confidence bound policies for switching bandit problems

venue: Conference on Algorithmic Learning Theory,

authors:
Aditya Gopalan
Shie Mannor
Yishay Mansour

title: Thompson sampling for complex online problems

authors:
Mohammad Ghavamzadeh
Shie Mannor
Joelle Pineau
Aviv Tamar

title: Bayesian reinforcement learning: A survey

venue: Foundations and Trends® in Machine Learning,

authors:
Jiachen Hu
Xiaoyu Chen
Chi Jin
Lihong Li
Liwei Wang

title: Near-optimal representation learning for linear bandits and linear RL

authors:
Jan Humplik
Alexandre Galashov
Leonard Hasenclever
Pedro A Ortega
Yee Whye Teh
Nicolas Heess

title: Meta reinforcement learning as task inference

authors:
Sepp Hochreiter
A Steven Younger
Peter R Conwell

title: Learning to learn using gradient descent

venue: International Conference on Artificial Neural Networks,

authors: Sham Machandranath Kakade. On the sample complexity of reinforcement learning

title: PhD thesis

venue: University College London,

authors:
Emilie Kaufmann
Nathaniel Korda
Rémi Munos

title: Thompson sampling: An asymptotically optimal finite-time analysis

venue: International Conference on Algorithmic Learning Theory,

authors:
Branislav Kveton
Mikhail Konobeev
Manzil Zaheer
Chih-wei Hsu
Martin Mladenov
Craig Boutilier
Csaba Szepesvari

title: Meta-thompson sampling

title: Lectures on the Coupling Method

venue: Courier Corporation,

authors:
Che-Yu Liu
Lihong Li

title: On the prior sensitivity of thompson sampling

authors:
Thodoris Lykouris
Vahab Mirrokni
Renato Paes Leme

title: Stochastic bandits robust to adversarial corruptions

venue: Symposium on Theory of Computing,

authors:
Tor Lattimore
Csaba Szepesvari
Gellert Weisz

title: Learning with good feature representations in bandits and in rl with a generative model

title: Machine learning: a probabilistic perspective

venue: MIT press,

authors:
Ian Osband
Benjamin Van Roy

title: Why is posterior sampling better than optimism for reinforcement learning

venue: In International Conference on Machine Learning,

authors:
My Phan
Yasin Abbasi Yadkori
Justin Domke

title: Thompson sampling and approximate inference

authors:
Ilya O Ryzhov
Warren B Powell
Peter I Frazier

title: The knowledge gradient algorithm for a general class of online learning problems

venue: Operations Research,

title: Simple bayesian algorithms for best arm identification

authors:
Daniel Russo
Benjamin Van Roy

title: An information-theoretic analysis of thompson sampling

venue: The Journal of Machine Learning Research,

title: A bayesian framework for reinforcement learning

authors:
Songsak Sriboonchita
Wing-Keung Wong
Sompong Dhompongsa
Hung T Nguyen. Stochastic dominance
applications to finance

title: risk and economics

venue: CRC Press,

authors:
Ram C. Tripathi
Ramesh C. Gupta
John Gurland

title: Estimation of parameters in the beta binomial model

venue: Annals of the Institute of Statistical Mathematics,

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

venue: Biometrika,

title: Explanation-based neural network learning: A lifelong learning approach

authors: Sebastian Thrun. Lifelong learning algorithms

title: In Learning to learn

title: High-dimensional probability: An introduction with applications in data science

venue: Cambridge University Press,

authors:
Benjamin Van Roy
Shi Dong

title: Comments on the du-kakade-wang-yang lower bounds

authors:
Jane X Wang
Zeb Kurth-Nelson
Dhruva Tirumala
Hubert Soyer
Joel Z Leibo
Remi Munos
Charles Blundell
Dharshan Kumaran
Matt Botvinick

title: Learning to reinforcement learn

venue: Annual Meeting of the Cognitive Science Society,

authors:
Chen-Yu Wei
Haipeng Luo

title: Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach

authors:
Jiaqi Yang
Wei Hu
Jason D Lee
Simon S Du

title: Impact of representation learning in linear bandits

authors:
Julian Zimmert
Yevgeny Seldin

title: Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits

heading: 1 Introduction

text:
Bayesian decision-making algorithms are widely popular, due to both strong empirical performance and the flexibility afforded by incorporating inductive biases and domain knowledge through priors. However, in practical applications, any chosen prior is at best an approximation of the true environment in which the algorithm is deployed. This raises a critical question:
How sensitive are Bayesian decision-making algorithms to prior misspecification?
For decision-making problems with a very large horizon, it suffices that the misspecified prior places a vanishingly small probability mass on the ground truth environment; this condition is referred to informally as a “grain of truth.” This is because, in the large-horizon limit, Bayesian algorithms (like many non-Bayesian methods) should converge to the optimal policy.
∗Massachusetts Institute of Technology, msimchow@mit.edu †Columbia University ‡Microsoft Research NYC §Massachusetts Institute of Technology
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
But in many practical settings, decision-making takes place on shorter time scales. Consider a news recommendation website that, when presented with a new user, sequentially offers a selection of currently trending articles. Such a system may only have a few opportunities to make recommendations before the user decides to navigate away, leaving little time to correct for misspecified or underspecified prior knowledge. Such examples are described more broadly by the meta-learning paradigm, where a single learning agent must complete multiple disparate-though-related tasks.
In meta-learning problems, and in short-horizon problems more broadly, the “grain of truth” argument paints a rather uninformative picture. Consequently, recent work has begun to explore sensitivity bounds in applications with shorter horizons [LL16, KKZ+21]. However, these recent works focus on particular classes of priors and/or reward models, as well as on the Thompson sampling algorithm specifically. Notably, this leaves open questions about the extent to which prior sensitivity is determined by properties of the Bayesian decision-making algorithm, the reward model, and the prior itself.

heading: 1.1 Our Contributions

text:
Motivated by meta-learning problems with short task horizons, we establish general, distributionindependent, and worst-case optimal bounds on the sensitivity of Bayesian algorithms to prior misspecification. We focus on the Bayesian bandit setting, where a mean-vector “environment” µ is drawn from a distribution P , and rewards for each action are drawn in accordance with µ. We study the performance of Bayesian algorithms which operate according to a misspecified prior P ′.
Sensitivity of Thompson Sampling and Related Bayesian Bandit Algorithms. As a concrete example, we consider the expected reward obtained by Thompson sampling with misspecified prior P ′ under environments drawn from true prior P .
When the mean rewards lie in the range [0, 1], as in the Bernoulli reward setting, we show that the difference in expected reward between Thompson sampling with P ′ and with P is at most twice the total variation distance between P and P ′ multiplied by the square of the horizon length. We prove a lower bound demonstrating that, for worst-case priors, this result is tight up to constants. Moreover, our upper bound holds for any two priors P and P ′ and suffers no dependence on the complexity of the decision space.
We extend this result in two directions. First, we remove the boundedness requirement on the mean reward range, showing that so long as certain tail probability conditions on the prior means are satisfied, a similar result holds. Second, we generalize beyond Thompson sampling, bounding the prior sensitivity of a broad class of Bayesian bandit algorithms, which we term n-Monte Carlo algorithms. Our lower bounds extend to this class, verifying sharp dependence on the parameter n.
Sample Complexity of Bayesian Meta-Learning. We apply our prior sensitivity results to the Bayesian bandit meta-learning setting, in which a meta-learner iteratively interacts on bandit instances that are sampled from an unknown prior distribution. Motivated by our sensitivity analysis we describe a generic algorithmic recipe for Bayesian meta-learning, in which the meta-learner explores for several episodes to estimate the prior and then exploits by instantiating a Bayesian decision-maker with the learned prior. We formally consider two instantiations of this setup: (1) the Beta-Bernoulli setting where the rewards are Bernoulli and the prior is a product of Beta distributions and (2) the Gaussian-Gaussian setting where the rewards are Gaussian and the prior is a Gaussian (with arbitrary covariance structure) over the means. We note that the Gaussian-Gaussian setting was recently studied in [KKZ+21] but only for the diagonal covariance setting.
Bayesian Decision-Making Beyond the Bandit Setting. A striking feature of our proof is that it makes no explicit reference to the structure of bandit decision-making. As a consequence, our results extend seamlessly to both contextual bandits and the most general Bayesian decision-making problem: Bayesian POMDPs. While our sensitivity bounds hold almost verbatim in these settings, we note that estimating the prior may be statistically much more challenging in these scenarios, so there is no free lunch. To facilitate readability of the paper, we defer all further discussion and formal results to Appendix E.
Experimental results. We complement our meta-learning theory with synthetic experiments in multi-armed and contextual bandit settings. Our experiments show the benefits of (a) meta-learning broadly, (b) estimating higher-order moments of the prior distribution, and (c) using less myopic
algorithms like the Knowledge Gradient [RPF12] over Thompson sampling when faced with structured environments.

heading: 1.2 Related Work

text:
Bayesian Decision-Making. Bayesian decision-making broadly refers to a class of algorithms that use Bayesian methods to estimate various problem parameters, and then derive decision/allocation rules from these estimates. The study of Bayesian decision-making began with the seminal work of Thompson [Tho33], who introduced the Thompson sampling algorithm for adaptive experiment design in clinical trials. Thompson sampling later gained popularity in the reinforcement learning community as a means to solve multi-armed bandit and tabular reinforcement learning problems [Str00, OVR17], and has been extended in many directions [AL17, AL18, GMM14]. Recent years have seen the proliferation of other Bayesian decision-making and learning algorithms, including Information Directed Sampling [RVR16], Top-Two Thompson Sampling [Rus16], and Knowledge Gradient [RPF12].
Sensitivity Analysis and Frequentist Regret. The field of robust Bayesian analysis examines the sensitivity of Bayesian inference to prior and model misspecification (c.f., [BMP+94]). These approaches typically do not consider decision-making, so they do not account for multi-step adaptive sampling inherent in our setting. More recent works study frequentist regret for Thompson sampling [AG12, KKM12]. These guarantees can be interpreted as controlling the sensitivity to arbitrary degrees of prior misspecification, but consequently, they do not provide a precise picture of how misspecification affects performance. Moreover, frequentist guarantees for Thompson sampling focus on relatively long learning horizons, so they are less relevant in the context of meta-learning with many short-horizon tasks.
Short-Horizon Sensitivity. Most closely related to our paper are two previous works on sensitivity of Thompson sampling to small amounts of misspecification in short-horizon settings. [LL16] study the sensitivity of Thompson sampling for two-armed bandits when the prior has finite support. More recently, [KKZ+21] study meta-learning with Thompson sampling and derive sensitivity bounds for Thompson sampling in multi-armed bandits with Gaussian rewards and independent-across-arm Gaussian priors. In contrast to both of these works, the bounds presented in this work apply to arbitrary families of priors, more general decision-making problems, and to more general families of decision-making algorithms. Further, as illustrated in Remark 2, our bounds are also tighter than those achieved by [KKZ+21] when specialized to their precise setting. Finally, our lower bounds demonstrate that the square-horizon factor incurred in [KKZ+21] is unavoidable for worst-case priors (though perhaps not for their special case).
[BSLZ19] study sensitivity of general Bayesian algorithms in a dynamic pricing context. Their approach requires “sufficiently random” reward noise and applies only to algorithms with a nonadaptive initial exploration phase (unlike true Thompson Sampling); under these conditions, they show that the trajectories under a well-specified and misspecified Bayesian decision maker can be coupled so that the two algorithms maintain the same posteriors with good probability. In contrast, our analysis applies only to Bayesian decision-making algorithms which have sufficient “internal randomness” (e.g., Thompson sampling, and more generally, the n-Monte Carlo algorithms). Our approach obviates assumptions about reward noise and initial exploration at the expense of slightly restricting the class of algorithms to which our guarantees apply.
Meta-learning and Meta-RL. Meta-learning is a classical learning paradigm in which a learner faces many distinct-but-related tasks [Thr96, Thr98, Bax98, Bax00, HYC01]. While the classical work primarily considered supervised learning tasks, recent, predominantly empirical work has focused on meta-reinforcement learning (Meta-RL), where each task is itself a decision-making problem (c.f., [WKNT+17, DSC+16]). This includes some Bayesian approaches [HGH+20]. While there have been some theoretical results on Meta-RL [ALB13, CLP20, YHLD21, HCJ+21], apart from [KKZ+21] we are not aware of other theoretical treatments with a Bayesian flavor.
Learning under model misspecification. This work studies a specific notion of misspecification: running Bayesian decision-making algorithms with inexact approximations of a true underlying prior. Numerous other types of mispecification have been considered by the learning theory community more
broadly, although typically in the absence of meta-learning and in frequentist settings. These include models where rewards may be changing with time [GM11, BGZ14, CSLZ18, WL21] or adversarially corrupted [LMPL18, GKT19, ZS21], or where a simple function class (e.g., linear models) is used to approximate a more complex reward function [DKWY20, VRD19, LSW20, FGMZ20]. The Bayesian analog of these models is that the likelihood is misspecified, which is quite different from the prior misspecification considered here. Translating these notions of misspecification to Bayesian decision-making and unifying these lines of work remains an exciting direction for future research.

heading: 2 Setting and Notation

text:
Throughout, we use bold v to denote vectors and non-bold va to denote scalars. When the vector vh has a subscript, vh,a denotes its coordinates.
Bayesian Bandit Learning under Misspecification. A Bayesian bandit learning instance is specified by (a) an abstract action space A, (b) a parametric family of priors Pθ indexed by parameters θ ∈ Θ over mean vectors µ ∈ RA with coordinates µa, and (c) a function D : RA → ∆(RA) mapping mean vectors µ to distributions over reward vectors r ∈ RA such that the expected reward under D(µ) is µ, i.e., Er∼D(µ)[r] = µ.5 Note that this general setup allows the prior Pθ to encode complex dependencies between the mean rewards µa of actions a ∈ A. We consider an episodic bandit protocol with horizon H . First, µ ∼ Pθ is drawn from the prior. Then, at each time step h = 1, 2, . . . ,H , the learner’s policy, specified by an algorithm alg, selects an action ah ∈ A. Simultaneously, a reward vector rh is drawn independently from D(µ), and the learner observes reward rh = rh,ah . The choice of action ah may depend on the partial trajectory τh−1 = (a1, r1, . . . , ah−1, rh−1). We let Pθ,alg denote the joint law over µ and the full trajectory τH , while expectations are denoted Eθ,alg. We abbreviate the full trajectory τ = τH . We denote the cumulative reward
R(θ, alg) := Eθ,alg [∑H h=1 rh ] = Eθ,alg [∑H h=1 µah ] .
Bayesian Learning Algorithms. We study a class of algorithms alg(θ) also parameterized by θ ∈ Θ. For concreteness, the reader may think of alg(θ) as corresponding to Thompson sampling, where the learner internally computes posteriors using Pθ as its prior. More general classes of Bayesian algorithms are defined in Section 3.1. We are interested in the consequences of misspecification; that is, interacting with µ ∼ Pθ, but executing alg(θ′) for some other θ′ ̸= θ. Note that our notation for the induced law on the trajectory is Pθ,alg(θ′).
Episodic Bayesian Meta-Learning. We apply the above framework to the problem of Bayesian meta-learning. Let θ⋆ ∈ Θ be a ground-truth parameter. At each episode t = 1, 2, . . . , T , a mean parameter µ(t) is drawn i.i.d. from Pθ⋆ . Simultaneously, the learner commits to a (potentially nonBayesian) exploration strategy explore(t) and collects the induced trajectory τ(t). At the end of T episodes, the learner selects a parameter θ̂ ∈ Θ as a function of τ(1), . . . , τ(T ). The learner’s performance is evaluated on the expected reward of the plug-in algorithm on θ̂: R(θ⋆, alg(θ̂)).
Further notation. Given two probability distributions P and Q over the same probability space (Ω,F), we denote their total variation TV(P ∥ Q) := supE∈F |P [E ]−Q[E ]| and Kullback-Leibler divergence KL(P ∥ Q). If P is a joint distribution of random variables (X,Y, Z, . . . ), P (X) denotes the marginal of X under P , and P (Y |X) the conditional distribution (as a function of random variable X). We define the diameter of a mean vector as diam(µ) := supa∈A µa− infa∈A µa, which is a random variable when µ is drawn from Pθ. Throughout, log(·) denotes the natural logarithm. Given a space X , we let ∆(X ) be the set of probability distributions on X ; see Appendix B.1 for measure-theoretic considerations.
5In fact, our analysis extends to more general cases where the reward distribution is parameterized by more than just the mean vectors, but we restrict ourselves to the current setting for ease of exposition.

heading: 3 Prior Sensitivity in Bayesian Learning

text:
This section states sensitivity bounds for various Bayesian bandit algorithms and families of priors, starting with the concrete instance of Thompson sampling under priors with bounded-range means. Our results extend almost verbatim to more general decision-making tasks such as contextual bandits; see Appendix E for further details. Throughout, we use the fact that the posterior distribution of the mean µ given trajectories τh does not depend on the choice of learning algorithm alg; hence, we denote these posteriors Pθ[· | τh−1].6
Recall the classical Thompson sampling algorithm: at each step h, TS(θ) draws a mean µ̃h ∼ Pθ[· | τh−1] and selects the reward-maximizing action ah ∈ argmaxa µ̃h,a. We say that the prior Pθ is B-bounded if Pθ[diam(µ) ≤ B] = 1. For Thompson sampling under B-bounded priors, we have the following result: Corollary 3.1. Let Pθ be B-bounded. Then, the suboptimality of misspecified Thompson sampling TS(θ′) on instance θ is at most
|R(θ,TS(θ))−R(θ,TS(θ′))| ≤ 2H2 · TV(Pθ ∥ Pθ′) ·B.
Corollary 3.1 follows directly from Theorem 3.2, which we state in Section 3.2, and which generalizes the statement of the corollary along two axes: to a more general family of Bayesian algorithms that we call “n-Monte Carlo” and to less restrictive conditions on the behavior of diam(µ), such as sub-Gaussian tails. Due to lack of space, we focus on the first such generalization; the second direction is more technical in nature, and we leave its exposition to Appendix B.2.
3.1 n-Monte Carlo algorithms
Unfortunately, for arbitrary Bayesian bandit algorithms, the behavior under two different priors cannot always be controlled in terms of the total variation distance of their priors. Indeed, consider an algorithm that always pulls a particular arm a⋆ if the prior places any probability mass on a mean for which a⋆ is best; clearly, this algorithm’s behavior is not robust to small changes in its prior distribution. However, many important Bayesian bandit algorithms, such as Thompson sampling, are not arbitrary functions of their priors; rather, they select actions based on their internal posterior distribution in a relatively stable manner. We call such algorithms n-Monte Carlo algorithms. Definition 3.1 (n-Monte Carlo algorithm). Given n > 0, we say that a family of algorithms alg(·) parameterized by θ ∈ Θ is n-Monte Carlo if, for any θ, θ′, step h ≥ 1, and partial trajectory τh−1,
TV(Palg(θ)(ah | τh−1) ∥ Palg(θ′)(ah | τh−1)) ≤ n · TV(Pθ(µ | τh−1) ∥ Pθ′(µ | τh−1)).
In words, n-Monte Carlo algorithms are those Bayesian algorithms for which small changes in the posterior distribution result in small changes (up to a multiplicative factor of n) in the distribution over actions. Note that on the left-hand side, we do not need to specify the true θ⋆, because each algorithm’s choice of an action can only depend on τh−1. The nomenclature arises because any algorithm that selects actions based exclusively on n samples from its posterior Pθ(µ | τh−1) is n-Monte Carlo. However, the definition is more general and in Appendix C we describe various algorithms that satisfy the n-Monte Carlo property, summarizing key insights here:
• We show that TS(θ) is 1-Monte Carlo. • We introduce a generalization of Thompson sampling, which we call k-shot Thompson sampling
(k-TS(θ)), that samples k means µ̃1, . . . , µ̃k i.i.d. from the posterior Pθ[· | τh−1], and selects the action ah ∈ argmaxa max{µ̃1,a, . . . , µ̃k,a}. We show that k-TS(θ) is k-Monte Carlo. • We introduce a Monte Carlo approximation of the knowledge gradient algorithm [RPF12], which we call two-step Receding Horizon Control (2-RHC(θ)). This algorithm is non-myopic in that it chooses an action that maximizes the expected value at the subsequent time (according to its own posterior updates). We show that when A is finite, 2-RHC(θ) is n-Monte Carlo for some n that is polynomial in |A| and the number of Monte Carlo samples it draws from its posterior.
6Note that whenever τh lies in the support of Pθ , the posterior Pθ[µ | τh−1] is well-defined and unique, even if τh−1 was generated by interacting with mean µ ∼ Pθ′ for some θ′ ̸= θ. When τh−1 does not lie in the support of Pθ , we allow Pθ[µ | τh−1] to be any distribution over µ (for concreteness, one may default to Pθ[µ]). Note, however, that although Pθ[µ | τh−1] may not be uniquely defined, Pθ,alg[τh−1 | µ] is always uniquely defined and independent of θ.

heading: 3.2 General Sensitivity Upper and Lower Bounds

text:
We are now ready to state a general prior sensitivity bound for n-Monte Carlo algorithms. For simplicity, we state our bounds for B-bounded priors, that is, Pθ[diam(µ) ≤ B] = 1, and under a natural sub-Gaussian tail condition stated formally in Appendix B.2 (Theorem B.2). Theorem 3.2. Let alg(·) be an n-Monte Carlo family of algorithms on horizon H ∈ N, and let θ, θ′ ∈ Θ. Setting ε = TV(Pθ ∥ Pθ′), we have the following guarantees.
(a) If Pθ is B-bounded, then |R(θ, alg(θ))−R(θ, alg(θ′))| ≤ 2nH2ε ·B. (b) If Pθ is coordinate-wise σ2-sub-Gaussian, then
|R(θ, alg(θ))−R(θ, alg(θ′))| ≤ 2nH2ε ( diam(Eθ[µ]) + σ ( 8 + 5 √ log ( |A|2 min{1,2nHϵ} ))) .
Next, we complement our upper bound with a lower bound that matches Theorem 3.2(a) for n-shot Thompson sampling (an n-Monte Carlo algorithm) up to a multiplicative constant: Theorem 3.3 (Lower Bound, Informal). For any parameter n ∈ N, horizon H ≫ 1, number of arms N = |A| ≫ H , and separation ϵ≪ 1/nH , there exist two priors Pθ and Pθ′ over bounded means µ ∈ [0, 1]N such that TV(Pθ ∥ Pθ′) = ϵ and
R(θ, n-TS(θ)) ≥ R(θ, n-TS(θ′)) + (1− o(1)) · nH 2ϵ
2 ,
where the o(1) decays to zero as 1/H , H/N , ϵnH → 0.
See Theorem D.1 for a precise, quantitative statement and Appendix D for a full proof. Remark 1 (Comparison to Õ( √ H) regret guarantees). At first glance, Theorem 3.3 appears inconsistent with known upper bounds for Thompson sampling which show that regret relative to the best action in hindsight scales sublinearly as Õ( √ |A|H) in the horizon H . Notice however that our lower bound requires the number of actions |A| to scale at least linearly in H , so the bound applies in a regime where regret upper bounds are in fact vacuous. Instead, the purpose of our lower bound is to quantify the influence of the misspecified prior for fixed horizons, but where the magnitude TV(Pθ ∥ Pθ′) of the misspecification may be arbitrarily small.
Proof ideas. One of the key ingredients in the proof of Theorem 3.2, and a result which may be of independent interest, is the following bound on the total variation of the trajectory of an algorithm run with the true prior and the same algorithm run with an incorrect prior. Proposition 3.4. Let alg(·) be an n-Monte Carlo family of algorithms on horizon H ∈ N. Then,
TV(PH ∥ P ′H) ≤ 2nH · TV(Pθ ∥ Pθ′),
where PH = Pθ,alg(θ)(µ, τH) and P ′H = Pθ,alg(θ′)(µ, τH).
A full proof is given in Appendix B.6 and relies on a careful coupling argument between the two trajectories detailed therein. As a concrete warmup, we illustrate this coupling for a Gaussian bandit instance in Appendix B.5. The factor of H arises from a telescoping argument (Lemma B.9) based on the performance-difference lemma [Kak03].
For B-bounded priors, Proposition 3.4 directly translates into the sensitivity bound in Theorem 3.2(a), where the difference in rewards can be bounded as BH times the probability that the trajectory of alg(θ) differs from the trajectory of alg(θ′). Addressing more general tail conditions like subGaussianity requires more care; see Appendix B for details.

heading: 4 Meta-learning

text:
In this section, we apply the above prior sensitivity guarantees to episodic Bayesian meta-learning and obtain sample-efficiency guarantees for canonical Bayesian bandit setups.
Suppose an episodic Bayesian meta-learner uses an exploration strategy explore(t) in T episodes and computes an estimate θ̂ = θ̂(τ(1), . . . , τ(T )) of the ground-truth parameter θ⋆. Suppose further that, for any ε, δ ∈ (0, 1), with probability at least 1− δ over the realizations of the episodes and internal
randomization of the meta-learner, the estimate θ̂ satisfies TV(Pθ⋆ ∥ Pθ̂) ≤ ε. Then, Theorem 3.2 implies that, for any n-Monte Carlo algorithm alg(·), the relative performance of alg(θ̂) compared to alg(θ⋆) is (essentially) bounded as Õ(nH2ε) over horizon H .
Our task of designing meta-learners is thus reduced to that of designing estimators (and exploration strategies) for θ⋆ that enjoy convergence guarantees in TV distance. This is quite a general recipe that can produce concrete meta-learning algorithms in many Bayesian bandit settings. We explain how to do so in two setups: (1) Pθ⋆ is a product of Beta distributions, and the rewards are Bernoulli; (2) Pθ⋆ is a multivariate Gaussian and the rewards are Gaussian.

heading: 4.1 Beta Priors and Bernoulli Rewards

text:
We first consider the situation where the prior distribution is a product of Beta distributions Pθ⋆ =⊗ a∈A Beta(α ⋆ a, β ⋆ a) and the reward distribution is a product of Bernoulli distributions D(µ) =⊗
a∈A Bern(µa). Recall that Beta(α, β) for α > 0 and β > 0 is a continuous probability distribution supported on (0, 1), and hence our parameter space Θ is the (strictly) positive orthant in R2|A|. Our approach is to directly estimate the parameters θ⋆ = (α⋆,β⋆) from the observed rewards in the T episodes. Since the family of Beta distributions is an exponential family [Bro86] (with (α, β) being the natural parameters), we can appeal to general statistical theory to bound the total variation distance between two such distributions in terms of their parameter distance.
Suppose we adopt the exploration strategy where arm 1 is selected in the first n rounds in each of the first T/|A| episodes, arm 2 in the next T/|A| episodes, and so on. (We assume the horizon H and n satisfy H ≥ n ≥ 2.) We focus on the estimation of (α⋆1, β⋆1), as the exact same approach works for all of the arms. Let Xt denote the cumulative reward collected in the first n rounds of episode t. Then, the random variables X1, . . . , XT/|A| are i.i.d. draws from a Beta-Binomial distribution with parameters (α⋆1, β ⋆ 1 , n), where n denotes the number of trials of the binomial component. The first and second moments of Xt are
m⋆1 = E[Xt] = nα⋆1
α⋆1 + β ⋆ 1
and m⋆2 = E[X2t ] = nα⋆1(n(1 + α ⋆ 1) + β ⋆ 1)
(α⋆1 + β ⋆ 1)(1 + α ⋆ 1 + β ⋆ 1)
.
These moments uniquely determine α⋆1 and β ⋆ 1 as long as n ≥ 2. Therefore, we can estimate (α⋆1, β⋆1) using plug-in estimates of the first two moments (m⋆1,m ⋆ 2) via the method of moments [TGG94]. Using this approach, we obtain the following sample complexity guarantee for estimating the prior distribution:
Theorem 4.1. The exploration strategy and estimator described above enjoy the following guarantee. If Pθ⋆ = ⊗ a∈A Beta(α ⋆ a, β ⋆ a) and D(µ) = ⊗ a∈A Bern(µa), then there is a constant C depending only on (α⋆,β⋆) such that, for any ε, δ ∈ (0, 1), if H ≥ 2 and
T ≥ C · |A| 2 log(|A|/δ) ε2 ,
then P[TV(Pθ⋆ ∥ Pθ̂) ≤ ε] ≥ 1− δ.
The proof of the theorem is given in Appendix F.1.

heading: 4.2 Gaussian Priors and Gaussian Rewards

text:
We now consider the situation where the prior distribution is a multivariate Gaussian Pθ⋆ = N (ν⋆,Ψ⋆) in RA, and the reward distribution is a spherical Gaussian distribution D(µ) = N (µ, σ2I). Note that such a prior distribution is able to capture correlations between the arms’ mean rewards in an episode, which cannot be captured by the product-form priors in the previous subsection (nor in previous work [KKZ+21]).
We again directly estimate the parameters θ⋆ = (ν⋆,Ψ⋆) using a simple exploration strategy and the method of moments. In each episode (which we assume to have H ≥ 2), we select independent and uniformly random actions in the first two rounds. Let at and bt denote the actions taken in episode t, and let rt and st denote the corresponding observed rewards. Our estimates for ν⋆ and Ψ⋆ based on
the information collected in T episodes are7
ν̂ := |A| T T∑ t=1 rteat and Ψ̂ := |A|2 T T∑ t=1 rtst ( eate T bt + ebte T at ) − ν̂ν̂T.
For these estimators, we have the following theorem. Theorem 4.2. The exploration strategy and estimator described above enjoy the following guarantee. If Pθ⋆ = N (ν⋆,Ψ⋆) andD(µ) = N (µ, σ2I), then there is a constant C depending only on (ν⋆,Ψ⋆) and σ2 such that, for any ε, δ ∈ (0, 1), if H ≥ 2 and
T ≥ C · (|A| 4 + |A|3 log(1/δ))
ε2 ,
then P[TV(Pθ⋆ ∥ Pθ̂) ≤ ε] ≥ 1− δ.
The proof of the theorem and the precise dependence on ν⋆, Ψ⋆, and σ2 are given in Appendix F.2. The quartic dependence on |A| is due to estimating Ψ⋆; it improves to |A|2 if Ψ⋆ is known. Remark 2 (Comparison to [KKZ+21]). [KKZ+21] study the case where Pθ⋆ = N (ν⋆, σ20I), which is a product-form prior over means µ with known σ20 . For ϵ̃ = |A| · ∥ν⋆ − ν̂∥∞/σ0, they show that8
|R(θ,TS(θ))−R(θ,TS(θ̂))| ≤ O ( ∥ν⋆∥∞ + σ0 √ log(H/ϵ̃) ) ·H2ϵ̃.
On the other hand, Theorem 3.2 applied to the 1-Monte Carlo Thompson Sampling algorithm (and bounding diam(ν⋆) ≤ ∥ν⋆∥∞) yields the same inequality, but with ϵ̃ replaced by ϵ = TV(N (ν⋆, σ20I) ∥ N (ν̂, σ20I)) ≤ ∥ν⋆ − ν̂∥2/σ0. Note that ϵ̃ is always larger than ϵ by a factor of at least √ |A|; thus, our result is strictly sharper.

heading: 5 Experiments

text:
We demonstrate the generality of our results in three distinct meta-learning experimental settings. First, we study a simple multi-armed bandit scenario with Gaussian prior and Gaussian rewards, where we demonstrate how meta-learning higher-order moments of the prior can significantly improve performance. Next, we consider a Gaussian linear contextual bandits scenario, to demonstrate the generality of Bayesian meta-learning. Finally, we study a more interesting multi-armed bandit problem with discrete priors, where, in addition to the value of meta-learning, we see that look-ahead algorithms can substantially outperform Thompson sampling. Additional experimental details are presented in Appendix A.
Gaussian MAB. Our first scenario is a multi-armed bandit problem with Gaussian prior and Gaussian reward. The instance has |A| = 6 arms and each episode has horizon H = 10. The prior is N (ν⋆,Ψ⋆) where ν⋆ = [0.5, 0, 0, 0.1, 0, 0] and Ψ⋆ has block structure so that arms 1, 2, 3 are
7This estimator can be generalized to explore for more of the episode and use more of the observed rewards. 8The following optimizes Lemma 5 of [KKZ+21] over its free parameter δ > 0 for ϵ̃ small.
highly correlated, and analogously for arms 4, 5, 6. The rewards are Gaussian with variance 1, which is known to all learners.
We run four algorithms. Two are non-meta-learning Thompson sampling algorithms: OracleTS, which uses the correct prior, and MisTS, which uses the misspecified prior N (0, I). We also run MetaTS:no-cov which only attempts to meta-learn the prior mean µ0 and assumes that the prior covariance matrix is the identity (this algorithm is essentially the one studied in [KKZ+21]). Finally, our algorithm is MetaTS:full which meta-learns both the prior mean and covariance. Both meta-learners are run in an explore-then-commit fashion where the first T0 episodes are used for exploration.9
In Figure 1, we plot the cumulative average per-episode reward for each algorithm, where for the metalearners we sweep over many choices of T0 and display the pointwise best (i.e., the upper envelope). The experiment clearly shows the value of meta-learning as both MetaTS:no-cov and MetaTS:full quickly outperform misspecified TS. Additionally, we also see the importance of learning the covariance matrix, even though it can require many samples. Indeed, the final performance of MetaTS:full with T0 = 5K, ignoring the regret incurred due to exploration, is competitive with OracleTS, while MetaTS:no-cov asymptotes to a much lower performance (see Figure 3 in Appendix A).
Gaussian linear contextual bandits. Our second experiment concerns Gaussian linear contextual bandits. Here we run OracleTS, MisTS, and MetaTS:full, on a synthetic linear contextual bandit problem where there are |A| = 6 actions each with a d = 6 dimensional action feature (generated stochastically at each time step), and with horizon H = 20. The prior is over the linear parameter µ that determines the reward for action-feature xa ∈ Rd as r(a) ∼ N (⟨µ,xa⟩, 1). We set the prior as N (1,Ψ⋆) where Ψ⋆ is a scaled-down version of the block diagonal matrix used in the previous experiment. In the right panel of Figure 1 we again see that by meta-learning the prior, we quickly outperform the misspecified approach and asymptotically achieve the oracle performance. This demonstrates that Bayesian meta-learning is quite broadly applicable and highlights the importance of our general theoretical development.
Discrete bandits. Finally, we study a synthetic MAB setting with |A| = 20 arms and a prior supported on a finite set of 16 reward distributions (tasks), under each of which rewards are deterministic. The instance is visualized in the left panel of Figure 2. It is constructed so that each task has a unique optimal arm and there are four arms that can quickly identify which task the agent is in (arms A1, A6,
9For MetaTS:no-cov, we follow [KKZ+21] and only use the first step of each exploration episode for exploration, switching to TS with the current prior estimate for the rest of the episode. On the other hand, MetaTS:full explores for all time steps in the first T0 episodes.
A11, A16), so that it can infer the optimal arm. Additionally, the prior is concentrated on the first four tasks, so that pulling the first identifying arm almost always reveals the current task.
We evaluate 6 algorithms: Oracle, Misspecified, and Meta-learning each with TS and Monte-Carlo Knowledge Gradient (an instantiation of the 2-RHC(θ) algorithm detailed in Appendix C) as the base learners, and we visualize the results in the top right panel of Figure 2. Perhaps more revealing is the bottom right panel of Figure 2, where we visualize the empirical distribution over the first arm pull in each episode for each algorithm. We see that OracleTS typically plays uniformly over arms A2–A5 in the first round as these are highly likely to be the optimal arm under the prior, while MisTS plays uniformly over the 16 plausibly optimal arms. MetaTS quickly learns to play uniformly over arms A2–A5 and is asymptotically competitive with OracleTS.
The interesting property of this instance is that playing the identifying arms is crucial for optimal behavior. However, since TS is myopic and these arms never produce large rewards, TS will never play them. Thus, to achieve optimal behavior, we must use a less myopic base learner like Knowledge Gradient. As can be seen, both OracleKG and MisKG first play the identifying arms, where the oracle almost always pulls the first one while MisKG plays them uniformly. The performance of OracleKG is much better than all TS configurations. Finally, the meta-learning configuration of Knowledge Gradient quickly learns to pull the first identifying arm and competes with OracleKG.

heading: 6 Discussion

text:
In our simulations, we demonstrated the superiority of more expressive prior families (e.g., modeling means and covariances) and non-myopic base algorithms (e.g., Knowledge Gradient) over less expressive priors (e.g., product measures) and greedy base learners (e.g., Thompson sampling). Notably, the generality and flexibility of our theoretical contributions ensure robustness to prior misspecification even for these richer priors and sophisticated base learners.
Still, theory and experiments alike point to a tradeoff: despite the potential for improved performance, richer prior families are harder to learn, and some base learners (e.g., n-Monte Carlo algorithms for large n) can be more sensitive to incorrect priors. It is an exciting direction for future work to investigate the joint problems of model selection (over priors) and algorithm selection (over base learners) in order to optimally navigate these tradeoffs. Perhaps model and algorithm selection can be coupled so that certain base learners exhibit improved performance, or greater robustness, over certain classes of priors. We would like to further understand how these tradeoffs interface with computational burdens of using certain priors and base learners, and whether our sensitivity analysis extends to computationally efficient approximations of sampling-based decision-making algorithms (e.g., via Laplace approximations, MCMC, Gibbs Sampling, and Variational Methods; the long-horizon performance of Thompson sampling under approximate inference has already been studied [PAYD19]). Finally, we hold hope that a more instance-dependent analysis may improve our sensitivity bounds for certain families of priors, which may in turn inform more clever exploration strategies that circumvent worst-case tradeoffs.

heading: Acknowledgements

text: The authors thank Wen Sun for many discussions that helped shape the current paper. At the time of writing, Max Simchowitz was generously supported by an Open Philanthropy AI Fellowship, and the research was initiated during his internship at MSR New York and PhD at UC Berkeley. Research was initiated during Thodoris Lykouris’ postdoc at MSR New York. Daniel Hsu is supported by NSF grants CCF-1740833, DMREF-1534910, IIS-1563785; a Bloomberg Data Science Research Grant, a JP Morgan Faculty Award, and a Sloan Research Fellowship; Christoper Tosh is also supported by NSF grant CCF-1740833 and Daniel Hsu’s JP Morgan Faculty Award.

title: Bayesian decision-making under misspecified priors with applications to meta-learning


summaries: The paper studies the problem of approximately learning a target function (in the realizable case) when having access to an equivalence-query oracle. In this direction an exponential separation is shown between the two learning models by using an algorithm that borrows ideas from boosting techniques. Furthermore, the authors connect the counterexamples returned from the equivalence query oracle to adversarial examples and thus try to connect their work with adversarially robust learning.

summaries: This work studies the query complexity of learning general hypothesis classes $(X,H)$ in the randomized equivalence query model (w/ PAC guarantees). In this interactive model, the learner has access to the “EQ oracle” which upon input of a hypothesis in H, outputs a random counterexample (based upon the target concept and marginal distribution chosen originally by the adversary). The authors use a boosting procedure to show that learning in the randomized EQ model requires only $d*\text{polylog}(1/\varepsilon)$ queries where $d$ is the VC-dimension of $(X,H)$. This provides an exponential separation with the PAC model, which takes $\Omega(d/\varepsilon)$ queries to achieve the same guarantees.  The authors motivate this theoretical result by tying it to recent research in adversarial robustness. They argue that the EQ model can be seen as adversarial training against a restricted adversary. They claim that their results give a theoretical explanation of recent experimental work showing that (on-manifold) adversarial training achieves good generalization, and argue that the exponential separation could be used as a potential tool to prove robustness against such adversaries.

summaries: The paper studies the query complexity of learning a VC class under a certain query model called the Equivalence-Query (EQ) model by Angluin'98. In this model, given a distribution $\mathcal{D}$ and the ground truth $g$, the learner interacts with the data in the following way: (1) learner selects a function f and (2) learner receives a random counter-example distributed according to $\mathcal{D}$, that is, a random draw from $\mathcal{D}|_{f \ne g}$. Under this model, the authors prove an exponentially improved upper bound of $d \cdot \mathsf{polylog}(1/\epsilon)$ compared to the $d/\epsilon$ bound for PAC learning. The paper further draws connections between this model of learning and adversarial robustness. The main argument here relies on viewing the equivalence-query sample oracle as the adversary restricted to on-manifold attacks.

summaries: The main result of the paper is showing a separation between the sample complexity of PAC model and the query complexity of an interactive model called Equivalence-Query-learning. The interactive model requires exponentially fewer queries/samples (in the mistake parameter - epsilon). Further, the implication of this result on the adversarial robustness is discussed.

summaries: This paper introduces a new abstract learning model called the EQ-learning, in which the oracle returns examples that the current classifier gets incorrect (rather than arbitrary examples drawn from the data distribution) and returns YES if no such examples exist (indicating the current classifier is correct). They then provide an algorithm which achieves a sample complexity (assuming finite VC dimension d)that is polylog in $1/\epsilon$ as opposed to $O(1/\epsilon)$. This is an exponential increase, and is a very interesting theoretical result on its own.  They then argue how their formalism plays a role in learning from on-manifold adversarial examples. In particular, each of these examples reveals a point that the classifier gets incorrect, and their result consequently suggests that learning from these results should improve the training procedure.

abstractText: We prove an exponential separation for the sample/query complexity between the standard PAC-learning model and a version of the Equivalence-Query-learning model. In the PAC model all samples are provided at the beginning of the learning process. In the Equivalence-Query model the samples are acquired through an interaction between a teacher and a learner, where the teacher provides counterexamples to hypotheses given by the learner. It is intuitive that in an interactive setting fewer samples are needed. We make this formal and prove that in order to achieve an error ✏ exponentially (in ✏) fewer samples suffice than what the PAC bound requires. It was shown experimentally by Stutz, Hein, and Schiele that adversarial training with on-manifold adversarial examples aids generalization (compared to standard training). If we think of the adversarial examples as counterexamples to the current hypothesis then our result can be thought of as a theoretical confirmation of those findings. We also discuss how our result relates to adversarial robustness. In the standard adversarial model one restricts the adversary by introducing a norm constraint. An alternative was pioneered by Goldwasser et. al. Rather than restricting the adversary the learner is enhanced. We pursue a third path. We require the adversary to return samples according to the Equivalance-Query model and show that this leads to robustness. Even though our model has its limitations it provides a fresh point of view on adversarial robustness.

title: Queries and concept learning

authors:
D. Angluin
T. Dohrn

title: The power of random counterexamples

venue: Proceedings of the 28th International Conference on Algorithmic Learning Theory,

authors:
S. Bhambri
S. Muku
A.S. Tulasi
A.B. Buduru

title: A study of black box adversarial attacks in computer

venue: vision. ArXiv,

authors:
B. Biggio
I. Corona
D. Maiorca
B. Nelson
N. Šrndić
P. Laskov
G. Giacinto
F. Roli

title: Evasion attacks against machine learning at test time

venue: Machine Learning and Knowledge Discovery in Databases,

authors:
N.H. Bshouty
D. Gavinsky

title: Pac=paexact and other equivalent models in learning

venue: In The 43rd Annual IEEE Symposium on Foundations of Computer Science,

authors:
S. Bubeck
Y.T. Lee
E. Price
I. Razenshteyn

title: Adversarial examples from computational constraints

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
P.-Y. Chen
H. Zhang
Y. Sharma
J. Yi
C.-J. Hsieh

title: Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec

title: Optimal decision functions for computer character recognition

venue: J. ACM,

authors:
L. Engstrom
B. Tran
D. Tsipras
L. Schmidt
A. Madry

title: A rotation and a translation suffice: Fooling CNNs with simple transformations, 2019

authors:
S. Garg
S. Jha
S. Mahloujifar
M. Mohammad

title: Adversarially robust learning could leverage computational hardness

venue: Proceedings of the 31st International Conference on Algorithmic Learning Theory,

authors:
J. Gilmer
L. Metz
F. Faghri
S.S. Schoenholz
M. Raghu
M. Wattenberg
I.J. Goodfellow

title: Adversarial spheres

venue: In 6th International Conference on Learning Representations,

authors:
G. Gluch
R.L. Urbanke

title: Query complexity of adversarial attacks

authors:
I.J. Goodfellow
J. Shlens
C. Szegedy

title: Explaining and harnessing adversarial examples

venue: URL http://arxiv.org/abs/1412.6572. cite arxiv:1412.6572

title: The optimal sample complexity of pac learning

venue: J. Mach. Learn. Res.,

authors:
J. Hayes
G. Danezis

title: Machine learning as an adversarial service: Learning black-box adversarial examples

authors:
D. Kingma
J. Ba

title: Adam: A method for stochastic optimization

authors:
Y. Liu
X. Chen
C. Liu
D. Song

title: Delving into transferable adversarial examples and black-box attacks

authors:
A. Madry
A. Makelov
L. Schmidt
D. Tsipras
A. Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: In International Conference on Learning Representations,

authors:
N. Papernot
P. McDaniel
I. Goodfellow
S. Jha
Z.B. Celik
A. Swami

title: Practical black-box attacks against machine learning

authors:
A. Rozsa
M. Günther
T.E. Boult

title: Are accuracy and robustness correlated

venue: In 2016 15th IEEE International Conference on Machine Learning and Applications (ICMLA),

title: The strength of weak learnability

venue: Mach. Learn.,

authors:
Y. Song
R. Shu
N. Kushman
S. Ermon

title: Constructing unrestricted adversarial examples with generative models

venue: Advances in Neural Information Processing Systems,

authors:
D. Stutz
M. Hein
B. Schiele

title: Disentangling adversarial robustness and generalization

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society,

authors:
F. Tramer
D. Boneh

title: Adversarial training and robustness for multiple perturbations

authors:
F. Tramèr
A. Kurakin
N. Papernot
I. Goodfellow
D. Boneh
P. McDaniel

title: Ensemble adversarial training: Attacks and defenses

authors:
D. Tsipras
S. Santurkar
L. Engstrom
A. Turner
A. Madry

title: Robustness may be at odds with accuracy

title: A theory of the learnable

venue: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing,

authors:
E. Wong
J.Z. Kolter

title: Provable defenses against adversarial examples via the convex outer adversarial polytope

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
C. Xiao
B. Li
J.-Y. Zhu
W. He
M. Liu
D. Song

title: Generating adversarial examples with adversarial networks, 2018

authors:
H. Xiao
K. Rasul
R. Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017

authors:
K.Y. Xiao
V. Tjeng
N.M.M. Shafiullah
A. Madry

title: Training for faster adversarial robustness verification via inducing reLU stability

authors:
Z. Zhao
D. Dua
S. Singh

title: Generating natural adversarial examples

authors:
T. Zheng
C. Chen
K. Ren

title: Distributionally adversarial attack

venue: Proceedings of the AAAI Conference on Artificial Intelligence, 33:2253–2260,

title: Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No] We used code provided in different work, where such error bars are not produced. (d) Did you include the total amount of compute and the type of resources used (e.g., type

heading: 1 Introduction

text:
We analyze the connections between adversarial training, generalization and robustness. Our key technical contribution is a novel result in the field of learning theory, showing an exponential separation for the sample/query complexity of two learning models. This result provides a theoretical confirmation for the experimental observations in Stutz et al. [2019] and points to a fresh research direction in the field of adversarial robustness.
Let us start with a discussion of our main technical contribution. The first model we consider is the PAC-learning introduced in Valiant [1984]. In this model the learner is given i.i.d. samples from an unknown distribution and is tasked with finding a hypothesis with low generalization error. The second model is a version of Equivalence-Query-learning (EQ-learning) introduced in [Angluin, 1988]. In this setting samples are acquired through an interaction between a teacher and a learner. In each round of interaction the learner presents a hypothesis and the teacher replies with a counterexample for this hypothesis. Very close models to the model we study were considered previously in Angluin and Dohrn [2017] and Bshouty and Gavinsky [2002]. In this setting the counterexamples produced by the teacher come from the data distribution constrained to being in the error set of the presented hypothesis. We use ideas similar to those used in boosting techniques [Schapire, 1990] to prove that in the EQ-learning model O(d · polylog(1/✏)) queries suffices to achieve a standard error of ✏, where d is the VC-dimension of the hypothesis class. This improves on the previously known
35th Conference on Neural Information Processing Systems (NeurIPS 2021), Sydney, Australia.
bounds of O(d/✏). We refer the reader to Section 3 for an in depth review of previous literature on the subject. Standard results for the sample complexity in the PAC model yields an upper bound of O(d/✏). Comparing the two results we see the advertised, exponential (in ✏), separation.
Let us discuss an “application” of our theorem to the relationship between adversarial robustness and generalization. In [Tsipras et al., 2019, Su et al., 2018] it is argued that there is an inherent trade-off between robustness and accuracy whereas in Gilmer et al. [2018], Rozsa et al. [2016] the authors make the case that robustness improves with accuracy. This seeming contradiction is partially resolved in Stutz et al. [2019] where it is pointed out that it crucially depends on whether adversarial examples are on or off the data manifold. It is worth mentioning that at the beginning of the field of adversarial robustness it was argued that the reason for the existence of adversarial examples is exactly that they are off-manifold [Tanay and Griffin, 2016]. However later on it was demonstrated that adversarial examples do also exist on-manifold [Zhao et al., 2018, Song et al., 2018]. The authors of Stutz et al. [2019] argue that it is important to understand this distinction. They introduce a version of adversarial training [Goodfellow et al., 2014, Madry et al., 2018, Tramèr et al., 2018, Xiao et al., 2019], which they call on-manifold adversarial training, where the adversarial examples are constrained to lie on the data manifold. They then show empirically that using on-manifold adversarial training one achieves better generalization in comparison to standard training (with the same number of samples). Our theorem can be seen as providing a theoretical support for this claim.
We also explore connections of our results to adversarial robustness. Before we describe these connections in detail, let us position this work in a broader context. Most of the literature on adversarial robustness considers adversaries whose perturbations are in some way restricted. A very common form of restriction is to bound the perturbation in the `0, `2, or `1 norm [Raghunathan et al., 2018, Wong and Kolter, 2018], but other perturbations (rotations, shifts, etc.) were also considered [Engstrom et al., 2019]. A recent paper [Goldwasser et al., 2020] argues that in order to obtain security for real-world systems we need to consider models beyond these "restricted perturbations." Unfortunately this change comes at a price: e.g., the results in Goldwasser et al. [2020] are based on the assumption that the learner can decide not to give an answer for some inputs (selective learning [Chu, 1965]) and that they see the test set upfront (transductive learning), thus the capabilities of the learner are enhanced. We follow a third path. Instead of restricting the type of perturbations that can be applied by the adversary or enhancing the learner we require the adversary to return counterexamples according to the EQ-model. We then show that the exponential separation theorem leads to robustness in our model in the following way: Th main idea of cryptography is to base security on computational hardness of specific problems. We follows this idea and base the security of our scheme on the hardness of learning. More specifically, our adversarial learning scheme computes a classifier that is robust assuming that the underlying learning task is hard in the low error regime.

heading: 2 Models of learning and attack

text:
We start by defining the models of learning considered in this paper.
Notation. For i 2 N we define [i] := [1, 2, . . . , i]. We use log to denote the log to the base 2. For a function f ! { 1,+1} and A ✓ X we define f A as a function that is equal to f at X \A and flips the prediction for points in A. For a distribution D on X and A ✓ X we denote by D|A the conditional distribution that is equal (up to scaling) to D on A and 0 on the complement.
Throughout the paper we consider only the realizable version of learning. That is, we assume that there is a feature space X , a distribution D on X , a hypothesis class H and a function h 2 H, h : X ! { 1,+1}, that defines the ground truth on D. The learner knows X and H but neither knows h nor D. The goal of the learner is to find an f : X ! { 1,+1} that has small risk. The risk is defined as RD,h(f) := Px⇠D[f(x) 6= h(x)]. We will consider algorithms that have access to one of the following two oracles:
Example Query Oracle according to D (EXD). When queried, EXD returns (x, h(x)), where x ⇠ D.
Equivalence Query Oracle according to D (EQD) [Angluin, 1988]. For every f : X ! { 1,+1} (not necessarily from H) the result of querying EQD(f) is a counterexample to f dis-
tributed according to D. More formally it is x ⇠ D|f 6=h. If RD,h(f) = 0 then EQD(f) returns "YES" indicating that f is equivalent to h. For every k 2 N we write EQD(f, k) to denote an oracle that returns k i.i.d. samples, each generated by EQD(f).
Next we define the two learning models for which we later show the advertised exponential separation. All our results are based on them.
PAC-learning. We say that a learning algorithm L PAC-learns H if for every ✏, 2 (0, 1) there exists m(✏, ) 2 N such that for every h 2 H and distribution D algorithm L(✏, ) asks m(✏, ) queries to the Example Query Oracle EXD and with probability 1 returns a function f 2 H such that RD,h(f)  ✏.
EQ-learning We say that a learning algorithm L EQ-learns H if for every ✏, 2 (0, 1) there exists m(✏, ) 2 N such that for every h 2 H and distribution D algorithm L(✏, ) asks m(✏, ) queries to the Equivalence Query Oracle EQD and with probability 1 returns a function f : X ! { 1,+1} such that RD,h(f)  ✏.

heading: 3 Exponential Separation

text:
We start this section with a short literature review.
It is worth mentioning that there is a slight difference between EQ-learning model and the model from Angluin and Dohrn [2017]. In Angluin and Dohrn [2017] X and H are finite, the learner has to return the exact hypothesis h that was chosen by the teacher, and the distribution on counterexamples is known, For us, on the other hand, X and H may be infinite, our goal is to return a function of small risk, and the distribution on counterexamples is not known.
The model from Bshouty and Gavinsky [2002], which is called Probably Almost Exact (PAE) is almost equal to the EQ-learning we consider. The difference is that in the PAE the goal of the learner is to return a hypothesis with negligible error (1/!(poly(n)), where n measures measures the “size” of the input. In the EQ-learning on the other hand we want to explore the dependence on ✏ in detail.
In Angluin and Dohrn [2017] it is shown that for a concept class |H| = n it is enough to ask log(n) queries. As we mentioned the setting is different and it’s not clear how to adapt this result to the EQ-learning, where we don’t need to find the hypothesis exactly (apart from other differences mentioned above). In Bshouty and Gavinsky [2002], where the model considered is closer to ours, it is shown that PAC-learnability =) PAE-learnability. A direct application of their technique in our setting yields an upper bound on the query complexity, which is no better than O(d/✏). No simple modification of this technique would yield the desired O(d · polylog(1/✏)) query complexity. We significantly extend the ideas from Bshouty and Gavinsky [2002] to obtain our result.

heading: 3.1 Main result

text:
We are now ready to state the main result of the paper, which is an exponential separation for the sample complexity between PAC-learning and EQ-learning. Theorem 1. There exists a learning algorithm (Algorithm 1) such that for every ✏ 2
0, 132 , 2
(0, 1), every hypothesis class H of VC-dimension d, for every distribution D the algorithm invoked with parameters ✏, ,H EQ-learns H asking
O((d+ log(1/ )) log9(1/✏)) queries.
To compare this result to the PAC model we recall that a slightly improved version of the PAC bound in the realizable case [Hanneke, 2016] states that for a hypothesis class H of VC-dimension d in order to learn (with constant probability) a classifier of risk ✏ it suffices to use O d
✏
samples. This result is
tight in a sense that there exist hypothesis classes and distributions for which that many samples are necessary. Theorem 1 guarantees that in the EQ-learning model O(d · polylog(1/✏)) many queries suffice. This is an exponential improvement. Why is this possible?
Imagine that there is a ground truth g 2 H that you try to learn and that you already found h 2 H such that RD,g(h)  ⌘. Then the counterexample oracle EQD(h, ·) provides you with samples from a distribution D|h 6=g. Querying the oracle O(d) times you get a sample S EQD(h,O(d)). You
can now use the PAC bound: if you find an h0 2 H that is consistent with S then you know that it has an error of at most 1/2 on D|h 6=g . It is then natural to define
Combine(h, h0)(x) = ⇢ h(x), if x 2 h = g h 0(x), if x 2 h 6= g .
Note that Combine(h, h0) has an error of at most ⌘/2. If we repeated this procedure log(1/✏) times, thus asking O(d log(1/✏)) queries, you would find a classifier with error ✏.
Unfortunately it is not possible to compute Combine(h, h0). Afterall, if you knew the region of the input space where h 6= g then you could just flip the prediction of h in that region and the resulting classifier would have zero error. But it turns out that the general intuition of decreasing the error by a multiplicative factor after every O(d) queries can indeed be achieved. The key to this result is to find a computable version of Combine(h, h0, ...) that guarantees an exponentially fast decay of the error.
Our algorithm is mainly inspired by boosting techniques, most notably by an approach from Bshouty and Gavinsky [2002]. In this work the authors consider capabilities of polynomially bounded learners. If we assume that the "complexity" of the hypothesis class H is measured by its VC-dimension then the relevant result from Bshouty and Gavinsky [2002] can be summarized as follows. If we have an algorithm LPAC that learns H to a constant error in time (the authors focus on time but the time is of course an upper-bound for the sample complexity) time(d) then this algorithm can be boosted to an algorithm LEQ that learns H in the EQ-model to an error 1
!(poly(d)) in time poly(time(d)).
Let us apply this boosting technique to our setting. Assume that LPAC runs in time O(d) (as this is the number of samples that are required by the standard PAC bound to learn to constant error). Then the boosting algorithm can be used to produce LEQ that learns H to error ✏. What bound on the run time of LEQ do we get? Unfortunately this bound is no better than O d
✏
. This is exactly what the
standard PAC bound provides in the first place. Thus, disappointingly, a direct application of these ideas do not yield a benefit in using the EQ-model versus using the PAC-model.
To get the claimed exponential separation between the two models we develop a boosting-like algorithm that differs significantly in several important aspects and hence also requires a different proof technique. The main idea is to compute h1, . . . , hO(polylog(1/✏)) 2 H in a sequential manner and then to define the final hypothesis as a version of a majority vote of these functions.
The simplified, high level, structure of the algorithm is as follows. Repeat the following for t = O(polylog(1/✏)) steps: at step i ask the oracle for Si EQD("Majority"(h1, . . . , hi 1), O(d)) and then define hi := FindConsistent(Si,H) (FindConsistent returns a function from H that agrees with all samples from Si). At the end return "Majority"(h1, . . . , ht). To make this approach work we need to ensure that the error sets of h1, . . . , ht are sufficiently independent.
The following points need particular attention. First, note that the EQD provides the algorithm with samples from the error set only. Thus, correctly classified points at one stage will not automatically remain correctly classified at later stages. To make sure this happens, at every step i we include in the training set Si samples from carefully chosen regions of the feature space that are already classified correctly (this is done in the inner "for" loop of the algorithm). Second, a simple majority vote of the previously constructed classifiers is not sufficient to get the desired result. This is true since a non-negligible region of the feature space might become incorrectly classified with higher and higher confidence by such a majority vote. This is the reason we clip the values of votes to a fixed interval (for details see Definition 1).
We start now with the formal definition of the algorithm.

heading: 3.2 The Algorithm

text:
In this section we give formal definitions of the concepts used in the algorithm. The proof of correctness of the algorithm is deferred to the appendix. As discussed above we cannot define the final prediction as a simple majority vote. That is why we need to “clip” the votes in a particular way and use a non-standard majority vote-like procedure. Now we define these notions formally. Definition 1 (Vote and Majority). For ✏ 2 (0, 1) we define B✏ := 2dlog(1/✏)e+1 and clip✏ : Z ! Z as:
clip ✏ (x) := min(max( B✏, x), B✏).
Algorithm 1 EQlearner Input: hypothesis class H of VC-dimension d, target error ✏, target confidence , Equivalence query oracle EQD.
✏ 0 := ✏105 log4(1/✏) B✏0 := 2dlog(1/✏0)e+ 1 m := O (d+ log(B4
✏0) + log(1/ )) ·B 4 ✏0
t := O B 3 ✏0 h1 2 H for i = 2 to t do Si := EQD(Maj(h1, . . . , hi 1),m) for v 2 [B✏0 ] \ 2Z+ 1 do h 0 := Maj(h1, . . . , hi 1) [Vote(h1, . . . , hi 1) 2 {v, v}]
S v i := EQD(h0,m)
end for hi := FindConsistent ⇣ Si [ S v2[B✏0 ] S v i ,H ⌘
end for
Return Maj(h1, h2, . . . , ht)
For a sequence of functions h1, . . . , hi : X ! { 1,+1}, ✏ 2 (0, 1) and x 2 X , we define Vote(h1, . . . , hi)(x) recursively as:
Vote(h1, . . . , hi)(x) :=
clip ✏ (Vote(h1, . . . , hi 1)(x) + 2hi(x)) ,
Vote(h1)(x) := h1(x).
Similarly, for a sequence of functions h1, . . . , hi : X ! { 1,+1}, ✏ 2 (0, 1) and a ground truth function g we define Voteg(h1, . . . , hi)(x) recursively as:
Voteg(h1, . . . , hi)(x) :=
clip ✏ ⇣ Vote(h1, . . . , hi 1)(x) + 2 · ( 1) hi(x)=g(x) ⌘ ,
Voteg(h1)(x) := ( 1) h1(x)=g(x).
Note. Vote(h1, . . . , hi)(x) expresses our current estimate for a particular input (together with a level of confidence), whereas Voteg(h1, . . . , hi)(x) denotes the error of this current estimate with respect to the ground truth.
Finally, we define:
Maj(h1, . . . , hi)(x) := ⇢ +1, if Vote(h1, . . . , hi)(x) 0, 1, otherwise.
Observation 1. Observe that for all i 2 N, h1, . . . , hi, g : X ! { 1,+1} and x 2 X we have: Vote(h1, . . . , hi)(x) 2 2Z+ 1 \ [ B✏, B✏] and Vote(h1, . . . , hi)(x) = ±Voteg(h1, . . . , hi)(x).

heading: 3.3 EQ-learner as a Booster

text:
Guarantees based on the VC-dimension are often not tight and as our result is phrased in these terms one might wonder how much it depends on this specific measure. As mentioned, our algorithm can be understood as a boosting technique and hence the result applies more generally. Next, we explain what we mean by that.
Let H be a hypothesis class and D be a distribution. Imagine that we have an algorithm A that for some distributions learns H. What we mean is that A is a "PAC-learner" for H but only for a class of
distributions D. Then imagine that we use A as a subroutine in the EQ-learning algorithm. I.e., instead of following the template of S := EQD(f,m), h := FindConsistent(S,H) (as in Algorithm 1) we use A to get an h that has a small error on distribution EQD(f). Now assume that all distributions EQD(f) for which A is run belong to D.
In this case a slight extension of Theorem 1 shows that we can boost A in the following sense. Assume that for every ✏, 2 (0, 1), every D0 2 D A learns H on D0 in QA(H, ✏, ) number of samples. Then there exists an EQ-learner (this is Algorithm 1, which uses A as a subroutine) that learns H up to error ✏ in number of queries upper-bounded by QA ⇣ H, 1 16 , polylog(1/✏) ⌘ ·polylog(1/✏). Now observe that if QA (H, ✏, )
QA
⇣ H,
1 16 , polylog(1/✏)
⌘ polylog(1/✏), (1)
then the constructed EQ-learner learns H to error ✏ with fewer queries than A does in the PACmodel. This is a different type of separation result. In words it says that in some cases you can boost an algorithm from the PAC-model to the EQ-model such that fewer queries are required. The condition from (1) in words means that the dependence of the runtime of A on ✏ grows faster than polylog(1/✏). This is a reasonable assumption as in the PAC-learning model for every hypothesis one needs ⌦(1/✏) samples just to see a single point from the error set of this hypothesis. This suggests that the dependence of QA (H, ✏, ) on ✏ might grow like ⌦(1/✏) (which is exactly what happens in the standard PAC-bound). To summarize, even in the cases when the VC-theory is far from reality one can still hope to get interesting results using our technique.

heading: 4 On-manifold adversarial training aids generalization

text:
As we mentioned in the introduction, the relationship between adversarial robustness and generalization has been the subject of a robust scientific discussion, no pun intended. We focus here on Stutz et al. [2019] and argue that our result can be interpreted as providing a theoretical confirmation of the important empiricial findings in this paper. As we will see, the setting of Stutz et al. [2019] is close but not identical to ours. But the parallels are strong.
In Stutz et al. [2019] a version of adversarial training called on-manifold adversarial training is proposed. In this scheme at every step one takes a point x sampled from the data distribution D and generates an adversarial example x0, which lies on the data manifold (x0 2 supp(D)) and on which the current hypothesis f makes an error. Thus we can associate with this procedure an induced distribution D0 on the error set of f , which is a result of the following process: x ⇠ D, generate adversarial example x0.
One of the methods to perform on-manifold adversarial training (as done in Stutz et al. [2019]) is to, first, learn class specific VAE-GANs and then when looking for adversarial examples, search for them in the latent space of the autoencoders.
Note that by construction (if the attacks are successful) supp(D0) ✓ supp(Df 6=h), as adversarial examples are crucially constrained to being on the data manifold and they are points on which f makes errors. But there is also one important distinction. The distributions D0 and Df 6=h may be different. It is reasonable to assume that they are not too different in many applications and we will proceed under this assumption. With this caveat, the attacker in the on-manifold training procedure can be thought of as being the teacher in our EQ model. Under this assumption, Theorem 1 guarantees that there exists an algorithm that learns faster than in the PAC model.
This is exactly what was experimentally found in Stutz et al. [2019]. When on-manifold adversarial training was used the resulting classifier had lower standard error (generalized better) compared to the standard learning procedure.
Note. We can look at the results from Stutz et al. [2019] from a different perspective. They are an experimental confirmation that Theorem 1 holds, as discussed in Section 3.3, also in situations where VC-theory doesn’t describe learnability well. Indeed, for neural networks VC-dimension doesn’t determine their learnability as in modern settings the number of parameters in networks is much bigger than the number of samples.
Note that Algorithm 1 is likely not the same as the algorithms that are used for training neural networks. One of the bigger differences is that Algorithm 1 uses a majority vote-like classifier. But in a similar fashion we can think of these experimental results as arguments that Theorem 1 holds for a broader class of learning algorithms.

heading: 4.1 Experiments

text: For the convenience of the reader we replicate experiments from Stutz et al. [2019], adapting the representation to our needs. Using the code provided by the authors, we reproduced some of their findings on F-MNIST dataset [Xiao et al., 2017]. Results are presented in Figure 1, which reproduces some entries from Figure 5 in Stutz et al. [2019]. In Figure 1 (a) we see that standard risk for on-manifold adversarial training is lower for most settings of the number of samples than for normal training and standard adversarial training. This is consistent with Theorem 1, which states than in a similar model there is an improvement over the PAC-model, which corresponds here to the normal training. We will go back to Figure 1 (b) in Section 5. More details about the experiments is deferred to the appendix.

heading: 5 Adversarial robustness

text:
Let us now discuss how our results can be seen through the lens of adversarial robustness. We start with a brief review of previous approaches and the lessons we can draw from those.
The standard adversarial learning setup considered in the literature is as follows. There is a classifier f that an adversary A wants to attack. Having some type of access to f , A generates adversarial examples to f . To do so, first a sample x is generated according to x ⇠ D. Then A tries to find x 0 such that x and x0 are semantically indistinguishable and f misclassifies x0. A formal definition of what "semantically indistinguishable" means is difficult to furnish and it is thus the subject of considerably discussion. The reason for this difficulty is that we expect the machine learning model to learn what "semantically indistinguishable" means from the data and not to decide it by ourselves up front. Many proxies for "semantically indistinguishable" were used in the literature. Usually they come in the form of a restriction on the set of allowed perturbations. As we mentioned in the introduction, some of the most popular restrictions include bounds on the `0, `2, `1 norm or restrictions to rotations, shifts and many others.
As argued in Tramer and Boneh [2019] defenses often overfit to a particular set of allowed perturbations and the resulting classifiers remain basically undefended against other attacks. This result sparked interest in defenses that make models robust against a wide variety of perturbations, even against unforeseen ones. A recent theoretical result [Goldwasser et al., 2020] proposed a defense that make models robust against all possible perturbations. Unfortunately to achieve this the authors need to allow the learner not to give answers for some inputs and the learner sees the test set before computing the classifier.
As shown in Bubeck et al. [2019] and Tsipras et al. [2019] finding defenses might not be possible even in a simple case of `2-bounded perturbations, when the adversary is computationally all powerful. This means that limiting the capabilities of the attacker is very likely to be necessary. Different limitations on the model of attack and the power of the adversary were considered. Early papers limited the type of access that A has to f : instead of full knowledge of f (known as white-box model, see Biggio et al. [2013], Zheng et al. [2019]), a black-box model [Bhambri et al., 2019], partial white-box, where the adversary sees the logits of the output probabilities but doesn’t see the internal nodes of a network, oracle access to a gradient of f and others were considered. Unfortunately, even
in the most restrictive model, namely the black-box model, efficient attacks have been shown to exist [Papernot et al., 2017, Chen et al., 2017, Liu et al., 2016, Xiao et al., 2018, Hayes and Danezis, 2017]. This lead the researches to explore models that limit the power of the adversary even further. In Gluch and Urbanke [2020] the authors consider a version of the black-box, where the attacker is limited by the number of evaluations of f it can perform. It is shown that classifiers with high entropy of decision boundaries are hard to attack. In Garg et al. [2020] the authors consider an adversary that is limited computationally. They show that there exist learning problems that can be attacked by an all powerful adversary but are secure against polynomially bounded attackers. These approaches however show security only for some synthetic distributions.
Summarizing this discussion we can formulate two conclusions
1. Introducing new attack models might be necessary for realizing adversarial robustness in the real world.
2. Limiting the power of the adversary is likely inevitable.

heading: 5.1 Model of attack

text:
As argued in point 1 new attack models might be necessary. We introduce a definition of the adversary as an algorithm that has access to the function it wants to attack and also to the Example Query Oracle for distribution D and returns points from X . More formally: Definition 2 (Adversary). For a feature space X we define an adversary A as an algorithm1 (potentially randomized) that for every function f : X ! { 1,+1} and x 2 X returns A(f, x) 2 X . Moreover, for a distribution D, we denote by A(f,EXD) a distribution on X that is generated according to a process: sample x EXD, return A(f, x). For every f we say that A is a restricted adversary for f if:
A(f,EXD) = EQD.
Note. We define the adversary as having access to the Example Query Oracle (EXD). This setting mimics the situation from Section 4 where the adversary was constructing adversarial examples based on samples from the data distribution. Access to EXD can be seen as a resource for the adversary that he can but doesn’t have to use. Indeed, a priori there is no restriction on the relationship between samples from EXD and A(f,EXD). Thus we could also assume that A doesn’t have access to EXD but posses some approximate knowledge of D that allows him to satisfy A(f,EXD) = EQD.
Finally, let us define the model of attack. It is an adversarial-learning-like scheme where the learning algorithm uses the adversary to learn a more robust model. Definition 3 (Adversarial learning game). For a distribution D on X , a learner L, and an adversary A we define an adversarial learning game as follows. Learner L interacts with A in rounds. In each round t learner L sends a function ft to A and then A sends a point xt 2 X back to L. At every round A can query EXD once and use the result when generating xt. Decisions made by L at round t can depend on the messages exchanged before round t. For simplicity of the statements we assume
that decisions of A don’t depend on the history. At the end of the interaction L declares a function f .

heading: 5.2 Interpretation of Theorem 1 for adversarial robustness

text:
We now state a corollary of our main result. The proof is deferred to the appendix: Corollary 1. For every feature space X , for every ✏ 2
0, 132 , for every d 2 N, for every hypothesis
class H on X of VC-dimension d there exists a learning algorithm L such that for every distribution

heading: D, for every ground truth h 2 H, for every adversary A the following holds. When L interacts with

text:
A as described in Definition 3 then with probability 2/3 at least one of the two properties holds:
• L, after O(d · polylog(1/✏)) rounds of interaction with A, returns a function f such that RD,h(f)  ✏,
• there exists t 2 [O(d · polylog(1/✏))] such that at the interaction round t a function ft was presented to A and A(ft, EXD) 6= EQD(ft).
1We use algorithm here since this seems more natural. But we do not limit the attacker computationally nor are we concerned with questions of computability. Hence, function would be equally correct.
Moreover, throughout the interaction only O(polylog(1/✏)) different functions are presented to A.
Next we explain how one can understand Corollary 1.
The first point of view is that Corollary 1 explores implications on the existence of restricted adversaries. Interpreted as such, it shows that there exists an adversarial-learning-like scheme where restricted adversaries can be used to learn a hypothesis of error ✏ exponentially faster than guaranteed by the standard learning theory results.
The second, and arguably the more interesting point of view is the following. If we assume that the adversary we want to defend against is unable to learn a classifier with error ✏ using O(d·polylog(1/✏)) samples from D then the adversarial-learning scheme from Corollary 1 can be understood as a defense. It is because throughout the execution of the protocol there was a function ft that was presented to A such that A(ft, EXD) 6= EQD(ft). Thus the protocol generates a list of O(polylog(1/✏)) many functions such that A is not a restricted adversary for at least one of them. We believe that this interpretation opens a door for designing defenses that are provably secure against adversaries that are limited by what they can learn. The results of experiments from Figure 1 (b) are consistent with our findings. The probability with which the on-manifold attacks succedes decreases faster than for normal training and standard adversarial training.
Why it makes sense to assume the learning problem is hard? As argued in point 2 above, limiting the power of the adversary is most likely unavoidable.
Imagine that the adversary you want to protect your model against is a very good learner. More formally, assume that for a distribution D and a ground truth h 2 H the adversary can compute a classifier g of very small risk RD,h(g) ⇡ 0. Then when the adversary attacks f it can compute [f 6= g] ✓ X . Note that as the risk of g is close to 0 we know that Px⇠D[f(x) 6= g(x)] ⇡ RD,h(f), that is the region [f 6= g] contains almost all errors of f . Even though A might not know the data distribution D (we only assumed that A is able to find a classifier with low error, which doesn’t necessarily imply the knowledge of the distribution) it is still able to attack f . To do that, for test example x ⇠ D, A can find x0 2 [f 6= g] that is semantically closest to x. Then if the error set of f is semantically close to most of the data distribution then f is indefensible against all powerful learners.
Our result provides an exponential separation between sample/query complexities, as the standard PAC-bound requires O d
✏
samples. This resembles the types of separation results, which cryptogra-
phy is built on and gives hope for following this line of research to find provably secure defenses. Unfortunately this separation doesn’t happen for all distributions as the PAC guarantee is only an upper bound. We also know that VC-theory does not necessarily give tight bounds for distributions encountered in practice. We note however that, as discussed in Section 3.3, our result if understood as a boosting technique can be applied to any learning algorithm and thus the implications are not necessarily restricted to the VC-theory.

heading: 6 Conclusions and Open Problems

text:
We study the interplay between adversarial training, generalization and robustness.
We start by proving an exponential separation between PAC and EQ-learning models. Then we show that our result provides a theoretical justification of previous experimental findings that on-manifold adversarial training helps with generalization. Finally we explore the interpretation of our results for adversarial robustness. We introduce a learning setting where one can use the power of the adversary to evolve a learning scheme to become increasingly robust.
Our result does not yield a provable defense in real-world settings. But it provides a novel point of view on the adversarial robustness problem that hopefully, with further study, will provide such a defense. As discussed the models considered in Section 3 and 4 are different. It would be interesting to prove a version of exponential separation also in the setting from Section 4.
Our result also poses some challenging technical questions. The query complexity upper-bound in the EQ-model we were able to prove is of the form O d · log9 (1/✏) . This is most likely not
optimal and what we believe to be the true query complexity is O(d · log(1/✏)). Proving an upper or a lower-bound close to this expression is an interesting theoretical challenge.

title: Exponential Separation between Two Learning Models and Adversarial Robustness