11in8.5in 11in8.5in* 0in0in 1.3in1.3in* 1.3in1.3in* 13pt26pt *13pt*
subsubsection default

# Sample Complexity of Robust Learning against Evasion Attacks

###### Abstract

It is becoming increasingly important to understand the vulnerability of
machine learning models to adversarial attacks. One of the fundamental
problems in adversarial machine learning is to quantify how much training data
is needed in the presence of so-called evasion attacks, where data is
corrupted at test time. In this thesis, we work with the exact-in-the-ball
notion of robustness and study the feasibility of adversarially robust
learning from the perspective of learning theory, considering sample
complexity.

We start with two negative results. We show that no non-trivial concept class
can be robustly learned in the distribution-free setting against an adversary
who can perturb just a single input bit. We then exhibit a sample-complexity
lower bound: the class of monotone conjunctions and any superclass on the
boolean hypercube has sample complexity at least exponential in the
adversary’s budget (that is, the maximum number of bits it can perturb on each
input). This implies, in particular, that these classes cannot be robustly
learned under the uniform distribution against an adversary who can perturb
$\omega(\log n)$ bits of the input.

As a first route to obtaining robust learning guarantees, we consider
restricting the class of distributions over which training and testing data
are drawn. We focus on learning problems with probability distributions on the
input data that satisfy a Lipschitz condition: nearby points have similar
probability. We show that, if the adversary is restricted to perturbing
$O(\log n)$ bits, then one can robustly learn the class of monotone
conjunctions with respect to the class of log-Lipschitz distributions. We then
extend this result to show the learnability of $1$-decision lists, 2-decision
lists and monotone $k$-decision lists in the same distributional and
adversarial setting. We finish by showing that for every fixed $k$ the class
of $k$-decision lists has polynomial sample complexity against a
$\log(n)$-bounded adversary. The advantage of considering intermediate
subclasses of $k$-decision lists is that we are able to obtain improved sample
complexity bounds for these cases.

As a second route, we study learning models where the learner is given more
power through the use of _local_ queries. The first learning model we consider
uses local membership queries (LMQ), where the learner can query the label of
points near the training sample. We show that, under the uniform distribution,
the exponential dependence on the adversary’s budget to robustly learn
conjunctions and any superclass remains inevitable even when the learner is
given access to LMQs in addition to random examples. Faced with this negative
result, we introduce a local _equivalence_ query oracle, which returns whether
the hypothesis and target concept agree in a given region around a point in
the training sample, as well as a counterexample if it exists. We show a
separation result: on the one hand, if the query radius $\lambda$ is strictly
smaller than the adversary’s perturbation budget $\rho$, then distribution-
free robust learning is impossible for a wide variety of concept classes; on
the other hand, the setting $\lambda=\rho$ allows us to develop robust
empirical risk minimization algorithms in the distribution-free setting. We
then bound the query complexity of these algorithms based on online learning
guarantees and further improve these bounds for the special case of
conjunctions. We follow by giving a robust learning algorithm for halfspaces
on $\left\\{0,1\right\\}^{n}$. Finally, since the query complexity for
halfspaces on $\mathbb{R}^{n}$ is unbounded, we instead consider adversaries
with _bounded precision_ and give query complexity upper bounds in this
setting as well.

###### Acknowledgements

I would first like to express my most sincere gratitude to my supervisors
James (Ben) Worrell, Varun Kanade, and Marta Kwiatkowska.

Marta, I am extremely grateful for your guidance, support and generosity. Your
help has been invaluable in setting a research agenda and navigating my DPhil.
I very much value the time you make for your students, your involvement and
reliability.

Varun, thank you for taking a chance working with me in my second year, and
for introducing me to learning theory and interesting problems in the field.
Your expertise and knowledge have been beyond helpful. I am tremendously
grateful for our discussions, and greatly appreciate your insightful comments
and approach to research. I value your mentorship immensely.

Ben, your enthusiasm for research is inspiring. Working with you, I have
learned so much on how to approach and solve research problems. You have
helped me look at research as a ludic and collaborative endeavour – a
perspective that I hope will last throughout my career. I cannot thank you
enough for your generosity with your time, energy and ideas.

I would also like to thank my masters supervisors, Prakash Panangaden and
Doina Precup, for their help and support which has lasted to this day and has
greatly contributed to my academic path.

To my amazing friends, I am forever grateful for your support, care and
kindness. Friends from Montréal, Pearson UWC, Oxford, and beyond: you know who
you are, and I love and cherish every one of you.

I would like to thank Gabrielle, Rick and Joanie from the Institut des
Commotions Cérébrales, without whom I would most likely never have finished my
degree.

I would also like to acknowledge the financial support provided to me during
my DPhil: the Clarendon Fund (Oxford University Press) for the Clarendon
Scholarship, the Natural Sciences and Engineering Research Council of Canada
(NSERC) for the Postgraduate Scholarship, and the European Research Council
(ERC) for funding under the European Union’s Horizon 2020 research and
innovation programme (FUN2MODEL, grant agreement No. 834115).

Finally, I would like to thank my family, especially my parents, Caroline and
Richard, who have supported me in ways that words will never do justice to. A
very special thank you to my grandmother, Colette, whose love and wisdom are
always with me. Raymonde and Pierre, I so deeply wish I could share this
moment with you.

###### Contents

  1. 1 Introduction
    1. 1 Main Contributions
    2. 2 Thesis Structure
    3. 3 Statement of Contribution
  2. 2 Literature Review
    1. 4 The Learning Theory Landscape
      1. 4.1 Classification
      2. 4.2 Learning with Queries
    2. 5 Adversarial Machine Learning
      1. 5.1 Evasion Attacks
  3. 3 Background
    1. 6 Learning Theory: Classification
      1. 6.1 The PAC Framework
      2. 6.2 Complexity Measures
      3. 6.3 Some Concept Classes and PAC Learning Algorithms
      4. 6.4 Online Learning: The Mistake-Bound Model
      5. 6.5 Learning with Membership and Equivalence Queries
    2. 7 Probability Theory
      1. 7.1 Log-Lipschitz Distributions
      2. 7.2 Concentration Bounds and Martingales
    3. 8 Fourier Analysis
  4. 4 Robustness & Monotone Conjunctions
    1. 9 Defining Robust Learnability
      1. 9.1 Two Notions of Robustness
      2. 9.2 A Separation between PAC and Robust Learning
    2. 10 The Distribution-Free Assumption
    3. 11 An Adversarial Sample Complexity Lower Bound
    4. 12 Logarithmically-Bounded Adversary
      1. 12.1 Log-Lipschitz Distributions
      2. 12.2 A Robustness Guarantee
    5. 13 Summary
  5. 5 Robustness Thresholds: Random Examples
    1. 14 Exact Learning
      1. 14.1 Parity Functions
      2. 14.2 Majority Functions
    2. 15 Decision Lists
      1. 15.1 1-Decision Lists
      2. 15.2 Generalizing from 1-DL to $2$-DL and Monotone $k$-DL
      3. 15.3 Non-Monotone Decision Lists
    3. 16 Decision Trees
    4. 17 Summary of Results and Open Problems
  6. 6 Robust Learning with Local Queries
    1. 18 Two Local Query Models
    2. 19 Robust Learning with Local Membership Queries
    3. 20 Robust Learning with Local Equivalence Queries
      1. 20.1 Impossibility of Distribution-Free Robust Learning for $\lambda<\rho$
      2. 20.2 Sample Complexity Upper Bounds
      3. 20.3 General Query Complexity Upper Bounds
      4. 20.4 Improved Query Complexity Bounds for Conjunctions
      5. 20.5 Bounds for Linear Classifiers
    4. 21 Precision-Bounded Adversaries
    5. 22 Lower Bounds on Robust Learning with $\mathsf{LEQ}$
      1. 22.1 General Query Complexity Lower Bounds
      2. 22.2 Bounds on the Restricted VC and Littlestone Dimensions
    6. 23 Further Comparing the Local Query Models
      1. 23.1 Local Membership and Equivalence Queries
      2. 23.2 A Two-Way Separation between $\mathsf{LEQ}$ and $\mathsf{EQ}$
    7. 24 Summary and Open Problems
      1. 24.1 Final Remarks on Local Query Oracles
      2. 24.2 Future Work
  7. 7 Conclusion
    1. 25 Future Work
  8. 8 Proofs from Chapter 5
    1. 8.A Proof of Lemma 5.12
    2. 8.B Proof of Corollary 5.24
  9. 9 Proofs from Chapter 6
    1. 9.A Proof of Lemma 6.6
    2. 9.B Proof of Lemma 6.8
    3. 9.C Bounds on the Restricted VC dimension
  10. 10 Discussions from Chapter 6
    1. 10.A A Closer Look at $\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))$
    2. 10.B A Lower Bound Based on $\mathsf{VC}(\mathcal{L}_{\rho}(\mathcal{C},\mathcal{H}))$

###### List of Figures

  1. 1 A school bus is classified as an ostrich after a small perturbation is applied to the original image (Szegedy et al.,, 2013).
  2. 2 A visual representation of sample-efficient PAC learning. $S_{c}$ means that the sample $S$ has been labelled with the ground truth $c$.
  3. 3 A set $X$ of three points in $\mathbb{R}^{2}$ that is shattered by linear classifiers. Subfigures (a)-(d) represent different dichotomies on $X$; note that (b) and (c) are not the only labellings with one and two positively labelled points, respectively, but the other cases are symmetric.
  4. (a)
  5. (b)
  6. (c)
  7. (d)
  8. 4 Any set of four points cannot be shattered by linear classifiers. Indeed, we distinguish two cases: either (a) one point is strictly in the convex hull of the three other points, and is the only point of its label (or all points are on the same line, which gives a similar argument) or (b) all points are on the boundary of the convex hull, in which case labelling opposite points with the same label gives an unachievable labelling. This argument is a special case for $\mathbb{R}^{2}$ which can be generalized to $\mathbb{R}^{n}$ using Radon’s theorem.
  9. (a)
  10. (b)
  11. 5 The natural point $x$ has robust loss of 1 with respect to both notions of robustness: $z_{1}$ is a counterexample for exact-in-the-ball robustness (as $c(z_{1})\neq h(z_{1})$), and $z_{2}$ for constant-in-the-ball robustness (as $c(x)\neq h(z_{2})$).
  12. 6 In all the examples above, the circles represent the support of the distribution, and the shaded region, its $\rho$-expansion (i.e., the points at a distance at most $\rho$ from points in the support of the distribution). (a) The support of the distribution is such that $\mathsf{R}^{C}_{\rho}(h,c)=0$ can only be achieved if $c$ is constant. (b) The $\rho$-expansion of the support of the distribution and target $c$ admit hypotheses $h$ such that $\mathsf{R}^{C}_{\rho}(h,c)=0$ (i.e., any $h$ that does not cross the shaded regions). (c) An example where $\mathsf{R}^{C}_{\rho}$ and $\mathsf{R}^{E}_{\rho}$ differ. The red concept, which crosses the shaded regions, is the target; the blue one is the hypothesis. The diamonds represent perturbed inputs which cause $\mathsf{R}^{E}_{\rho}(c,h)>0$, while $\mathsf{R}^{C}_{\rho}(h,c)=0$.
  13. (a)
  14. (b)
  15. (c)
  16. 7 Images from the CIFAR-10 (above) and MNIST (below) datasets, respectively from (Krizhevsky and Hinton,, 2009) and (LeCun,, 1998). While the margin assumption generally holds for CIFAR (e.g., the “boat” and “dog” classes are well-separated), this is not necessarily the case for MNIST (the three above could easily be transformed into an eight, and the left-hand side picture could be a one or a seven).
  17. 8 A unifying result. When $\rho=\log(n)$, $\mathsf{SAT}_{\rho}(\varphi)$, the $\rho$-expansion of the error region, is not too large compared to the set $\mathsf{SAT}(\varphi)$.
  18. 9 The dotted line is the hypothesis $h$, and the solid line, the target $c$. The adversary has precision $\tau$. The shaded regions represent the set $B_{\tau}(z_{i})$. The counterexample $z_{1}$ is valid as $c$ and $h$ disagree on all of $B_{\tau}(z_{1})$ and both functions are constant in this region, but $z_{2}$ is not as $c$ and $h$ agree on part of $B_{\tau}(z_{2})$.
  19. 10 A visual representation of the proof of Theorem 6.28. The dotted lines on either side of the target $c$ represent a margin of $\tau/2$. Any hypothesis within the dotted lines in the (shaded) perturbation region ensures that an adversary of bounded precision $\tau$ cannot return any counterexamples. Finally, counterexamples must be labelled according to the target $c$, and both $h$ and $c$ are not constant on $B_{\rho}(x)$.

###### List of Tables

  1. 1 The pros and cons of the two robust risk functions. The last line refers to the behaviour of hypotheses minimizing the robust risk as the perturbation region increases. At the extreme case, when the perturbation region is the whole space, the robust risk minimizer for the constant-in-the-ball risk is a constant function, while it is the target for the exact-in-the-ball risk (as we require exact learning).
  2. 2 The robustness thresholds of concept classes from Chapters 4 and 5, and open problems.
  3. 3 Comparing the VC dimension and the $\rho$-restricted VC dimension for given concept classes. The $\widetilde{\Theta}$ notation hides the logarithmic factors. Unless otherwise stated, we assume $\rho\geq 1$.

##  Chapter 1 Introduction

In the standard theoretical analysis of machine learning, the learning process
uses and is evaluated on clean, unperturbed examples. Moreover, many machine
learning tasks are evaluated according to predictive accuracy alone, e.g.,
maximizing the accuracy of a classifier with respect to the ground truth which
labels the data. Though there remain existing knowledge gaps in the literature
(e.g., explaining the success of deep neural networks), machine learning
theory has generally been successful at designing algorithms and deriving
guarantees to explain generalization in this framework, even in the presence
of noise.

It is natural to ask whether similar results can be derived when the learning
objectives go beyond standard accuracy. This could be when the learning
process allows for the presence of a malicious adversary–which is more
powerful than simply adding random noise to the data– and thus requires
_robustness_. The study of robustness in machine learning falls under the more
general umbrella of _trustworthiness_ of machine learning models, where other
considerations such as privacy, interpretability or fairness come into play,
see, e.g., (Dwork,, 2008; Doshi-Velez and Kim,, 2017; Kleinberg et al.,,
2017). The trustworthiness of machine learning models is of utmost importance,
especially considering the speed at which new technology is currently
deployed. Crucially, learning theory can provide us with valuable tools to
explain, evaluate and guarantee the behaviour of safety-critical machine-
learning applications.

The focus of this thesis is on the robustness of machine learning algorithms
to _evasion attacks_ , which happen at test time after a model is trained
(without the presence of an adversary). This is in contrast to _poisoning
attacks_ , which happen at training time with the goal of reducing the test-
time accuracy of a machine learning algorithm. The distinction between these
two settings was proposed by Biggio et al., (2013), who independently observed
the phenomenon of adversarial examples presented by Szegedy et al., (2013),
who coined the latter term.

One of the main challenges in the theory of adversarial machine learning is to
analyse the intrinsic difficulty of learning in the presence of an adversary
that can modify the data. The present work studies various assumptions in a
learning problem, such as properties of the distribution underlying the data,
how the learner obtains data, limitations of the adversary, etc., and
determines whether robust learning is feasible with a reasonable amount of
data. Here, reasonable means that the _sample complexity_ of a robust learning
algorithm, i.e., the amount of data needed to enable guarantees, is
_polynomial_ in the input space dimension and the learning parameters (e.g.,
an algorithm’s _confidence_ and the desired _robust accuracy_ of a hypothesis
output by the learning algorithm).

###  1 Main Contributions

This thesis focuses on the existence of adversarial examples in classification
tasks. An adversarial example is obtained from a natural example at test time
by adding a perturbation, in the malicious goal of causing a
misclassification. We work under the _exact-in-the-ball_ notion of
robustness,111Also known as _error region_ risk in Diochnos et al., (2018).
which relies on the existence of a ground truth function (i.e., there exists a
concept that labels the data correctly). A misclassification occurs when the
hypothesis returned by the learning algorithm and the ground truth _disagree_
in the perturbation region. This is in contrast to the _constant-in-the-ball_
notion of robustness222Also known as _corrupted input_ robustness from the
work of Feige et al., (2015). which requires that the unperturbed point be
labelled correctly, and that the hypothesis remain _constant_ in the
perturbation region. Guarantees derived for the constant-in-the-ball notion of
robustness imply that the hypothesis returned has a certain stability (perhaps
at the cost of accuracy in certain cases, as demonstrated in Tsipras et al.,
(2019)), as an optimal algorithm would return a hypothesis that limits the
probability of a label change in the perturbation region. On the other hand,
guarantees derived for the exact-in-the-ball notion of robustness usually give
stronger accuracy, as we want to be _correct_ with respect to the ground truth
in the perturbation region. Deciding which notion of robustness to use depends
on the learning problem at hand, and what kind of guarantees one wishes to
ensure. We gave in (Gourdeau et al.,, 2019, 2021) a thorough comparison
between these two notions of robustness, and remarked that the exact-in-the-
ball notion of robustness is much less studied than the constant-in-the-ball
one.

Our motivation in this thesis is to study the intrinsic robustness of learning
algorithms from a learning theory perspective in the probably approximately
correct (PAC) learning model of Valiant, (1984). We investigate how different
learning settings enable robust learning guarantees, or, to the contrary, give
rise to hardness results. In this sense, our main aim is to delineate the
frontier of robust learnability in various learning models. We conceptually
divide our contributions based on the learning models we have studied.

##### Random examples.

In this model, as in the PAC framework, the learner has access to a random-
example oracle which samples a point from an underlying distribution, and
returns the point along with its label. We exhibit an impossibility result
(Gourdeau et al.,, 2019), stating that the distribution-free guarantees for
(standard) PAC learning cannot be achieved for robust learning under the
exact-in-the-ball definition of robustness, highlighting a key obstacle in
adversarial machine learning compared to its standard counterpart. Here,
distribution-free means that the learning guarantees hold for any distribution
that generates the data, provided that the training and testing data are both
drawn independently from the same distribution.

The above impossibility result is obtained by choosing a badly-behaved, and
quite unnatural distribution on the data. But we show that, even when looking
at natural distributions and simple concept classes, robust learning can have
high sample complexity. Indeed, we prove that there is no efficient robust
learning algorithm that learns monotone conjunctions under the uniform
distribution if the adversary can perturb $\rho=\omega(\log n)$ bits of a test
point in $\\{0,1\\}^{n}$; the maximum number $\rho$ of bits the adversary is
allowed to perturb at test time is called the _perturbation budget_. This is
particularly striking as the class of monotone conjunctions is one the
simplest non-trivial concept classes on the boolean hypercube. We extend this
result to establish a general sample complexity lower bound of
$\Omega(2^{\rho})$ (Gourdeau et al., 2022a, ), highlighting an _exponential_
dependence on the adversary’s budget $\rho$ in the sample complexity of robust
learning. Since linear classifiers and decision lists subsume this class of
functions, the lower bound holds for them as well. To complement these
results, we show that, under distributional assumptions and against a
_logarithmically-bounded_ adversary (i.e., with budget $\rho=O(\log n)$),
efficient robust learning is possible for various concept classes. We require
that the underlying distribution be _log-Lipschitz_ ; this notion encapsulates
the idea that nearby instances should have similar probability masses and
includes as particular instances product distributions with bounded means. We
show the above-mentioned result for conjunctions (Gourdeau et al.,, 2019),
monotone decision lists (Gourdeau et al.,, 2021), and non-monotone decision
lists (Gourdeau et al., 2022a, ). We define the term _robustness threshold_ to
mean a function $f(n)$ of the input dimension $n$ for which it is possible to
efficiently robustly learn against an adversary with budget $f(n)$, but
impossible if the adversary’s budget is $\omega(f(n))$ (with respect to a
given distribution family). The robustness threshold of these concept classes
is thus $\log(n)$ under log-Lipschitz distributions.

In general, the above-mentioned results rely on a proof of independent
interest: an upper bound on the $\log(n)$-expansion of subsets of the
hypercube defined by $k$-CNF formulas. This result relies on concentration
bounds for martingales, as well as properties of the resolution proof system.
In all the cases above, as well as for decision trees (Gourdeau et al.,,
2021), the error region between a hypothesis and a target333That is, for
target $c$ and hypothesis $h$ on input space $\mathcal{X}$, the set of points
$x\in\mathcal{X}$ such that $c(x)\neq h(x)$. can be expressed as a union of
$k$-CNF formulas. By controlling the standard risk, we can bound the robust
risk and, as a result, use PAC learning algorithms as black boxes for robust
learning.

##### Local membership queries.

In this model, introduced by Awasthi et al., (2013), the learner has access to
the random-example oracle and can query the label of points that are near the
randomly-drawn training sample. We show that at least $\Omega(2^{\rho})$ local
membership queries are needed for robustly learning conjunctions under the
uniform distribution against an adversary that can perturb $\rho$ bits of the
input (Gourdeau et al., 2022b, ). We thus have the same exponential dependence
in the adversary’s budget as with random examples only, implying that adding
local membership queries cannot, in general, improve the robustness threshold
of this concept class (and any superclass)., e.g. linear classifiers and
decision lists.

##### Local equivalence queries.

Faced with the lower bound for robust learning with a local membership query
oracle, we introduce a learning model where the learner is allowed to query
whether the hypothesis is _correct_ in a specific region of the space and get
a counterexample if not, which we call local equivalence queries in (Gourdeau
et al., 2022b, ), following the work of Angluin, (1987).

We first establish that, when the query budget is strictly smaller than the
perturbation budget (hence the adversary can access regions of the instance
space that the learner cannot), distribution-free robust learning with random
examples and local equivalence queries is in general impossible for monotone
conjunctions and any superclass thereof. However, when the query and
perturbation budgets coincide, a query to the local equivalence query oracle
is equivalent to querying the robust loss and getting a counterexample if it
exists. As a result, the local equivalence query oracle becomes the exact-in-
the-ball analogue of the Perfect Attack Oracle of Montasser et al., (2021). In
this case, efficient distribution-free robust learning becomes possible for a
wide variety of concept classes. Indeed, we show random-example and local-
equivalence-query upper bounds, which we refer to as sample and query
complexity, respectively. We demonstrate that the query complexity depends on
mistake bounds from online learning, and the sample complexity on the VC
dimension of the robust loss of a concept class, a notion of complexity that
we have adapted from Cullina et al., (2018) to the exact-in-the-ball notion of
robustness. We also show that the local equivalence query bound can be
improved in the special case of conjunctions. We moreover establish that the
VC dimension of the robust loss between linear classifiers on $\mathbb{R}^{n}$
is $O(n^{3})$.

Since the query complexity of linear classifiers is in general unbounded, we
study the setting in which we restrict the adversary’s _precision_ (e.g., the
number of bits needed to express an adversarial example). We use and adapt
tools and techniques from Ben-David et al., (2009), which pertain to the study
of margin-based classifiers in the context of online learning, for our
purposes and exhibit finite query complexity bounds. We then exhibit expected
local equivalence query lower bounds that are linear in the _restricted_
Littlestone dimension of a concept class (we require that a set of potential
counterexamples be in a specific region of the instance space), and show that,
for a wide variety of concept classes, they coincide asymptotically with the
local equivalence query upper bounds derived in Gourdeau et al., 2022b .
Finally, we offer a more nuanced discussion of the local membership and
equivalence query oracles. In particular, we show that the local equivalence
query and its global counterpart, the equivalence query, are in general
incomparable.

###  2 Thesis Structure

#### Chapter 2

This chapter consists of the literature review. We first review foundational
work on classification in the learning theory literature. We then turn our
attention to the more recent related work on adversarial robustness in machine
learning, particularly in the context of evasion attacks. We mainly focus on
work that is foundational in nature, as it is the lens with which we study
adversarial robustness.

#### Chapter 3

We review necessary technical background to the understanding of the technical
contributions of this thesis, which largely focuses on classification in the
following models: the PAC framework of Valiant, (1984), the exact learning
framework of Angluin, (1987), and the online learning setting. We also review
some probability theory and Fourier analysis.

#### Chapter 4

We motivate the study of adversarial robustness for classification tasks under
the exact-in-the-ball notion of robustness. We rigorously discuss the
different notions of robust risk and their significance, particularly the
impossibility of obtaining distribution-free guarantees in our setting. We
initiate our study of efficient robust learnability (from a sample-complexity
point of view) with monotone conjunctions. We show a sample complexity lower
bound that is exponential in the adversary’s budget under the uniform
distribution, ruling out the existence of efficient robust learning algorithms
against adversaries with a budget super-logarithmic in the input dimension in
this setting. We show, however, that it is possible to robustly learn monotone
conjunctions under log-Lipschitz distributions against a logarithmically-
bounded adversary.

The material in this chapter is based on the following papers:

  * •

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell, “On the
hardness of robust classification,” in _33rd Conference on Neural Information
Processing Systems (NeurIPS)_ , 2019.

  * •

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell, “Sample
complexity bounds for robustly learning decision lists against evasion
attacks,” in _International Joint Conference on Artificial Intelligence
(IJCAI)_ , 2022.

#### Chapter 5

In this chapter, we study the _robustness thresholds_ of various concept
classes under distributional assumptions. We show the exact learning of
parities under log-Lipschitz distributions and of majority functions under the
uniform distribution, giving a robustness threshold of $n$ for these classes.
We then show a robustness threshold of $\log(n)$ for the class of $k$-decision
lists, which is parametrized by the size $k$ of a conjunction at each node in
the list. Since our aim is to bound the sample complexity of robustly
learning, we study various restrictions of decision lists: 1-decision lists,
2-decision lists, monotone $k$-decision lists and finally (non-monotone)
$k$-decision lists. The proofs not only rely on different technical tools, but
they more importantly yield much better sample complexity bounds for the
simpler subclasses. We finish by relating the standard and robust errors of
decision trees under log-Lipschitz distributions.

This chapter is based on the following two papers, the first one being the
journal version of the NeurIPS 2019 paper presented in the previous chapter:

  * •

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell, “On the
hardness of robust classification,” in _Journal of Machine Learning Research
(JMLR)_ , 2021.

  * •

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell, “Sample
complexity bounds for robustly learning decision lists against evasion
attacks,” in _International Joint Conference on Artificial Intelligence
(IJCAI)_ , 2022.

#### Chapter 6

We consider learning models in which the learner has access to local queries
in addition to random examples. We first show that local membership queries do
not increase the robustness threshold of conjunctions under the uniform
distribution. We then study local equivalence queries, and show that
distribution-free robust learning is impossible for a wide variety of concept
classes if the query budget is strictly smaller than the adversarial budget.
We demonstrate, however, that when the two coincide, distribution-free robust
learning becomes possible. We exhibit general sample and query complexity
upper bounds as well as tighter bounds in the special case of conjunctions. We
also give explicit bounds for linear classifiers on the boolean hypercube. We
then study linear classifiers in the continuous case and establish a general
sample complexity upper bound, as well as a query complexity upper bound when
we limit the adversary’s precision. We complement the upper bounds by showing
general lower bounds on the expected number of queries to the local
equivalence query oracle and instantiate them for specific concept classes. We
finish by comparing the local membership and equivalence query oracles, as
well as how they compare with the membership and equivalence query oracles.

Sections 18, 19 and 20 are based on the following publication:

  * •

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell, “When
are local queries useful for robust learning?” in _36th Conference on Neural
Information Processing Systems (NeurIPS)_ , 2022.

Sections 21, 22 and 23 are based on work that we are currently preparing for
submission.

#### Chapter 7

We conclude by summarizing our contributions and drawing a picture of robust
learnability in the learning models we have studied. Finally, we outline
various avenues for future work.

###  3 Statement of Contribution

The publications mentioned in the previous section have largely been my own
work, with direction from my supervisors James Worrell, Varun Kanade and Marta
Kwiatkowska. While NeurIPS 2019/JMLR 2021 papers addressed research questions
posed by my supervisors, I lead the research – including the technical aspect
by deriving the proofs, and wrote most of the paper. For the IJCAI 2022 paper,
I continued to lead in the technical development and writing up of the
manuscript. In addition to this, I played a major role in formulating the
research questions and positioning the work in a wider context. For the
NeurIPS 2022 paper and subsequent ongoing work, I did most of the work on my
own – from finding and defining the research problem and learning model,
providing insights on the problem at hand, deriving the proofs and writing the
whole paper. I was of course supported by my supervisors: they referred me to
a paper and suggested a way to prove a particular bound, they strengthened the
paper by providing helpful feedback through nuanced discussions, and reviewed
many iterations of the draft.

##  Chapter 2 Literature Review

This chapter gives an overview of the literature relevant to this thesis. We
start by reviewing classical learning theory results, focusing on
classification. We finish with a review of adversarial machine learning. While
we mention work pertaining to other views on robustness, our focus is the
study of robustness to evasion attacks, particularly from a foundational
viewpoint.

The results in this chapter are presented at a high level. However, readers
who are not familiar with learning theory may find it beneficial to refer to
Chapter 3, which gives a thorough technical introduction to various frameworks
and complexity measures discussed in this chapter.

###  4 The Learning Theory Landscape

We start with an overview of the established literature in classification in
the probably approximately correct and online learning frameworks, and then
move to learning with access to membership and equivalence queries.

####  4.1 Classification

The probably approximately correct (PAC) learning model of Valiant, (1984) is
one of the most well-studied classification models in learning theory. In this
framework, the learner has access to the example oracle, which returns a point
$x\sim D$ sampled from an underlying distribution and its label $c(x)$, where
$c$ is the target concept (ground truth). The goal is to output a hypothesis
$h$ from a hypothesis class $\mathcal{H}$ such that $h$ has low error with
high probability.444In the realizable setting, where it is possible to achieve
zero risk, we want the risk to be as close as possible to zero. In the
agnostic setting, we compare the risk of the hypothesis output by an algorithm
to the risk of the optimal function from the hypothesis class. Remarkably,
there exists a complexity measure, namely the VC dimension of Vapnik and
Chervonenkis, (1971), that characterizes the learnability of a hypothesis
class. Indeed, it is possible to get both upper and lower bounds for the
number of samples needed for learning (i.e., the sample complexity) that are
_linear_ in the VC dimension. The upper bound is due to Vapnik, (1982); Blumer
et al., (1989), and the lower bounds to Blumer et al., (1989); Ehrenfeucht et
al., (1989). These bounds are tight up to a
$\log\left(\frac{1}{\epsilon}\right)$ factor, where $\epsilon$ is the
parameter controlling the accuracy of the hypothesis output by the learning
algorithm.

The one-inclusion graph of Haussler et al., (1994), which also enjoys an upper
bound that is linear in the VC dimension, was conjectured to be optimal (in
the sense that the upper and lower bounds on sample complexity are tight) by
Warmuth, (2004) until the recent work of Aden-Ali et al., (2023) showing that
this is not the case. However, the breakthrough work of Hanneke, (2016) showed
it is in general possible to get rid of the
$\log\left(\frac{1}{\epsilon}\right)$ factor with a majority-vote classifier,
following important advances made by Simon, (2015).

Another popular learning setting is that of online learning, introduced in the
seminal work of Littlestone, (1988) and in which a learning algorithm competes
against an adversary. At each iteration, the learner is presented with an
instance to predict, and afterwards the adversary reveals the true label of
the instance. The goal is to make as few mistakes as possible. Littlestone,
(1988) studied the _realizable setting_ , where there always is a function
that makes zero mistakes on the learning sequence, and showed that a notion of
complexity (the Littlestone dimension) characterizes online learnability in
this framework. The algorithm achieving this is called the standard optimal
algorithm (SOA), which was later adapted by Ben-David et al., (2009) to the
_agnostic setting_ , where there need not exist a function that makes zero
mistakes; the algorithm’s performance is instead compared with the best
hypothesis _a posteriori_. There is a vast literature on online learning, and
we refer the reader to the book of Cesa-Bianchi and Lugosi, (2006) for a
technical overview and references therein.

####  4.2 Learning with Queries

The works mentioned in the previous section studied classification when the
learner has access to random examples. Active learning is another learning
framework in which the learner is given more power, often through the use of
membership and equivalence queries. Membership queries allow the learner to
query the label of any point in the input space $\mathcal{X}$, namely, if the
target concept is $c$, the membership query ($\mathsf{MQ}$) oracle returns
$c(x)$ when queried with $x\in\mathcal{X}$. On the other hand, the equivalence
query ($\mathsf{EQ}$) oracle takes as input a hypothesis $h$ and returns
whether $h=c$, and provides a counterexample $z$ such that $h(z)\neq c(z)$
otherwise. The goal in the $\mathsf{MQ}+\mathsf{EQ}$ model is usually to learn
the target $c$ exactly, which is in contrast to the PAC setting which requires
to learn with high confidence a hypothesis with low error.

The seminal work of Angluin, (1987) showed that deterministic finite automata
(DFA) are exactly learnable with a polynomial number of queries to
$\mathsf{MQ}$ and $\mathsf{EQ}$ in the size of the DFA. Follow-up work
generalized these results. E.g., Bshouty, (1993) showed that poly-size
decision trees are efficiently learnable in this setting as well; Angluin,
(1988) later investigated other types of queries and also showed that $k$-CNFs
and $k$-DNFs are exactly learnable with access to membership queries; Jackson,
(1997) showed that, in the $\mathsf{PAC}+\mathsf{MQ}$ setting, the class of
$\mathsf{DNF}$ formulas is learnable under the uniform distribution. But even
these powerful learning models have limitations: learning DFAs only with
$\mathsf{EQ}$ is hard (Angluin,, 1990) and, under cryptographic assumptions,
DFAs are also hard to learn solely with the $\mathsf{MQ}$ oracle (Angluin and
Kharitonov,, 1995).

On a more applied note, the $\mathsf{MQ}+\mathsf{EQ}$ model has recently been
used for recurrent and binarized neural networks (Weiss et al.,, 2018, 2019;
Okudono et al.,, 2020; Shih et al.,, 2019), and interpretability (Camacho and
McIlraith,, 2019). It is also worth noting that the $\mathsf{MQ}$ learning
model has been criticized by the applied machine learning community, as labels
can be queried in the whole input space, irrespective of the distribution that
generates the data. In particular, Baum and Lang, (1992) observed that query
points generated by a learning algorithm on the handwritten characters often
appeared meaningless to human labellers. Awasthi et al., (2013) thus offered
an alternative learning model to Valiant’s original model, the PAC and local
membership query ($\mathsf{EX}+\mathsf{LMQ}$) model, where the learning
algorithm is only allowed to query the label of points that are close to
examples from the training sample. Bary-Weisberg et al., (2020) later showed
that many concept classes, including DFAs, remain hard to learn in the
$\mathsf{EX}+\mathsf{LMQ}$ model.

###  5 Adversarial Machine Learning

There has been considerable interest in adversarial machine learning since the
seminal work of Szegedy et al., (2013), who coined the term _adversarial
example_ to denote the result of applying a carefully chosen perturbation that
causes a classification error to a previously correctly classified datum. This
work was largely experimental in nature and presented a striking instability
of deep neural networks, where for example a correctly-classified image of a
school bus was labelled as an ostrich after a perturbation (imperceptible to
the human eye) was applied, as in Figure 1. Biggio et al., (2013)
independently observed this phenomenon with experiments on the MNIST (LeCun,,
1998) dataset. However, as pointed out by Biggio and Roli, (2018), adversarial
machine learning has been considered much earlier in the context of spam
filtering (Dalvi et al., (2004); Lowd and Meek, 2005a ; Lowd and Meek, 2005b ;
Barreno et al., (2006)). Their survey also distinguished two settings:
_evasion attacks_ , where an adversary modifies data at test time, and
_poisoning attacks_ , where the adversary modifies the training data. For an
in-depth review and definitions of different types of attacks, the reader may
refer to (Biggio and Roli,, 2018; Dreossi et al.,, 2019). For an introduction
to adversarial defences in practice, see, e.g., (Goodfellow et al.,, 2015;
Zhang et al.,, 2019).

Figure 1: A school bus is classified as an ostrich after a small perturbation
is applied to the original image (Szegedy et al.,, 2013).

As our work pertains to the robustness of machine learning algorithms to
evasion attacks in classification tasks from a learning theory perspective,
our review of related work will mainly concern this topic (Section 5.1).
Before discussing this body of work, we will briefly mention other views on
robustness.

Many works have studied the robustness of learning algorithms to poisoning
attacks, in which an adversary can modify the training data in order to
increase the (standard) error at test time, one of the earliest being that of
Kearns and Li, (1988). Various types of poisoning attacks have been put
forward since then, especially as the study of robustness has garnered
interest in recent years. Clean-label attacks, proposed by Shafahi et al.,
(2018), are a distinct form of poisoning attacks where the poisoned examples
are labelled correctly, i.e., by the target function, and not adversarially.
For a learning-theoretic approach and results on this problem, see
(Mahloujifar and Mahmoody,, 2017, 2019; Mahloujifar et al.,, 2018, 2019;
Etesami et al.,, 2020; Blum et al.,, 2021) (non-exhaustive). In case there is
no restriction on the label of poisoned data, see, e.g., the works of (Barreno
et al.,, 2006; Biggio et al.,, 2012; Papernot et al.,, 2016; Steinhardt et
al.,, 2017) (non-exhaustive). Finally, for work on defences against poisoning
attacks, we refer the reader to (Goldblum et al.,, 2022).

Another view on robustness is out-of-distribution detection, where the goal is
to identify outliers at test time. We refer the reader to the textbook
(Quinonero-Candela et al.,, 2008) for an introduction on dataset shifts, and
to (Fang et al.,, 2022) for a study on out-of-distribution detection from a
PAC-learning perspective, as well as references therein for the empirical work
on the matter. A more general view on distributional discrepancies at test-
time is that of distribution shift. See (Wiles et al.,, 2022) for a taxonomy
on various distribution shifts and a review of important work in the area
(mostly from an empirical perspective).

####  5.1 Evasion Attacks

We now turn our attention to the focus of this thesis: robustness to evasion
attacks. For ease of reading, we have thematically split the related work in
this section.

##### Defining Robustness.

The majority of the guarantees and impossibility results for evasion attacks
are based on the existence of adversarial examples. However, what is
considered to be an adversarial example has been defined in different, and in
some respects contradictory, ways in the literature. What we refer to as the
_exact-in-the-ball_ notion of robustness in this work (also known as _error
region_ risk in (Diochnos et al.,, 2018)) requires that the hypothesis and the
ground truth agree in the perturbation region around each test point; the
ground truth must thus be specified on all input points in the perturbation
region. On the other hand, what we refer to as the constant-in-the-ball notion
of robustness (which is also known as _corrupted input_ robustness from the
work of Feige et al., (2015)) requires that the unperturbed point be correctly
classified and that the points in the perturbation region share its label,
meaning that we only need access to the test point labels; the works Diochnos
et al., (2018); Dreossi et al., (2019); Pydi and Jog, (2021) offer thorough
discussions on the subject and also compare robustness definitions. Moreover,
Chowdhury and Urner, (2022) have studied settings where a model’s change of
label is justified by looking at robust-Bayes classifiers and their standard
counterparts.

We note that Suggala et al., (2019) proposed an alternative definition of
robustness, where a perturbation is deemed adversarial if it causes a label
change in the hypothesis _while the target classifier’s label remains
constant_. The existence of a ground truth is thus explicitly assumed (which
is not in general necessary for constant-in-the-ball robustness).

Rather than studying the existence of a misclassification in the perturbation
region, Pang et al., (2022) define robustness using the Kullback-Leibler (KL)
divergence. The robust loss at a given unperturbed point $x$ is the maximal KL
divergence over perturbations $z$ between the underlying labelling function
($\underset{{}}{\Pr}\left(y\;|\;z\right)$) of $z$ and the hypothesis’ label
for $z$ (which could also be non-deterministic). The authors proposed this
definition of robustness in an effort to avoid the trade-off between accuracy
and robustness observed in prior work, e.g., (Tsipras et al.,, 2019).

In the remainder of this section, whenever the robust risk is not explicitly
mentioned, the results will hold for the constant-in-the-ball notion of
robustness, as it is the most widely used in the literature.

##### Existence of Adversarial Examples.

There is a considerable body of work that studies the inevitability of
adversarial examples, e.g., (Fawzi et al.,, 2016; Fawzi et al., 2018a, ; Fawzi
et al., 2018b, ; Gilmer et al.,, 2018; Shafahi et al.,, 2019; Tsipras et al.,,
2019). These papers characterize robustness in the sense that a classifier’s
output on a point should not change if a perturbation of a certain magnitude
is applied to it. These works also study geometrical characteristics of
classifiers and statistical characteristics of classification data that lead
to adversarial vulnerability. It has been shown that, in many instances, the
vulnerability of learning models to adversarial examples is inevitable due to
the nature of the learning problem. Notably, Bhagoji et al., (2019) study
robustness to evasion attacks from an optimal transport perspective, obtaining
lower bounds on the robust error. Moreover, many works exhibit a trade-off
between standard accuracy and robustness in this setting, e.g., (Tsipras et
al.,, 2019; Dobriban et al.,, 2020).

As for the exact-in-the-ball definition of robustness, Diochnos et al., (2018)
consider the robustness of monotone conjunctions under the uniform
distribution. Their results concern the ability of an adversary to magnify the
missclassification error of _any_ hypothesis with respect to _any_ target
function by perturbing the input.555We will draw an explicit comparison with
the work of Diochnos et al., (2018) in Section 11. Mahloujifar et al., (2019)
generalized the above-mentioned result to Normal Lévy families and a class of
well-behaved classification problems (i.e., ones where the error regions are
measurable and average distances exist).

##### Computational Complexity of Robust Learning.

The computational complexity of robust learning is an active research area.
Bubeck et al., (2018) and Degwekar et al., (2019) have shown that there are
concept classes that are hard to robustly learn under cryptographic
assumptions, even when robust learning is information-theoretically feasible.
(Bubeck et al.,, 2019) established super-polynomial lower bounds for robust
learning in the statistical query framework. Diakonikolas et al., (2019) study
the more specific problem of (standard) proper learning of halfspaces with
noise and large $\ell_{2}$ margins in the agnostic PAC setting, focussing on
the computational complexity of this learning problem. They remark that these
guarantees can apply to robust learning. In follow-up work (Diakonikolas et
al.,, 2020), they explicitly study robustness to $\ell_{2}$ perturbations and
generalize their previous results. In particular, they obtain computationally-
efficient algorithms using an online learning reduction, and building on a
hardness result in (Diakonikolas et al.,, 2019), and provide tight running
time lower bounds. Finally, Awasthi et al., (2019) draw connections between
robustness to evasion attacks and polynomial optimization problems, obtaining
a computational hardness result. On the other hand, they exhibit
computationally efficient robust learning algorithms for linear and quadratic
threshold functions in the realizable case.

##### Sample Complexity of Robust Learning.

Despite being a relatively recent research area, there already exists a vast
literature on the sample complexity of robust learning to evasion attacks. One
of the earlier works is that of Cullina et al., (2018), who define the notion
of adversarial VC dimension to derive sample complexity upper bounds for
robust empirical risk minimization (ERM) algorithms, with respect to the
constant-in-the-ball robust risk. They also study the special case of
halfspaces under $\ell_{p}$ perturbations and show the adversarial VC
dimension is in general incomparable with its standard counterpart. Shortly
after, Attias et al., (2019) adopted a game-theoretic framework to study
robust learnability for classification and regression in a setting where the
adversary is limited to a fixed number $k$ of perturbations per input. They
obtain sample complexity bounds that are linear in both $k$ and the VC
dimension of a hypothesis class. The work of Montasser et al., (2019) later
provided a more complete picture of robust learnability. The authors show
sample complexity upper bounds for robust ERM algorithms that are polynomial
in the VC and dual VC dimensions of concept classes, giving general upper
bounds that are exponential in the VC dimension. They also exhibit sample
complexity lower bounds linear in the robust shattering dimension, a notion of
complexity introduced therein. The gap between the upper and lower bounds was
closed in their later work (Montasser et al.,, 2022), where they fully
characterize the sample complexity of robust learning with arbitrary
perturbation functions. The robust learning algorithm achieving the upper
bound is a generalization of the one-inclusion graph algorithm of Haussler et
al., (1994). Their robust variant of the one-inclusion graph is defined for
the constant-in-the-ball _realizable_ setting,666I.e., there exists a
hypothesis that has zero constant-in-the-ball robust loss. but the agnostic-
to-realizable reduction from previous work (Montasser et al.,, 2019) can be
applied. The (random-example) sample complexity characterizing robust
learnability is a notion of _dimension_ defined through the edges on the graph
structure.

The above bounds consider the supervised setting, where the learner has access
to labelled examples. Since the cost of obtaining data is at times largely due
to its labelling,777Think for example of obtaining images vs needing humans to
label them. studying semi-supervised learning, where the learner has access to
both unlabelled as well as labelled examples, is of general interest. Ashtiani
et al., (2020) build on the work of Montasser et al., (2019) (who showed that
proper robust learning, where the learner is required to output a hypothesis
from the same class as the potential target concept, is sometimes impossible)
and delineate when proper robust learning is possible. They moreover draw a
more nuanced picture of proper robust learnability with access to unlabelled
random examples. Attias et al., (2022) also study the sample complexity of
robust learning in the semi-supervised framework. Notably, in the realizable
setting, their labelled sample complexity bounds are linear in a variant of
the VC dimension where, for a shattered set, the perturbation region around a
given point must share the same label.888This complexity measure is always
upper bounded by the VC dimension, and the gap can be arbitrarily large.  The
unlabelled sample complexity is linear in the sample complexity of
_supervised_ learning. The authors also extend their results to the agnostic
setting.

While it is worthwhile to study robust learnability for arbitrary perturbation
regions, focussing on specific perturbation functions that are more faithful
to real-world problems is of high interest, especially if this can provide
better guarantees or a clearer picture of robustness in this setting. In this
vein, Shao et al., (2022) study the robustness to evasion attacks under
_transformation invariances_. This terminology comes from group theory: the
transformations applied to instances form a group, and an invariant hypothesis
will give the same label to points in the orbit of every instance in the
support of the distribution generating the data.999E.g., rotating an image of
a cat will still result in an image of a cat, while rotating an image of a six
can result in an image of nine. Transformation invariances are thus problem
specific.  As a characterization of robust learnability in these settings,
they propose two combinatorial measures that are variants of the VC dimension
that take into account the orbits of points in the shattered set, and prove
nearly-matching upper and lower bounds.

All the works mentioned above study sample complexity through the VC dimension
of a concept class, or variants adapted to robust learnability. On the other
hand, Khim et al., (2019); Yin et al., (2019); Awasthi et al., (2020) instead
use the _adversarial_ Rademacher complexity to study robust learning. These
works give results for ERM on linear classifiers and neural networks.

As for the exact-in-the-ball definition of robustness, Diochnos et al., (2020)
study sample complexity lower bounds. They show that, for a wide family of
concept classes, any learning algorithm that is robust against all attacks
with budget $\rho=o(n)$ must have a sample complexity that is at least
exponential in the input dimension $n$. They also show a superpolynomial lower
bound in case $\rho=\Theta(\sqrt{n})$. This, along with the previously-
mentioned works of Diochnos et al., (2018); Mahloujifar et al., (2019) are to
our knowledge the only other works apart from ours that consider the sample
complexity of exact-in-the-ball robust learning from a theoretical
perspective.

##### Relaxing Robustness Requirements.

Most adversarial learning guarantees and impossibility results in the
literature have focused on all-powerful adversaries. Recent works have studied
learning problems where the adversary’s power is curtailed. One way to do this
is to consider _computationally-bounded_ adversaries. E.g, Mahloujifar and
Mahmoody, (2019) and Garg et al., (2020) study the robustness of classifiers
to polynomial-time attacks. They show that, for product distributions, an
initial constant error implies the existence of a (black-box) polynomial-time
attack for adversarial examples that are $O(\sqrt{n})$ bits away from the test
instances. However, Garg et al., (2020) show a separation result for a
learning problem where a classifier can be successfully attacked by a
computationally-unbounded adversary, but not by a polynomial-time bounded
adversary subject to standard cryptographic hardness assumptions.

It is also possible to relax the optimality condition when evaluating a
hypothesis. Ashtiani et al., (2023) and Bhattacharjee et al., (2023) both
study _tolerant robust learning_ , where the learner is evaluated relative to
the hypothesis with the best robust risk under a slightly larger perturbation
region. Ashtiani et al., (2023) show that this setting enables better sample
complexity bounds that the standard robust setting for metric spaces
$(\mathcal{X},d)$ in case the perturbation region is a ball with respect to
the metric $d$. Bhattacharjee et al., (2023) build on their work and instead
consider problems with a geometric niceness property called _regularity_ to
get more general perturbation regions. They obtain matching sample complexity
bounds to (Ashtiani et al.,, 2023) as well as propose a variant of robust ERM
as a simpler robust learning algorithm for this problem.

Another relaxation of the robust learning objective is a probabilistic variant
of robust learning. Viallard et al., (2021) derive PAC-Bayesian generalization
bounds (where the output is a posterior distribution over hypotheses after
seeing the data) for the averaged risk on the perturbations, rather than
working in a worst-case scenario. (Robey et al.,, 2022) also consider
probabilistic robustness, where the aim is to output a hypothesis that is
robust to _most_ perturbations.

##### Increasing the Learner’s Power.

To improve robustness guarantees, it is also possible to give the learner
access to more powerful oracles than the random-example one. Montasser et al.,
(2020, 2021) study robust learning with access to a (constant-in-the-ball)
robust loss oracle, which they call the Perfect Attack Oracle (PAO). For a
perturbation type $\mathcal{U}:\mathcal{X}\rightarrow 2^{\mathcal{X}}$,
hypothesis $h$ and labelled point $(x,y)$, the PAO returns the constant-in-
the-ball robust loss of $h$ in the perturbation region $\mathcal{U}(x)$ and a
counterexample $z\in\mathcal{U}(x)$ where $h(z)\neq y$ if it exists. In the
constant-in-the-ball _realizable_ setting, the authors use online learning
results to show sample and query complexity bounds that are linear and
quadratic in the Littlestone dimension of concept classes, respectively
(Montasser et al.,, 2020). Montasser et al., (2021) moreover use the algorithm
from (Montasser et al.,, 2019) to get sample and query complexity upper bounds
that respectively have a linear and exponential dependence on the VC and dual
VC dimensions of the hypothesis class at hand. Finally, they extend their
results to the agnostic setting and derive lower bounds.

##  Chapter 3 Background

In this chapter, we introduce the necessary background and notation for the
main contributions of this thesis. We start by reviewing standard learning
theory concepts in Section 6, before moving to probability theory in Section
7. We finish with an overview of Fourier analysis in Section 8.

##### Notation.

Throughout this text, we will use $[n]$ to denote the set
$\left\\{1,\dots,n\right\\}$. The symbol $\Delta$ will represent the symmetric
difference between two sets: $I\Delta J=\left\\{x\;|\;x\in I\setminus J\text{
or }x\in J\setminus I\right\\}$. We will use the asymptotic notation
($o,O,\omega,\Omega,\Theta$), with the convention that the symbol
$\;\widetilde{\;}$ (e.g., $\widetilde{O}$) omits the logarithmic factors.
Given a metric space $(\mathcal{X},d)$ and $\lambda\in\mathbb{R}$, we denote
by $B_{\lambda}(x)$ the ball
$\left\\{z\in\mathcal{X}\;|\;d(x,z)\leq\lambda\right\\}$ of radius $\lambda$
centred at $x$. We will use the symbol $\mathbf{1}[\cdot]$ for the indicator
function. Finally, for a given formula $\varphi$ and instance $x$, we denote
by $x\models\varphi$ the event that $x$ satisfies $\varphi$.

###  6 Learning Theory: Classification

Learning theory offers an elegant abstract framework to analyse the behaviour
of machine learning algorithms, as well as to provide performance and
correctness guarantees or show impossibility results. There exist various
learning settings, depending on assumptions on how the data is obtained and on
the learning objectives. This thesis is primarily concerned with _binary
classification_ , where, given an input space $\mathcal{X}$, the goal is to
output a function $h:\mathcal{X}\rightarrow\\{0,1\\}$ called a _hypothesis_ ,
which upon being given an instance $x\in\mathcal{X}$ outputs a label
$h(x)\in\\{0,1\\}$. The more general task of learning a function
$\mathcal{X}\rightarrow\mathcal{Y}$ is called _multiclass classification_ when
$\mathcal{Y}$ is a discrete finite set, and _regression_ when
$\mathcal{Y}=\mathbb{R}$.

In this section, we give an overview of three learning settings for binary
classification: learning with random examples in the Probably Approximately
Correct (PAC) framework, the mistake-bound model of online learning, and
learning with membership and equivalence queries. For each setting, we discuss
various notions of complexity that control the amount of data needed to learn,
i.e., the _sample complexity_. In all cases, we will be using the terms
learning algorithm, learner and learning process interchangeably to denote a
process of data acquisition and analysis resulting in outputting a hypothesis
$h$ as above. For a more in-depth introduction to the concepts presented in
this section, we refer the reader to Mohri et al., (2012) and Shalev-Shwartz
and Ben-David, (2014), both excellent introductory textbooks on learning
theory.

####  6.1 The PAC Framework

The Probably Approximately Correct (PAC) framework of Valiant, (1984),
depicted in Figure 2, formalises the desired behaviour of a learning
algorithm. In this learning setting, a learning algorithm has access to
_random examples_ drawn in an i.i.d. fashion from an underlying distribution
$D$, and we wish to output a hypothesis that has small _error_ with high
_confidence_. The error $\text{err}_{D}(h,c)$ of a hypothesis with respect to
$D$ is measured against a _ground truth function_ or _target concept_
$c:\mathcal{X}\rightarrow\\{0,1\\}$ which labels the data, and is defined as

$\text{err}_{D}(h,c)=\underset{{x\sim D}}{\Pr}\left(c(x)\neq
h(x)\right)\enspace.$

The set of points $x\in\mathcal{X}$ such that $c(x)\neq h(x)$ is often
referred to as the _error region_. We sometimes model the sampling process by
having access to the random example oracle $\mathsf{EX}(c,D)$. The “probably”
part of the PAC learning framework speaks to the confidence of the learning
algorithm, and allows for the possibility that a sample $S\sim D^{m}$ of size
$m$ drawn from the underlying distribution $D$ is not representative of $D$.
The “approximately” part of PAC learning refers to the requirement that the
hypothesis have sufficiently high accuracy, a relaxation from learning
_exactly._ Both the confidence and accuracy parameters are inputs to the
learning algorithm, and are _learning parameters_.

Another important parameter that affects the sample complexity is how _large_
the instance size is, e.g., the larger the number of pixels for image
classification is, the larger the amount of data needed to learn could be.
This is usually controlled by the _dimension $n$ of the input space_, in
reference to $\left\\{0,1\right\\}^{n}$ and $\mathbb{R}^{n}$. To this end we
consider a collection of pairs of input space and concepts classes
$\mathcal{X}_{n}$ and $\mathcal{C}_{n}$ for each dimension $n$, where
$\mathcal{C}_{n}$ is a set of functions
$c:\mathcal{X}_{n}\rightarrow\\{0,1\\}$.

We are now ready to formally define the PAC learning setting.

######  Definition 3.1 (PAC Learning, Realizable Setting).

For all $n\in\mathbb{N}$, let $\mathcal{C}_{n}$ be a concept class over
$\mathcal{X}_{n}$ and let
$\mathcal{C}=\bigcup_{n\in\mathbb{N}}\mathcal{C}_{n}$. We say that
$\mathcal{C}$ is _PAC learnable using hypothesis class $\mathcal{H}$_ and
sample complexity function $m(\cdot,\cdot,\cdot,\cdot)$ if there exists an
algorithm $\mathcal{A}$ that satisfies the following: for all
$n\in\mathbb{N}$, for every $c\in\mathcal{C}_{n}$, for every $D$ over
$\mathcal{X}_{n}$, for every $0<\epsilon<1/2$ and $0<\delta<1/2$, if whenever
$\mathcal{A}$ is given access to $m\geq
m(n,1/\epsilon,1/\delta,\text{size}(c))$ examples drawn i.i.d. from $D$ and
labeled with $c$, $\mathcal{A}$ outputs an $h\in\mathcal{H}$ such that with
probability at least $1-\delta$,

$\text{err}_{D}(h,c)=\underset{{x\sim D}}{\Pr}\left(c(x)\neq
h(x)\right)\leq\epsilon\enspace.$

We say that $\mathcal{C}$ is statistically efficiently PAC learnable if $m$ is
polynomial in $n,1/\epsilon$, $1/\delta$ and size$(c)$, and computationally
efficiently PAC learnable if $\mathcal{A}$ runs in polynomial time in
$n,1/\epsilon$, $1/\delta$ and size$(c)$ and $h$ is polynomially evaluatable.

Probably Approximately Correct Learning

$\mathcal{A}$$S_{c}\sim D^{m}$
$m=\text{poly}(n,\frac{1}{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\varepsilon}},\frac{1}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\delta}})$$h\in\mathcal{H}$
s.t.
err${}_{D}(h,c)\leq{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\varepsilon}$w.p.
$>1-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\delta}$

Figure 2: A visual representation of sample-efficient PAC learning. $S_{c}$
means that the sample $S$ has been labelled with the ground truth $c$.

##### Size$(c)$ and polynomial evaluatability.

Two additional requirements from accuracy and confidence are introduced in the
above definition: these are a sample complexity function dependent on the size
$size(c)$ of the target concept $c$, and, if one requires computational
efficiency, the fact that $h$ is _polynomially evaluatable_. The size of a
concept is defined through a _representation scheme_. Essentially, there could
exist several representations of a function, e.g., a function can be computed
by many different boolean circuits. Assuming that there exists a function
measuring the size of a representation, the size of a concept $c$ is the
minimal size of a representation of $c$. The second requirement is natural: if
the hypothesis is not required to be polynomially evaluatable, then the
learner could simply “offload” the learning process at test time (there is
nothing to do at training, so it would be considered “efficient”), and overall
require arbitrarily high computational complexity.

##### Proper vs improper learning.

The setting where $\mathcal{C}=\mathcal{H}$ is called _proper learning_ , and
_improper learning_ if $\mathcal{C}\subseteq\mathcal{H}$. While requiring
proper learning does not affect the sample complexity of learning very
much,101010It is possible to get rid of the $\log 1/\epsilon$ factor of
Theorem 3.8 as shown by the recent breakthrough of Hanneke, (2016) with an
improper learner, but, aside from this, the sample complexity bounds in
Theorems 3.8 and 3.9 are tight for any consistent learner. it can affect its
computational efficiency. Indeed, unless $\mathsf{RP}=\mathsf{NP}$, which is
widely believed not to be the case, it is impossible to computationally
efficiently _properly_ learn the class of 3-term formulas in disjunctive
normal form (DNF), i.e., formulas of the form $T_{1}\vee T_{2}\vee T_{3}$
where the $T_{i}$’s are conjunctions of arbitrary lengths. However, it is
possible to computationally efficiently PAC learn 3-CNF formulas properly
(formulas in conjunctive normal form where each term is a disjunction of at
most 3 literals), and this class subsumes 3-term DNFs. Hence, one can use the
PAC-learning algorithm for 3-CNF to (improperly) PAC learn 3-term DNFs in a
computationally efficient manner.

##### The distribution-free assumption.

PAC learning is _distribution-free_ , in the sense that no assumptions are
made about the distribution from which the data is generated. As long as the
training data is sampled i.i.d. from a given distribution $D$, and that the
algorithm is tested on independent examples drawn from $D$, the learning
guarantees hold. Of course, this is sometimes not a sensible assumption to
make in practice. Many lines of work consider learning settings that allow for
this and provide a more realistic learning framework, e.g., when noise is
added to the data, or when the training and testing distributions differ
(i.e., distribution shift), as outlined in Chapter 2.

##### Realizable vs agnostic learning.

The _realizability assumption_ of Definition 3.1, where there always exists a
concept with zero error, does not always hold. In the presence of noise, or
more generally in the absence of a _deterministic_ labelling function $c$
representing the ground truth (e.g., there is a joint distribution on
$\mathcal{X}\times\mathcal{Y}$), we instead work in the _agnostic setting_. In
this setting, the goal is rather to learn a hypothesis that does well compared
to the best concept in the concept class:

######  Definition 3.2 (PAC Learning, Agnostic Setting).

Let $\mathcal{C}_{n}$ be a concept class over $\mathcal{X}_{n}$ and let
$\mathcal{C}=\bigcup_{n\in\mathbb{N}}\mathcal{C}_{n}$. We say that
$\mathcal{C}$ is _agnostically PAC learnable using $\mathcal{H}$_ with sample
complexity function $m(\cdot,\cdot,\cdot,\cdot)$ if there exists an algorithm
$\mathcal{A}$ that satisfies the following: for all $n\in\mathbb{N}$, for
every $D$ over $\mathcal{X}_{n}\times\\{0,1\\}$, for every $0<\epsilon<1/2$
and $0<\delta<1/2$, if whenever $\mathcal{A}$ is given access to $m\geq
m(n,1/\epsilon,1/\delta,s)$ labelled examples drawn i.i.d. from $D$, where
$s=\underset{c\in\mathcal{C}_{n}}{\sup}\;\text{size(c)}$, $\mathcal{A}$
outputs an $h\in\mathcal{H}$ such that with probability at least $1-\delta$,

$\text{err}_{D}(h)\leq\underset{c\in\mathcal{C}_{n}}{\inf}\text{err}_{D}(c)+\epsilon\enspace,$

where $\text{err}_{D}(h)=\underset{{(x,y)\sim D}}{\Pr}\left(h(x)\neq
y\right)$. We say that $\mathcal{H}$ is statistically efficiently agnostically
learnable if $m$ is polynomial in $n,1/\epsilon$, $1/\delta$ and $s$, and
computationally efficiently agnostically learnable if $\mathcal{A}$ runs in
polynomial time in $n,1/\epsilon$, $1/\delta$ and $s$, and $h$ is polynomially
evaluatable.

The definition above allows for improper learning ($\mathcal{C}$ is usually
called the “touchstone” class), but we can recover proper learning by setting
$\mathcal{C}=\mathcal{H}$. In this work, unless otherwise stated, we will
assume the realizability of a learning problem, and the sample complexity
bounds will be derived for this setting. Note that there exist PAC guarantees
for classes of finite VC dimension in the agnostic setting as well, at the
cost of a multiplicative factor of $1/\epsilon$ in the sample complexity. See
(Kearns et al.,, 1994; Haussler,, 1992) for original work on the matter and
the textbook (Mohri et al.,, 2012) for an introduction on the topic.

####  6.2 Complexity Measures

While it is possible to derive sample complexity bounds for specific
hypothesis classes, one can take a more general approach with the use of
_complexity measures_. Indeed, a complexity measure assigns to each hypothesis
class $\mathcal{H}$ a function (w.r.t. the size $n$ of the instance space)
quantifying its richness. Intuitively, as the complexity measure increases,
more data should be needed to identify a candidate hypothesis that would
generalize well on unseen data. We briefly note that the standard theory
outlined in this chapter has failed to explain the recent success of
overparametrised deep neural networks in practice which in many ways remains
an open problem in the learning theory literature.

The first complexity measure we will study is perhaps the simplest one: the
size of $\mathcal{H}$. Similarly to $\mathcal{C}$, the class $\mathcal{H}$ is
defined as the union $\bigcup_{n\in\mathbb{N}}\mathcal{H}_{n}$, and the size
of $\mathcal{H}$ is a function of $n$. The theorem below, known as Occam’s
razor, gives an upper bound on the sample complexity of learning with finite
hypothesis classes, given access to a _consistent_ learner. A consistent
learner is a learning algorithm that outputs a hypothesis that has zero
empirical loss on the training sample, i.e., a hypothesis that correctly
classifies all the points in the training sample.

######  Theorem 3.3 (Occam’s Razor (Blumer et al.,, 1987)).

Let $\mathcal{C}$ and $\mathcal{H}$ be a concept and hypothesis classes,
respectively. Let $\mathcal{A}$ be a consistent learner for $\mathcal{C}$
using $\mathcal{H}$. Then, for all $n\in\mathbb{N}$, for every
$c\in\mathcal{C}_{n}$, for every $D$ over $\mathcal{X}_{n}$, for every
$0<\epsilon<1/2$ and $0<\delta<1/2$, if whenever $\mathcal{A}$ is given access
to
$m\geq\frac{1}{\epsilon}\left(\log(|\mathcal{H}_{n}|)+\log(1/\delta)\right)$
examples drawn i.i.d. from $D$ and labeled with $c$, then $\mathcal{A}$ is
guaranteed to output an $h\in\mathcal{H}_{n}$ such that
$\text{err}_{D}(h,c)<\epsilon$ with probability at least $1-\delta$.
Furthermore, if $\log(|\mathcal{H}_{n}|)$ is polynomial in $n$ and size$(c)$,
and $h$ is polynomially evaluatable, then $\mathcal{C}$ is statistically
efficiently PAC-learnable using $\mathcal{H}$.

While the theorem above can be useful if $\mathcal{H}_{n}$ is finite for all
$n$, it does not tell us much when $\mathcal{H}$ is infinite. To this end, one
would want to consider complexity measures that are meaningful for infinite
concept classes as well. In the PAC setting, a useful complexity measure is
the Vapnik Chervonenkis (VC) dimension of a hypothesis class, from the work of
Vapnik and Chervonenkis, (1971). It turns out that this measure fully
_characterizes_ the learnability of a concept class, in the sense that one can
obtain upper _and_ lower bounds on the sample complexity that are both
_linear_ in the VC dimension of $\mathcal{H}$.

In order to define the VC dimension of a concept class, we must first define
the notion of _shattering_ of a set. In Figure 3, we give an example of a set
being shattered by linear classifiers in $\mathbb{R}^{2}$.

######  Definition 3.4 (Shattering).

Given a class of functions $\mathcal{F}$ from input space $\mathcal{X}$ to
$\left\\{0,1\right\\}$, we say that a set $S\subseteq\mathcal{X}$ is
_shattered by $\mathcal{F}$_ if all the possible dichotomies of $S$ (i.e., all
the possible ways of labelling the points in $S$) can be realized by some
$f\in\mathcal{F}$.

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$
(a)

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$
(b)

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$
(c)

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$
(d)

Figure 3: A set $X$ of three points in $\mathbb{R}^{2}$ that is shattered by
linear classifiers. Subfigures (a)-(d) represent different dichotomies on $X$;
note that (b) and (c) are not the only labellings with one and two positively
labelled points, respectively, but the other cases are symmetric.

We are now ready to define the VC dimension of a class.

######  Definition 3.5 (VC Dimension).

The VC dimension of a hypothesis class $\mathcal{H}$, denoted
$\mathsf{VC}(\mathcal{H})$, is the size $d$ of the largest set that can be
shattered by $\mathcal{H}$. If no such $d$ exists then
$\mathsf{VC}(\mathcal{H})=\infty$.

Figure 4 illustrates the argument that no set in $\mathbb{R}^{2}$ of size 4
can be shattered by linear classifiers.

An important property of the VC dimension is that it is upper bounded by
$\log\left|\mathcal{H}\right|$. Indeed, a shattered set $S$ of size $m$ needs
$2^{m}$ distinct functions to achieve all its possible labellings.

It also is possible to define the VC dimension through the _growth function_
of a concept class. For some finite set of instances $S$, we denote by
$\Pi_{\mathcal{C}}(S)=\\{c|_{S}\;|\;c\in\mathcal{C}\\}$ the set of distinct
restrictions of concepts in $\mathcal{C}$ on the set $S$, which is referred to
as the set of all possible dichotomies on $S$ induced by $\mathcal{C}$. Then a
shattered set $S$ satisfies
$\left|\Pi_{\mathcal{C}}(S)\right|=2^{\left|S\right|}$, and the VC dimension
is thus the largest set satisfying this relationship.

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$
(a)

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-}$
(b)

Figure 4: Any set of four points cannot be shattered by linear classifiers.
Indeed, we distinguish two cases: either (a) one point is strictly in the
convex hull of the three other points, and is the only point of its label (or
all points are on the same line, which gives a similar argument) or (b) all
points are on the boundary of the convex hull, in which case labelling
opposite points with the same label gives an unachievable labelling. This
argument is a special case for $\mathbb{R}^{2}$ which can be generalized to
$\mathbb{R}^{n}$ using Radon’s theorem.

######  Definition 3.6 (Growth Function).

For any natural number $m\in\mathbb{N}$, the growth function is defined as
$\Pi_{\mathcal{C}}(m)=\max\left\\{\left|\Pi_{\mathcal{C}}(S)\right|\;|\;\left|S\right|=m\right\\}$.

Denote by $\Phi_{d}(m)$ the summation $\sum_{i=0}^{d}{m\choose i}$. The growth
function of a concept class $\mathcal{C}$ can be bounded as follows, as a
function of $m$ and the VC dimension $d$.

######  Lemma 3.7 (Sauer-Shelah).

Let $\mathcal{C}$ be a concept class of VC dimension $d$. Then

$\Pi_{\mathcal{C}}(m)\leq\Phi_{d}(m)\leq\left(\frac{em}{d}\right)^{d}\enspace.$

As previously mentioned, the VC dimension characterizes PAC learnability. We
start with a sample complexity upper bound that is linear in the VC dimension,
due to Vapnik, (1982) and Blumer et al., (1989).

######  Theorem 3.8 (VC Dimension Sample Complexity Upper Bound).

Let $\mathcal{C}$ be a concept class. Let $\mathcal{A}$ be a consistent
learner for $\mathcal{C}$ using a hypothesis class $\mathcal{H}$ of VC
dimension $\mathsf{VC}(\mathcal{H})=d$. Then $\mathcal{A}$ is a PAC-learning
algorithm for $\mathcal{C}$ using $\mathcal{H}$ provided it is given an i.i.d.
sample $S\sim D^{m}$ drawn from some $D$ and labelled with some
$c\in\mathcal{C}$, where

$m\geq\kappa_{0}\cdot\frac{1}{\epsilon}\left(d\log\frac{1}{\epsilon}+\log\frac{1}{\delta}\right)\enspace,$

for some universal constant $\kappa_{0}$.

We now have a sample complexity lower bound that is also linear in the VC
dimension, due to Blumer et al., (1989) and Ehrenfeucht et al., (1989). The
proofs of both Theorems 3.8 and 3.9 appear in reference textbooks such as
(Mohri et al.,, 2012) and (Shalev-Shwartz and Ben-David,, 2014).

######  Theorem 3.9 (VC Dimension Sample Complexity Lower Bound).

Let $\mathcal{C}$ be a concept class with VC dimension $d$. Then any PAC-
learning algorithm for $\mathcal{C}$ requires
$\Omega\left(\frac{d}{\epsilon}+\frac{1}{\epsilon}\log\frac{1}{\delta}\right)$
examples.

While the bounds of Theorems 3.8 and 3.9 are tight up to a
$\log\frac{1}{\epsilon}$, the breakthrough work of Hanneke, (2016) recently
showed the existence of a specific learning algorithm that is optimal in the
sense that its sample complexity matches that of Theorem 3.9 up to constant
factors, and thus avoids the $\log\frac{1}{\epsilon}$ dependence.

####  6.3 Some Concept Classes and PAC Learning Algorithms

In this section, we introduce various concept classes that have been studied
in the learning theory literature, along with PAC learning algorithms. All the
algorithms outlined below are consistent on a given training sample, given we
are working in the realizable setting. A bound on the VC dimension of these
concept classes directly gives sample complexity upper bounds as per Theorem
3.8. We start with concept classes defined on the boolean hypercube
$\mathcal{X}=\left\\{0,1\right\\}^{n}$.

##### Singletons.

For an input space $\mathcal{X}$, the class of singletons is the class of
functions
$\left\\{x\mapsto\mathbf{1}[x=x^{*}]\;|\;x^{*}\in\mathcal{X}\right\\}$.

##### Dictators.

The class of dictators on $\left\\{0,1\right\\}^{n}$ is the class of functions
determined by a single bit, i.e., functions of the form $h(x)=x_{i}$ or
$h(x)=\bar{x_{i}}$ for $i\in[n]$. Dictators are subsumed by conjunctions.
Monotone dictators are dictators where negations are not allowed, i.e.,
functions of the form $h(x)=x_{i}$.

##### Conjunctions.

Conjunctions, which we denote CONJUNCTIONS, are perhaps one of the simplest
non-trivial concept classes one can study on the boolean hypercube. A
conjunction $c$ over $\\{0,1\\}^{n}$ is a logical formula over a set of
literals $l_{1},\dots,l_{k}$ from
$\left\\{x_{1},\bar{x_{1}},\dots,x_{n},\bar{x_{n}}\right\\}$, where, for
$x\in\mathcal{X}_{n}$, $c(x)=\bigwedge_{i=1}^{k}l_{i}$. The _length_ of a
conjunction $c$ is the number of literals in $c$.111111We use the term
_length_ for conjunctions that are not equivalent to the constant function 0.
For example, $c(x)=x_{1}\wedge\bar{x_{2}}\wedge{x_{5}}$ is a conjunction of
length 3. Monotone conjunctions are the subclass of conjunctions where
negations are not allowed, i.e., all literals are of the form $l_{i}=x_{j}$
for some $j\in[n]$. Note that this implies that monotone conjunctions do not
include the constant function 0.

Algorithm 1 PAC-learning algorithm for conjunctions

$S_{c}\sim D^{m}$

$L\leftarrow\left\\{x_{1},\bar{x_{1}},\dots,x_{n},\bar{x_{n}}\right\\}$

$h(x)=\bigwedge_{l\in L}l$ $\triangleright$ $h=0$

for $(x,c(x))\in S$ do

if $c(x)\neq h(x)$ then $\triangleright$ Only happens if $c(x)=1$

$L\leftarrow L\setminus\left\\{l\in L\;|\;l(x)=0\right\\}$

end if

end for

The standard PAC learning algorithm to learn conjunctions is as outlined in
Algorithm 1. We start with the constant hypothesis $h(x)=\bigwedge_{i\in
I_{h}}(x_{i}\wedge\bar{x_{i}})\equiv 0$, where $I_{h}=[n]$. To ensure
consistency, for each example $x$ in the training sample, we remove a literal
$l$ from $h$ if $c(x)=1$ and $l(x)=0$, as if $l$ is in the conjunction, $h$
must evaluate to $0$ on $x$. After seeing all the examples in the training set
$S$, the resulting hypothesis will thus be consistent on $S$. Note that
$\mathsf{VC}(\textsf{CONJUNCTIONS}_{n})=n$ (Natschläger and Schmitt,, 1996).
Finally, Algorithm 1 can also be used for monotone conjunctions, but where the
initial hypothesis is $h(x)=\bigwedge_{i\in[n]}x_{i}$.

##### CNF and DNF formulas.

A formula $\varphi$ in the conjunctive normal form (CNF) is a conjunction of
clauses, where each clause is itself a disjunction of literals. A $k$-CNF
formula is a CNF formula where each clause contains at most $k$ literals. For
example, $\varphi=(x_{1}\vee x_{2})\wedge(\bar{x_{3}}\vee
x_{4})\wedge\bar{x_{5}}$ is a 2-CNF. On the other hand, a DNF formula is a
disjunction of clauses, where each clause is itself a conjunction of literals.
A $k$-DNF is defined analogously to a $k$-CNF.

##### Decision lists.

Given a positive integer $k$, a $k$-decision list $f\in k$-$\mathsf{DL}$ is a
list $(K_{1},v_{1}),\dots,(K_{r},v_{r})$ of pairs where $K_{j}$ is a term in
the set of all conjunctions of size at most $k$ with literals drawn from
$\left\\{x_{1},\bar{x_{1}},\dots,x_{n},\bar{x_{n}}\right\\}$, $v_{j}$ is a
value in $\left\\{0,1\right\\}$, and $K_{r}$ is $\mathtt{true}$. The output
$f(x)$ of $f$ on $x\in\left\\{0,1\right\\}^{n}$ is $v_{j}$, where $j$ is the
least index such that the conjunction $K_{j}$ evaluates to $\mathtt{true}$ on
$x$. Decision lists subsume conjunctions. Indeed, a conjunction
$c(x)=\bigwedge_{i=1}^{k}l_{i}$ can be expressed as the following 1-decision
list: $(\neg l_{1},0),\dots,(\neg l_{k},0),(\mathtt{true},1)$.

The PAC-learning algorithm for decision lists, introduced by Rivest, (1987),
is outlined in Algorithm 2. The sample size $m$ is given by Theorem 3.8 and an
observation that the size of the class is
$O\left(3^{\left|C_{n,k}\right|}\left|C_{n,k}\right|!\right)$, where $C_{n,k}$
is the set of conjunctions of length at most $k$ on $n$ variables, giving a VC
dimension bound of $O(n^{k}\log n)$. Note that, as we consider $k$ to be a
fixed constant, the sample complexity bound is polynomial in $n$ and the
learning parameters.

Algorithm 2 PAC-learning algorithm for 1-decision lists from Rivest, (1987)

$S\sim D^{m}$

$L:=\left\\{x_{i},\bar{x_{i}}\right\\}_{i=1}^{n}$ $\triangleright$ Set of all
literals

$h=\emptyset$ $\triangleright$ Empty decision list

while $S\neq\emptyset$ do

if $\exists b\in\left\\{0,1\right\\}$ s.t. $\forall(x,y)\in S,\;y=b$ then

$S\leftarrow\emptyset$

append $(\mathtt{true},b)$ to $h$

else

for $l\in L$ s.t. $\exists(x,y)\in S$ s.t. $l(x)=1$ do $\triangleright$ $l$ is
true for some $x$

if $\exists b\in\left\\{0,1\right\\}$ s.t. $\forall(x,y)\in
S\;\left(l(x)=1\Rightarrow y=b\right)$ then

append $(l,b)$ to $h$

$S\leftarrow S\setminus\left\\{(x,y)\in S\;|\;l(x)=1\right\\}$

end if

end for

end if

end while

Note that, while the algorithm above is for 1-decision lists, it is sufficient
to only consider this case. Indeed, if we are dealing with $k$-decision lists,
we can draw our attention to the set $C_{n,k}$ of conjunctions of length at
most $k$ on $n$ variables by defining the following injective map:

$\Phi:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,1\right\\}^{C_{n,k}}\enspace,$
(1)

where $\Phi(x)_{c_{i}}=\mathbf{1}[x\models c_{i}]$ for $c_{i}\in C_{n,k}$,
i.e. whether $x$ satisfies clause $c_{i}$. Now, any distribution $D$ on
$\left\\{0,1\right\\}^{n}$ induces a well-defined distribution $D^{\prime}$ on
$\left\\{0,1\right\\}^{C_{n,k}}$. Moreover, since
$\left|{C_{n,k}}\right|=O(n^{k})$, an input $x\in\left\\{0,1\right\\}^{n}$ and
a 1-decision $h$ on $\left\\{0,1\right\\}^{n}$ can respectively be transformed
into $\Phi(x)\in\left\\{0,1\right\\}^{C_{n,k}}$ and a $k$-decision list
$h^{\prime}$ on $\left\\{0,1\right\\}^{C_{n,k}}$ in polynomial time, for a
fixed $k$, and vice-versa in the case of going from $h^{\prime}$ to $h$. It
also follows that
$\text{err}_{D}(h,c)=\text{err}_{D^{\prime}}(h^{\prime},c^{\prime})$, where
$c^{\prime}$ is the $k$-decision list on $\left\\{0,1\right\\}^{C_{n,k}}$
induced by $c$. Hence, an efficient learning algorithm for 1-decision lists
can be used as a black box to efficiently learn $k$-decision lists.

Finally, the class of $k$-decision lists subsume $k$-CNF and $k$-DNF (Rivest,,
1987).

##### Decision trees.

A decision tree $T$ is a binary tree whose nodes are positive literals in
$\left\\{x_{1},\dots,x_{n}\right\\}$. For a given node with variable $x_{i}$,
the edge to its left child node is labelled with 0 and the edge to its right
child node is labelled as 1, representing the value of the $x_{i}$ for a given
instance $x\in\left\\{0,1\right\\}^{n}$. The leaves take label in
$\left\\{0,1\right\\}$; a given $x\in\left\\{0,1\right\\}^{n}$ induces a path
from the root to a leaf in $T$, which will give the label $T(x)$. Decision
trees generalize 1-decision lists: a 1-decision list is a decision tree with
each node having at most one child. Note that it is currently unknown whether
polynomial-sized decision trees are PAC learnable.

##### Parities.

Parities are defined with respect to a subset $I\subseteq[n]$ of indices as
$f_{I}(x)=\left(\sum_{i\in I}x_{i}\right)\bmod 2$, i.e. the output is whether
adding the bits at indices in $S$ results in an odd or even sum. Learning
parities amounts to learning the set $S$. Given a set of examples
$(X,Y)\subseteq\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}$, where each
$(x,y)\in(X,Y)$ is a labelled example, finding this set is equivalent to
finding a solution $a\in\left\\{0,1\right\\}^{n}$ to the system of linear
equations $Xa=Y$ in the finite field $\mathbb{F}_{2}$. The set
$J:=\left\\{j\in[n]\;|\;a_{j}=1\right\\}$ gives a hypothesis
$f_{J}(x)=\left(\sum_{j\in J}x_{j}\right)\bmod 2$ consistent with the data.
This can be done using Gaussian elimination, provided a solution exists (this
is guaranteed by the realizability assumption). See (Helmbold et al.,, 1992;
Goldberg,, 2006) for details.

Note that, when working in $\left\\{-1,1\right\\}^{n}$ instead of
$\left\\{0,1\right\\}^{n}$, we can define the parity function as
$f_{I}(x)=\prod_{i\in I}x_{i}$ instead. This representation will be especially
relevant in Section 8 when we introduce Fourier analysis concepts.

##### Majorities.

Similarly to parities, majorities are defined with respect to a set $I$ of
indices, as follows: $\text{maj}_{I}(x)=\mathbf{1}\left[\sum_{i\in
I}x_{i}\geq\left|I\right|/2\right]$. Again, when working in
$\left\\{-1,1\right\\}^{n}$ instead of $\left\\{0,1\right\\}^{n}$, majority
functions are defined as $\text{maj}_{I}(x)=\text{sgn}\left(\sum_{i\in
I}x_{i}\right)$. Clearly, from the representations above, majorities are
subsumed by linear classifiers, which are defined further below.

##### Linear classifiers.

The class of linear classifiers (also known as halfspaces and linear threshold
functions) on input spaces $\mathcal{X}=\left\\{0,1\right\\}^{n}$ or
$\mathcal{X}=\mathbb{R}^{n}$ are defined as
$\left\\{x\mapsto\text{sgn}\left(w\cdot
x+b\right)\;|\;w\in\mathbb{R}^{n},b\in\mathbb{R}\right\\}$, where the
$w_{i}\in w$ are the _weights_ and $b$ is the _bias_. When the instance space
is the reals, we will denote the class as $\mathsf{LTF}_{\mathbb{R}^{n}}$.
Moreover, we will denote by $\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W}$ the
class of linear threshold functions on $\left\\{0,1\right\\}^{n}$ with integer
weights such that the sum of the absolute values of the weights and the bias
is bounded above by $W$, and $W^{+}$ when the weights are positive. Finally,
when the weights and the bias are binary, i.e., $w_{i},b\in\\{0,1\\}$ for all
$i$, the class is called _boolean threshold functions_.

The VC dimension of halfspaces is $n+1$. The upper bound of $n+1$ can be shown
by using Radon’s theorem (any set of size $n+2$ in $\mathbb{R}^{n}$ can be
partitioned into two subsets whose convex hulls intersect), and the lower
bound can be obtained by showing that the set
$\left\\{\mathbf{e}_{i}\right\\}_{i=1}^{n}\cup\mathbf{0}$ can be shattered.
The support vector machine (SVM) algorithm, or solving a system of linear
inequalities with linear programming, can be used as a consistent learner for
this concept class. Finally, the class of conjunctions is subsumed by linear
classifiers: a conjunction $f(x)=\bigwedge_{i=1}^{k}l_{i}$ can be represented
as the linear classifier $g(x)=\text{sgn}\left(\sum_{i\in
I^{+}}x_{i}-\sum_{i\in I^{-}}x_{i}-\left|I\right|+1\right)$, where
$I^{+}=\left\\{j\in[n]\;|\;\exists i\;.\;l_{i}=x_{j}\right\\}$ and
$I^{-}=\left\\{j\in[n]\;|\;\exists i\;.\;l_{i}=\bar{x_{i}}\right\\}$.

####  6.4 Online Learning: The Mistake-Bound Model

In online learning, the learner is given access to examples _sequentially_. At
each time step $t$, the learner receives an example $x_{t}$, predicts its
label $\hat{y}_{t}$ using a given hypothesis class $\mathcal{H}$, receives the
true label $y_{t}$ and can update its hypothesis, typically when
$\hat{y}_{t}\neq y_{t}$. A fundamental distinction between the PAC- and
online-learning models is that, in the latter, there are usually no
distributional assumptions on the data.121212Some lines of work in online
learning look at mild distributional assumptions in the learning problem in
order to get better guarantees, but the basic mistake-bound online learning
set-up assumes that examples (or more generally losses in the regret
framework) can be given in an adversarial and adaptive manner. Thus, we need
to evaluate the learner’s performance with different benchmark than the error
$\text{err}_{D}(h)$ from the (offline) PAC setting.

In the mistake-bound model, examples and their labels can be given in an
adversarial fashion. The performance of the learner is evaluated with respect
to the number of mistakes it makes compared to the ground truth; we again
assume the _realizability_ of the learning problem, meaning that there is a
target concept $c\in\mathcal{C}$ such that $c(x_{t})=y_{t}$ for all $t$.
Crucially, the target concept need not be chosen a priori: the only
requirement is that, at every time $t$, there exists a concept
$c\in\mathcal{C}$ that is consistent on the past sequence of points
$(x_{1},y_{1}),\dots,(x_{t},y_{t})$. The goal of the learner is to learn the
target exactly.

We now formally define the mistake-bound model of online learning.

######  Definition 3.10 (Mistake Bound).

For a given hypothesis class $\mathcal{C}$ and instance space
$\mathcal{X}=\bigcup_{n}\mathcal{X}_{n}$, we say that an algorithm
$\mathcal{A}$ learns $\mathcal{C}$ with mistake bound $M$ if $\mathcal{A}$
makes at most $M$ mistakes on any sequence of samples consistent with a
concept $c\in\mathcal{C}$.

In the mistake bound model, we usually require that $M$ be polynomial in $n$
and size$(c)$. A good example where this holds is the online learning
algorithm for conjunctions, outlined in Algorithm 3, which is immediately
adapted from its PAC-learning counterpart. Indeed, Algorithm 1 only changes
its hypothesis whenever it sees a positive example $(x,1)$ such that $h(x)=0$,
and works through the sample sequentially.

Algorithm 3 PAC-learning algorithm for conjunctions, online version

$L\leftarrow\left\\{x_{1},\bar{x_{1}},\dots,x_{n},\bar{x_{n}}\right\\}$

$h(x)=\bigwedge_{l\in L}l$ $\triangleright$ $h=0$

for $t=1,2,\dots$ do

Receive $x_{t}$

Predict $h(x_{t})$

Receive true label $y_{t}$

if $h(x_{t})\neq y_{t}$ then $\triangleright$ Only happens if $y=1$

$L\leftarrow L\setminus\left\\{l\in L\;|\;l(x)=0\right\\}$

end if

end for

Unlike with conjunctions, the vast majority of PAC-learning algorithms cannot
be so straightforwardly tailored to online learning, resulting in a rich
literature on algorithms, benchmarks and guarantees specific to this setting.

One of the simplest general-purpose algorithms for online learning in the
realizable mistake-bound model is the halving algorithm, outlined in Algorithm
4.

Algorithm 4 Halving algorithm

A hypothesis class $\mathcal{H}$

for $t=1,2,\dots$ do

Receive example $x_{t}$

$V^{(b)}_{t}\leftarrow\left\\{h\in V_{t}\;|\;h(x_{t})=b\right\\}$

$\hat{y_{t}}=\arg\max_{b}\left|V_{t}^{(b)}\right|$ $\triangleright$ Predict
label acc. to a majority vote

Receive true label $y_{t}$

$V_{t+1}\leftarrow V^{(y_{t})}_{t}$

end for

At each time step, the learner predicts the label of a new point according to
the majority vote of the hypotheses consistent with the sequence of data seen
so far, which is denoted as $V_{t}$. It is easy to see that the halving
algorithm will make at most $\log\left|\mathcal{H}\right|$ mistakes: every
time the learner makes a mistake on $(x_{t},y_{t})$, at least half of the
hypotheses are not consistent with $(x_{t},y_{t})$, and are thus eliminated.
There are two significant disadvantages to this learning algorithm: (i) its
computational complexity, with a runtime $\Omega(\left|\mathcal{H}\right|)$,
as it requires iterating through the whole hypothesis class to get a majority
vote and (ii) it can only be used on _finite_ concept classes. Note that these
drawbacks can be addressed by instead drawing a hypothesis at random from the
version space, as argued in (Maass,, 1991). We will now address the second
drawback and turn our attention to potentially _infinite_ concept classes.

We have seen that, in PAC learning, the VC dimension of a concept class
characterizes its learnability, enabling learning guarantees for infinite
concept classes that have finite VC dimension. One may wonder whether there
exists an analogous complexity measure to the VC dimension when working in the
mistake-bound model. It turns out that such a measure exists in this setting:
the Littlestone dimension, defined and proved to characterize online
learnability in (Littlestone,, 1988). In order to define the Littlestone
dimension, we must first define Littlestone trees.

######  Definition 3.11 (Littlestone Tree).

A Littlestone tree for a hypothesis class $\mathcal{H}$ on $\mathcal{X}$ is a
complete binary tree $T$ of depth $d$ whose internal nodes are instances
$x\in\mathcal{X}$. Each edge is labeled with $0$ or $1$ and corresponds to the
potential labels of the parent node. Each path from the root to a leaf must be
consistent with some $h\in\mathcal{H}$, i.e. if $x_{1},\dots,x_{d}$ with
labelings $y_{1},\dots,y_{d}$ is a path in $T$, there must exist
$h\in\mathcal{H}$ such that $h(x_{i})=y_{i}$ for all $i$.

We are now ready to define the Littlestone dimension.

######  Definition 3.12 (Littlestone Dimension).

The Littlestone dimension of a hypothesis class $\mathcal{H}$, denoted
$\mathsf{Lit}(\mathcal{H})$, is the largest depth $d$ of a Littlestone tree
for $\mathcal{H}$. If no such $d$ exists then
$\mathsf{Lit}(\mathcal{H})=\infty$.

##### Relationship to other complexity measures.

Before showing that the Littlestone dimension characterizes online
learnability in this setting, we will study some of its properties. First, the
Littlestone dimension is an upper bound on the VC dimension. Indeed, it is
possible to convert any shattered set $X=\left\\{x_{1},\dots,x_{d}\right\\}$
of size $d$ into a Littlestone tree of depth $d$, where the nodes at depth $i$
are all $x_{i}$ and every path from the root to a leaf corresponds to a
dichotomy on $X$.

Moreover, from the definition of Littlestone trees, since each path from the
root to a leaf of a tree is achievable by a distinct function
$h\in\mathcal{H}$, the Littlestone dimension is bounded above by the logarithm
of the size of $\mathcal{H}$. We then have the following inequality for all
$\mathcal{H}$

$\mathsf{VC}(\mathcal{H})\leq\mathsf{Lit}(\mathcal{H})\leq\log(\left|\mathcal{H}\right|)\enspace.$
(2)

It can be shown that the gaps between the terms in Equation 2 can be
arbitrarily large. To show the gap between $\mathsf{VC}(\mathcal{H})$ and
$\mathsf{Lit}(\mathcal{H})$, consider the set
$\mathsf{THRESHOLDS}=\bigcup_{a\in\mathbb{R}}\mathbf{1}[x\geq a]$ of threshold
functions on $\mathbb{R}$. The VC dimension of $\mathsf{THRESHOLDS}$ is 1, as
a set of one point can be shattered, but a set of two points
$x_{1}<x_{2}\in\mathbb{R}$ cannot achieve the labelling $(1,0)$. However, its
Littlestone dimension is infinite: consider the interval $[0,1]$. At each
depth $i$ of the Littlestone tree, the set of nodes from left to right is
$\left\\{\frac{j+1}{2^{i}}\right\\}_{j=0}^{2^{i-1}}$, and the labelling of all
the left edges is $1$ and $0$ for right edges. For a given depth $i$, a path
$p$ from the root to node $x_{i,j}:=\frac{j+1}{2^{i}}$ for some
$j\in\left\\{0,1,\dots,2^{i-1}\right\\}$ (including $x_{i,j}$’s label) is thus
consistent with the threshold function $\mathbf{1}[x\geq x^{*}]$ where $x^{*}$
is the deepest node in $p$ (inclusive of $x_{i,j}$) that is positively
labelled. This infinite gap between the VC and Littlestone dimensions clearly
illustrates that online and offline (PAC) learnability are fundamentally
different from each other, as some concept classes are PAC learnable but not
online learnable. To show the other arbitrary large gap between
$\mathsf{Lit}(\mathcal{H})$ and $\log(\left|\mathcal{H}\right|)$, consider the
singletons on $\mathbb{R}$, i.e. the class of functions
$\bigcup_{a\in\mathbb{R}}\mathbf{1}[x=a]$. While the class is infinite, any
Littlestone tree, which must be complete, has depth 1, as each hypothesis in
the class labels a unique point (the target $a$) positively. Thus
$\mathsf{Lit}(\mathcal{H})=1$.

We now show that the Littlestone dimension lower bounds the number of mistakes
any online learning makes.

######  Theorem 3.13.

(Littlestone,, 1988) Any online learning algorithm for $\mathcal{C}$ has
mistake bound $M\geq\mathsf{Lit}(\mathcal{C})$.

###### Proof.

Let $\mathcal{A}$ be any online learning algorithm for $\mathcal{C}$. Let $T$
be a Littlestone tree of depth $\mathsf{Lit}(\mathcal{C})$ for $\mathcal{C}$.
Clearly, an adversary can force $\mathcal{A}$ to make
$\mathsf{Lit}(\mathcal{C})$ mistakes by sequentially and adaptively choosing a
path in $T$ in function of $\mathcal{A}$’s predictions. ∎

As previously suggested, the Littlestone dimension can also upper bound the
number of mistakes made by an online learning algorithm. This bound is
achieved for arbitrary concept classes with finite Littlestone dimension by
the Standard Optimal Algorithm from Littlestone, (1988), outlined in Algorithm
5.

Algorithm 5 Standard Optimal Algorithm from Littlestone, (1988)

A hypothesis class $\mathcal{\mathcal{C}}$

for $t=1,2,\dots$ do

Receive example $x_{t}$

$V^{(b)}_{t}\leftarrow\left\\{h\in V_{t}\;|\;h(x_{t})=b\right\\}$

$\hat{y_{t}}=\arg\max_{b}\mathsf{Lit}(V^{(b)}_{t})$

Receive true label $y_{t}$

$V_{t+1}\leftarrow V^{(y_{t})}_{t}$

end for

The SOA works in a similar fashion as the halving algorithm, only considering
at time $t$ the version space $V_{t}$ of hypotheses that are consistent with
the sequence of examples so far. However, instead of taking the majority vote,
the algorithm predicts the label $\hat{y_{t}}$ of a new point according to the
subclass (w.r.t. a label prediction $b\in\left\\{0,1\right\\}$) with larger
Littlestone dimension. The theorem below completes the proof that the
Littlestone dimension characterizes online learnability.

######  Theorem 3.14.

The Standard Optimal Algorithm from Littlestone, (1988) makes at most
$\mathsf{Lit}(\mathcal{C})$ mistakes in the mistake-bound model.

###### Proof.

We will show that, at every mistake, the Littlestone dimension of the subclass
$V_{t}$ decreases by at least 1 after receiving the true label $y_{t}$.

Suppose that, at time $t$, $y_{t}=\arg\min_{b}\mathsf{Lit}(V^{(b)}_{t})$. Note
that $V_{t+1}=V^{(y_{t})}_{t}$. Now, consider any two Littlestone trees
$T_{y_{t}}$ and $T_{\hat{y}_{t}}$ of maximal depths for $V^{(y_{t})}_{t}$ and
$V^{(\hat{y})}_{t}$, respectively. By definition, neither tree can contain
$x_{t}$, so it is possible to construct a Littlestone tree $T$ for $V_{t}$ of
depth $\min_{b}\mathsf{Lit}(V^{(b)}_{t})+1$ (recall that $T$ must be
complete). Then
$\mathsf{Lit}(V_{t})\geq\mathsf{Lit}(V^{({y_{t}})}_{t})+1=\mathsf{Lit}(V_{t+1})+1$,
as required.131313Note that the Littlestone dimension does not necessarily
decrease when $y_{t}=\hat{y}_{t}$, as we could have $V_{t}=V_{t}^{y_{y}}$. ∎

While the SOA has an optimal mistake bound and is defined for arbitrary
concept classes, it remains highly inefficient in general, as computing the
Littlestone dimension of the concept subclasses could be very costly. For the
remainder of this section, we will consider online learning algorithms for
specific concept classes in order to circumvent some of these issues.141414We
will discuss the algorithms and their mistake bounds here, but we refer the
reader to the references for the algorithms themselves and their analysis.

The first algorithm we will look at is Winnow, which is for linear threshold
functions with bounded weights in the boolean hypercube. This algorithm and
its analysis are due to Littlestone, (1988).

We now recall the mistake upper bound for Winnow in the special case of
$\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W+}$, where the weights are positive
integers.151515See https://www.cs.utexas.edu/~klivans/05f7.pdf for a full
derivation.

######  Theorem 3.15 (Winnow Mistake Bound).

The Winnow algorithm for learning the class
$\mathsf{LTF}_{\left\\{0,1\right\\}^{n}}^{W+}$ makes at most $O(W^{2}\log(n))$
mistakes.

We now look at the perceptron algorithm, which first appeared in Rosenblatt,
(1958), and whose first proofs of convergence were shown in Block, (1962) and
Novikoff, (1963).

While it is not possible to have a mistake bound for linear classifiers in
$\mathbb{R}^{n}$, as the Littlestone dimension is infinite, requiring a
_margin_ on the data ensures a finite mistake bound with the perceptron
algorithm, as stated below.

######  Theorem 3.16 (Mistake Bound for Perceptron, Margin Condition; Theorem
7.8 in Mohri et al., (2012)).

Let $\mathbf{x}_{1},\dots,\mathbf{x}_{T}\in\mathbb{R}^{n}$ be a sequence of
$T$ points with $\left\|\mathbf{x}_{t}\right\|\leq r$ for all $1\leq t\leq T$
for some $r>0$. Assume that there exists $\gamma>0$ and
$\mathbf{v}\in\mathbb{R}^{n}$ such that for all $1\leq t\leq T$,
$\gamma\leq\frac{y_{t}(\mathbf{v}\cdot\mathbf{x}_{t})}{\left\|\mathbf{v}\right\|}$.
Then, the number of updates made by the Perceptron algorithm when processing
$\mathbf{x}_{1},\dots,\mathbf{x}_{T}$ is bounded by $r^{2}/\gamma^{2}$.

####  6.5 Learning with Membership and Equivalence Queries

So far, we have studied models where the learner does not have any control
over the data it gets: in the PAC setting, labelled instances are received
i.i.d. from the random example oracle, and in the online setting, the new
points can be given adversarially. In this sense the learner is quite passive
during the learning process. We will now turn our attention towards learning
models where the learner is more active, and, in addition to receiving random
examples, can make queries to an oracle, also sometimes referred to as
teacher.

For simplicity, we will for now assume that there is no distribution
underlying the data. Hence, similarly to the mistake-bound model of online
learning, the goal is to learn the target concept _exactly_ on the instance
space. We will start by defining two different types of queries: membership
and equivalence queries.

######  Definition 3.17.

A _membership oracle_ $\mathsf{MQ}(c)$ defined for a concept $c\in\mathcal{C}$
returns the value $c(x)$ when queried with an instance $x\in\mathcal{X}$.

The terminology refers to the fact that $\mathcal{C}$ is a class of boolean
functions, which can be interpreted as a subsets of $\mathcal{X}$. Then, a
membership query returns whether an instance $x$ is in the target subset of
$\mathcal{X}$. In the case of real-valued functions, a _value oracle_ might be
a more appropriate term.

######  Definition 3.18.

An _equivalence query oracle_ $\mathsf{EQ}(c)$ defined for a target concept
$c\in\mathcal{C}$ takes as input a representation of a hypothesis $h$ and
returns whether or not $h$ agrees with $c$ on the input space $\mathcal{X}$.
If $h\neq c$ on $\mathcal{X}$, $\mathsf{EQ}(c)$ also returns an instance
$x\in\mathcal{X}$, called a _counterexample_ , such that $h(x)\neq c(x)$.

With these two types of queries, we will now present the exact learning model
for concept classes in this setting, where the goal is to learn a hypothesis
$h$ such that for all $x\in\mathcal{X}$, $h(x)=c(x)$. We formally define this
model below, where we will assume that the learning algorithm is
deterministic.

######  Definition 3.19.

A concept class $\mathcal{C}$ is _efficiently exactly learnable_ using
membership and equivalence queries if there exists a polynomially-evaluatable
hypothesis class $\mathcal{H}$, a learning algorithm $\mathcal{A}$ and a
polynomial $p(\cdot,\cdot)$ such that for all $n\geq 1$, $c\in\mathcal{C}$,
whenever $\mathcal{A}$ is given access to the $\mathsf{MQ}(c)$ and
$\mathsf{EQ}(c)$ oracles, it halts in time $p(n,\text{size}(c))$ and outputs
some $h\in\mathcal{H}_{n}$ such that $h(x)=c(x)$ for all instances
$x\in\mathcal{X}$. Furthermore, every query made to $\mathsf{EQ}(c)$ by
$\mathcal{A}$ must made with some $h\in\mathcal{H}_{n}$.

The exact learning model with access to $\mathsf{MQ}$ and $\mathsf{EQ}$ has a
long history, particularly in automata theory, where the seminal work of
Angluin, (1987) presented an exact learning algorithm, called $L^{*}$, to
exactly learn deterministic finite automata.

Before going further, a few remarks are in order. First, the efficiency in
this definition is with respect to the computational complexity of the
problem. This entails requiring statistical efficiency as well, in the sense
that the number of queries to the $\mathsf{MQ}$ and $\mathsf{EQ}$ oracles be
also polynomial in $n$ and size$(c)$.

Second, it may seem that having access to an equivalence oracle is an
impractical requirement. After all, while it makes sense to consider
membership oracles, as they can often be simulated by human “experts” (e.g.,
captioning done by internet users), it could perhaps be unrealistic to expect
humans or automated systems to simulate the equivalence oracle in practice.
However, the following result shows that, if the exact learning requirement
can be relaxed to PAC learning, i.e., allowing for accuracy and confidence
parameters, then one can simply work in the $\mathsf{EX}+\mathsf{MQ}$ learning
model, and forgo equivalence queries.

######  Theorem 3.20.

Let $\mathcal{C}$ be exactly efficiently learnable using membership and
equivalence queries. Then $\mathcal{C}$ is efficiently PAC-learnable using
random examples and membership queries.

The proof, omitted for brevity, relies on the fact that it is possible to
simulate (with sufficient accuracy) the $\mathsf{EQ}$ oracle with access to
random examples.

Third, we have assumed that the learning algorithm is deterministic. It would
be possible to accommodate randomized learning algorithms with the addition of
a confidence parameter $\delta$ as in PAC learning. In this case, the
probability of failure would not come from the randomness in sampling the
data, but rather from the fact that we are working with an algorithm with
internal randomization, which could result in computational gains.

Now, note that it is possible to efficiently exactly learn conjunctions in the
$\mathsf{MQ}+\mathsf{EQ}$ model (just by using the $\mathsf{EQ}$ oracle). We
simply need to use the online learning version of the algorithm (Algorithm 3)
and, instead of receiving an instance and predicting its label, the learner
gives the hypothesis $h$ to $\mathsf{EQ}(c)$ and receives a counterexample if
$h\neq c$. The number of calls to $\mathsf{EQ}$ is upper bounded by the
mistake bound (the reasoning is the same as in the online setting).

A more interesting class of functions to study is the class
$\mathsf{MONOTONE\text{-}DNF}$, i.e., functions of the form
$T_{1}\vee\dots\vee T_{r}$ where each $T_{i}$ is a monotone conjunction
$\bigwedge_{j\in S_{i}}x_{j}$. It is not known whether
$\mathsf{MONOTONE\text{-}DNF}$ is PAC learnable. However, it can be shown that
this class can be exactly learned in the $\mathsf{MQ}+\mathsf{EQ}$ model (and
thus is PAC learnable when the learner has additional access to $\mathsf{MQ}$
by Theorem 3.20).

We finish this section by formally introducing _local_ membership queries
(LMQ), which were mentioned in Chapter 2. They were introduced by Awasthi et
al., (2013) and shown to circumvent some impossibility results in the standard
PAC setting (or impossibility conjectures). Here, given a sample $S$ drawn
from the example oracle $\mathsf{EX}(c,D)$, a membership query for a point $x$
is $\lambda$-_local_ if there exists $x^{\prime}\in S$ such that $x\in
B_{\lambda}(x^{\prime})$, i.e., an algorithm can only query the label of
points within distance $\lambda$ of the training sample.

######  Definition 3.21 (PAC Learning with $\lambda$-$\mathsf{LMQ}$ ).

Let $\mathcal{X}$ be the instance space equipped with a metric $d$,
$\mathcal{C}$ a concept class over $\mathcal{X}$, and $\mathcal{D}$ a class of
distributions over $\mathcal{X}$. We say that $\mathcal{C}$ is $\rho$-robustly
learnable using $\lambda$-local membership queries with respect to
$\mathcal{D}$ if there exists a learning algorithm $\mathcal{A}$ such that for
every $\epsilon>0$, $\delta>0$, for every distribution $D\in\mathcal{D}$ and
every target concept $c\in\mathcal{C}$, the following hold:

  1. 1.

$\mathcal{A}$ draws a sample $S$ of size
$m=\text{poly}(n,1/\delta,1/\epsilon,\text{size}(c))$ using the example oracle
$\mathsf{EX}(c,D)$

  2. 2.

Each query $x^{\prime}$ made by $\mathcal{A}$ to the $\mathsf{LMQ}$ oracle is
$\lambda$-local with respect to some example $x\in S$

  3. 3.

$\mathcal{A}$ outputs a hypothesis $h$ that satisfies
$\text{err}_{D}(h,c)\leq\epsilon$ with probability at least $1-\delta$

  4. 4.

The running time of $\mathcal{A}$ (hence also the number of oracle accesses)
is polynomial in $n$, $1/\epsilon$, $1/\delta$, $\text{size}(c)$ and the
output hypothesis $h$ is polynomially evaluable.

We conclude this section by remarking that learnability in the above setting
is with respect to a family $\mathcal{D}$ of distributions, rather than the
distribution-free setting of PAC learning. This is because LMQs have mostly
been used in the literature for learning problems which require distributional
assumptions.

###  7 Probability Theory

In this section, we first present log-Lipschitz distributions, a family of
distributions that will be studied throughout the text. We then introduce
martingales, which are sequences of random variables satisfying certain
properties. They can be used to give concentration bounds for random variables
which are not necessarily independent, such as bits in instances from
$\left\\{0,1\right\\}^{n}$ sampled from log-Lipschitz distributions.

####  7.1 Log-Lipschitz Distributions

While it is natural to consider product distributions on the input space
$\left\\{0,1\right\\}^{n}$, such as the uniform distribution, independence
among the values of the bits of an input is seldom a reasonable assumption to
make in practice (e.g., two features may be correlated). By working with log-
Lipschitz distributions, we can still operate in a regime where some
distributional assumptions hold, but where the requirements are less stringent
than for product distributions. A distribution is log-Lipschitz if the
logarithm of the density function is $\log(\alpha)$-Lipschitz with respect to
the Hamming distance:

######  Definition 3.22.

A distribution $D$ on $\left\\{0,1\right\\}^{n}$ is said to be
$\alpha$-$\log$-Lipschitz if for all input points
$x,x^{\prime}\in\left\\{0,1\right\\}^{n}$, if $d_{H}(x,x^{\prime})=1$, then
$|\log(D(x))-\log(D(x^{\prime}))|\leq\log(\alpha)$.

The intuition behind $\log$-Lipschitz distributions is that points that are
close to each other must not have frequencies that greatly differ from each
other. From the definition, it is straightforward to see that if two points
$x,x^{\prime}$ differ only by one bit, then $D(x)/D(x^{\prime})\leq\alpha$.
Thus, neighbouring points in $\left\\{0,1\right\\}^{n}$ have probability
masses that differ by at most a multiplicative factor of $\alpha$. This
implies that the decay of probability mass along a chain of neighbouring
points is at most exponential. Not having sharp changes to the underlying
distribution is a very natural assumption, and weaker than many other
distributional assumptions in the literature. Again note that features are
allowed a small dependency between each other and, by construction, log-
Lipschitz distributions are supported on the whole input space. Log-Lipschitz
distributions have been studied in Awasthi et al., (2013), and their variants
in Feldman and Schulman, (2012); Koltun and Papadimitriou, (2007).

##### Examples of log-Lipschitz distributions.

The uniform distribution is $\log$-Lipschitz with parameter $\alpha=1$.
Another example of $\log$-Lipschitz distributions is the class of product
distributions where the probability of drawing a $0$ (or equivalently a $1$)
at index $i$ is in the interval
$\left[\frac{1}{1+\alpha},\frac{\alpha}{1+\alpha}\right]$. For an example
where some of the bits are not independent, let $\eta\in(1/2,1)$ and let the
input space be $\left\\{0,1\right\\}^{n}$ again. We first draw $x_{1}$
uniformly at random (u.a.r.), and then let $x_{2}$ be $x_{1}$ with probability
$\eta$ and $\bar{x_{1}}$ with probability $1-\eta$. The remaining bits are
drawn u.a.r. Then, this distributions is $\frac{\eta}{1-\eta}$-log-Lipschitz.

##### Properties.

Log-Lipschitz distributions have the following useful properties, which we
will often refer to in our proofs.

######  Lemma 3.23.

Let $D$ be an $\alpha$-$\log$-Lipschitz distribution over
$\left\\{0,1\right\\}^{n}$. Then the following hold:

  1. 1.

For $b\in\\{0,1\\}$, $\frac{1}{1+\alpha}\leq\underset{{x\sim
D}}{\Pr}\left(x_{i}=b\right)\leq\frac{\alpha}{1+\alpha}$.

  2. 2.

For any $S\subseteq[n]$, the marginal distribution $D_{\bar{S}}$ is
$\alpha$-$\log$-Lipschitz, where
$D_{\bar{S}}(y)=\sum_{y^{\prime}\in\\{0,1\\}^{S}}D(yy^{\prime})$.

  3. 3.

For any $S\subseteq[n]$ and for any property $\pi_{S}$ that only depends on
variables $x_{S}$, the marginal with respect to $\bar{S}$ of the conditional
distribution $(D|\pi_{S})_{\bar{S}}$ is $\alpha$-$\log$-Lipschitz.

  4. 4.

For any $S\subseteq[n]$ and $b_{S}\in\\{0,1\\}^{S}$, we have that
$\left(\frac{1}{1+\alpha}\right)^{|S|}\leq\underset{{x\sim
D}}{\Pr}\left(x_{i}=b\right)\leq\left(\frac{\alpha}{1+\alpha}\right)^{|S|}$.

###### Proof.

To prove (1), fix $i\in[n]$ and $b\in\\{0,1\\}$ and denote by $x^{\oplus i}$
the result of flipping the $i$-th bit of $x$. Note that

$\displaystyle\underset{{x\sim D}}{\Pr}\left(x_{i}=b\right)$
$\displaystyle=\sum_{\begin{subarray}{c}z\in\left\\{0,1\right\\}^{n}:\\\
z_{i}=b\end{subarray}}D(z)$
$\displaystyle=\sum_{\begin{subarray}{c}z\in\left\\{0,1\right\\}^{n}:\\\
z_{i}=b\end{subarray}}\frac{D(z)}{D(z^{\oplus i})}D(z^{\oplus i})$
$\displaystyle\leq\alpha\sum_{\begin{subarray}{c}z\in\left\\{0,1\right\\}^{n}:\\\
z_{i}=b\end{subarray}}D(z^{\oplus i})$ $\displaystyle=\alpha\underset{{x\sim
D}}{\Pr}\left(x_{i}\neq b\right)\enspace.$

The result follows from solving for $\underset{{x\sim
D}}{\Pr}\left(x_{i}=b\right)$.

Without loss of generality, let $\bar{S}=\\{1,\dots,k\\}$ for some $k\leq n$.
Let $x,x^{\prime}\in\\{0,1\\}^{\bar{S}}$ with $d_{H}(x,x^{\prime})=~{}1$.

To prove (2), let $D_{\bar{S}}$ be the marginal distribution. Then,

$D_{\bar{S}}(x)=\sum_{y\in\\{0,1\\}^{S}}D(xy)=\sum_{y\in\\{0,1\\}^{S}}\frac{D(xy)}{D(x^{\prime}y)}D(x^{\prime}y)\leq\alpha\sum_{y\in\\{0,1\\}^{S}}D(x^{\prime}y)=\alpha
D_{\bar{S}}(x^{\prime})\enspace.$

To prove (3), denote by $X_{\pi_{S}}$ the set of points in $\\{0,1\\}^{S}$
satisfying property $\pi_{S}$, and by $xX_{\pi_{S}}$ the set of inputs of the
form $xy$, where $y\in X_{\pi_{S}}$. By a slight abuse of notation, let
$D(X_{\pi_{S}})$ be the probability of drawing a point in
$\left\\{0,1\right\\}^{n}$ that satisfies $\pi_{S}$. Then,

$D(xX_{\pi_{S}})=\sum_{y\in X_{\pi_{S}}}D(xy)=\sum_{y\in
X_{\pi_{S}}}\frac{D(xy)}{D(x^{\prime}y)}D(x^{\prime}y)\leq\alpha\sum_{y\in
X_{\pi_{S}}}D(x^{\prime}y)=\alpha D(x^{\prime}X_{\pi_{S}})\enspace.$

We can use the above to show that

$(D|\pi_{S})_{\bar{S}}(x)=\frac{D(xX_{\pi_{S}})}{D(x^{\prime}X_{\pi_{S}})}\frac{D(x^{\prime}X_{\pi_{S}})}{D(X_{\pi_{S}})}\leq\alpha(D|\pi_{S})_{\bar{S}}(x^{\prime})\enspace.$

Finally, (4) is a corollary of (1)–(3).

∎

####  7.2 Concentration Bounds and Martingales

Let us start with some notation and probability theory basics. A random
variable $X$ on a sample space $\Omega$, which represents the set of all
possible outcomes, is a real-valued measurable function
$X:\Omega\rightarrow\mathbb{R}$. Turning our attention to discrete random
variables, the conditional probability of $X$ given a random variable $Y$ is
defined as

$\underset{{}}{\Pr}\left(X=x\;|\;Y=y\right)=\frac{\underset{{}}{\Pr}\left(X=x\wedge
Y=y\right)}{\underset{{}}{\Pr}\left(Y=y\right)}\enspace.$

We can now use this to define the conditional expectation as
$\underset{{}}{\mathbb{E}}\left[X\;|\;Y=y\right]=\sum_{x}\underset{{}}{\Pr}\left(X=x\;|\;Y=y\right)\enspace$,
where $\underset{{}}{\Pr}\left(Y=y\right)$ is assumed to be non-zero. While
these are defined for discrete random variables, they can be extended to
continuous random variables. Moreover, note that the conditional expectation
$\underset{{}}{\mathbb{E}}\left[X\;|\;Y\right]$ is itself a random variable.

##### Useful facts.

The law of total expectation, which in full generality states that
$\underset{{}}{\mathbb{E}}\left[X\right]=\underset{{}}{\mathbb{E}}\left[\underset{{}}{\mathbb{E}}\left[X\;|\;Y\right]\right]$,
can also be formulated as

$\underset{{}}{\mathbb{E}}\left[X\right]=\sum_{y}\underset{{}}{\Pr}\left(Y=y\right)\underset{{}}{\mathbb{E}}\left[X\;|\;Y=y\right]\enspace.$

Moreover, the linearity of expectation also holds under conditioning, i.e.,

$\underset{{}}{\mathbb{E}}\left[X+Z\;|\;Y\right]=\underset{{}}{\mathbb{E}}\left[X\;|\;Y\right]+\underset{{}}{\mathbb{E}}\left[Z\;|\;Y\right]\enspace.$

Concentration inequalities and tail bounds are key tools to provide guarantees
in machine learning. Among the most commonly used and well-known bounds are
the Hoeffding inequality and the Chernoff bound, stated below.

######  Theorem 3.24 (Hoeffding, (1963)).

Let $X_{1},\dots,X_{n}$ be $n$ independent random variables such that
$X_{i}:\Omega\rightarrow[0,1]$. Denote by
$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ their arithmetic mean and let
$\mu=\underset{{}}{\mathbb{E}}\left[\bar{X}\right]$. Then, for every $t\geq
0$,

$\underset{{}}{\Pr}\left(\left|\bar{X}-\mu\right|\geq t\right)\leq
2\exp\left(-2mt^{2}\right)\enspace.$ (3)

The Chernoff bound is the multiplicative form of Hoeffding’s inequality.

######  Theorem 3.25 (Chernoff, (1952)).

Let $X_{1},\dots,X_{n}$ be $n$ independent random variables such that
$X_{i}:\Omega\rightarrow\left\\{0,1\right\\}$. Denote their sum by
$\bar{X}=\sum_{i=1}^{n}X_{i}$ and let
$\mu=\underset{{}}{\mathbb{E}}\left[\bar{X}\right]$. Then, for every
$0\leq\delta\leq 1$,

$\displaystyle\underset{{}}{\Pr}\left(\bar{X}\leq(1-\delta)\mu\right)$
$\displaystyle\leq\exp\left(-\delta^{2}\mu/2\right)\enspace,$
$\displaystyle\underset{{}}{\Pr}\left(\bar{X}\geq(1+\delta)\mu\right)$
$\displaystyle\leq\exp\left(-\delta^{2}\mu/3\right)\enspace.$

Both results rely on the _independence_ of the random variables, which is not
always a reasonable assumption to make. Which tools are available to us when
independence cannot be guaranteed?

Martingales offer us the opportunity to weaken assumptions on the random
variables, which are allowed to depend on each other. To this end, we consider
a _sequence_ of random variables, where the value of a given random variable
is a function of the preceding ones. Additional requirements on their
expectation and conditional expectation are given in order to get meaningful
mathematical objects to study.

######  Definition 3.26.

A _martingale_ is a sequence of random variables $X_{0},X_{1},\dots$ of
bounded expectation, i.e.,
$\underset{{}}{\mathbb{E}}\left[\left|X_{i}\right|\right]<\infty$, for all
$i$, such that, for every $i\geq 0$,
$\underset{{}}{\mathbb{E}}\left[X_{i+1}\;|\;X_{0},\dots,X_{i}\right]=X_{i}$.
More generally, a sequence of random variables $Z_{0},Z_{1},\dots$ is a
martingale with respect to the sequence $X_{0},X_{1},\dots$ if for all $n\geq
0$

  1. (i)

$Z_{n}$ is a function of $X_{0},\dots,X_{n}$,

  2. (ii)

$\underset{{}}{\mathbb{E}}\left[\left|Z_{n}\right|\right]<\infty$,

  3. (iii)

$\underset{{}}{\mathbb{E}}\left[Z_{n+1}\;|\;X_{0},\dots,X_{n}\right]=Z_{n}$.

When $\underset{{}}{\mathbb{E}}\left[Z_{n+1}\;|\;X_{0},\dots,X_{n}\right]\leq
Z_{n}$ the sequence is a supermartingale, and when
$\underset{{}}{\mathbb{E}}\left[Z_{n+1}\;|\;X_{0},\dots,X_{n}\right]\geq
Z_{n}$, the sequence is a submartingale.

######  Example 3.27 (Gambler’s fortune.).

Suppose a gambler plays a sequence of fair games, meaning that
$\underset{{}}{\mathbb{E}}\left[X_{i}\;|\;X_{0},\dots,X_{i-1}\right]=0$, where
$X_{i}$ is the gains (or losses) incurred at every game $i$. We are interested
in the cumulative gains $Z_{n}=\sum_{i=0}^{n}X_{i}$, the gambler’s total gains
at the end of the $n$-th game. If
$\underset{{}}{\mathbb{E}}\left[\left|X_{i}\right|\right]<\infty$ for all
games $i$, then
$\underset{{}}{\mathbb{E}}\left[\left|Z_{n}\right|\right]<\infty$ as well.
Moreover,

$\underset{{}}{\mathbb{E}}\left[Z_{n+1}\;|\;X_{0},\dots,X_{n}\right]=\underset{{}}{\mathbb{E}}\left[X_{n+1}\;|\;X_{0},\dots,X_{n}\right]+\underset{{}}{\mathbb{E}}\left[Z_{n}\;|\;X_{0},\dots,X_{n}\right]=Z_{n}\enspace,$

together implying that the sequence $Z_{0},Z_{1},\dots$. is a martingale. Note
that the assumptions are quite permissive: the gambler’s strategy can fully
depend on the history of the previous games.

Now, when bounding the difference between two consecutive random variables,
one can obtain a powerful concentration bound, known as the Azuma-Hoeffding
inequality.

######  Theorem 3.28 (Azuma-Hoeffding Inequality).

Let $X_{0},\dots,X_{n}$ be (super)martingales such that
$\left|X_{i}-X_{i+1}\right|\leq c_{i}$. Then for any $\lambda>0$:

$\displaystyle\underset{{}}{\Pr}\left(X_{n}-X_{0}\geq\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right)\enspace,$
$\displaystyle\underset{{}}{\Pr}\left(X_{n}-X_{0}\leq-\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right)\enspace.$

Note that this inequality is similar in form to the Chernoff bounds, though
the gain in generality results in a weaker bound.

As previously mentioned, martingales and the Azuma-Hoeffding inequality will
be valuable when considering log-Lipschitz distributions, where the values of
the bits in an instance are not assumed to be independent.

###  8 Fourier Analysis

In this section, we introduce basic Fourier analysis concepts for boolean
functions, i.e., functions of the form
$f:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,1\right\\}$, which comprise a
large part of the functions studied in this thesis. As previously mentioned,
it is also possible to look at functions of the form
$f:\left\\{-1,1\right\\}^{n}\rightarrow\left\\{-1,1\right\\}$. In fact, this
is what we will do in this section as it eases analyses and notation. For
various reasons, the encoding
$\varphi:\left\\{0,1\right\\}\rightarrow\left\\{-1,1\right\\}$ satisfying
$\varphi(0)=1$ and $\varphi(1)=-1$ for both the input and output spaces is
usually preferred. In general, one can also consider real-valued functions
$f:\left\\{-1,1\right\\}^{n}\rightarrow\mathbb{R}$. The type of functions for
a given theorem will be featured in the theorem statements, unless it is clear
from the context. A thorough introduction to the Fourier analysis of boolean
functions, as well as the proofs omitted in this section, can be found in the
textbook by O’Donnell, (2014).

Fourier analysis relies on considering functions’ _Fourier expansion_ : their
representation as real multilinear polynomials. We start with some notation.