# Fast Rates for Bandit PAC Multiclass Classification

Liad Erez∗ Alon Cohen∗,† Tomer Koren∗,† Yishay Mansour∗,† Shay Moran†,‡

###### Abstract

We study multiclass PAC learning with bandit feedback, where inputs are
classified into one of $K$ possible labels and feedback is limited to whether
or not the predicted labels are correct. Our main contribution is in designing
a novel learning algorithm for the agnostic $(\varepsilon,\delta)$-PAC version
of the problem, with sample complexity of
$O\big{(}(\operatorname{poly}(K)+1/\varepsilon^{2})\log(\abs{\mathcal{H}}/\delta)\big{)}$
for any finite hypothesis class $\mathcal{H}$. In terms of the leading
dependence on $\varepsilon$, this improves upon existing bounds for the
problem, that are of the form $O(K/\varepsilon^{2})$. We also provide an
extension of this result to general classes and establish similar sample
complexity bounds in which $\log|\mathcal{H}|$ is replaced by the Natarajan
dimension. This matches the optimal rate in the full-information version of
the problem and resolves an open question studied by Daniely, Sabato, Ben-
David, and Shalev-Shwartz (2011) who demonstrated that the multiplicative
price of bandit feedback in realizable PAC learning is $\Theta(K)$. We
complement this by revealing a stark contrast with the agnostic case, where
the price of bandit feedback is only $O(1)$ as $\varepsilon\to 0$. Our
algorithm utilizes a stochastic optimization technique to minimize a log-
barrier potential based on Frank-Wolfe updates for computing a low-variance
exploration distribution over the hypotheses, and is made computationally
efficient provided access to an ERM oracle over $\mathcal{H}$.

**footnotetext:  Blavatnik School of Computer Science, Tel Aviv University,
Tel Aviv, Israel.††footnotetext:  Google Research Tel Aviv,
Israel.‡‡footnotetext: Departments of Mathematics and Computer Science,
Technion, Haifa, Israel.

##  1 Introduction

Multiclass classification is a fundamental learning problem in which a learner
is tasked with classifying objects into one of $K$ possible labels. In _bandit
multiclass classification_ (Kakade et al., 2008), upon making a prediction,
the learner does not observe the true label, but only whether or not the
prediction was correct. As a concrete example, consider a the task of
classifying images, say, from the ImageNet dataset, with the number of labels
$K$ being several thousands. After the learner predicts a label for a
particular image, both the image and the prediction are shown to a human rater
who is asked if the prediction is correct or not, after which the answer is
revealed to the learner. Thus, the learner faces a bandit multiclass
classification instance as the true label is not revealed in case the
prediction was deemed incorrect by the rater.

Much of previous work on the foundations of bandit multiclass classification
focused on the _online_ setting (Kakade et al., 2008; Daniely et al., 2011;
Daniely and Helbertal, 2013; Long, 2020; Raman et al., 2023; Erez et al.,
2024), where the goal of the learner is to minimize the _regret_ compared to a
given _hypothesis class $\mathcal{H}$_, namely, the learner’s total number of
correct predictions throughout the learning process compared to that of the
best fixed hypothesis from $\mathcal{H}$. A central line of work focused on
studying the properties of $\mathcal{H}$ that allow for sublinear regret in
this context, and on characterizing the achievable regret rates in terms of
$K$, $|\mathcal{H}|$ and the number of prediction rounds $T$. For instance,
Auer et al. (2002) show that for any finite $\mathcal{H}$ one can obtain a
regret bound of $O(\smash{\sqrt{KT\log|\mathcal{H}|}})$, by casting the
classification problem as a (contextual) $K$-armed bandit problem. Daniely and
Helbertal (2013) demonstrate that the dependence on $\log|\mathcal{H}|$ can be
replaced by the Littlestone dimension of $\mathcal{H}$, which may potentially
be smaller than $\log|\mathcal{H}|$ and, in particular, may be finite even
when $\mathcal{H}$ is infinite. Very recently, Erez et al. (2024) establish a
characterization of the optimal regret rates for finite hypothesis classes and
show that it is of the form
$\Theta\brk{\min\smash{\brk[c]{\sqrt{KT\log|\mathcal{H}|}},|\mathcal{H}|+\sqrt{T}}}$,
which is tight even when the labeled examples are drawn i.i.d. from a fixed
distribution.

Here we focus on a different, yet closely related version of multiclass
classification, viewed as a learning problem in a PAC framework (Valiant,
1984). In this setting, the labeled examples are drawn from a fixed unknown
distribution, and the learner’s goal is to ultimately output a prediction rule
which performs well, over this distribution, relative to the best hypothesis
from the underlying class $\mathcal{H}$. This problem has mainly been studied
in the analogous full-information setting, that is, when the learner as access
to a training set of i.i.d. examples along with their true labels, where the
number of samples required to learn an $\varepsilon$-optimal hypothesis was
shown to be $O((1/\varepsilon^{2})\log\brk{|\mathcal{H}|/\delta})$ for finite
classes (Natarajan, 1989; Ben-David et al., 1992; Daniely et al., 2011;
Brukhim et al., 2022). In the bandit case, however—namely where the learner
may repeatedly predict labels of drawn examples and obtain feedback only on
whether the prediction was correct or not—a comprehensive understanding of the
achievable sample complexity rates is still missing.

On the surface, the PAC bandit multiclass problem might be deemed trivial: a
straightforward approach of uniformly approximating the losses of all
hypotheses in $\mathcal{H}$ by drawing i.i.d. examples and predicting labels
uniformly at random, already gives rise to
$O((K/\varepsilon^{2})\log{|\mathcal{H}|})$ sample complexity which appears to
be optimal due to the bandit feedback. Furthermore, the simple underlying
algorithm can be implemented efficiently, provided that empirical risk
minimization (ERM) can be carried out efficiently over the hypothesis class.
However, this view regards multiclass classification as a generic $K$-armed
(contextual) bandit problem and neglects a crucial aspect of the setting: each
example has a single correct label, as opposed to a more general scenario
where each label may be associated with its own loss, independently of other
labels. And indeed, no non-trivial lower bounds can be found in the existing
literature for this problem.111We note that Daniely and Helbertal (2013) do
provide a stochastic lower bound construction, but it pertains to multi-label
multiclass rather to the standard single-label setting we consider here.

The following questions thus remain:

  1. (1)

_What is the optimal sample complexity of the bandit multiclass setting? In
particular, can one improve upon the prototypical $K/\varepsilon^{2}$ rate,
representative of bandit problems?_

  2. (2)

_Can this sample complexity be attained by an efficient (polynomial time)
algorithm, whenever ERM can be computed efficiently over the underlying
hypothesis class?_

In this work, we address the questions above and establish a nearly-tight
characterization of the achievable sample complexity in the bandit multiclass
problem, along with an efficient algorithm.

###  1.1 Summary of contributions

Our main contributions are summarized as follows.

  1. (i)

For a finite hypothesis class $\mathcal{H}$, we give an algorithm with sample
complexity of $O((\operatorname{poly}(K)+1/\varepsilon^{2})\log(|H|/\delta))$
for producing an $\varepsilon$-optimal classifier with probability at least
$1-\delta$; see Theorem 1 in Section 3. Further, our algorithm is a proper
learner and can be implemented efficiently provided a (weighted) ERM oracle
for the class $\mathcal{H}$. In terms of the leading dependence on
$\varepsilon$, this bound significantly improves over the previously mentioned
$O(K/\varepsilon^{2})$ bound, and matches the optimal rate in the full-
information version of the problem.

  2. (ii)

For more general, possibly infinite hypothesis classes $\mathcal{H}$ with
finite Natarajan dimension $d$, we establish a generalized sample complexity
bound of $O((\operatorname{poly}(K)+1/\varepsilon^{2})d\log(1/\delta))$; see
Theorem 2 in Section 4. This improves over the previous
$\smash{\widetilde{O}}(\ifrac{Kd}{\varepsilon^{2}})$ bound due to Daniely,
Sabato, Ben-David, and Shalev-Shwartz (2011), and matches the known rate in
the full-information case (Natarajan, 1989) up to logarithmic factors for
sufficiently small $\varepsilon$.

These results bear some interesting consequences. First, and perhaps most
surprisingly, they imply that there is _no additional price for bandit
feedback_ in PAC multiclass classification, as $\varepsilon\to 0$; namely,
that the ratio between the optimal sample complexity rates in the bandit and
the full-information settings is $\Theta(1)$, and not $\Theta(K)$ as one might
expect. Indeed, the latter is often the multiplicative price of bandit
information in a multitude of scenarios (see, e.g., Lattimore and Szepesvári,
2020), and further, it is the tight price in the realizable case of bandit
multiclass (Daniely et al., 2011). This phenomenon occurs already in the case
of a finite hypothesis class, and extends naturally to general Natarajan
classes.

Second, the results reveal an unexpected gap between the attainable bounds in
the online (i.e., regret minimization) and the PAC settings of the bandit
multiclass problem. A recognized trademark of online learning is that online-
to-batch conversions of regret bounds very often give sharp sample complexity
rates in the i.i.d. PAC setting (see e.g., Cesa-Bianchi and Lugosi, 2006;
Bubeck et al., 2012; Hazan et al., 2016). In bandit multiclass classification,
however, we exhibit a stark separation between the two settings, where for
sufficiently large hypothesis classes an online-to-batch conversion of the
optimal regret rate results with sample complexity
$\smash{\widetilde{\Theta}}(K/\varepsilon^{2})$ (Erez et al., 2024), whereas
the rate we establish here is
$\smash{\widetilde{O}}(1/\varepsilon^{2}+\operatorname{poly}(K))$.222A similar
separation has been observed before, e.g., in the context of general
online/stochastic convex optimization (Shamir, 2013).

The core novelty in our algorithmic approach is a stochastic optimization
technique for efficiently recovering a low-variance exploration distribution
over the hypotheses in $\mathcal{H}$, with variance $O(1)$ rather than the
$O(K)$ obtained by simple uniform exploration of labels. We show that through
minimization of a stochastic objective akin to a log-barrier (convex)
potential over the induced label probabilities, such a distribution can be
computed in a sample-efficient way and in turn be used to uniformly estimate
the losses of all hypotheses in $\mathcal{H}$ via importance sampling.
Moreover, we demonstrate how this stochastic optimization problem can be
solved efficiently using a stochastic Frank-Wolfe method. More details about
the algorithmic ideas and an overview of the analysis are given in Section 3.

###  1.2 Additional related work

#### Bandit multiclass classification.

In agnostic online multiclass classification with bandit feedback, regret
bounds of the form $O(\sqrt{KT\log|\mathcal{H}|})$ can be obtained by viewing
the problem as an instance of contextual multi-armed bandits (Auer et al.,
2002); this bound has been recently improved by Erez et al. (2024) to
$\Theta\brk{\min\smash{\brk[c]{\sqrt{KT\log|\mathcal{H}|},|\mathcal{H}|+\sqrt{T}}}}$
for the classification setting. Daniely and Helbertal (2013) show how to
replace the $\log|\mathcal{H}|$ dependence in the first bound by the
Littlestone dimension of $\mathcal{H}$, and (Raman et al., 2023) show how $K$
can be replaced with a refined quantity which encapsulates the effective
number of labels. Additional refinements in the realizable setting include the
_Bandit Littlestone dimension_ which provides a characterization of the
optimal mistake bound for deterministic learning algorithms (Daniely et al.,
2011).

#### Contextual bandits.

The PAC objective of the bandit multiclass classification problem can be seen
as a special case of the problem of identifying an approximately optimal
policy in contextual multi-armed bandits. In the more general contextual
bandit framework, sample complexity lower bounds of
$\widetilde{\Omega}\brk{K/\varepsilon^{2}}$ are known (Auer et al., 2002),
with regret upper bounds of the form $\widetilde{O}(\sqrt{KT})$ obtained in
several previous works (Auer et al., 2002; Dudik et al., 2011; Agarwal et al.,
2014). Reducing our problem to contextual bandits, however, ignores the
special structure exhibited by the reward function in the classification
setting, namely their sparsity (see Erez et al. (2024) for a more detailed
comparison), and indeed we establish improved sample complexity rates in this
special case. In a bit more detail, in the works of Dudik et al. (2011);
Agarwal et al. (2014), one of the main technical ideas is to compute a
distribution over policies which induces a reward estimator whose variance is
bounded, uniformly over the policies, by $O(K)$ (it is actually nontrivial to
show that such a distribution even exists). Our approach involves similar
ideas in the sense that we also aim to compute such a low-variance exploration
distribution over the hypotheses, but the crucial difference is that in the
classification setting, the sparse nature of the rewards allows us to
uniformly bound the variance by $O(1)$ rather than $O(K)$.

##  2 Problem Setup

#### Bandit multiclass classification.

We consider a learning setting in which a learner is tasked with classifying
objects from a set of examples $\mathcal{X}$ with a single label from a set of
$K$ possible labels $\mathcal{Y}=\brk[c]*{1,\ldots,K}$. A stochastic
multiclass classification instance is specified by a hypothesis class
$\mathcal{H}\subseteq\brk[c]*{\mathcal{X}\to\mathcal{Y}}$ and a joint
distribution $\mathcal{D}$ over example-label pairs over
$\mathcal{X}\times\mathcal{Y}$. We focus on finite hypothesis classes and
denote $N\triangleq\abs{\mathcal{H}}$. In the bandit setup, the learner
interacts with the environment in an iterative manner according to the
following protocol, over $i=1,2,\ldots$:

  1. (i)

The environment generates a pair $(x_{i},y_{i})\sim\mathcal{D}$ and the
example $x_{i}$ is revealed to the learner;

  2. (ii)

The learner predicts a label $\widehat{y}_{i}\in\mathcal{Y}$;

  3. (iii)

The learner observes whether or not the classification of $x_{i}$ is correct,
namely $\mathds{1}\\{\widehat{y}_{i}=y_{i}\\}$.333Note that in the bandit
setting, the learner does _not_ observe the true label $y_{i}$ directly.

#### Agnostic PAC model.

In the PAC version of the problem, given parameters $\varepsilon,\delta>0$ the
goal of the learner is to produce a hypothesis
$\hat{h}:\mathcal{X}\to\mathcal{Y}$,444In this model we allow for _improper_
learners, that is, the output hypothesis may not be a member of $\mathcal{H}$;
we emphasize, however, that our main algorithm below is a _proper_ learner,
namely it returns a hypothesis $\hat{h}\in\mathcal{H}$. such that with
probability at least $1-\delta$ (over the randomness of the environment as
well as any internal randomization of the algorithm):

$\displaystyle
L_{\mathcal{D}}(\hat{h})-L_{\mathcal{D}}(h^{\star})\leq\varepsilon,$

where here $L_{\mathcal{D}}(h)\triangleq\Pr[h(x)\neq y]$ is the expected zero-
one loss of $h$ with respect to $(x,y)\sim\mathcal{D}$, and
$h^{\star}\triangleq\operatorname*{argmin}_{h\in\mathcal{H}}L_{\mathcal{D}}(h)$
is the best hypothesis in $\mathcal{H}$. That is, the learner needs to
identify a hypothesis which is $\varepsilon$-optimal in $\mathcal{H}$ with
respect to the expected zero-one loss, with probability at least $1-\delta$.
In this model, the learner’s performance is measured in terms of _sample
complexity_ , which is the number of interaction rounds with the environment
as a function of $\varepsilon,\delta$ required for satisfying the guarantee
stated above.

#### Weighted ERM oracle.

For our computational results, we will assume a weighted empirical risk
minimization (ERM) oracle access to the hypothesis class $\mathcal{H}$. In
more detail, we assume access to an oracle, denoted
$\mathcal{O}_{\mathcal{H}}$, defined as follows: given a sequence of examples,
labels and weights
$(x_{1},y_{1},\alpha_{1}),\ldots,(x_{t},y_{t},\alpha_{t})\in\mathcal{X}\times\mathcal{Y}\times\mathbb{R}$
as input, the oracle $\mathcal{O}_{\mathcal{H}}$ returns

$\displaystyle\operatorname*{argmin}_{h\in\mathcal{H}}\sum_{s=1}^{t}\alpha_{s}\mathds{1}\\{h(x_{s})\neq
y_{s}\\}.$ (1)

We remark that this is a version of the argmin oracle often considered in the
more general contextual bandit setting (e.g., Dudik et al., 2011; Agarwal et
al., 2014), specialized for the classification setting we focus on here. For
our runtime results, we will assume that each call to
$\mathcal{O}_{\mathcal{H}}$ takes $O(1)$ time.

#### Additional notation.

We denote by
$\Delta_{N}\triangleq\brk[c]!{P\in\mathbb{R}^{N}_{+}\mid\sum_{i=1}^{N}P_{i}=1}$
the $N$-dimensional _simplex_ which corresponds to the set of all probability
distributions over $\mathcal{H}$. Given $P\in\Delta_{N}$ and $h\in\mathcal{H}$
we use the notation $P(h)$ to denote the probability assigned to $h$ by the
probability vector $P$. Given an example-label pair
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ we define the binary vector
$r_{x,y}\in\brk[c]*{0,1}^{N}$ by

$\displaystyle r_{x,y}(h)\triangleq\mathds{1}\\{h(x)=y\\}\quad\forall
h\in\mathcal{H},$

that is, $r_{x,y}(h)$ is the zero-one reward of the hypothesis $h$ on the pair
$(x,y)$. Given $P\in\Delta_{N}$ and $(x,y)\in\mathcal{X}\times\mathcal{Y}$ we
denote the probability of predicting the label $y$ for $x$ when sampling a
hypothesis from $P$ by

$\displaystyle
W_{x,y}(P)\triangleq\sum_{h=\mathcal{H}}P(h)\mathds{1}\\{h(x)=y\\}=P\cdot
r_{x,y},$

and for $\gamma\in(0,1)$ we let
$W^{\gamma}_{x,y}(P)\triangleq(1-\gamma)W_{x,y}(P)+\gamma/K$, which
corresponds to mixing the distribution $W_{x,y}(P)$ with a uniform
distribution over labels with weight factor $\gamma$.

##  3 Algorithm and Analysis

In this section we present and analyze our main contribution: an efficient
bandit multiclass classification algorithm, detailed in Algorithm 1, which
will be shown to satisfy the following agnostic PAC guarantee.

######  Theorem 1.

If we set $\gamma=\frac{1}{2}$, $M_{1}=\Theta(K^{8}\log\brk{N/\delta})$,
$M_{2}=\Theta\brk*{\log\brk{N/\delta}\brk*{K/\varepsilon+1/\varepsilon^{2}}}$
and use Algorithm 2 to solve the optimization problem defined in Eq. 2 for
$T=\Theta\brk{(K^{4}/\gamma^{4})\sqrt{\log(N/\delta)}}$ rounds with step sizes
$\eta_{t}=1/t$ and batch sizes $b_{t}=(\gamma/2K)^{2}t^{2}$ for
$t\in\set{2^{k}-1}_{k\geq 1}$ and $b_{t}=t$ otherwise; then with probability
at least $1-\delta$ Algorithm 1 outputs $\hat{h}\in\mathcal{H}$ with
$L_{\mathcal{D}}(\hat{h})-L_{\mathcal{D}}(h^{\star})\leq\varepsilon,$ using a
total sample complexity of

$O\brk*{\brk*{K^{9}+\frac{1}{\varepsilon^{2}}}\log\frac{N}{\delta}}.$

Furthermore, Algorithm 1 makes a total number of
$O\brk!{K^{4}\sqrt{\log(N/\delta)}}$ calls to the weighted ERM oracle
$\mathcal{O}_{\mathcal{H}}$, and runs in total time polynomial in $K$,
$1/\varepsilon$ and $\log(N/\delta)$.

Algorithm 1 Bandit PAC Multiclass Classification via Log Barrier Stochastic
Optimization

Parameters: $M_{1},M_{2},\gamma\in(0,\frac{1}{2}]$.

Phase 1:

Initialize $S\leftarrow\emptyset$.

while $\abs{S}<M_{1}$ do

Environment generates $(x,y)\sim\mathcal{D}$, algorithm receives $x$.

Predict $\hat{y}$ uniformly at random from $\mathcal{Y}$ and receive feedback
$\mathds{1}\\{\hat{y}=y\\}$.

Update $S\leftarrow S\cup\brk[c]*{(x,y)}$ if $y=\hat{y}$, otherwise $S$ is
unchanged.

end while

Solve the stochastic optimization problem defined in Eq. 2 up to an additive
error of $\mu=\gamma^{2}/2K^{2}$ using the dataset $S$. Let
$\hat{P}\in\Delta_{N}$ be its output.

Phase 2:

for $i=1,\ldots,M_{2}$ do

Environment generates $(x_{i},y_{i})\sim\mathcal{D}$, algorithm receives
$x_{i}$.

With prob. $\gamma$, pick $\hat{y}_{i}\in\mathcal{Y}$ uniformly at random;
otherwise sample $h_{i}\sim\hat{P}$ and set $\hat{y}_{i}=h_{i}(x_{i})$.

Predict $\hat{y}_{i}$ and receive feedback
$\mathds{1}\\{\hat{y}_{i}=y_{i}\\}$.

end for

Return:
$\hat{h}=\mathcal{O}_{\mathcal{H}}\brk*{\brk[c]*{\brk*{x_{i},\hat{y}_{i},\alpha_{i}}}_{i=1}^{M_{2}}},$
where
$\alpha_{i}=\mathds{1}\\{y_{i}=\hat{y}_{i}\\}/W^{\gamma}_{\hat{P}}(x_{i},\hat{y}_{i}).$

Algorithm 1 operates in two phases. In the first phase, we construct a dataset
$S$ of $M_{1}=\operatorname{poly}(K)\log\brk*{N/\delta}$ i.i.d. samples from
$\mathcal{D}$ by predicting labels uniformly at random and taking into $S$ the
samples for which the correct label is predicted (and is thus known). We then
feed these samples to a stochastic optimization scheme which finds an
approximate solution to the following stochastic optimization problem:

$\displaystyle\min\quad$
$\displaystyle\Phi(P)\triangleq\boldsymbol{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\brk[s]*{\phi(P;x,y)},\quad\text{where}\quad\phi(P;x,y)\triangleq-\log\brk*{W^{\gamma}_{x,y}(P)}$
(2) s.t. $\displaystyle P\in\Delta_{N}.$

The approximate solution, $\hat{P}\in\Delta_{N}$ will be shown to satisfy
certain low-variance properties, which will allow us to repeatedly sample from
$\hat{P}$ for
$M_{2}=O\brk*{\brk*{K/\varepsilon+1/\varepsilon^{2}}\log\brk*{N/\delta}}$
rounds and estimate the loss of hypotheses in $\mathcal{H}$ such that we are
guaranteed to find an approximately optimal policy with high probability. We
again emphasize that our algorithm is a proper learner in the sense that the
returned hypothesis $\hat{h}$ is a member of the underlying class
$\mathcal{H}$.

###  3.1 Overview of algorithmic ideas

We next outline the details and intuition leading to Algorithm 1.

#### Low-variance exploration distribution.

The main goal of the first phase of Algorithm 1 is to compute an exploration
distribution $\hat{P}\in\Delta_{N}$ with the property that with probability at
least $1-\delta/2$, the following holds:

$\displaystyle\forall
h\in\mathcal{H}:\qquad\boldsymbol{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}}\leq
C,$ (3)

where $\gamma$ is some predefined parameter and $C$ is an absolute constant,
which crucially does not depend on $K$. The intuition behind this property is
that the quantity of the left-hand side of Eq. 3 constitutes an upper bound on
the variance of the random variable

$\frac{J_{x,y}(h)\mathds{1}\\{y=\hat{y}\\}}{W^{\gamma}_{x,y}(\hat{P})},$

which is an unbiased estimator of the expected reward of the hypothesis $h$,
that is, of $\mathds{1}\\{h(x)=y\\}$ if the label $\hat{y}$ is chosen
according to an hypothesis drawn from $\hat{P}$ and $(x,y)$ is drawn from
$\mathcal{D}$. Thus, we think of Eq. 3 as a property which guarantees that the
exploration distribution $\hat{P}$ can be used to estimate rewards,
_uniformly_ for all hypotheses in $\mathcal{H}$, with low (constant) variance.
This is reminiscent of a technique of Dudik et al. (2011); Agarwal et al.
(2014), who consider the more general stochastic contextual bandit problem,
and rely on computing a distribution over policies which induces a reward
estimator whose variance is bounded by $O(K)$. The low-variance estimator
allows us to make use of variance-sensitive concentration bounds, namely
Bernstein’s inequality, in order to accurately approximate the optimal policy
using a small number of samples (this is done in the second phase of the
algorithm, described below).

#### Controlling variance via stochastic optimization.

In some more detail, our approach for computing such a low-variance
exploration distribution $\hat{P}$ is via approximately solving the stochastic
convex optimization problem defined in Eq. 2. The reason for the choice of
$\Phi$ as a convex potential to be minimized is the fact that its gradient is,
up to a constant factor, given by

$\displaystyle\forall
h\in\mathcal{H}:\qquad(\nabla\Phi(P))_{h}\approx\boldsymbol{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P)}},$
(4)

so that finding a low-variance exploration distribution amounts to computing
$\hat{P}\in\Delta_{N}$ for which $\nabla\Phi(\hat{P})$ is bounded in
$L_{\infty}$ norm. Indeed, we show that the optimal solution to the
optimization problem given in Eq. 2 satisfies such a property. This, together
with the properties of $\Phi$ as a self-concordant function allows finding
such $\hat{P}$ by approximately minimizing $\Phi$ over the simplex: the self-
concordance of $\Phi$ acts as a “restricted strong convexity” property, which
roughly implies that approximate minimizers of $\Phi$ must also have small
(low norm) gradients.

#### Efficient optimization via Stochastic Frank-Wolfe.

In order to compute an approximate minimizer of the convex potential $\Phi$
defined in Eq. 2, we employ a stochastic optimization procedure, formally
described in Algorithm 2, which is based on a stochastic version of the Frank-
Wolfe (FW) algorithm (Frank et al., 1956) with SPIDER gradient estimates (Fang
et al., 2018). The reason for choosing a FW based approach, is that it allows
for efficient optimization of $\Phi$ in $N$-dimensional space, with runtime
essentially independent of $N$, by exploiting the weighted ERM oracle at our
disposal. Furthermore, the FW algorithm, when performed over the simplex,
generates iterates $P_{1},P_{2},\ldots$ such that $P_{t}$ is supported on at
most $t$ coordinates (provided that $P_{1}$ is initialized at an arbitrary
vertex of the simplex), allowing us to maintain a succinct representation of
the FW iterates—again, essentially independently of the ambient dimension $N$.
Additionally, we remark that while existing analyses (e.g. Yurtsever et al.
(2019b)) of the stochastic FW algorithm rely on smoothness of the objective
with respect to the $L_{2}$-norm, our objective of interest, namely $\Phi$, is
not smooth in this classical sense, however it is smooth with respect to the
$L_{1}$ norm. Therefore, we crucially rely on a different analysis of the FW
algorithm with SPIDER gradient estimates, presented in Appendix C, which
accommodates smoothness with respect to the $L_{1}$ norm.

#### Final exploration phase.

The second phase of Algorithm 1 is more straightforward, where we repeatedly
predict labels using i.i.d. samples from a distribution which mixes the
distribution over labels induced by $\hat{P}$ (the exploration distribution
computed in phase 1) with a uniform distribution over $\mathcal{Y}$. Using
Bernstein’s inequality and the uniform low-variance property of $\hat{P}$, we
show that
$M_{2}=O\brk*{\brk*{K/\varepsilon+1/\varepsilon^{2}}\log\brk*{N/\delta}}$
samples suffice in order to ultimately output an hypothesis
$\hat{h}\in\mathcal{H}$ being $\varepsilon$-optimal with probability at least
$1-\delta/2$. With this in hand, the desired PAC guarantee follows by a union
bound over the failure probabilities of the two phases of the algorithm.

###  3.2 Stochastic Optimization via SPIDER Frank-Wolfe

Next, we present the stochastic FW procedure used in our algorithm as
subprocedure; see Algorithm 2. It is essentially the SPIDER FW algorithm of
Yurtsever et al. (2019b), specialized for solving the stochastic optimization
problem defined in Eq. 2. We remark that the algorithm makes calls to a linear
optimization oracle over the simplex denoted by LOO, that given an input
$g\in\mathbb{R}^{N}$ computes
$\textsf{LOO}(g)=\operatorname*{argmin}_{Q\in\Delta_{N}}Q\cdot g$. As we will
show later, each of the calls Algorithm 2 makes to LOO can be implemented by a
call to the weighted ERM oracle. We also remark that, as discussed before,
existing analyses of the stochastic FW procedure with SPIDER gradient
estimates relies on $L_{2}$ smoothness of the objective (Yurtsever et al.,
2019b), and here we provide an analysis with respect to $L_{1}$ smoothness
being crucial in our case. We defer further details about SPIDER FW and its
analysis to Appendix C.

Algorithm 2 Stochastic Frank-Wolfe with SPIDER gradient estimates

Parameters: Dataset $S\subseteq\mathcal{X}\times\mathcal{Y}$, step sizes
$\brk[c]*{\eta_{t}}_{t}$, batch sizes $\set{b_{t}}_{t}$.

Initialize $P_{1}\in\Delta_{N}$ and initial gradient estimate $g_{1}=0$.

Let $\tau_{k}=2^{k}-1$ for $k=1,2,\ldots$.

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

Draw $b_{t}$ fresh samples $(x_{1},y_{1}),\ldots,(x_{b_{t}},y_{b_{t}})$ from
$S$;

if $t\in\brk[c]*{\tau_{k}}_{k\geq 1}$ then

Set  $g_{t}=\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\nabla\phi(P_{t};x_{i},y_{i});$

else

Set
$g_{t}=g_{t-1}+\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}(\nabla\phi(P_{t};x_{i},y_{i})-\nabla\phi(P_{t-1};x_{i},y_{i}));$

end if

Compute $Q_{t}=\textsf{LOO}(g_{t})$;

Update $P_{t+1}=(1-\eta_{t})P_{t}+\eta_{t}Q_{t}$;

end for

###  3.3 Proof of Theorem 1

We now turn to formally prove Theorem 1. For clarity of notation, we
henceforth use $\boldsymbol{\mathbb{E}}[\cdot]$ instead of
$\boldsymbol{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[\cdot]$ to denote an
expectation of a random variable with respect to $\mathcal{D}$. We begin this
section by analyzing the first phase of Algorithm 1. The following lemma,
which is proven in Appendix A, characterizes the optimal solution to the
stochastic optimization problem defined in Eq. 2, and shows that the gradient
of $\Phi$ at that optimum is bounded by a constant in $L_{\infty}$ norm.

######  Lemma 1.

Suppose $\gamma\leq\tfrac{1}{2}$ and let
$P_{\star}\in\operatorname*{argmin}_{P\in\Delta_{N}}\Phi(P)$, where
$\Phi:\Delta_{N}\to\mathbb{R}_{+}$ was defined in Eq. 2. Then for any
$P\in\Delta_{N}$ we have

$\mathbb{E}\brk[s]3{\frac{W^{\gamma}_{x,y}(P)}{W^{\gamma}_{x,y}(P_{\star})}}\leq
1.$ (5)

In particular, letting $P$ be the delta distribution on some
$h\in\mathcal{H}$:

$\mathbb{E}\brk[s]3{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P_{\star})}}\leq 2.$

The next key lemma, whose proof is also in Appendix A ensures that a
sufficiently approximate minimizer of $\Phi$ is also a point in which the
gradient $\Phi$ is bounded in $L_{\infty}$-norm, establishing the property
given in Eq. 3.

######  Lemma 2.

Suppose $\gamma\leq\frac{1}{2}$ and assume that for all
$P_{\star}\in\Delta_{N}$ the following holds for $\hat{P}$ which was computed
in phase 1 of Algorithm 1:

$\displaystyle\Phi(\hat{P})-\Phi(P_{\star})\leq\mu.$

Then,

$\displaystyle\norm{\nabla\Phi(\hat{P})}_{\infty}\leq 2+\sqrt{\frac{2\mu
K^{2}}{\gamma^{2}}}.$

In particular, setting $\mu=\gamma^{2}/2K^{2}$ gives
$\norm{\nabla\Phi(\hat{P})}_{\infty}\leq 3$.

The fact that the property given in Eq. 3 can be guaranteed with high
probability using as few as
$M_{1}=\Theta\brk*{\operatorname{poly}(K)\log\brk*{N/\delta}}$ samples relies
on the following lemma, also proven in Appendix A, which follows from the
analysis of the stochastic Frank-Wolfe procedure (see Appendix C for the
detailed analysis).

######  Lemma 3.

Suppose $\gamma\leq\frac{1}{2}$. If
$M_{1}=58000\brk*{K^{8}/\gamma^{8}}\log\brk*{16N/\delta}$ and
$T=240\brk*{K^{4}/\gamma^{4}}\sqrt{\log\brk*{16N/\delta}}$, then with
probability at least $1-\delta/2$, for all $P_{\star}\in\Delta_{N}$ it holds
that

$\displaystyle\Phi(\hat{P})-\Phi(P_{\star})\leq\frac{\gamma^{2}}{2K^{2}}.$

We are now in position to prove Theorem 1 by analyzing the second phase of
Algorithm 1. We make use of the guarantee of the first phase given in Lemma 2
with respect to the exploration distribution $\hat{P}$, which allows us to use
Bernstein’s concentration inequality in order to compute an
$\varepsilon$-optimal hypothesis in high probability using only $\approx
K/\varepsilon+1/\varepsilon^{2}$ samples.

###### Proof of Theorem 1.

We first show that we can in fact use Algorithm 2 as specified in the
theorem’s statement. That is, we prove that the calls to the linear
optimization oracle, denoted by LOO in Algorithm 2 can be implemented using
the weighted ERM oracle $\mathcal{O}_{\mathcal{H}}$. Indeed, we first note
that for any $g\in\mathbb{R}^{N}$ it holds that

$\displaystyle\textsf{LOO}(g)=\operatorname*{argmin}_{P\in\Delta_{N}}\brk[c]*{P\cdot
g}=\operatorname*{argmin}_{h\in\mathcal{H}}\brk[c]*{g_{h}},$

so it suffices to show that this can be represented in the form given in Eq. 1
for the SPIDER gradient estimates used in Algorithm 2, which we denote by
$g_{t}$. It is straightforward to see each $g_{t}$ is a linear combination of
terms of the form $\nabla\phi(P,x,y)$ where $P$ is either $P_{t}$ or
$P_{t-1}$. Thus, we show that for
$g=\frac{1}{n}\sum_{i=1}^{n}\nabla\phi(P_{t},x_{i},y_{i})$, $\textsf{LOO}(g)$
can be computed by a call to the weighted ERM oracle. Indeed,

$\displaystyle\textsf{LOO}(g)=\operatorname*{argmin}_{h\in\mathcal{H}}\brk[c]*{-(1-\gamma)\frac{1}{n}\sum_{i=1}^{n}\frac{\mathds{1}\\{h(x_{i})=y_{i}\\}}{W^{\gamma}_{x_{i},y_{i}}(P_{t})}}=\operatorname*{argmin}_{h\in\mathcal{H}}\sum_{i=1}^{n}\alpha_{i}\mathds{1}\\{h(x_{i})\neq
y_{i}\\},$

where $\alpha_{i}=(1-\gamma)/nW^{\gamma}_{x_{i},y_{i}}(P_{t})$. Now, assume
that after phase 1, Algorithm 1 computed $\hat{P}\in\Delta_{N}$ with

$\displaystyle\max_{h\in\mathcal{H}}\boldsymbol{\mathbb{E}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}}\leq
3.$

Fix some $h\in\mathcal{H}$. For $i\in\brk[c]*{1,\ldots,M_{2}}$ define
$X_{i}(h)=\frac{r_{x_{i},y_{i}}(h)\mathds{1}\\{y_{i}=\hat{y}_{i}\\}}{W^{\gamma}_{x_{i},y_{i}}(\hat{P})}$.
Note that $\boldsymbol{\mathbb{E}}[X_{i}(h)]=\Pr[h(x)=y]$ and that
$X_{1}(h),\ldots,X_{M_{2}}(h)$ are i.i.d. Additionally, by the guarantee of
phase 1:

$\mathrm{Var}[X_{i}(h)]\leq\boldsymbol{\mathbb{E}}[X_{i}(h)^{2}]=\boldsymbol{\mathbb{E}}\brk[s]4{\frac{r_{x_{i},y_{i}}(h)\mathds{1}\\{y_{i}=\hat{y}_{i}\\}}{\brk{W^{\gamma}_{x_{i},y_{i}}(\hat{P})}^{2}}}=\boldsymbol{\mathbb{E}}\brk[s]4{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}}\leq
3.$

Define $\bar{X}(h)=\frac{1}{M_{2}}\sum_{i=1}^{M_{2}}X_{i}(h)$, and note that
by the form of the weighted ERM oracle,
$\hat{h}=\operatorname*{argmax}_{h\in\mathcal{H}}\bar{X}(h)$. Therefore, by an
application of Bernstein’s inequality (see e.g. Lattimore and Szepesvári
(2020), page 86) and a union bound, we have with probability at least
$1-\delta/2$ for all $h\in\mathcal{H}$:

$\abs{\bar{X}(h)-\Pr[h(x)=y]}\leq\sqrt{\frac{6\log(2N/\delta)}{M_{2}}}+\frac{2K\log(2N/\delta)}{\gamma
M_{2}}.$

Hence for $\hat{h}$, with probability at least $1-\delta/2$ we have

$\displaystyle L_{\mathcal{D}}(\hat{h})-L_{\mathcal{D}}(h^{\star})$
$\displaystyle=\Pr[\hat{h}(x)\neq y]-\Pr[h^{\star}(x)\neq y]$
$\displaystyle=\Pr[h^{\star}(x)=y]-\Pr[\hat{h}(x)=y]$
$\displaystyle\leq\Pr[h_{\star}(x)=y]-\bar{X}(h^{\star})+\bar{X}(\hat{h})-\Pr[\hat{h}(x)=y]$
$\displaystyle\leq\sqrt{\frac{36\log(2N/\delta)}{M_{2}}}+\frac{4K\log(2N/\delta)}{\gamma
M_{2}}.$

Choosing
$M_{2}\geq\max\\{144\log(2N/\delta)/\varepsilon^{2},8K\log(2N/\delta)/(\gamma\varepsilon)\\}$
gives $L_{\mathcal{D}}(\hat{h})-L_{\mathcal{D}}(h^{\star})\leq\varepsilon$.
Thus, using Lemma 2 and Lemma 3, we are only left with proving that with high
probability, collecting $M_{1}$ samples for $S$ takes at most
$O\brk{K^{9}\log\brk*{N/\delta}}$ steps. This essentially follows from the
fact that a binomial random variables is smaller than half of its expected
value with very small probability. Formally, we use lemma F.4 of Dann et al.
(2017) to deduce that if $X\sim\operatorname{Bin}\brk{4KM_{1},1/K}$ then with
probability at least $1-\delta$ it holds that $X\geq 2M_{1}-\log(1/\delta)\geq
M_{1},$ which means that $4KM_{1}$ trials suffice to guarantee that with
probability at least $1-\delta$, the dataset $S$ will contain at least $M_{1}$
samples. Thus, the proof of Theorem 1 is complete once we make the observation
that $2K/\varepsilon\leq K^{2}+1/\varepsilon^{2}$ (using the AM-GM inequality)
so that the $K/\varepsilon$ term is of lower order and can be dropped from the
final bound. ∎

##  4 Extension to Natarajan Classes

In this section we extend our result for finite classes given in Theorem 1 to
general, possibly infinite hypothesis classes $\mathcal{H}$ with finite
_Natarajan dimension_. The Natarajan dimension is an extension of the VC
dimension to the multiclass setting, defined as follows:

######  Definition 1 (Natarajan dimension; Natarajan, 1989).

The Natarajan dimension of a hypothesis class
$\mathcal{H}\subseteq\mathcal{X}\to\mathcal{Y}$ is the largest integer $d$ for
which there exist $d$ points $x_{1},\ldots,x_{d}\in\mathcal{X}$ and $d$ pairs
of distinct labels
$\\{y_{1,1},y_{1,2}\\},\ldots,\\{y_{d,1},y_{d,2}\\}\in\smash{\binom{\abs{\mathcal{Y}}}{2}}$
such that all $2^{d}$ sequences of the form
$(x_{1},y_{1}),\ldots,(x_{d},y_{d})$, with $y_{i}\in\\{y_{i1},y_{i2}\\}$, are
realizable by $\mathcal{H}$.

Note that in the binary case, when $\mathcal{Y}=\\{0,1\\}$, the Natarajan
dimension reduces to the VC dimension. Our main result in this case
effectively replaces the $\log\lvert\mathcal{H}\rvert$ term, relevant when
$\mathcal{H}$ is finite, with the Natarajan dimension $d_{N}$ of
$\mathcal{H}$.

######  Theorem 2.

Let $\mathcal{H}:\mathcal{X}\to\mathcal{Y}$ be a hypothesis class of finite
Natarajan dimension $d_{N}$. Then there exists a bandit multiclass
classification algorithm which outputs a hypothesis $\hat{h}$ with
$L_{\mathcal{D}}(\hat{h})-\inf_{h\in\mathcal{H}}L_{\mathcal{D}}(h)\leq\varepsilon$
with a sample complexity of
$\smash{\widetilde{O}}\brk{\brk{K^{9}+\ifrac{1}{\varepsilon^{2}}}d_{N}\log(\ifrac{1}{\delta})}.$

As discussed, this result improves the classical result of Daniely et al.
(2011), who provided an upper bound on the sample complexity of PAC learning
with bandit feedback, given by
$\smash{\widetilde{O}}(\ifrac{Kd_{N}}{\varepsilon^{2}})$, and left obtaining
tighter bounds as an open question. In particular, for small target excess
loss ($\varepsilon\to 0$), our bound eliminates the linear dependence on the
number of labels $K$, thereby matching the
$\smash{\widetilde{\Theta}}(\ifrac{d_{N}}{\varepsilon^{2}})$ bound from the
full information setting (Natarajan, 1989).

Theorem 2 follows directly from the following technical result, which is
proven in Appendix B, when put together with Theorem 1.

######  Proposition 1.

Assume that the sample complexity of PAC learning with bandit feedback a
finite class of size $N$ over a label-space of size $K$ is at most
$m(N,K,\varepsilon,\delta)$, where $\epsilon,\delta$ are the error and
confidence parameters. Then, the sample complexity of learning an infinite
class $\mathcal{H}$ is at most

$s+m(S,K,\epsilon/2,\delta/2),$

where

$\displaystyle s$
$\displaystyle:=O\Bigl{(}\frac{d_{N}\ln(K)\ln(1/\epsilon)+\ln(1/\delta)}{\epsilon}\Bigr{)},$
$\displaystyle S$
$\displaystyle:=\sum_{i=0}^{d_{N}}{\binom{s}{i}}{\binom{K}{2}}^{i}\leq\Bigl{(}\frac{e\,s}{d_{N}}\Bigr{)}^{d_{N}}K^{2d_{N}},$

and $d_{N}$ is the Natarajan dimension of $\mathcal{H}$.

The proposition is proven by using the first $s$ examples to construct a
finite discretization of size $S$ of the class $\mathcal{H}$, which is
$(\epsilon/2)$-dense in $\mathcal{H}$ in the sense that every
$h\in\mathcal{H}$ is $(\epsilon/2)$-close to some $h^{\prime}$ in the
discretization. Then, we apply our algorithm for finite classes on this finite
discretization. Most of the proof is dedicated to establishing that the
discretization is dense and to upper bounding its size. A similar result for
discretizing binary classes, with the VC dimension replacing the Natarajan
dimension, is well known. In the VC case, the proof is based on considering
the class of all symmetric differences of hypotheses from $\mathcal{H}$ and
analyzing the VC dimension of that class using standard techniques. In our
proof, we follow a similar argument, but the analysis of the VC dimension of
the symmetric difference class, which remains binary even in the multiclass
setting, is more nuanced.

###### Proof of Theorem 2.

By Theorem 1, we have an upper bound on the sample complexity for PAC learning
with bandit feedback over finite classes of size $N$ of

$\displaystyle
m\brk{N,K,\varepsilon,\delta}=O\brk*{(K^{9}+1/\varepsilon^{2})\log(N/\delta)}.$

Thus, the proof follows immediately from Proposition 1 together with the fact
that:

$\displaystyle\log\brk*{\frac{S}{\delta}}\leq
d_{N}\log\brk*{\frac{es}{d_{N}}}+2d_{N}\log K+\log\frac{1}{\delta},$

where $s$ and $S$ are defined in the statement of Proposition 1 (note that
$\log(s)$ only contributes logarithmic terms to the overall bound). ∎

## Acknowledgments

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program (grant
agreements No. 101078075; 882396). Views and opinions expressed are however
those of the author(s) only and do not necessarily reflect those of the
European Union or the European Research Council. Neither the European Union
nor the granting authority can be held responsible for them. This project has
also received funding from the Israel Science Foundation (ISF, grant numbers
2549/19; 2250/22), the Yandex Initiative for Machine Learning at Tel Aviv
University, the Tel Aviv University Center for AI and Data Science (TAD), the
Len Blavatnik and the Blavatnik Family foundation, and from the Adelis
Foundation.

Shay Moran is a Robert J. Shillman Fellow; supported by ISF grant 1225/20, by
BSF grant 2018385, by an Azrieli Faculty Fellowship, by Israel PBC-VATAT, by
the Technion Center for Machine Learning and Intelligent Systems (MLIS), and
by the European Union (ERC, GENERALIZATION, 101039692). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Research Council Executive
Agency. Neither the European Union nor the granting authority can be held
responsible for them.

## References

  * Agarwal et al. (2014) A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. Schapire.  Taming the monster: A fast and simple algorithm for contextual bandits.  In _International Conference on Machine Learning_ , pages 1638–1646. PMLR, 2014.
  * Alon et al. (2019) N. Alon, R. Bassily, and S. M. and.  Limits of private learning with access to public data.  In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 10342–10352, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/9a6a1aaafe73c572b7374828b03a1881-Abstract.html.
  * Asi et al. (2021) H. Asi, V. Feldman, T. Koren, and K. Talwar.  Private stochastic convex optimization: Optimal rates in l1 geometry.  In _International Conference on Machine Learning_ , pages 393–403. PMLR, 2021.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002.
  * Ben-David et al. (1992) S. Ben-David, N. Cesa-Bianchi, and P. M. Long.  Characterizations of learnability for classes of $\\{$O,…, n$\\}$-valued functions.  In _Proceedings of the fifth annual workshop on Computational learning theory_ , pages 333–340, 1992.
  * Brukhim et al. (2022) N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff.  A characterization of multiclass learnability.  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 943–955. IEEE, 2022.
  * Bubeck et al. (2012) S. Bubeck, N. Cesa-Bianchi, et al.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , 5(1):1–122, 2012.
  * Cesa-Bianchi and Lugosi (2006) N. Cesa-Bianchi and G. Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Daniely and Helbertal (2013) A. Daniely and T. Helbertal.  The price of bandit information in multiclass online classification.  In _Conference on Learning Theory_ , pages 93–104. PMLR, 2013.
  * Daniely et al. (2011) A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz.  Multiclass learnability and the erm principle.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pages 207–232. JMLR Workshop and Conference Proceedings, 2011.
  * Dann et al. (2017) C. Dann, T. Lattimore, and E. Brunskill.  Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Dudik et al. (2011) M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang.  Efficient optimal learning for contextual bandits.  _arXiv preprint arXiv:1106.2369_ , 2011.
  * Erez et al. (2024) L. Erez, A. Cohen, T. Koren, Y. Mansour, and S. Moran.  The real price of bandit information in multiclass classification, 2024.
  * Fang et al. (2018) C. Fang, C. J. Li, Z. Lin, and T. Zhang.  Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  _Advances in neural information processing systems_ , 31, 2018.
  * Frank et al. (1956) M. Frank, P. Wolfe, et al.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2):95–110, 1956.
  * Haussler and Long (1995) D. Haussler and P. M. Long.  A generalization of sauer’s lemma.  _J. Comb. Theory, Ser. A_ , 71(2):219–240, 1995.
  * Hazan et al. (2016) E. Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Kakade et al. (2008) S. M. Kakade, S. Shalev-Shwartz, and A. Tewari.  Efficient bandit algorithms for online multiclass prediction.  In _Proceedings of the 25th international conference on Machine learning_ , pages 440–447, 2008.
  * Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Long (2020) P. M. Long.  New bounds on the price of bandit feedback for mistake-bounded online multiclass learning.  _Theor. Comput. Sci._ , 808:159–163, 2020.  doi: 10.1016/J.TCS.2019.11.017.
  * Natarajan (1989) B. K. Natarajan.  On learning sets and functions.  _Machine Learning_ , 4(1):67–97, 1989.
  * Raman et al. (2023) A. Raman, V. Raman, U. Subedi, and A. Tewari.  Multiclass online learnability under bandit feedback.  _arXiv preprint arXiv:2308.04620_ , 2023.
  * Shamir (2013) O. Shamir.  On the complexity of bandit and derivative-free stochastic convex optimization.  In _Conference on Learning Theory_ , pages 3–24. PMLR, 2013.
  * Valiant (1984) L. G. Valiant.  A theory of the learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Vapnik and Chervonenkis (1968) V. Vapnik and A. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In _Proc. USSR Acad. Sci._ , 1968.
  * Wainwright (2019) M. J. Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Yurtsever et al. (2019a) A. Yurtsever, S. Sra, and V. Cevher.  Conditional gradient methods via stochastic path-integrated differential estimator.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 7282–7291. PMLR, 09–15 Jun 2019a.
  * Yurtsever et al. (2019b) A. Yurtsever, S. Sra, and V. Cevher.  Conditional gradient methods via stochastic path-integrated differential estimator.  In _International Conference on Machine Learning_ , pages 7282–7291. PMLR, 2019b.

##  Appendix A Proofs for Section 3

###### Proof of Lemma 1.

First note that the gradient of $\Phi(\cdot)$ is given by

$\displaystyle\nabla\Phi(P)$
$\displaystyle=\boldsymbol{\mathbb{E}}\brk[s]*{-\frac{(1-\gamma)r_{x,y}}{W^{\gamma}_{x,y}(P)}}.$

Thus, using a first-order optimality condition for $P_{\star}$, the following
holds that for any $P\in\Delta_{N}$,

$\displaystyle\nabla\Phi(P_{\star})\cdot\brk*{P-P_{\star}}\geq 0,$

which amounts to

$\mathbb{E}\brk[s]3{\frac{(1-\gamma)\brk*{P-P_{\star}}\cdot
r_{x,y}}{W^{\gamma}_{x,y}(P)}}\leq 0,$

or equivalently,

$\boldsymbol{\mathbb{E}}\brk[s]*{\frac{W^{\gamma}_{x,y}(P)-W^{\gamma}_{x,y}(P_{\star})}{W^{\gamma}_{x,y}(P_{\star})}}\leq
0,$

which rearranges to the first inequality to be proven. Letting $P$ be the
delta distribution on some $h\in\mathcal{H}$, we have proven that

$\mathbb{E}\brk[s]3{(1-\gamma)\frac{r_{x,y}}{W^{\gamma}_{x,y}(P_{\star})}}\leq
1,$

and the second inequality follows since $\gamma\leq\frac{1}{2}$. ∎

###### Proof of Lemma 2.

Assume that $\hat{P}$ minimizes $\Phi$ up to an additive error of $\mu$, that
is, the assumption given in the statement of the lemma. Now, note that for
every $(x,y)\in\mathcal{X}\times\mathcal{Y}$, using the explicit form of
$\phi(\cdot;x,y)$ and its gradient, it holds that:

$\displaystyle\phi(\hat{P};x,y)-\phi(P_{\star};x,y)-\nabla\phi(P_{\star};x,y)\cdot\brk*{\hat{P}-P_{\star}}$
$\displaystyle=\omega(R_{x,y}),$

where $\omega(z)=-\log z+z-1$ and
$R_{x,y}=W^{\gamma}_{x,y}(\hat{P})/W^{\gamma}_{x,y}(P_{\star})$. Using the
lower bound
$\omega(z)\geq\frac{1}{2}\min\brk[c]*{(1-z)^{2},(1-\frac{1}{z})^{2}}$ (see
Lemma 4 in Appendix A; this is where the self-concordance of $\phi$ comes in)
we obtain that for all $h\in\mathcal{H}$,

$\displaystyle\phi(\hat{P};x,y)-\phi(P_{\star};x,y)-\nabla\phi(P_{\star};x,y)\cdot\brk*{\hat{P}-P_{\star}}$
$\displaystyle\geq\frac{\gamma^{2}}{2K^{2}}\brk*{\frac{1}{W^{\gamma}_{x,y}(\hat{P})}-\frac{1}{W^{\gamma}_{x,y}(P_{\star})}}^{2}$
$\displaystyle\geq\frac{\gamma^{2}}{2K^{2}}\brk*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}-\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P_{\star})}}^{2}.$

Taking expectation of the inequality over $(x,y)\sim\mathcal{D}$ while using a
first-order optimality condition for $P_{\star}$ with respect to $\Phi$ and
the fact that
$\boldsymbol{\mathbb{E}}[(\cdot)^{2}]\geq\boldsymbol{\mathbb{E}}^{2}[\cdot]$,
we obtain

$\displaystyle\mu\geq\Phi(\hat{P})-\Phi(P_{\star})\geq\frac{\gamma^{2}}{2K^{2}}\brk*{\boldsymbol{\mathbb{E}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}}-\boldsymbol{\mathbb{E}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P_{\star})}}}^{2},$

and rearranging we obtain that for all $h\in\mathcal{H}$,

$\displaystyle\boldsymbol{\mathbb{E}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(\hat{P})}}$
$\displaystyle\leq\sqrt{\frac{2\mu
K^{2}}{\gamma^{2}}}+\boldsymbol{\mathbb{E}}\brk[s]*{\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P_{\star})}},$

so using Lemma 1 and the form of $\nabla\Phi$ we obtain the desired bound. ∎

###### Proof of Lemma 3.

In order to invoke Theorem 3 on $\Phi(\cdot)$, we prove that $\phi(\cdot;x,y)$
satisfies the required Lipschitz and smoothness properties with $G=K/\gamma$
and $\beta=K^{2}/\gamma^{2}$. Indeed, the gradient of $\phi$ is given by

$\displaystyle\nabla\phi(P,x,y)=-(1-\gamma)\frac{r_{x,y}}{W^{\gamma}_{x,y}(P)},$

and since $W^{\gamma}_{x,y}(P)\geq\gamma/K$ and $\norm{r_{x,y}}_{\infty}\leq
1$ we obtain the required Lipschitz property, that is,
$\norm{\nabla\phi(P,x,y)}_{\infty}\leq G$. For $L_{1}$ smoothness, it suffices
to show that for any $P,Q\in\Delta_{N}$ and any
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ it holds that

$\displaystyle\norm{\nabla\phi(P,x,y)-\nabla\phi(Q,x,y)}_{\infty}\leq\beta\norm{P-Q}_{1}.$

Indeed,

$\displaystyle\norm{\nabla\phi(P,x,y)-\nabla\phi(Q,x,y)}_{\infty}$
$\displaystyle=(1-\gamma)\max_{h\in\mathcal{H}}\left|\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(P)}-\frac{r_{x,y}(h)}{W^{\gamma}_{x,y}(Q)}\right|$
$\displaystyle\leq\left|\frac{W^{\gamma}_{x,y}(Q)-W^{\gamma}_{x,y}(P)}{W^{\gamma}_{x,y}(P)W^{\gamma}_{x,y}(Q)}\right|$
$\displaystyle=(1-\gamma)\left|\frac{r_{x,y}\cdot\brk*{Q-P}}{W^{\gamma}_{x,y}(P)W^{\gamma}_{x,y}(Q)}\right|$
$\displaystyle\leq\frac{K^{2}}{\gamma^{2}}\norm{P-Q}_{1},$

where in the last step we used Hölder’s inequality. Now, using Theorem 3, our
choice of $T$ and $M_{1}$ for which the batch sizes $b_{t}$ defined in Theorem
3 satisfy $\sum_{t=1}^{T}b_{t}\leq M_{1}$, the proof is complete. ∎

######  Lemma 4.

Let $\omega(z)=-\log{z}+z-1$. It holds that:

$\omega(z)\geq\min\set*{\tfrac{1}{2}(1-z)^{2},\tfrac{z}{2}\big{(}1-\tfrac{1}{z}\big{)}^{2}}.$

The first lower bound is relevant for $z\leq 1$ and the second for $z\geq 1$.

###### Proof.

Note that $\omega^{\prime}(z)=1-1/z$ and $\omega(1)=0$, hence
$\omega(z)=\int_{1}^{z}(1-1/x)dx$. When $0<z\leq 1$ we can bound $1-1/x\leq
1-x$ for any $z\leq x\leq 1$. Therefore,

$\omega(z)=\int_{1}^{z}(1/x-1)dx\geq\int_{1}^{z}(x-1)dx=\tfrac{1}{2}(1-z)^{2}.$

When $z\geq 1$, we can use the elementary inequality, for any $z\geq x\geq 1$:

$1-\frac{1}{x}\geq\frac{1}{2}\left(1-\frac{1}{x^{2}}\right)=\frac{d}{dx}\left\\{\frac{x}{2}\left(1-\frac{1}{x}\right)^{2}\right\\}$

to bound

$\omega(z)=\int_{1}^{z}(1-1/x)dx\geq\int_{1}^{z}\left(\tfrac{1}{2}(1-1/x^{2})\right)dx=\tfrac{z}{2}(1-1/z)^{2}.$

∎

##  Appendix B Proof of Proposition 1

###### Proof.

Consider the following learning rule: first sample $s$ examples
$x_{1},\ldots,x_{s}$ from the population (guess their label arbitrarily). Now
for each pattern $\\{(x_{i},y_{i})\\}_{i=1}^{s}$ which is realizable by some
function $h\in\mathcal{H}$, pick a representative $h\in\mathcal{H}$ such that
$h(x_{i})=y_{i}$ for all $i\leq s$. Define $\mathcal{H}_{\mathtt{fin}}$ to be
the set of all such representatives. The Sauer-Shelah-Perles Lemma for the
Natarajan dimension (Haussler and Long, 1995) implies that

$\lvert\mathcal{H}_{\mathtt{fin}}\rvert\leq S.$

Now, apply the assumed algorithm on the finite class
$\mathcal{H}_{\mathtt{fin}}$ with error and confidence parameters
$\varepsilon/2,\delta/2$. Let $\hat{h}$ denote the hypothesis outputted by the
algorithm. Thus, with probability at least $\delta/2$ the excess loss (or
regret) of $\hat{h}$ with respect to $\mathcal{H}_{\mathtt{fin}}$ is at most
$\varepsilon/2$. A union bound combined with the following lemma imply that
with probability at least $\delta$, the excess loss of $\hat{h}$ with respect
to $\mathcal{H}$ is at most $\varepsilon$.

######  Lemma 5.

With probability at least $1-\delta/2$ over the sampling of $x_{1},\ldots
x_{s}$, the finite class $\mathcal{H}_{\mathtt{fin}}$ is an
$(\varepsilon/2)$-cover for $\mathcal{H}$. That is, for every
$h\in\mathcal{H}$ there exists $h^{\prime}\in\mathcal{H}_{\mathtt{fin}}$ such
that the probability that $h^{\prime}(x)\neq h(x)$ for a random point $x$
drawn from the population is at most $\varepsilon/2$.

Indeed, by a union bound, with probability at least $1-\delta$, both (i) the
excess loss of $\hat{h}$ is at most $\epsilon/2$, and (ii)
$\mathcal{H}_{\mathtt{fin}}$ is an $(\varepsilon/2)$-cover for $\mathcal{H}$.
Hence, the excess loss of $\hat{h}$ with respect to the best hypothesis in
$\mathcal{H}$ is at most $\varepsilon/2+\varepsilon/2=\varepsilon$, as
required. ∎

Lemma 5 follows from a standard uniform convergence argument. In the case of
binary labels $K=2$, this lemma is known and has been used e.g. in Alon et al.
(2019). The general case is derived below using a similar argument like in
Alon et al. (2019).

###### Proof of Lemma 5.

We need to show that with probability at least $1-\delta/2$ over
$(x_{1},y_{1}),\ldots,(x_{s},y_{s})\sim\mathcal{D}$, for every
$h\in\mathcal{H}$, there exists $h^{\prime}\in\mathcal{H}_{\mathtt{fin}}$ such
that $\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq h^{\prime}(x)]\leq\varepsilon/2$.
For convenience, we use the notation
$d(h,h^{\prime}):=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq h^{\prime}(x)]$.

Let $T=(x_{1},\ldots,x_{s})$ be the sequence of points in the random sample,
and for a hypothesis $h$ let $h(T)=\left(h(x_{1}),\ldots,h(x_{s})\right)$. By
construction, for every $h\in\mathcal{H}$, there exists
$h^{\prime}\in\mathcal{H}_{\mathtt{fin}}$ such that $h^{\prime}(T)=h(T)$. We
will show that $d(h,h^{\prime})\leq\varepsilon/2$.

Define the event

$\displaystyle E=\bigl{\\{}\exists
h_{1},h_{2}\in\mathcal{H}:~{}d(h_{1},h_{2})>\varepsilon/2~{}\text{ and
}h_{1}(T)=h_{2}(T)\bigr{\\}}.$

We prove that

$\displaystyle\Pr[E]$ $\displaystyle\leq
2\left(\frac{2e\,s}{d_{N}}\right)^{2d_{N}}K^{4d_{N}}\,e^{-\epsilon\,s/4}.$ (6)

Before we do so, we first show that this suffices to prove the lemma: indeed,
if $d(h,h^{\prime})>\epsilon/2$ for some $h\in\mathcal{H}$ and
$h^{\prime}\in\mathcal{H}_{\mathtt{fin}}$ such that $h^{\prime}(T)=h(T)$, then
the event $E$ occurs because $\mathcal{H}_{\mathtt{fin}}\subseteq\mathcal{H}$.
Now, via standard manipulation, this bound is at most $\delta/2$ for some

$s=O\Bigl{(}\frac{d_{N}\ln(K)\ln(1/\epsilon)+\ln(1/\delta)}{\epsilon}\Bigr{)},$

which yields the desired bound and completes the proof.

It remains to prove (6). To do so, we use a standard VC-based uniform
convergence bound on the class
$\mathcal{H}_{\Delta}=\\{\Delta_{h_{1},h_{2}}:h_{1},h_{2}\in\mathcal{H}\\}$,
where

$\Delta_{h_{1},h_{2}}(x)=\begin{cases}1&h_{1}(x)\neq h_{2}(x),\\\
0&h_{1}(x)=h_{2}(x).\end{cases}$

Let $\mathcal{G}_{\Delta}$ denote the growth function of
$\mathcal{H}_{\Delta}$; that is, for any number $m,$

$\mathcal{G}_{\Delta}(m)=\max_{\\{V:\lvert
V\rvert=m\\}}\Bigl{\lvert}\mathcal{H}_{\Delta}|_{V}\Bigr{\rvert},$

where $\mathcal{H}_{\Delta}|_{V}$ is the set of all restrictions (or
projections) on $V$ of functions from $\mathcal{H}_{\Delta}$. Note that

$\mathcal{G}_{\Delta}(m)\leq\left(\frac{2e\,s}{d_{N}}\right)^{2d_{N}}K^{4d_{N}}.$

This follows from the fact that for any set $V$ of size $m$, we have
$\lvert\mathcal{H}_{\Delta}|_{V}\rvert\leq\lvert\mathcal{H}|_{V}\rvert^{2}$,
since every binary vector in $\mathcal{H}_{\Delta}|_{V}$ is determined by a
pair of functions in $\mathcal{H}|_{V}$. Hence,

$\mathcal{G}_{\Delta}(m)\leq\max_{\lvert
V\rvert=m}\bigl{\lvert}\mathcal{H}|_{V}\bigr{\rvert}^{2}\leq\left(\frac{2e\,s}{d_{N}}\right)^{2d_{N}}K^{4d_{N}},$

where the last inequality follows from the extended Sauer’s Lemma for
Natarajan classes applied on $\mathcal{H}$ (Haussler and Long, 1995).

Now, by invoking a uniform convergence argument, we have

$\displaystyle\Pr[E]$ $\displaystyle=\Pr[\exists
h_{1},h_{2}\in\mathcal{H}:~{}d(h_{1},h_{2})>\varepsilon/2~{}\text{ and
}h_{1}(T)=h_{2}(T)]$ $\displaystyle=\Pr[\exists
b\in\mathcal{H}_{\Delta}:~{}d(b,b_{0})\geq\varepsilon/2\text{ and
}b(T)=b_{0}(T)]$ (Here $b_{0}$ is the all-zero vector)
$\displaystyle\leq~{}2\mathcal{G}_{\Delta}(2\,s)\,e^{-\varepsilon,s/4}$
(double-sample symmetrization argument) $\displaystyle\leq
2\left(\frac{2e\,s}{d_{N}}\right)^{2d_{N}}K^{4d_{N}}\,e^{-\epsilon\,s/4}.$

The bound in the third line is non-trivial; it is known as the double-sample
argument which was used by Vapnik and Chervonenkis in their seminal paper
(Vapnik and Chervonenkis, 1968). The same argument is used in virtually all
VC-based uniform convergence bounds. This proves inequality (6) and completes
the proof of the lemma. ∎

##  Appendix C Stochastic (SPIDER) Frank-Wolfe in L1 Norm

In this section we present and analyze the stochastic Frank-Wolfe (FW) method
used as a sub-procedure in our main algorithm. Crucially, we require a
specific variant of stochastic FW due to Yurtsever et al. (2019a), called
SPIDER-FW, that employs mini-batching and variance-reduced for stochastic
gradient estimation.

SPIDER FW has been shown to obtain the optimal $1/\varepsilon^{2}$ rate of
convergence in a general stochastic setting that involves a convex and smooth
objective (Yurtsever et al., 2019a). However, the existing analysis pertain to
the Euclidean case, whereas we crucially require an $L_{1}$–$L_{\infty}$
analysis. We provide such analysis here with a specialized argument for
variance-reduction with respect to the $L_{1}$ norm. (We note that similar
arguments have appeared in Asi et al. (2021) in the context of differentially-
private optimization.)

#### Setup.

The setup for this section is the following. We consider a stochastic
optimization problem of the form

minimize $\displaystyle F(w)=\boldsymbol{\mathbb{E}}[f(w,z)]$ s.t.
$\displaystyle w\in W,$

where $W$ is a convex domain in $\mathbb{R}^{d}$ and the expectation is over
$z$ drawn from an underlying distribution $\mathcal{D}$. In the context of
this section, we think of $\mathcal{D}$ as being unknown but assume that
i.i.d. samples $z_{1},z_{2},\ldots\sim\mathcal{D}$ are readily available.

We further make the following assumptions:

  * •

We assume that $f$ convex, $\beta$-smooth and $G$-Lipschitz (in its first
argument) with respect to the $L_{1}$ norm over $W$, that is,

$\displaystyle f(u,z)\leq f(v,z)+\nabla
f(v,z)\cdot\brk*{u-v}+\frac{\beta}{2}\norm{u-v}_{1}^{2}\quad\forall
z\in\mathcal{Z},\forall u,v\in W,$

and further, that $\norm_{\nabla f(v,z)}{}_{\infty}\leq G$ for all $z\in Z$
and $v\in\mathcal{W}$;

  * •

We assume that the feasible domain $W$ has $L_{1}$ diameter $\leq D$, that is,
$\norm{u-v}_{1}\leq D$ for all $u,v\in W$. the algorithmic access to the set
$W$ is through a linear optimization oracle (LOO), that given any vector
$g\in\mathbb{R}^{d}$ computes

$\textsf{LOO}(g)=\operatorname*{argmin}_{w\in W}g\boldsymbol{\cdot}w.$

###  C.1 Stochastic FW with SPIDER gradient estimates

The SPIDER FW algorithm is presented in Algorithm 3. The algorithm makes
Frank-Wolfe type updates using “SPIDER” gradient estimates $g_{t}$, that are
computed from the raw stochastic gradients. The SPIDER estimates work in mini-
batches, but employ low-variance bias correction in order to update the
estimates without resetting them entirely from round to round, thus saving in
the mini-batch sizes.

Algorithm 3 Stochastic Frank-Wolfe with SPIDER gradient estimates

Parameters: step sizes $\brk[c]*{\eta_{t}}_{t}$, batch sizes
$\set{b_{t}}_{t}$.

Initialize $w_{1}\in\mathcal{W}$ and initial gradient estimate $g_{1}=0$.

Let $\tau_{k}=2^{k}-1$ for $k=1,2,\ldots$.

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

Draw fresh $b_{t}$ samples $z_{1},\ldots,z_{b_{t}}$ from $\mathcal{D}$;

if $t\in\brk[c]*{\tau_{k}}_{k\geq 1}$ then

Set  $g_{t}=\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\nabla f(w_{t},z_{i});$

else

Set  $g_{t}=g_{t-1}+\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}(\nabla
f(w_{t},z_{i})-\nabla f(w_{t-1},z_{i}));$

end if

Compute $v_{t}=\textsf{LOO}(g_{t})$;

Update $w_{t+1}=(1-\eta_{t})w_{t}+\eta_{t}v_{t}$;

end for

The main result of this section is given in the following theorem.

######  Theorem 3.

Algorithm 3 with step sizes $\eta_{t}=1/t$ and batch sizes $b_{t}$ defined as

$\displaystyle b_{t}=\begin{cases}(G/\beta D)^{2}\,t^{2}&\text{if
$t\in\set{\tau_{k}}_{k\geq 1}$};\\\ t&\text{otherwise,}\end{cases}$ (7)

guarantees that, for all $t\geq 2$ and any $\delta>0$:

$\boldsymbol{\mathbb{E}}[F(w_{t})-F(w^{*})]\leq\frac{25\beta
D^{2}}{t}\sqrt{\log{d}}~{},\quad\text{and}\quad\Pr\left(F(w_{t})-F(w^{*})\leq\frac{25\beta
D^{2}}{t}\sqrt{\log\frac{dt}{\delta}}\right)\geq 1-\delta~{}.$

Consequently, for convergence to within $\epsilon>0$ with probability at least
$1-\delta$, the algorithm requires $O((\beta
D^{2}/\epsilon)\sqrt{\log(d/\delta)})$ calls to LOO and
$O(((G^{2}D^{2}+\beta^{2}D^{4})/\epsilon^{2})\log(d/\delta))$ stochastic
gradient computations.

###  C.2 Analysis

To analyze Algorithm 3, we first record a generic convergence guarantee for
stochastic FW template with gradient estimates. The template operates as
follows; starting from an arbitrary initialization $w_{1}\in W$, for
$t=1,...,T$:

  1. (i)

get gradient estimator $g_{t}$ at $w_{t}$;

  2. (ii)

use LOO to compute $v_{t}=\operatorname*{argmin}_{w\in
W}g_{t}\boldsymbol{\cdot}w$;

  3. (iii)

update $w_{t+1}=(1-\eta_{t})w_{t}+\eta_{t}v_{t}$.

######  Lemma 6.

Set $\eta_{t}=1/t$ for all $t$ and suppose that the gradient estimates
satisfy, for some $c>0$,555The claim of this particular theorem holds in fact
for any pair of dual norms, but for consistency, is stated and proved here
only for the $L_{1}$-$L_{\infty}$ case.

$\displaystyle\forall~{}t\geq
1:\qquad\boldsymbol{\mathbb{E}}\norm{g_{t}-\nabla F(w_{t})}_{\infty}\leq
c\eta_{t}.$

Then the FW iterations guarantees for all $t\geq 2$ and $w^{*}\in W$ that:

$\displaystyle\boldsymbol{\mathbb{E}}[F(w_{t})-F(w^{*})]\leq\frac{\beta
D^{2}+2cD}{t}.$

Similarly, if the estimates satisfy

$\displaystyle\forall~{}t\geq 1:\qquad\Pr(\norm{g_{t}-\nabla
F(w_{t})}_{\infty}>c_{\delta}\eta_{t})\leq\delta.$

for some $\delta\in(0,1)$ and $c_{\delta}>0$, then for any $t\geq 2$ and
$w^{*}\in W$, with probability at least $1-t\delta$,

$\displaystyle F(w_{t})-F(w^{*})\leq\frac{\beta D^{2}+2c_{\delta}D}{t}.$

###### Proof.

First, using $\beta$-smoothness (with respect to $\norm{\cdot}_{1}$) we have
that

$\displaystyle F(w_{t+1})$ $\displaystyle\leq F(w_{t})+\nabla
F(w_{t})\boldsymbol{\cdot}(w_{t+1}-w_{t})+\tfrac{1}{2}\beta\norm{w_{t+1}-w_{t}}_{1}^{2}$
$\displaystyle\leq F(w_{t})+\eta_{t}\nabla
F(w_{t})\boldsymbol{\cdot}(v_{t}-w_{t})+\tfrac{1}{2}\eta_{t}^{2}\beta D^{2}.$

Next, due to the minimality of $v_{t}$, notice that for any $w^{*}\in W$,

$\displaystyle\nabla F(w_{t})\boldsymbol{\cdot}(v_{t}-w_{t})$
$\displaystyle=g_{t}\boldsymbol{\cdot}(v_{t}-w_{t})+(\nabla
F(w_{t})-g_{t})\boldsymbol{\cdot}(v_{t}-w_{t})$ $\displaystyle\leq
g_{t}\boldsymbol{\cdot}(w^{*}-w_{t})+(\nabla
F(w_{t})-g_{t})\boldsymbol{\cdot}(v_{t}-w_{t})$ $\displaystyle=\nabla
F(w_{t})\boldsymbol{\cdot}(w^{*}-w_{t})+(\nabla
F(w_{t})-g_{t})\boldsymbol{\cdot}(v_{t}-w^{*})$ $\displaystyle\leq
F(w^{*})-F(w_{t})+D\norm{\nabla F(w_{t})-g_{t}}_{\infty},$

where the final inequality follows from convexity and the diameter bound.
Plugging into the inequality and rearranging, we obtain

$\displaystyle
F(w_{t+1})-F(w^{*})\leq(1-\eta_{t})(F(w_{t})-F(w^{*}))+\eta_{t}D\norm{\nabla
F(w_{t})-g_{t}}_{\infty}+\tfrac{1}{2}\eta_{t}^{2}\beta D^{2}.$

Taking the expectation of both sides and using our assumption on the gradient
estimates, we obtain the following progress inequality, that holds for all
$t\geq 1$:

$\displaystyle\boldsymbol{\mathbb{E}}[F(w_{t+1})-F(w^{*})]\leq(1-\eta_{t})\boldsymbol{\mathbb{E}}[F(w_{t})-F(w^{*})]+\tfrac{1}{2}\eta_{t}^{2}(\beta
D^{2}+2cD).$

We are now ready to prove the main claim by induction on $t\geq 2$. First,
plugging $t=1$ and $\eta_{1}=1$ into the progress inequality we have that
$\boldsymbol{\mathbb{E}}[F(w_{2})-F(w^{*})]\leq\tfrac{1}{2}(\beta D^{2}+2cD)$,
that is, the claim holds for $t=2$. For the induction step, let us assume that
$\boldsymbol{\mathbb{E}}[F(w_{t})-F(w^{*})]\leq(\beta D^{2}+2cD)/t$ for some
$t\geq 2$. Then by the progress inequality:

$\displaystyle\boldsymbol{\mathbb{E}}[F(w_{t+1})-F(w^{*})]$
$\displaystyle\leq(1-\eta_{t})\boldsymbol{\mathbb{E}}[F(w_{t})-F(w^{*})]+\tfrac{1}{2}\eta_{t}^{2}(\beta
D^{2}+2cD)$ $\displaystyle=\left(1-\frac{1}{t}\right)\frac{\beta
D^{2}+2cD}{t}+\frac{\beta D^{2}+2cD}{2t^{2}}$ $\displaystyle\leq\frac{\beta
D^{2}+2cD}{t}.$

This concludes the proof in expectation. The second claim regarding
convergence with high probability follows from the same arguments together
with a union bound. ∎

The next lemma analyzes the variance-reduced (SPIDER) gradient estimates used
in Algorithm 3.

######  Lemma 7.

If we set the batch sizes as defined in Eq. 7, then for all $t$ and
$\delta>0$:

$\displaystyle\boldsymbol{\mathbb{E}}\norm{g_{t}-\nabla
F(w_{t})}_{\infty}\leq\frac{12\beta
D}{t}\sqrt{\log{d}}~{},\quad\text{and}\quad\Pr\left(\norm{g_{t}-\nabla
F(w_{t})}_{\infty}>\frac{12\beta
D}{t}\sqrt{\log\frac{d}{\delta}}\right)\leq\delta~{}.$ (8)

###### Proof.

The proof relies on standard properties of sub-Gaussian random variables, all
of which can be found in, e.g., (Wainwright, 2019). Let $Z_{t,j}=(g_{t}-\nabla
F(w_{t}))_{j}$ be the $j$’th coordinate of the error at step $t$. Note that
$Z_{t,j}$ is zero-mean. We will show that $Z_{t,j}$ is also sub-Gaussian with
parameter $\sigma_{t}=6\beta D/t$. The claim will then follow since
$\norm{g_{t}-\nabla F(w_{t})}_{\infty}$ is a maximum of $2d$ zero-mean sub-
Gaussians with parameter $\sigma_{t}$, which implies Eq. 8.

First, consider $t$ of the form $t=\tau_{k}$ and any coordinate $j\in[d]$. The
claim follows in this case from variance reduction by mini-batching: condition
on randomness before step $t$; since all gradients are bounded in $L_{\infty}$
norm by $G$, we have by Hoeffding’s Lemma that $(\nabla f(w_{t},z_{i})-\nabla
F(w_{t}))_{j}$ are independent zero-mean $G$-sub-Gaussians RVs (for
$i=1,\ldots,b_{t}$), thus their mean $Z_{t,j}=(g_{t}-\nabla F(w_{t}))_{j}$ is
zero-mean sub-Gaussian with parameter $\sigma_{t}=G/\sqrt{b_{t}}=\beta D/t$.

Next, consider any other round such that $\tau_{k}<t<\tau_{k+1}$ and any
coordinate $j\in[d]$. In this case, the claim will follow from accumulation of
variance starting from the reset step $\tau_{k}$. Note that due to smoothness,

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\abs{((\nabla f(w_{t},z_{i})-\nabla
F(w_{t}))_{j}-(\nabla f(w_{t-1},z_{i})-\nabla F(w_{t-1}))_{j}}$
$\displaystyle\leq\abs{(\nabla f(w_{t},z_{i})-\nabla
f(w_{t-1},z_{i}))_{j}}+\abs{(\nabla F(w_{t})-\nabla F(w_{t-1}))_{j}}$
$\displaystyle\leq\norm{\nabla f(w_{t},z_{i})-\nabla
f(w_{t-1},z_{i})}_{\infty}+\norm{\nabla F(w_{t})-\nabla F(w_{t-1})}_{\infty}$
$\displaystyle\leq 2\beta\norm{w_{t}-w_{t-1}}_{1}$ $\displaystyle\leq 2\beta
D\eta_{t-1}.$

Thus, as before, the random variable $Z_{t,j}-Z_{t-1,j}=(g_{t}-\nabla
F(w_{t}))_{j}-(g_{t-1}-\nabla F(w_{t-1}))_{j}$ is a zero-mean sub-Gaussian
with parameter $2\beta D\eta_{t-1}/\sqrt{b_{t}}$, conditioned on randomness
before step $t$. By the martingale-summation property of sub-Gaussian RVs, we
then obtain that $Z_{t,j}$ is zero-mean sub-Gaussian with parameter
$\sigma_{t}$, where

$\displaystyle\sigma_{t}^{2}$
$\displaystyle=\frac{G^{2}}{b_{\tau_{k}}}+\sum_{s=\tau_{k}+1}^{t}\frac{4\beta^{2}D^{2}\eta_{s-1}^{2}}{b_{s}}$
$\displaystyle=\frac{\beta^{2}D^{2}}{\tau_{k}^{2}}+4\beta^{2}D^{2}\sum_{s=\tau_{k}+1}^{t}\frac{1}{s(s-1)^{2}}$
$\displaystyle\leq\frac{\beta^{2}D^{2}}{\tau_{k}^{2}}+8\beta^{2}D^{2}\sum_{s=\tau_{k}+1}^{t}\left(\frac{1}{(s-1)^{2}}-\frac{1}{s^{2}}\right)$
$\displaystyle\leq\frac{\beta^{2}D^{2}}{\tau_{k}^{2}}+\frac{8\beta^{2}D^{2}}{\tau_{k}^{2}}$
$\displaystyle\leq\frac{36\beta^{2}D^{2}}{t^{2}}$

where the final inequality uses $\tau_{k}\geq t/2$. Therefore, we deduce that
$\sigma_{t}\leq 6\beta D/t$. ∎

We are now ready to prove Theorem 3.

###### Proof of Theorem 3.

The theorem follows directly from Lemmas 6 and 7 and plugging in the specified
parameters. The number of steps for convergence to within a given $\epsilon>0$
is therefore $t=O((\beta D^{2}/\epsilon)\sqrt{\log(d/\delta)})$, which is also
the number of LOO calls. For the total sample complexity, observe that the
contribution of rounds $t\notin\set{\tau_{k}}_{k\geq 1}$ is bounded by
$\sum_{s=1}^{t}s=O(t^{2})$, while the contribution of rounds
$t\in\set{\tau_{k}}_{k\geq 1}$ is at most $O((G/\beta D)^{2}t^{2})$. ∎