# Multiclass Classification using dilute bandit feedback

Gaurav Batra Machine Learning Lab
IIIT Hyderabad
<EMAIL_ADDRESS>Naresh Manwani Machine Learning Lab
IIIT Hyderabad
<EMAIL_ADDRESS>
###### Abstract

This paper introduces a new online learning framework for multiclass
classification called learning with diluted bandit feedback. At every time
step, the algorithm predicts a candidate label set instead of a single label
for the observed example. It then receives a feedback from the environment
whether the actual label lies in this candidate label set or not. This
feedback is called "diluted bandit feedback". Learning in this setting is even
more challenging than the bandit feedback setting Kakade et al. [2008], as
there is more uncertainty in the supervision. We propose an algorithm for
multiclass classification using dilute bandit feedback (MC-DBF), which uses
the exploration-exploitation strategy to predict the candidate set in each
trial. We show that the proposed algorithm achieves
$\mathcal{O}(T^{1-\frac{1}{m+2}})$ mistake bound if candidate label set size
(in each step) is $m$. We demonstrate the effectiveness of the proposed
approach with extensive simulations.

##  1 Introduction

In multi-class classification, the learning algorithm is given access to the
examples and their actual class labels. The goal is to learn a classifier
which given an example, correctly predicts its class label. This is called the
full information setting. In the full information setting, online algorithms
for multiclass classification are discussed in Crammer and Singer [2003], Fink
et al. [2006], Matsushima et al. [2010]. In many applications, we do not get
labels for all the examples. Instead, we can only access whether the predicted
label for an example is correct. This is called bandit feedback setting Kakade
et al. [2008]. Bandit feedback-based learning is useful in several web-based
applications, such as sponsored advertising on web pages and recommender
systems as mentioned in Kakade et al. [2008].

In the linearly separable case, Kakade et. al Kakade et al. [2008] propose
Banditron algorithm which can learn using bandit feedbacks. Banditron makes
$\mathcal{O}(\sqrt{T})$ expected number of mistakes in the linearly separable
case and $\mathcal{O}(T^{2/3})$ in the worst case. On the other hand Newtron
Hazan and Kale [2011b] (based on the online Newton method) achieves
$\mathcal{O}(\log T)$ regret bound in the best case and $\mathcal{O}(T^{2/3})$
regret in the worst case. Beygelzimer et. al Beygelzimer et al. [2017] propose
Second Order Banditron (SOBA) which achieves $\mathcal{O}(\sqrt{T})$ regret in
the worst case.

Figure 1: The three types of supervised learning settings are explained in
this figure. (a) Full Information Setting: In this setting, the agent receives
the correct label on prediction. (b) Bandit Feedback Setting: Here, the agent
gets the information whether his prediction is accurate or not. (c) Partial
Bandit Feedback Setting: In this setting, the agent predicts a set of labels
and gets the feedback whether the correct label lies in the predicted set or
not.

In the bandit feedback-based approaches, the algorithm predicts a single label
and seeks the feedback whether the predicted label is correct. Here, we
introduce a new learning framework called "learning under diluted bandit
feedback". At every time step, when the algorithm observes a new example, it
predicts a candidate label set instead of a single label. Now the algorithm
seeks the oracle’s feedback whether the actual label lies in this candidate
label set or not. Note that learning in this setting is even more challenging
than bandit feedback setting as there is another level of uncertainty in the
supervision. That is, if the feedback says that the actual label lies in the
predicted candidate label set, we still do not know which of the label in the
candidate set is the true one. Using the example presented in Figure 1, we can
see the difference between bandit feedback and diluted bandit feedback.

Diluted bandit feedback-based learning can be useful in many applications. For
example, consider the situation where a doctor is trying to diagnose a
patient. Based on the patient’s initial symptoms, she starts the treatment
with some idea about possible diseases. Based on the treatment outcome, the
doctor would know whether the actual disease was correctly diagnosed in the
possible diseases guessed by the doctor. The result of the treatment here is
diluted bandit feedback. It does not tell the exact disease but only indicates
whether the actual disease lies in a possible set of diseases.

Another example would be that of advertising on web pages. The user first
queries the system. Based on the query and user-specific information, the
system makes a prediction as a set of advertisements. Finally, the user may
either click on one of the ads or just ignore all of them. The action of the
user clicking or ignoring the advertisements is the dilute bandit feedback. In
the cases mentioned above, knowing the ground truth label beforehand may not
always be possible. Hence, this provides the motivation for coming up with the
setting and the corresponding algorithm.

Note that diluted bandit feedbacks make the supervision weaker than bandit
feedbacks. In this paper, we attempt the problem of learning multiclass
classifier using diluted bandit feedbacks. To the best of our knowledge, this
is the first work in this direction. Following are the key contributions in
this paper:

  * •

We propose an algorithm which learns multiclass classifier using diluted
bandit feedbacks.

  * •

We show that the proposed algorithm achieves sub-linear mistake bound of
$\mathcal{O}(T^{1-(m+2)^{-1}})$, where $m$ is the size of the subset
predicted.

  * •

We experimentally show that the proposed approach learns efficient classifiers
using diluted bandit feedbacks.

The main novelty of the MC-DBF algorithm is that it is able to train even
under the dilute bandit feedback setting. Comparing the dilute bandit feedback
with the bandit and full information setting, we see that the amount of
feedback that MC-DBF receives at the time of training is very less. In spite
of this, our algorithm achieves an error rate that is comparable to that of
algorithms that receive bandit feedback (Banditron) or full feedback
(Perceptron) at the time of training. The dilute bandit feedback setting has
been introduced for the first time in our paper and this algorithm is the
first approach to train a classifier in this type of setting.

##  2 Problem Setting: Diluted Bandit Feedback

We now formally describe the problem statement for our multi-class
classification with diluted bandit feedback. The classification is done in a
sequence of rounds. At each round $t$, the algorithm observes an instance
$\mathbf{x}^{t}\in\mathbb{R}^{d}$. The algorithm predicts a set of labels
$\tilde{Y}^{t}\subset\\{1,\ldots,k\\}$ such that $|\tilde{Y}^{t}|=m$. After
predicting the set of labels, we observe the feedback
$\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$ where $y^{t}$ is the true label
corresponding to the input $\mathbf{x}^{t}$.
$\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$ is $1$ if $y^{t}\in\tilde{Y}^{t}$
else $0$. In this type of bandit feedback, the classifier receives the
information if the predicted set contains the correct label or not. There are
two possibilities of the value of $m$.

  * •

Case 1 ($m=1$): Here, $\tilde{Y}^{t}=\tilde{y}^{t}$ and the feedback reduces
to $\mathbb{I}{\\{y^{t}=\tilde{y}^{t}\\}}$ which is discussed in Kakade et al.
[2008], Hazan and Kale [2011a], Arora and Manwani [2020]. Thus, when
$\mathbb{I}{\\{y^{t}=\tilde{y}^{t}\\}}=1$, we know the true label. On the
other hand, $\mathbb{I}{\\{y^{t}=\tilde{y}^{t}\\}}=0$, the true label can be
anything among $[k]\setminus\tilde{y}_{t}$.

  * •

Case 2 ($1<m<k$): Here, the uncertainty is present in both possibilities of
the feedback $\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$. When
$\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}=1$, then the true label could be
anything among the labels in the set $\tilde{Y}^{t}$. When
$\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}=0$, the true label lies in the set
$[k]\setminus\tilde{Y}^{t}$. Thus, in both possibilities of the feedback,
there is ambiguity about the true label. Hence the name diluted bandit
feedback.

This paper is mainly concerned about Case 2, where $1<m<k$ (diluted bandit
feedback setting). The algorithm’s final goal is to minimize the number of
prediction mistake $\hat{M}$ as defined below.

$\begin{split}\hat{M}:=\sum_{t=1}^{T}\mathbb{I}{\\{y^{t}\notin\hat{Y}^{t}\\}}\end{split}$
(1)

To the best of our knowledge, this is first time diluted bandit feedback
setting has been discussed.

##  3 Proposed Approach

The algorithm tries to learn a linear classifier parameterized by a weight
matrix $W\in\mathbb{R}^{k\times d}$. To formulate the algorithm which learns
using diluted bandit feedback, let us first look at a simple full information
approach.

###  3.1 Multiclass Algorithm with Subset Label Prediction: A Full Information
Approach

Consider the approach where the algorithm can predict a subset of labels. We
first define label set prediction function.

######  Definition 1.

Label Set Prediction Function $\hat{Y}(\mathbf{x},W)$: Given an example
$\mathbf{x}$ and a weight matrix $W\in\mathbb{R}^{k\times d}$, we denote
predicted label set of size $m$ as $\hat{Y}(\mathbf{x},W)$. We define
$\hat{Y}(\mathbf{x},W):=\\{a_{1},\dots,a_{m}\\}$ where

$a_{i}=\underset{j\in[k]\setminus\\{a_{1},\dots,a_{i-1}\\}}{\arg\max}\;(W\mathbf{x})_{j}.$

Parameters: $\gamma\in$ (0,1.0);

Initialize $W^{1}$ = 0 $\in\mathbb{R}^{k\times d}$ ;

for  _t= 1,…,T_ do

Receive $\mathbf{x}^{t}\in R^{d}$;

Predict $\hat{Y}(\mathbf{x}^{t},W^{t})$ and receive feedback $y^{t}$;

Define
$U^{t}_{r,j}=x^{t}_{j}\Big{(}\mathbb{I}{\\{r=y^{t}\\}}-\frac{1}{m}\mathbb{I}\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}\Big{)}$;

Update: $W^{t+1}=W^{t}+\tilde{U}^{t}$;

end for

Algorithm 1 MC-SLP: Multiclass Classification using Subset Label Prediction

Thus, $\hat{Y}(\mathbf{x},W)$ predicts top $m$-labels based on $m$-largest
values in the vector $W\mathbf{x}$. Then we observe the true label
$y\in[k]$.111Note that this setting is exactly opposite to the partial label
setting Bhattacharjee and Manwani [2020], Arora and Manwani [2021]. In the
partial label setting, ground truth is a labelled subset, and the algorithm
predicts a single label. We use following variant of 0-1 loss to capture the
discrepancy between the true label ($y$) and the predicted label set
$\hat{Y}(\mathbf{x},W)$.

$\begin{split}L_{0-1}=\mathbb{I}{\\{y\notin\hat{Y}(\mathbf{x},W)\\}}\end{split}$
(2)

But, this loss is not continuous. So, we use following average hinge loss as a
surrogate loss function,

$L_{avg}(W,(\mathbf{x},y))=[1-(W\mathbf{x})_{y}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x},W)}(W\mathbf{x})_{i}]_{+}$
(3)

where $[A]_{+}=A$ if $A>0$ else $0$. It is easy to see that $L_{avg}$ is upper
bound to $L_{0-1}$.

######  Lemma 2.

$L_{avg}$ is an upper-bound on $\mathbb{I}{\\{y\in\hat{Y}(\mathbf{x},W)\\}}$,
that is $L_{avg}\geq\mathbb{I}{\\{y\notin\hat{Y}(\mathbf{x},W)\\}}$.

An online algorithm in this setting can be easily derived by using stochastic
gradient descent on the loss $L_{avg}$. We call it MC-SLP (multiclass
classification using subset label prediction). The algorithm works as follows.
At trial $t$ we observe example $\mathbf{x}^{t}$. We predict the label set
$\hat{Y}(\mathbf{x}^{t},W^{t})$ using the existing parameters $W^{t}$. Then we
observe the true label $y^{t}$. We update the parameters using stochastic
gradient descent on the loss $L_{avg}$ which results in the update equation
$W^{t+1}=W^{t}+U^{t}$ where $U^{t}$ is described as follows.

$\begin{split}U^{t}_{r,j}=x^{t}_{j}\Big{(}\mathbb{I}{\\{r=y_{t}\\}}-\frac{\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}}{m}\Big{)}.\end{split}$
(4)

We repeat this process for $T$ number of trials. The complete description of
this approach is given in Algorithm 1. Note that MC-SLP is a full information
type algorithm as we get access to the true label for each example. The
following is true for MC-SLP (Algorithm 1).

######  Lemma 3.

Let $W^{t}$ be the weight matrix in the beginning of trial $t$ of MC-SLP and
$U^{t}$ be the update matrix in trial $t$ by MC-SLP. Let $\langle
W^{t},U^{t}\rangle=\sum_{r=1}^{k}\sum_{j=1}^{d}W^{t}_{r,j}U^{t}_{r,j}$ (matrix
inner product). Then,

$\begin{split}L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))\geq\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}\;-\;\langle
W^{t},U^{t}\rangle\end{split}$

This lemma gives us a lower bound on the loss $L_{avg}$ computed for example
$\mathbf{x}^{t}$ at trial $t$. This is a useful result which we will need
later.

###  3.2 MC-DBF: Multiclass Learning with Diluted Bandit Feedback

Parameters: $\gamma\in$ (0,1.0);

Initialize $W^{1}=\mathbf{0}^{d\times k}$;

for  _$t=1,\dots,T$_ do

Receive $\mathbf{x}^{t}\in\mathbb{R}^{d}$;

Find $\hat{Y}(\mathbf{x}^{t},W^{t})$;

Define
$\mathbb{P}(r):=\frac{(1-\gamma)}{m}\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}+\frac{\gamma}{k},\;\forall
r\in[k]$;

Define
$Z(A)=\mathbb{P}(b_{1})\mathbb{P}(b_{2}|b_{1})\dots\mathbb{P}(b_{m}|b_{1},\dots,b_{m-1}),\;\forall
A=\\{b_{1},\dots,b_{m}\\}\in\mathbb{S}$;

Randomly sample $\tilde{Y}^{t}$ according to $Z$;

Predict $\tilde{Y}^{t}$ and receive feedback
$\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$;

Compute $\forall r\in[K]$ and $\forall j\in[d]$;

$\tilde{U}^{t}_{r,j}=x^{t}_{j}\left[\frac{\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}\mathbb{I}{\\{r\in\tilde{Y}^{t}\\}}}{Z(\tilde{Y}^{t})\tau_{1}}-\tau_{2}-\frac{\mathbb{I}\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}{m}\right]$;

Update: $W^{t+1}=W^{t}+\tilde{U}^{t}$;

end for

Algorithm 2 MC-DBF: Multiclass Classification Using Diluted Bandit Feedback

We now describe the algorithm for learning using diluted bandit feedback.
Here, for each example $\mathbf{x}^{t}$, we do not receive the true label
$y^{t}$. We instead receive the feedback whether $y^{t}$ lies in the predicted
label set $\tilde{Y}^{t}$ (i.e. $\mathbb{I}\\{y^{t}\in\tilde{Y}^{t}\\}$). The
algorithm works as follows.

At each iteration $t$, we receive $\mathbf{x}^{t}$ as input. We find
$\hat{Y}(\mathbf{x}^{t},W^{t})=\\{a_{1},a_{2},\dots,a_{m}\\}$ where

$a_{i}=\underset{j\in[k]\setminus\\{a_{1},\dots,a_{i-1}\\}}{\arg\max}\;(W^{t}\mathbf{x}^{t})_{j}.$

We define probability distribution $\mathbb{P}$ on individual class labels as
follows.

$\begin{split}\mathbb{P}(r)=\frac{(1-\gamma)}{m}\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}+\frac{\gamma}{k},\;\forall
r\in[k]\end{split}$ (5)

Here, $\gamma$ is the exploration parameter. Let $\mathbb{S}$ denote the set
of all $m$ size subsets of $\\{1,\ldots,k\\}$. We call them superarms of size
$m$. Now, we define probability distribution $Z$ on the set $\mathbb{S}$ as
follows. For all $A=\\{b_{1},\dots,b_{m}\\}\in\mathbb{S}$, we define

$Z(A)=\mathbb{P}(b_{1})\mathbb{P}(b_{2}|b_{1})\dots\mathbb{P}(b_{m}|b_{1},\dots,b_{m-1}),$

where
$\mathbb{P}(b_{i}|b_{1},\dots,b_{i-1})=\frac{\mathbb{P}(b_{i})}{(1-\mathbb{P}(b_{1})\;-\;\cdots\;-\;\mathbb{P}(b_{i-1}))}$.
$Z(A)$ is the probability of choosing $b_{1},b_{2},\dots,b_{m}$ from the set
$[k]$ without replacement.222We see that $\sum_{A}Z(A)=1$ as follows.
$\displaystyle\sum_{A}Z(A)$
$\displaystyle=\sum_{A}\mathbb{P}(b_{1})\dots\mathbb{P}(b_{m}|b_{1},b_{2},\dots,b_{m-1})$
$\displaystyle=\sum_{b_{1}}\mathbb{P}(b_{1})\dots\sum_{b_{m}}\frac{\mathbb{P}(b_{m})}{(1-\mathbb{P}(b_{1})\dots-\mathbb{P}(b_{m-1}))}$
But,
$\sum_{b_{i}}\frac{\mathbb{P}(b_{i})}{(1-\mathbb{P}(b_{1})-\dots-\mathbb{P}(b_{i-1})}=1$.
Thus, $\sum_{A}Z(A)=1$.

We randomly sample $\tilde{Y}^{t}$ from $Z$ and predict $\tilde{Y}^{t}$. We
receive the diluted bandit feedback $\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$.
We update the weight matrix as $W^{t+1}=W^{t}+\tilde{U}^{t}$, where

$\displaystyle\tilde{U}^{t}_{r,j}=x^{t}_{j}\Big{(}\frac{\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}\mathbb{I}{\\{r\in\tilde{Y}^{t}\\}}}{Z(\tilde{Y}^{t})\tau_{1}}-\frac{\mathbb{I}\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}{m}-\tau_{2}\Big{)}$
(6)

where $\tau_{1}=m\;^{k-2\mkern-2.5mu}{}P_{m-1}$ and
$\tau_{2}=\frac{m-1}{k-m}$. $\tilde{U}^{t}$ accesses $y^{t}$ only through the
indicator $\mathbb{I}{\\{y^{t}\in\tilde{Y}^{t}\\}}$. We will see that
$\tilde{U}^{t}$ is an unbiased estimator of $U^{t}$ using the following Lemma.

######  Lemma 4.

Consider $\tilde{U}^{t}$ defined in Eq.(6). Then,
$\mathbb{E}_{Z}[\tilde{U}^{t}]=U^{t}$, where $U^{t}$ is defined in Eq.(4).

##  4 Mistake Bound Analysis of MC-DBF

In this section, we derive the expected mistake bound
($\mathbb{E}_{Z}[\hat{M}]$) for the proposed approach MC-DBF (Algorithm 2). To
get the mistake bound, we first need to derive some intermediate results. We
first derive an upper bound the expected value of the Frobenius norm of the
update matrix $\tilde{U}^{t}$.

######  Lemma 5.

$\displaystyle\mathbb{E}_{Z}[||\tilde{U}^{t}||^{2}_{F}]\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}$
$\displaystyle+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\Big{]}+\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$

Now we derive the expected mistake bound $\mathbb{E}_{Z}[\hat{M}]$ using
Theorem as follows.

######  Theorem 6.

Assume that for the sequence of examples,
$(\mathbf{x}^{1},y^{1}),\dots,(\mathbf{x}^{t},y^{t})$, we have, for all $t$,
$\mathbf{x}^{t}\in\mathbb{R}^{d}$, $||\mathbf{x}^{t}||\leq 1$ and
$y^{t}\in[k]$. Let $W^{*}$ be any matrix and let $R_{T}$ be the cumulative
average hinge loss of $W^{*}$ defined as follows.

$\begin{split}R_{T}&=\sum_{t=1}^{T}L_{avg}(W^{*},(\mathbf{x}^{t},y^{t})).\end{split}$

Let $D$ be the complexity of $W^{*}$ defined as below: $D=2||W^{*}||^{2}_{F}$.
Then the number of mistakes $\hat{M}$ made by the Algorithm 2 satisfies

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
R_{T}+\sqrt{\frac{\lambda_{1}DR_{T}}{2}}+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)$
$\displaystyle\qquad+\gamma T.$ (7)

where
$\hat{M}=\sum_{t=1}^{T}\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}$,
$\lambda_{1}=\frac{2}{\tau_{1}}$ and

$\begin{split}\lambda_{2}&=\big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\big{]}\end{split}$

We will now analyze different cases and find out the mistake bound in those
cases. Before going ahead, we state a new separability definition as follows.

######  Definition 7.

Linear Separability: A sequence of examples,
$(\mathbf{x}^{1},y^{1}),\dots,(\mathbf{x}^{T},y^{T})$ is linearly separable if
there exists a matrix $W^{*}\in\mathbb{R}^{k\times d}$ such that

$(W^{*}\mathbf{x}^{t})_{y^{t}}-(W^{*}\mathbf{x}^{t})_{i}\;\geq\;1,\;\forall
i\neq y^{t},\;\forall t\in[T].$

Note that linear separability also implies
$(W^{*}\mathbf{x}^{t})_{y^{t}}-\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x},W^{*})}(W^{*}\mathbf{x}^{t})_{i}\geq
1,\forall t\in[T]$. Which implies
$L_{avg}(W^{*},(\mathbf{x}^{t},y^{t}))=0,\;\forall t\in[T]$. Thus, when a
sequence of examples $(\mathbf{x}^{1},y^{1}),\dots,(\mathbf{x}^{T},y^{T})$ is
linearly separable with respect to a weight matrix $W^{*}$, then

$R_{T}=\sum_{t=1}^{T}L_{avg}(W^{*},(\mathbf{x}^{t},y^{t}))=0.$

######  Corollary 8.

Let $(\mathbf{x}^{1},y^{1}),\dots,(\mathbf{x}^{T},y^{T})$ be the sequence of
examples which are linearly separable. Then algorithm MC-DBF achieves
$\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$ mistake bound on it.

######  Corollary 9.

Moreover, if we consider $R_{T}\leq\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$, by
setting $\gamma=\mathcal{O}((\frac{1}{T})^{\frac{1}{(m+2)}})$, we get that
$\mathbb{E}_{Z}[\hat{M}]\leq\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$.

Thus, we see that on increasing $m$, running time complexity of the algorithm
also increases.

Figure 2: Searching best value of $\gamma$: graphs show converged error rates
for MC-DBF (with different values of $m$) and Second Order Banditron (SOBA)
for varying values of $\gamma$. The $\gamma$ values on the X-axis are on a
$\log$ scale.

Figure 3: Comparison of MC-DBF Algorithm using different values of $m$ with
Perceptron (benchmark algorithm with full information feedback) and Second
Order Banditron (SOBA) (benchmark algorithm for bandit feedback).

Figure 4: Comparison of MC-DBF Algorithm with different values of $m$ with MC-
SLP

Figure 5: Plot to show the variation of the error rate of MC-DBF algorithm
with different values of $m$.

##  5 Experiments

This section shows the experimental results of the proposed algorithm MC-DBF
(Algorithm 2) and its comparison with other benchmark algorithms on various
datasets.

###  5.1 Datasets Used and Preprocessing

We use CIFAR-10 Krizhevsky et al. [2009], SVHN Netzer et al. [2011], MNIST
LeCun et al. [2010] and Fashion-MNIST Xiao et al. [2017] datasets to show
experimental results. We use VGG-16 Simonyan and Zisserman [2014] model that
is pre-trained on ImageNet dataset to extract the features. We use TensorFlow
framework Abadi et al. [2015] on all the datasets mentioned above for feature
extraction using VGG-16. All the experiments have been executed on a machine
with Intel (R) Xeon(R) CPU @ 2.30 GHz with 12.72 Gb of RAM.

The images are passed through the VGG-16 network, and then relevant features
are extracted from the last layer of VGG-16 network. The final dimension of
the features extracted for each dataset is 512.

In addition to the datasets mentioned above, we also use a synthetic linearly
separable dataset SYNSEP Kakade et al. [2008] for the purpose of comparison.

###  5.2 Benchmark Algorithms

We compare the proposed approach MC-DBF with Perceptron Crammer and Singer
[2003], which is an algorithm for full information setting, Second Order
Banditron (SOBA) Beygelzimer et al. [2017], which is a bandit feedback
algorithm. We also compare with MC-SLP, which is a full information version of
MC-DBF. We will use three types of values of $m$ \- (low, medium, high) in MC-
DBF to observe the effect of variations in $m$.

###  5.3 Experimental Setup and Performance Metric

We run each of the algorithms mentioned above for $1,000,000$ iterations for
$10$ independent runs for every dataset. In each iteration, we calculate the
error rate (number of incorrectly classified samples averaged over the total
number of rounds). For calculating the error rate we compare the ground truth
label $y_{t}$, with the predicted label
$\hat{y}^{t}=\arg\max_{j\in[k]}\;(W^{t}\mathbf{x}^{t})_{j}$. The final plots
have error rate averaged over the $10$ independent trials on the Y-axis and
number of trials on the X-axis.

###  5.4 Choosing Optimal value of $\gamma$ in MC-DBF

MC-DBF takes $\gamma$ as a parameter. To choose the parameter’s best values,
we plot the trend of error rates for varying values of $\gamma$. We choose the
value of $\gamma$ for which the error rate value is minimized from these
plots. While calculating the error rate, we compare the true label $y_{t}$
with the predicted label
$\hat{y}^{t}=\arg\max_{j\in[k]}\;(W^{t}\mathbf{x}^{t})_{j}$. We use a similar
process to get optimal values of hyper-parameters for the other benchmark
algorithms.

Figure 2 shows the trend of the converged error rates with $\log(\gamma)$ on
all the datasets for all the algorithms. The best values of $\gamma$ for MCDBF
for different datasets have been summarized in Table 1. All the final plots
have been made using these optimal values.

SOBA
---
Dataset | $\gamma$
MNIST | 0.02
Fashion-MNIST | 0.1
CIFAR-10 | 0.3
SVHN | 0.25

MC-DBF ($m$: low)
---
Dataset | $\gamma$
MNIST | 0.12
Fashion-MNIST | 0.12
CIFAR-10 | 0.28
SVHN | 0.31

MC-DBF ($m$: medium)
---
Dataset | $\gamma$
MNIST | 0.12
Fashion-MNIST | 0.2
CIFAR-10 | 0.25
SVHN | 0.3

MC-DBF ($m$: high)
---
Dataset | $\gamma$
MNIST | 0.25
Fashion-MNIST | 0.3
CIFAR-10 | 0.3
SVHN | 0.5

Table 1: Optimal values of $\gamma$ for different algorithms

###  5.5 Comparison of MC-BDF with Benchmarking algorithms

Figure 3 presents the comparison results of our proposed algorithm (MC-DBF)
using different values of $m$ with Perceptron Crammer and Singer [2003] (full
information setting) and Second Order Banditron (SOBA) Beygelzimer et al.
[2017] (bandit feedback setting).
We observe the MC-DBF algorithm performs well for low and medium values of
$m$. Its performance is comparable to the Banditron algorithm in almost all
the datasets and even comparable to Perceptron in the Fashion-MNIST and SVHN
datasets for low values of $m$. We must keep in mind that increasing the value
of $m$ forces the value of feedback to become more diluted, which is correctly
demonstrated by high values of $m$ in the figure.

Figure 4 show the comparison reults of our proposed algorithm MC-DBF with MC-
SLF (full information version of MC-DBF) for different values of $m$. We
observe that MC-DBF converges to MC-SLF in all the datasets, which is expected
as according to Lemma 4 $E_{Z}[\tilde{U}]=U$.

Figure 6 shows the comparison of the various benchmark algorithms with our
proposed algorithm (MC-DBF) using different values of $m$ on the SYNSEP
dataset, which is a linearly separable dataset. The $x$ and $y$ axes have been
plotted on a log scale. From the figure, we observe that our proposed
algorithm performs comparable to Second Order Banditron (SOBA), in the
linearly separable case as well.

###  5.6 Effect of changing values of $m$

Figure 5 shows the trend of the error rate of MC-DBF versus $m$ for all the
datasets. We observe that the error rate increases on increasing $m$ which is
not surprising as increasing $m$ implies feedback to the algorithm becomes
increasing dilute leading to increasing error-rate for the same number of
rounds and constant $\gamma$.

Figure 6: Plot to show the variation of the error rate of MC-DBF algorithm
with other benchmark algorithms on SYNSEP (linearly separable dataset)

##  6 Conclusion

This paper proposed a multiclass classification algorithm that uses diluted
bandit feedback for training, namely MC-BDF. We used the exploration-
exploitation strategy to predict a subset of labels in each trial. We then
update the matrix, using an unbiased estimator of the MC-SLP update matrix
(full information version of MC-DBF). We also proved the upper bound for the
expected number of mistakes made by our algorithm. We also experimentally
compared MC-DBF with other benchmark algorithms for the full/bandit feedback
settings on various datasets. The results show that our algorithm MC-DBF
performs comparably to the benchmark algorithms, despite receiving lesser
feedback on most of the datasets.

## References

  * Abadi et al. [2015] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL http://tensorflow.org/.  Software available from tensorflow.org.
  * Arora and Manwani [2020] Maanik Arora and Naresh Manwani.  Exact passive-aggressive algorithms for multiclass classification using bandit feedbacks.  In _Proceedings of The 12th Asian Conference on Machine Learning_ , volume 129, pages 369–384, Bangkok, Thailand, 18–20 Nov 2020.
  * Arora and Manwani [2021] Maanik Arora and Naresh Manwani.  Exact passive aggressive algorithm for multiclass classification using partial labels.  In _8th ACM IKDD CODS and 26th COMAD_ , page 38–46, 2021.
  * Beygelzimer et al. [2017] Alina Beygelzimer, Francesco Orabona, and Chicheng Zhang.  Efficient online bandit multiclass learning with $\tilde{O}(\sqrt{T})$ regret.  _CoRR_ , abs/1702.07958, 2017.  URL http://arxiv.org/abs/1702.07958.
  * Bhattacharjee and Manwani [2020] Rajarshi Bhattacharjee and Naresh Manwani.  Online algorithms for multiclass classification using partial labels.  In _Proceedings of the 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)_ , pages 249–260, 2020.
  * Crammer and Singer [2003] Koby Crammer and Yoram Singer.  Ultraconservative online algorithms for multiclass problems.  _J. Mach. Learn. Res._ , 3(null):951–991, March 2003.
  * Fink et al. [2006] Michael Fink, Shai Shalev-Shwartz, Yoram Singer, and Shimon Ullman.  Online multiclass learning by interclass hypothesis sharing.  pages 313–320, 01 2006.  10.1145/1143844.1143884.
  * Hazan and Kale [2011a] Elad Hazan and Satyen Kale.  Newtron: An efficient bandit algorithm for online multiclass prediction.  In _Proceedings of the 24th International Conference on Neural Information Processing Systems_ , page 891–899, 2011a.
  * Hazan and Kale [2011b] Elad Hazan and Satyen Kale.  Newtron: an efficient bandit algorithm for online multiclass prediction.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 891–899. Curran Associates, Inc., 2011b.  URL https://proceedings.neurips.cc/paper/2011/file/fde9264cf376fffe2ee4ddf4a988880d-Paper.pdf.
  * Kakade et al. [2008] Sham M. Kakade, Shai Shalev-Shwartz, and Ambuj Tewari.  Efficient bandit algorithms for online multiclass prediction.  In _Proceedings of the 25th International Conference on Machine Learning_ , ICML ’08, page 440–447, 2008.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. [2010] Yann LeCun, Corinna Cortes, and CJ Burges.  Mnist handwritten digit database.  _ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist_ , 2, 2010.
  * Matsushima et al. [2010] Shin Matsushima, Nobuyuki Shimizu, Kazuhiro Yoshida, Takashi Ninomiya, and Hiroshi Nakagawa.  Exact passive-aggressive algorithm for multiclass classification using support class.  In _Proceedings of the SIAM International Conference on Data Mining, SDM 2010, Columbus, Ohio, USA_ , pages 303–314, 2010.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng.  Reading digits in natural images with unsupervised feature learning.  _NIPS_ , 01 2011.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _CoRR_ , abs/1409.1556, 2014.  URL http://arxiv.org/abs/1409.1556.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.

Multiclass Classification using dilute bandit feedback - Supplementary
Material

##  7 Proof of Lemma 2

There are basically two cases that we have to analyse.

  * •

$y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})$: In this case, we see that
$\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}$
due to the way $\hat{Y}(\mathbf{x}^{t},W^{t})$ is generated. Thus,

$\begin{split}L_{avg}=1-(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq
1\\\ =\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}\end{split}$

  * •

$y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})$:

$\begin{split}L_{avg}=\Big{[}1-(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\Big{]}_{+}\\\
\geq 0=\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}\end{split}$

Therefore,
$L_{avg}\geq\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}$.

##  8 Proof of Lemma 3

We know from the definition of $U^{t}$, that

$\begin{split}U^{t}_{r,j}=x^{t}_{j}\Big{(}\mathbb{I}{\\{r=y_{t}\\}}-\frac{\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}}{m}\Big{)}\end{split}$
(8)

Substituting this in $\langle W^{t},U^{t}\rangle$ results in,

$\begin{split}\langle W^{t},U^{t}\rangle\
=(W^{t}\cdot\mathbf{x}^{t})_{y^{t}}-\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\end{split}$
(9)

We now have three cases:

  * •

$y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})$: This implies that

$\begin{split}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq(W^{t}\cdot\mathbf{x}^{t})_{y^{t}}\quad\forall
i\in\hat{Y}(\mathbf{x}^{t},W^{t})\end{split}$

Summing over all $i\in\hat{Y}(\mathbf{x}^{t},W^{t})$, we get

$\displaystyle\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}$
$\displaystyle\Rightarrow\;\;$ $\displaystyle
1-(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq
0.$

Thus,

$\begin{split}L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))&=1-(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\\\
&=1\;-\;\langle W^{t},U^{t}\rangle\\\
&=\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}\;-\;\langle
W^{t},U^{t}\rangle\end{split}$

  * •

$y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})$ and
$\frac{1}{m}\sum_{i}(W^{t}\cdot\mathbf{x}^{t})_{i}\geq(W^{t}\cdot\mathbf{x}^{t})_{y^{t}}$:
In this case also,

$\begin{split}L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))&=1-(W^{t}\cdot\mathbf{x}^{t})_{y_{t}}+\frac{1}{m}\sum_{i\in\hat{Y}(\mathbf{x}^{t},W^{t})}(W^{t}\cdot\mathbf{x}^{t})_{i}\\\
&=1-\langle W^{t},U^{t}\rangle\\\ {}&\geq-\langle W^{t},U^{t}\rangle\\\
&=\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}\;-\;\langle
W^{t},U^{t}\rangle\end{split}$

  * •

$y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})$ and
$\frac{1}{m}\sum_{i}(W^{t}\cdot\mathbf{x}^{t})_{i}<(W^{t}\cdot\mathbf{x}^{t})_{y^{t}}$:

In this case, using Eq.(9), we get

$\begin{split}\langle W^{t},U^{t}\rangle\ >0\end{split}$

As $L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))\geq 0$ by definition of hinge loss,
we get

$\begin{split}L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))&\geq 0\\\ {}&>-\;\langle
W^{t},U^{t}\rangle\\\
&=\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}\;-\;\langle
W^{t},U^{t}\rangle\end{split}$

Hence, using from these three cases, we infer that

$\begin{split}L_{avg}(W^{t},(\mathbf{x}^{t},y^{t}))\geq\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}-\langle
W^{t},U^{t}\rangle\end{split}$

##  9 Proof of Lemma 4

For all $r\in[k]$ and for all $j\in[d]$ we have:

$\displaystyle\mathbb{E}_{Z}[\tilde{U}^{t}_{r,j}]=\sum_{A}Z(A)x^{t}_{j}\Big{(}\frac{\mathbb{I}{\\{y^{t}\in
A\\}}\mathbb{I}{\\{r\in
A\\}}}{Z(A)(m^{k-2\mkern-2.5mu}{}P_{m-1})}-\frac{\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}}{m}$
$\displaystyle-\frac{m-1}{k-m}\Big{)}$
$\displaystyle=x^{t}_{j}\Big{(}\frac{\sum_{A}\mathbb{I}{\\{y^{t}\in
A\\}}\mathbb{I}{\\{r\in
A\\}}}{m^{k-2\mkern-2.5mu}{}P_{m-1}}-\frac{\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}}{m}-\frac{m-1}{k-m}\Big{)}$
(10)

Now, we simplify the term $\sum_{A}\mathbb{I}{\\{y^{t}\in
A\\}}\mathbb{I}{\\{r\in A\\}}$. We know that
$\mathbb{I}{\\{r=y^{t}\\}}+\mathbb{I}{\\{r\neq y^{t}\\}}=1$. We use this to
simplify the above expression as follows:

$\displaystyle\sum_{A}\mathbb{I}{\\{y^{t}\in A\\}}\mathbb{I}{\\{r\in A\\}}$
$\displaystyle=\sum_{A}\mathbb{I}{\\{y^{t}\in A\\}}\mathbb{I}{\\{r\in
A\\}}\mathbb{I}{\\{r=y^{t}\\}}$ $\displaystyle+\sum_{A}\mathbb{I}{\\{y^{t}\in
A\\}}\mathbb{I}{\\{r\in A\\}}\mathbb{I}{\\{r\neq y^{t}\\}}$

Number of sets $A$ satisfying condition $\mathbb{I}{\\{y^{t}\in
A\\}}\mathbb{I}{\\{r\in A\\}}\mathbb{I}{\\{r=y^{t}\\}}=1$ are
$m(^{k-1\mkern-2.5mu}{}P_{m-1})$. Also, number of sets $A$ that satisfy the
condition $\mathbb{I}{\\{y^{t}\in A\\}}\mathbb{I}{\\{r\in
A\\}}\mathbb{I}{\\{r\neq y^{t}\\}}=1$ are
$m(m-1)(^{k-2\mkern-2.5mu}{}P_{m-2})$. Therefore,

$\displaystyle\sum_{A}\mathbb{I}{\\{y^{t}\in A\\}}\mathbb{I}{\\{r\in
A\\}}=m(^{k-1\mkern-2.5mu}{}P_{m-1})\mathbb{I}{\\{r=y^{t}\\}}+$
$\displaystyle\qquad\qquad
m(m-1)(^{k-2\mkern-2.5mu}{}P_{m-2})\mathbb{I}{\\{r\neq y^{t}\\}}$
$\displaystyle=m(^{k-2\mkern-2.5mu}{}P_{m-1})\mathbb{I}{\\{r=y^{t}\\}}+m(m-1)(^{k-2\mkern-2.5mu}{}P_{m-2})$
(11)

We can verify the expression by setting $m=1$ in Eq.(11). The L.H.S. evaluates
to $\mathbb{I}{\\{r=y^{t}\\}}$ as $A$ reduces to a singleton set. Similarly,
the R.H.S. also reduces to $\mathbb{I}{\\{r=y^{t}\\}}$. Plugging the value
obtained in Eq.(11) in Eq.(10), we get

$\displaystyle\mathbb{E}_{Z}[\tilde{U}_{r,j}^{t}]=x^{t}_{j}\Big{(}\mathbb{I}{\\{r=y^{t}\\}}+\frac{m(m-1)\;\;^{k-2\mkern-2.5mu}{}P_{m-2}}{m\;\;^{k-2\mkern-2.5mu}{}P_{m-1}}-$
$\displaystyle\qquad\qquad\;\;\;\;-\frac{1}{m}\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}-\frac{m-1}{k-m}\Big{)}$
$\displaystyle=x^{t}_{j}\Big{(}\mathbb{I}{\\{r=y^{t}\\}}-\frac{1}{m}\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}\Big{)}=U^{t}_{r,j}\
(Eq.(\ref{Update-Matrix}))$

Thus, we have proved that $\mathbb{E}_{Z}[\tilde{U}^{t}]=U^{t}$.

##  10 Proof of Lemma 5

We first find a lower bound on the probability of a superarm $A$.

######  Proposition 10.

Let $A=\\{b_{1},\cdots,b_{m}\\}\in\mathbb{S}$ and $Z(A)$ be the probability of
selecting super-arm $A$. Then, we can show that
$Z(A)\geq\frac{\gamma}{k}\left({\frac{2}{m}}\right)^{m-1}e^{-(m-1)}.$

###### Proof.

As $Z(A)$ is the probability of choosing $\\{b_{1},b_{2},\cdots,b_{m}\\}$ from
the set $[k]$ without replacement. We see that

$\begin{split}Z(A)&=\mathbb{P}(b_{1})\mathbb{P}(b_{2}|b_{1})\dots\mathbb{P}(b_{m}|b_{1},\dots,b_{m-1})\\\
{}&=\frac{\prod_{i}^{m}\mathbb{P}(b_{i})}{\prod_{i}^{m}(1-\sum_{j=1}^{i-1}\mathbb{P}(b_{j}))}\geq\prod_{i}^{m}\mathbb{P}(b_{i})\geq\left(\frac{\gamma}{k}\right)^{m},\end{split}$

where the last inequality holds because
$\mathbb{P}(b_{i})\geq\frac{\gamma}{k},\;\forall i$ (as
$P(b_{i})=\frac{(1-\gamma)}{m}\mathbb{I}{\\{b_{i}\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}+\frac{\gamma}{k}$).
∎

We first compute the value of $||\tilde{U}^{t}||^{2}_{F}$. There are 2 cases
possible.

  * •

$y^{t}\notin\tilde{Y}^{t}$:
$\tilde{U}^{t}_{r,j}=x^{t}_{j}\Big{[}-\tau_{2}-\frac{\mathbb{I}{\\{r\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}}}{m}\Big{]}$

$\displaystyle||\tilde{U}^{t}||^{2}_{F}$
$\displaystyle=||\mathbf{x}^{t}||^{2}_{2}\Big{[}m\big{[}\tau_{2}+\frac{1}{m}\big{]}^{2}+(k-m)\big{[}\tau_{2}\big{]}^{2}\Big{]}$
$\displaystyle\mathbb{E}[||\tilde{U}^{t}||^{2}_{F}|y^{t}\notin\tilde{Y}^{t}]$
$\displaystyle=||\mathbf{x}^{t}||^{2}_{2}\Big{[}m\big{[}\tau_{2}+\frac{1}{m}\big{]}^{2}+(k-m)\big{[}\tau_{2}\big{]}^{2}\Big{]}$

  * •

$y^{t}\in\tilde{Y}^{t}$:

$\displaystyle||\tilde{U}^{t}||^{2}_{F}=||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{Z(\tilde{Y}^{t})^{2}\tau_{1}^{2}}-\frac{2m\tau_{2}}{Z(\tilde{Y}^{t})\tau_{1}}+m[\tau_{2}+\frac{1}{m}]^{2}$
$\displaystyle+(k-m)\big{[}\tau_{2}^{2}\big{]}-\frac{2}{Z(\tilde{Y}^{t})\tau_{1}}\sum_{r}\mathbb{I}\\{y^{t}\in\tilde{Y}^{t}\\}\mathbb{I}\\{y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}\Big{]}$
$\displaystyle\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{Z(\tilde{Y}^{t})^{2}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}+m[\tau_{2}+\frac{1}{m}]^{2}$
$\displaystyle+(k-m)\big{[}\tau_{2}^{2}\big{]}-\frac{2}{\tau_{1}}\Big{]}\mathbb{I}\\{y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle+||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{Z(\tilde{Y}^{t})^{2}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}+m[\tau_{2}+\frac{1}{m}]^{2}$
$\displaystyle+(k-m)\big{[}\tau_{2}^{2}\big{]}\Big{]}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle=-\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\in\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle+||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{Z(\tilde{Y}^{t})^{2}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}+m[\tau_{2}+\frac{1}{m}]^{2}$
$\displaystyle+(k-m)\big{[}\tau_{2}^{2}\big{]}\Big{]}$
$\displaystyle=\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle+||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{Z(\tilde{Y}^{t})^{2}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}+m[\tau_{2}+\frac{1}{m}]^{2}$
$\displaystyle+(k-m)\big{[}\tau_{2}^{2}\big{]}-\frac{2}{\tau_{1}}\Big{]}$

Taking expectation on both sides, we get the following.

$\displaystyle\mathbb{E}[||\tilde{U}^{t}||^{2}_{F}|y^{t}\in\tilde{Y}^{t}]\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{m}{\tau_{1}^{2}}\sum_{\tilde{Y}^{t}:y^{t}\in\tilde{Y}^{t}}\frac{1}{Z(\tilde{Y}^{t})}$
$\displaystyle+m[\tau_{2}+\frac{1}{m}]^{2}+(k-m)\big{[}\tau_{2}^{2}\big{]}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}\Big{]}$
$\displaystyle+\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$

We use the lower bound on $Z(A),\;A\in\mathbb{S}$ derived in Proposition 10.
Also, using the fact that
$|\\{\tilde{Y}^{t}|y^{t}\in\tilde{Y}^{t}\\}|\;\leq\;^{k\mkern-2.5mu}{}P_{m}$,
we get

$\displaystyle\mathbb{E}[||\tilde{U}^{t}||^{2}_{F}|y^{t}\in\tilde{Y}^{t}]\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}$
$\displaystyle+m[\tau_{2}+\frac{1}{m}]^{2}+(k-m)\big{[}\tau_{2}^{2}\big{]}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}\Big{]}$
$\displaystyle+\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$

Let $\Gamma=\mathbb{P}(y^{t}\in\tilde{Y}^{t})$. Thus,
$\mathbb{E}_{Z}[||\tilde{U}^{t}||^{2}_{F}]$ can be upper bounded as follows.

$\displaystyle\mathbb{E}_{Z}[||\tilde{U}^{t}||^{2}_{F}]=\mathbb{P}(y^{t}\in\tilde{Y}^{t})\mathbb{E}[||\tilde{U}^{t}||^{2}_{F}|y^{t}\in\tilde{Y}^{t}]$
$\displaystyle\quad+\left(1-\mathbb{P}(y^{t}\in\tilde{Y}^{t})\right)\mathbb{E}[||\tilde{U}^{t}||^{2}_{F}|y^{t}\notin\tilde{Y}^{t}]$
$\displaystyle\leq\Gamma||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}$
$\displaystyle\qquad+m[\tau_{2}+\frac{1}{m}]^{2}+(k-m)\big{[}\tau_{2}^{2}\big{]}\Big{]}$
$\displaystyle+\frac{2\Gamma||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle+(1-\Gamma)||\mathbf{x}^{t}||^{2}_{2}\Big{[}m\big{[}\tau_{2}+\frac{1}{m}\big{]}^{2}+(k-m)\big{[}\tau_{2}\big{]}^{2}\Big{]}$
$\displaystyle=\Gamma||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}\Big{]}$
$\displaystyle+||\mathbf{x}^{t}||^{2}_{2}(k-m)\big{[}\tau_{2}\big{]}^{2}+||\mathbf{x}^{t}||^{2}_{2}m\big{[}\tau_{2}+\frac{1}{m}\big{]}^{2}$
$\displaystyle+\frac{2\Gamma||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$
$\displaystyle\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}\Big{]}$
$\displaystyle\qquad+||\mathbf{x}^{t}||^{2}_{2}(k-m)\big{[}\tau_{2}\big{]}^{2}+||\mathbf{x}^{t}||^{2}_{2}m\big{[}\tau_{2}+\frac{1}{m}\big{]}^{2}$
$\displaystyle+\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$

Thus we get,

$\displaystyle\mathbb{E}_{Z}[||\tilde{U}^{t}||^{2}_{F}]$
$\displaystyle\leq||\mathbf{x}^{t}||^{2}_{2}\Big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}$
$\displaystyle\;\;+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\Big{]}$
$\displaystyle+\frac{2||\mathbf{x}^{t}||^{2}_{2}}{\tau_{1}}\mathbb{I}\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}$

##  11 Proof of Theorem 6

We start the proof by defining the inner product between two matrix $W^{*}$
and $W_{t}$ as follows:

$\begin{split}\langle
W^{*},W^{t}\rangle=\sum_{r=1}^{k}\sum_{j=1}^{d}W^{*}_{r,j}W^{t}_{r,j}\end{split}$
(12)

We will next try to upper-bound and lower-bound $\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]$, with the assumption that $W^{1}=0$. Let us first start
with lower-bound.

#### Lower-bound of $\mathbb{E}_{Z}[\langle W^{*},W^{T+1}\rangle]$:

We first define a new variable $\Delta_{t}$:

$\begin{split}\Delta_{t}=\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]-\mathbb{E}_{Z}[\langle W^{*},W^{t}\rangle]\end{split}$
(13)

Also, we know from the definition of Update Matrix $\tilde{U}^{t}$, that
$W^{t+1}=W^{t}+\tilde{U}^{t}$. Substituting this in the above equation gives,

$\begin{split}\Delta_{t}=\mathbb{E}_{Z}[\langle
W^{*},\tilde{U}^{t}\rangle]\end{split}$

Also, using Lemma 4, we obtain that $\forall t$,

$\begin{split}\Delta_{t}=\mathbb{E}_{Z}[\langle
W^{*},{U}^{t}\rangle]\end{split}$

Using Lemma 3, we know that,

$\begin{split}L_{avg}(W^{*},(\mathbf{x}^{t},y^{t}))\geq\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{*})\\}}-\langle
W^{*},{U}^{t}\rangle\end{split}$ (14)

Therefore, taking Expectation on both sides and summing over $t$ we get

$\begin{split}\sum_{t}\Delta_{t}&\geq\sum_{t}\mathbb{E}_{Z}[\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}]-\sum_{t}L_{avg}(W^{*},(\mathbf{x}^{t},y^{t}))\\\
{}&\geq\mathbb{E}_{Z}[{M}]-R_{T}\end{split}$ (15)

where ${M}=\sum_{t}\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}$
and $R_{T}$ is the cumulative hinge loss defined.

Therefore,

$\begin{split}\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]&=\sum_{t}\Delta_{t}\geq\mathbb{E}_{Z}[M]-R_{T}\end{split}$
(16)

Hence we get the lower-bound for $\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]$. Now we will try to derive its upper bound.

#### Upper-bound on $\mathbb{E}_{Z}[\langle W^{*},W^{T+1}\rangle]$:

Using Cauchy-Schwartz inequality, we get the following,

$\begin{split}\langle W^{*},W^{T+1}\rangle&\
\leq||W^{*}||_{F}||W^{T+1}||_{F}\end{split}$ (17)

where $||.||_{F}$ is the Frobenius Norm. Using the definition of $D$,the
concavity of the square root function and Jensen’s inequality, we can obtain
that

$\begin{split}\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]&\leq\sqrt{\frac{D\mathbb{E}_{Z}[||W^{T+1}||_{F}^{2}]}{2}}\end{split}$
(18)

Now, we need to upper bound the expected value of $||W^{T+1}||_{F}^{2}$. Using
the definition of $W^{T+1}$, we get

$\begin{split}\mathbb{E}_{Z}[||W^{T+1}||_{F}^{2}]&=\mathbb{E}_{Z}[||W^{T}||_{F}^{2}+\langle
W^{T},\tilde{U}^{T}\rangle+||\tilde{U}^{T}||_{F}^{2}]\\\
{}&=\sum_{t=1}^{T}\left(\mathbb{E}_{Z}[\langle
W^{t},\tilde{U}^{t}\rangle]+\mathbb{E}_{Z}[||\tilde{U}^{t}||_{F}^{2}]\right)\end{split}$
(19)

Using Lemma 4 , we know that

$\begin{split}\mathbb{E}_{Z}[\langle
W^{t},\tilde{U}^{t}\rangle]&=\mathbb{E}_{Z}[\langle
W^{t},U^{t}\rangle]\end{split}$ (20)

Using Lemma 5, we can also obtain an Upper bound on
$\mathbb{E}_{Z}[||\tilde{U}^{t}||_{F}^{2}]$ of the form:

$\begin{split}\mathbb{E}_{Z}[||\tilde{U}^{t}||_{F}^{2}]&\leq||\mathbf{x}^{t}||^{2}\left[\lambda_{1}\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}+\lambda_{2}\right]\end{split}$
(21)

where $\lambda_{1}$ and $\lambda_{2}$ are as defined below:

$\begin{split}\lambda_{1}&=\frac{2}{\tau_{1}}\\\
\lambda_{2}&=\big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\big{]}\end{split}$
(22)

Also, using the Cauchy-Schwartz inequality again we get

$\begin{split}\langle W^{t},U^{t}\rangle\
\leq||W^{t}||_{F}^{2}||U^{t}||_{F}^{2}\leq 1\end{split}$ (23)

If we use Eq. (19) and (21) and assume $||\mathbf{x}^{t}||\leq 1\ \forall t$,
we can obtain that

$\begin{split}\mathbb{E}_{Z}[||W^{T+1}||^{2}]&\leq\sum_{t=1}^{T}\mathbb{E}_{Z}\left[\lambda_{1}\mathbb{I}{\\{y^{t}\notin\hat{Y}(\mathbf{x}^{t},W^{t})\\}}+\lambda_{2}+1\right]\\\
{}&\leq\lambda_{1}\mathbb{E}_{Z}[{M}]+(\lambda_{2}+1)T\end{split}$ (24)

Substituting this in Eq. (18) and using the inequality
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, we can upper-bound $\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]$ as follows:

$\begin{split}\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]&\leq\sqrt{\frac{D\mathbb{E}_{Z}[||W^{T+1}||_{F}^{2}]}{2}}\\\
{}&\leq\sqrt{\frac{\lambda_{1}D\mathbb{E}_{Z}[{M}]}{2}}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\end{split}$
(25)

Now, we have both the upper bound and lower-bound for $\mathbb{E}_{Z}[\langle
W^{*},W^{T+1}\rangle]$. We compare these two bounds, to obtain

$\begin{split}\mathbb{E}_{Z}[{M}]-\sqrt{\frac{\lambda_{1}D\mathbb{E}_{Z}[{M}]}{2}}-\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\leq
0\end{split}$ (26)

Some simple algebraic manipulation as shown in Proposition 11 shows that

$\begin{split}\mathbb{E}_{Z}[{M}]&\leq R_{T}+\sqrt{\frac{\lambda_{1}DL}{2}}\\\
{}&+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\end{split}$
(27)

Now as $\mathbb{E}_{Z}[{M}]+\gamma T\geq\mathbb{E}_{Z}[\hat{M}]$ because we
are not exploring for more than $\gamma T$ rounds, we get

$\begin{split}\mathbb{E}_{Z}[\hat{M}]&\leq
R_{T}+\sqrt{\frac{\lambda_{1}DL}{2}}\\\
{}&+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)+\gamma
T\end{split}$ (28)

######  Proposition 11.

If we are given that,

$\begin{split}\mathbb{E}_{Z}[\hat{M}]-\sqrt{\frac{\lambda_{1}D\mathbb{E}_{Z}[\hat{M}]}{2}}-\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\leq
0,\end{split}$

then we can prove that,

$\begin{split}\mathbb{E}_{Z}[\hat{M}]&\leq
R_{T}+\sqrt{\frac{\lambda_{1}DR_{T}}{2}}+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\end{split}$

###### Proof.

We are given that,

$\begin{split}\mathbb{E}_{Z}[{M}]-\sqrt{\frac{\lambda_{1}D\mathbb{E}_{Z}[{M}]}{2}}-\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\leq
0\end{split}$ (29)

As $\mathbb{E}_{Z}[{M}]\geq 0$, let us assume that
$x^{2}=\mathbb{E}_{Z}[{M}]$. Therefore, the equation becomes,

$\begin{split}x^{2}-\sqrt{\frac{\lambda_{1}D}{2}}x-\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\leq
0\end{split}$ (30)

This is the equation of a convex quadratic equation, with roots as:

$\begin{split}x=\frac{\sqrt{\frac{\lambda_{1}D}{2}}\pm\sqrt{\frac{\lambda_{1}D}{2}+4\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)}}{2}\end{split}$
(31)

As the Discriminant is positive, we have real roots and therefore the value of
quadratic is negative between the roots. We need to bound
$x^{2}=\mathbb{E}_{Z}[{M}]$, we obtain that,

$\begin{split}\mathbb{E}_{Z}[{M}]&=x^{2}\\\
{}&\leq\Bigg{(}\frac{\sqrt{\frac{\lambda_{1}D}{2}}+\sqrt{\frac{\lambda_{1}D}{2}+4\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)}}{2}\Bigg{)}^{2}\\\
{}&\leq\frac{1}{4}\Bigg{[}\frac{\lambda_{1}D}{2}+\frac{\lambda_{1}D}{2}+4\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\\\
{}&+2\sqrt{\frac{\lambda_{1}D}{2}}\sqrt{\frac{\lambda_{1}D}{2}+4\left(R_{T}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)}\Bigg{]}\end{split}$

Using the inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ we get,

$\begin{split}x^{2}&\leq
R_{T}+\frac{\lambda_{1}D}{2}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\\\
{}&+\sqrt{\frac{\lambda_{1}DR_{T}}{2}}+\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\sqrt{\frac{\lambda_{1}D}{2}}\\\
{}&\leq R_{T}+\sqrt{\frac{\lambda_{1}DR_{T}}{2}}\\\
{}&+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\end{split}$
(32)

Therefore, we prove the upper bound on $\mathbb{E}_{Z}[{M}]$ as

$\begin{split}\mathbb{E}_{Z}[{M}]&\leq
R_{T}+\sqrt{\frac{\lambda_{1}DR_{T}}{2}}\\\
{}&+3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)\end{split}$
(33)

∎

##  12 Proof of Corollary 8

Using $R_{T}=0$, we get

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
3\max\left(\frac{\lambda_{1}D}{2},\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)+\gamma
T.$

There are 2 cases that we need to consider:

  1. 1.

When $(\frac{\lambda_{1}D}{2}\leq\sqrt{\frac{(\lambda_{2}+1)DT}{2}})$:

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
3\left(\sqrt{\frac{(\lambda_{2}+1)DT}{2}}\right)+\gamma T.$

Using the inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ we get:

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
3\left(\sqrt{\frac{\lambda_{2}DT}{2}}+\sqrt{\frac{DT}{2}}\right)+\gamma T.$
(34)

Also, $\lambda_{2}$ is given by:

$\begin{split}\lambda_{2}&=\big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}-\frac{2m\tau_{2}}{\tau_{1}}-\frac{2}{\tau_{1}}+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\big{]}\\\
{}&\leq\big{[}\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}+{k}[\tau_{2}^{2}+\frac{1}{km}+\frac{2\tau_{2}}{k}]\big{]}\\\
{}&=[\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}}{\gamma^{m}\tau_{1}^{2}}+c_{1}]]\end{split}$

Substituting this in Eq. (8) and using the inequality
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ we get:

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
3\left(\sqrt{\frac{mk^{m}\;{}^{k\mkern-2.5mu}{}P_{m}DT}{2\gamma^{m}\tau_{1}^{2}}}+\sqrt{\frac{mc_{1}T}{2}}+\sqrt{\frac{DT}{2}}\right)+\gamma
T.$

Now, we need to find optimal value of $\gamma$ which maximizes the L.H.S of
the above equation. So, we differentiate it with respect to $\gamma$ to get:

$\displaystyle
T-\frac{3}{2\sqrt{2}}\left(\frac{m^{\frac{3}{2}}k^{\frac{m}{2}}\;(^{k\mkern-2.5mu}{}P_{m})^{\frac{1}{2}}D^{\frac{1}{2}}}{\tau_{1}}\right)\frac{T^{\frac{1}{2}}}{\gamma^{\frac{m+2}{2}}}=0$
(35)

Therefore, optimal value of
$\gamma=\left(\frac{9m^{{3}}k^{{m}}(^{k\mkern-2.5mu}{}P_{m})D}{8\tau_{1}T}\right)^{\frac{1}{m+2}}$,
which is of the form $\gamma=\left(\frac{c_{2}}{T}\right)^{\frac{1}{(m+2)}}$.

Substituting $\gamma$ in Eq. (9) we get,

$\displaystyle\mathbb{E}_{Z}[\hat{M}]\leq\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$

  2. 2.

When $(\frac{\lambda_{1}D}{2}>\sqrt{\frac{(\lambda_{2}+1)DT}{2}})$:

$\displaystyle\mathbb{E}_{Z}[\hat{M}]$ $\displaystyle\leq
3\left(\frac{\lambda_{1}D}{2}\right)+\gamma T.$

Setting value of $\gamma\leq\mathcal{O}(\frac{1}{T}^{\frac{1}{(m+2)}})$, we
get:

$\displaystyle\mathbb{E}_{Z}[\hat{M}]\leq\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$

Proof of Collorary (9), where $R_{T}\leq\mathcal{O}(T^{(1-\frac{1}{(m+2)})})$,
can be done in a similar manner as described above.