# Federated Learning using Smart Contracts on Blockchains, based on Reward
Driven Approach

Monik Raj Behera, Sudhir Upadhyay, Suresh Shetty
<EMAIL_ADDRESS>Monik Raj
Behera, Onyx Engineering, J.P.Morgan Chase & Co, India (e-mail:
monik.r.behera@jpmorgan.com).Sudhir Upadhyay, Onyx Engineering, J.P.Morgan
Chase & Co, India (e-mail: sudhir.x.upadhyay@jpmorgan.com).Suresh Shetty, Onyx
Engineering, J.P.Morgan Chase & Co, India (e-mail:
suresh.shetty@jpmorgan.com).

###### Abstract

Over the recent years, Federated machine learning continues to gain interest
and momentum where there is a need to draw insights from data while preserving
the data provider’s privacy. However, one among other existing challenges in
the adoption of federated learning has been the lack of fair, transparent and
universally agreed incentivization schemes for rewarding the federated
learning contributors. Smart Contracts on a Blockchain network provide
transparent, immutable and independently verifiable proofs by all participants
of the network. We leverage this open and transparent nature of smart
contracts on a blockchain to define incentivization rules for the
contributors, which is based on a novel scalar quantity - federated
contribution. Such a smart contract based reward-driven model has the
potential to revolutionize the federated learning adoption in enterprises. Our
contribution is two-fold: first is to show how smart contract based blockchain
can be a very natural communication channel for federated learning. Second,
leveraging this infrastructure, we can show how an intuitive measure of each
agents’ contribution can be built and integrated with the life cycle of the
training and reward process.

###### Index Terms:

Machine Learning, Blockchain, Federated Learning, Fairness in Federated
Learning, Systems and infrastructure for Federated Learning

##  I Introduction

The concept of federated machine learning was introduced around 2016[1]. It
relies on the principle of remote and distributed execution of machine
learning algorithm, and the ability to share and aggregate individual models
in a secure and anonymous manner. Therefore, it is implicit that federated
machine learning would depend on availability of secure communication channels
between remote participants to allow distribution of locally trained
individual models.

Blockchain became popular with launch of bitcoin around 2009[2]. Blockchain is
a form of distributed ledger technology that relies on honest majority members
in a network to validate the accuracy of the executed transactions on the
network. It accomplishes this by allowing each of its members to execute a
piece of turing complete software code (a.k.a smart contract), in an
independent fashion without any external influence or interventions. Although
the proposed solution could be extended to other blockchains, this paper
focuses primarily on Ethereum’s implementation. Therefore, blockchains can
help the deployment of federated learning by both bringing dataset on a
unique, structured, ledger (with potential privacy layers on it), and by
guaranteeing the security, accuracy and correctness of the distribution of the
model’s parameters. This could be of particular value in compliance and anti-
money laundering cases requiring the reconciliation of multiple sensible
dataset, and in which the use of fraud and anomaly detection models could
improve manual audits and investigations[3].

However, because of the distributed nature of validation, in current
blockchains, unless it implements a privacy layer, all communications between
any two nodes is visible to rest of the nodes of the network. Preserving
privacy of transaction in a blockchain, while still allowing all nodes to
participate in consensus process is a difficult problem to solve. This is an
active area of research, and includes technologies such as Zero Knowledge
Proof (zKP). The foundations of zKP is based on interactive proofs, as
described in previous works[4] [5] [6]. However, setup of those continues to
be an onerous process, in real world implementation.

This poses a challenge for federated learning, that requires maintaining the
privacy of the individual participant’s machine learning models (and model
gradients too) and anonymity of the model contributor. The proposed
implementation solves this challenge via dynamically generating asymmetric and
symmetric keys for each federated learning round ( details to follow in
subsequent sections), with a caveat that the aggregation server node is
conceptually akin to a Trusted Execution Environment (TEEs), but at a
consortium level[7].

However, even with consortium trusted aggregation server implementation, the
risk of lack of contribution in the overall federated learning rounds from
individual nodes continues to exist. In addition, the malicious nodes could
potentially send a misleading model that could skew the efficacy of the
aggregated models. One of the potential ways to address the above challenges
could be to have the aggregation server detect somehow, such behavior and drop
those contributors from the collaboration process. Unfortunately, this
solution tends to centralizes the solution and lack of transparency in the
overall process.

The current paper proposes a solution to avoid the above potential pitfalls by
leveraging unique and transparent smart contracts design on blockchain to
reward honest/active ( and penalize malicious/under performing) participants
in the learning process, based on computing a novel, scalar quantity -
federated contribution. In our proposed solution, smart contract is
responsible for reward ( or penalty) specification and distribution (or fees)
as well, through immutable federated contribution records on blockchain.

##  II Related work

###  II-A Federated Learning

Federated learning is a distributed machine learning setting where the goal is
to train a high quality global model, while training is done locally and
privately on individual participant (federated learning client). The training
is done across large number of clients. After the local models are trained,
the improved local model gradients are sent securely over the network to the
federated server for federated aggregation[8].

###  II-B Blockchain

There are several implementations of blockchain - Bitcoin, Ethereum,
Hyperledger Fabric etc. Ethereum[9] is a decentralized, open-source blockchain
with smart contract functionality. Ether is the native cryptocurrency of the
platform. After Bitcoin, it is the second-largest cryptocurrency by market
capitalization. In addition to existing public Ethereum mainnet, there exists
Ethereum for Enterprises[10] that offer certain enterprise desired features.
Some of these features include more control on nodes in the network, higher
performance, difference in cost, node permissioning and different privacy
implementation.

In general, there are three main types of Blockchains[11]

  * •

Public Blockchain: a blockchain that anyone in the world can read, anyone in
the world can send transactions to and expect to see them included if they are
valid, and anyone in the world can participate in the consensus process.

  * •

Consortium Blockchain: a consortium blockchain is a blockchain where the
consensus process is controlled by a pre-selected set of nodes.

  * •

Fully private Blockchains: a fully private blockchain is a blockchain where
write permissions are kept centralized to one organization. Read permissions
may be public or restricted to an arbitrary extent.

The proposed solution in this paper applies to the Consortium (Enterprise)
blockchain where the identity of individual nodes are known to the Consortium
Operator ( a.k.a. Network Operator).

###  II-C Smart Contract on blockchain

A smart contract[12] is simply a program that runs on the Ethereum blockchain.
It’s a collection of code (its functions) and data (its state) that resides at
a specific address on the blockchain. Smart contract are permission-less, i.e.
anyone can write a smart contract and deploy it to the network. The smart
contract code is visible to all participants on the network, and any
participant can independently execute that code to validate the outcome[13].
Smart Contracts on Ethereum are written in its own programming language called
Solidity. Events on Ethereum[14] are well defined ways of asynchronously
exchanging data among the participants of blockchain network. In Solidity,
events[15] are dispatched as signals, that the smart contracts can fire.
DApps, which are essentially decentralized applications, or anything connected
to Ethereum JSON-RPC API (an interface exposed by blockchain network for
connectivity and programmatic interactions with blockchain), can listen to
these events and act accordingly. Event can also be indexed, so that the event
history can be searched later.

###  II-D Federated learning and blockchain

There is a growing literature on federated learning implementations through
blockchain, a sign of the natural complementarity between these two
technologies we are arguing for. Since [16] proposed using blockchain to
maintain the global model with community and reach a consensus, a number of
papers [17, 18, 19, 20] explored this avenue, but mainly using the blockchain
as a safe and coherent storage for the global model, and fail to make full use
of the potential of smart contracts to both coordinate the learning, and
through that compute measurement functions of how each agent is contributing
to the global model.

[21] adds implementation of oracles to make it possible to deploy regressions
on Hyperledger Fabric. While oracles can act as decentralized web services,
that extend the capabilities of smart contracts, we would also argue in this
paper that by having a federated learning life cycle that is exactly that of
some smart contract improves both security, performance and conceptualization
(especially on how to distinguish and reward contributors) of the federated
learning task.

For that measurement of contribution framework we build on [22] proposal to
leverage the blockchain to evaluate updates from nodes, and potentially kick
out underrated nodes as a defense against malicious devices, and link that to
the literature on deletion based rewarding and Shapley value computations. It
is our hope to further bridge these two literatures, to be able to
automatically compute different variations of Shapley values through
blockchain-based smart contract in federated learning settings. Our main
contribution is to showcase how a natural infrastructure and life cycle could
support these, leveraging the cryptographic, distributed computing, and
consensus mechanisms within blockchain.

###  II-E RSA and AES algorithm

Asymmetric key cryptographic algorithm are popular cryptography techniques,
which focus on using public-private key pair for encryption. In RSA
algorithm[23], the fundamental idea is to use a computationally impossible,
long prime numbers based public key and private key. Public key can be used to
encrypt data, where as it can only be deciphered using private key, which is
kept privately and securely with the owner. In case of symmetric cryptography,
like of AES algorithm[24], the same key would be used for encryption and
decryption. Thus special care needs to be given to safeguard the symmetric key
itself.

###  II-F Measuring contributions in federated learning

In recent work[25], measurement of contributions towards improvising the
global model in federated learning has been described, for both horizontal and
vertical class of federated learning. Authors have discussed the approach of
using ‘deletion method’ for horizontal federated learning approach, where the
change in testing accuracy is considered by various iterations of training,
with each iteration, we remove the data points from a single client. This way,
we measure the degradation in model performance, and then infer the
contributions accordingly by the federated clients. In case of vertical
federated learning, Shapley values are computed for each feature. Shapley
values gives a strong quantification of each feature’s importance, followed by
a mathematical approach of inferring contributions of parties in vertical
federated learning. There are, however, a multiplicity of ways in which the
Shapley value can be implemented, with very disparate results, as shown in
[26]. On the other hand, deletion based methods have the merits of simplicity
(whereas Shapley values rely on utility functions, and for that reason can be
hard to compute), the uniform value attributed to each data point make
deletion based rewards very easily biased toward providers of outliers and
irrelevant data. Our contribution will aim at both drawing from the simplicity
of the deletion based approach (but by focusing on weights differences,
instead of training data differences) and the conceptualization of Shapley
values (as in our case accuracy of the resulting global model can be a proxy
for agents’ utility function).

##  III Blockchain for federated communication

Earlier works have proved REST, RPC, gRPC[27] as popular choices for
communication between federated server and clients. For more secure
communication, various battle-tested approaches include network firewalls, SSL
and token based authentication have been leveraged. Though these methods
provide a secure medium, they lack the transparency in the communication
medium itself, which can be well established by using blockchain. This paper
proposes use of blockchain and smart contracts (ethereum based), which
provides a decentralized mechanism of communication between peers and the
federated server. Using smart contracts, the communications are secured at
blockchain level, which uses various asymmetric cryptography techniques for
encryption and modification of state on blockchain network. This also entrusts
the emission of events for communication between federated server and client
nodes with extended level of security and transparency.

Owing to the “consortium blockchain network”, where individual participants
are trusted enterprises and organizations, there is a distant possibility of
few of the participants acting as a bad actors. Some of the participants are
only consuming the resources, but not contributing enough, or vice versa.
These are few of the possible scenarios in consortium governed federated
learning network. To manage and counter these measures through incentives
(both reward and penalty), smart contracts provide a transparent and immutable
way of maintaining contributions record on the blockchain. Based on the
contribution record from blockchain, a given participant would be either
rewarded or penalized through on-chain blockchain tokens, or through off-chain
mechanism established by consortium.

###  III-A Life-cycle of a federated aggregation event

Federated learning in a consortium network comprises of a consortium trusted
and security hardened aggregation server. All the participants, who are
clients in the federated learning ecosystem are listening the blockchain
events from a smart contract (ethereum smart contracts, as ethereum is the
blockchain network being used). Table I gives an overview of a typical
federated learning round. All the events on the blockchain network, regarding
federated learning is triggered by federated aggregating server. This design
makes it possible for individual participants to be lightweight, in terms of
responsibilities, and only focus on local model improvisation. The possible
event initiation from federated learning server includes initial distribution
of base machine learning model, subsequent federated learning cycles,
contribution announcement on the chain and contribution fees notification.

TABLE I: Life-cycle of a federated learning communication event. Time column
represents relative timestamp, where increment in timestamp suggests relative
increment, not the absolute increment. Event is the respective event type on
communication round. ‘Action On’ column shows the expected action for which
role, whether client or server. ‘Publish’ column depicts whether the event is
published as broadcast on blockchain or not.
Time |  Event |  Action on- |  Publish?
---|---|---|---
$t_{k}$ |  Initiate FL round |  Server |  $\surd$
$t_{k+1}$ |  Receive Initiate Event |  Client(s) |  $\times$
$t_{k+2}$ |  Encrypt local model; with key received in previous step |  Client(s) |  $\times$
$t_{k+3}$ |  Publish encrypted local model |  Client(s) |  $\surd$
$t_{k+4}$ |  Aggregate encrypted local models |  Server |  $\times$
$t_{k+5}$ |  Broadcast new global model |  Server |  $\surd$

###  III-B Encryption of event data

In the previous sections, we discussed about how blockchain ensures required
security and privacy at its core. Though data on blockchain is immutable, the
privacy is not guaranteed, because of the very nature of how blockchain works.
A consortium network with enterprise participants, there is a high possibility
of participants not comfortable with letting peer participants knowing about
the model weight gradients. If local model weights (and gradients) are
revealed, this posses risk of revealing statistical properties of the data
from individual participant, if not the actual data.

In order to privately send model weights from participant to federated server
on blockchain, in a consortium network, asymmetric encryption using RSA
cryptography is proposed in the paper. Every time a new federated learning
round is published as blockchain event, through smart contract, federated
aggregation server generates a new set of RSA key pair. The private key of the
pair stays with the server, as this will be used by the server in later stages
to decrypt the encrypted event message cipher to plain-text. The public key is
sent across the network to all the participants. Participant will generate an
AES key for encrypting machine learning model, and then use the public key
received from federated server to encrypt the AES key[28]. With RSA keys
revolving for every new federated learning round, this decreases the chances
of compromising model information over the blockchain, for any given
participant on the network. One thing to note here is - the event data
containing participant’s local model weights need to be encrypted only. Other
event data like global model, which is sent from server to clients, initiation
of federated round broadcast would be sent as plain text, as they are not
sensitive data among the peers in blockchain network.

###  III-C Smart contract for communication and contribution towards federated
learning

In the previous sections, smart contracts have been described as a way of
executing turing complete programs on blockchains. Ethereum smart contracts
have a concept of events, which are essentially simple and cheap method of
emitting a broadcast message to all the nodes, with defined parameters. Events
are not considered as a state change on blockchain, hence they consume very
less gas price[29], in comparison to state change transactions on blockchain.
It is important to understand that events generated, when published by the
participants or the federated server, would be a broadcast. Dynamically
generated encryption keys, explained in earlier section would safeguard the
privacy interest of the federated clients. Federated clients would have to
listen to the agreed upon ethereum event from a smart contract, in order to
receive the event and take necessary actions, essentially making smart
contracts a rudimentary pub-sub[30] channel of communication.

In the current paper, smart contracts are proposed as a mechanism to maintain
transparent, immutable records of contributions, which improvises (or
degrades) the global federated learning model. The computation to determine
the contribution of individual in the federated learning round (described in
subsequent section) is performed off the blockchain, considering the resource
and computation constraints. After the computation is completed, the records
are published on blockchain, anonymously, for everyone to see. This makes the
contributions (and indirectly participants expense fees) transparent. The idea
is to motivate the participants to be honest in the network, at-least to a
certain extent.

##  IV Federated aggregation and contribution

Federated learning with centralized aggregation server implements various ways
to implement federated aggregation[31], like FedAvg, FedSGD, etc. Assuming the
number of clients is quite large (in order of $10^{5}$ ), if few of the
clients are acting as bad actors, or clients with noise in training data,
their impact towards the global model is smoothed by averaging algorithm. But
in case of consortium setting, where number of clients is not that huge (in
order of $10^{2}$ ), the local weights of federated client with noisy data or
malicious intention would impact the overall weight(s) of the federated
learning model. In order to tackle the challenge, we are proposing a novel way
of computing a novel scalar quantity, federated contribution across the
network, and using smart contract to publish and store on the blockchain (as
discussed in earlier section). As compared to earlier work[25], federated
contribution establishes a way to define contribution of each participant in
federated learning setting, whether they might have train data of similar
statistical properties, or non overlapping (orthogonal in feature space)
statistical properties.

###  IV-A Federated aggregation

FedAvg[32] is one of the popular algorithms in federated aggregation domain,
which ensures complete and optimal solution, provided the learning rate and
local learning contribution is accurately considered. Inspired from the
previous works, our problem formulation for non-IID (or IID) data, which
assumes more real world problem setup, in a consortium blockchain network, we
have formulated our problem as described below -

$\min_{\theta\in\mathbf{R^{d}}}f(\theta):=\sum_{k=1}^{K}p_{k}F_{k}(\theta)$

where $k$ as index for client, $\theta$ as the set of model weight parameters
for any generic machine learning algorithm, which can be modified for
federated learning setting. $f(\theta)$ is the global objective function,
$F_{k}(\theta)$ is the local objective function for client $k$, $p_{k}$ is the
learning importance factor - a scalar value to determine individual client’s,
local model’s relative importance, and $K$ is the total number of clients.
Considering $p_{k}$ as learning importance factor in federated learning, it is
assumed that -

$\sum_{k=1}^{K}p_{k}=1$

With fedAvg as algorithm for aggregation, the individual weight updates for
$t+1$ iteration, $l^{th}$ layer can be defined as -

$w_{t+1,l}\leftarrow w_{t,l}+\alpha\sum_{k=1}^{K}p_{k}\nabla F_{k}(\theta)$

where $w_{t,l}$ is weight for $t^{th}$ iteration at $l^{th}$ layer and
$\alpha$ is the learning rate parameter.

###  IV-B Federated learning contribution

In previous sections, motivation for federated contribution is discussed.
Intuitively, federated computation is a scalar quantity, which depicts the
deviation, or divergence of two machine learning models. We will now define
the federated contribution mathematically.

$\gamma^{k}:=\|\beta^{k}\|_{2}$

$\beta^{k}:=\langle\|\delta_{1}^{k}\|_{\mathbf{F}},\quad\|\delta_{2}^{k}\|_{\mathbf{F}},\quad\ldots\quad,\|\delta_{L}^{k}\|_{\mathbf{F}}\rangle$

$\delta_{l}^{k}:=\mathbf{w_{l,t}^{global}}-\mathbf{w_{l,t+1}^{k}}$

$\gamma^{k}_{rel}:=\frac{\gamma^{k}}{\sum_{k=1}^{K}\gamma^{k}}$

where $\gamma^{k}$ is the absolute federated contribution of client $k$,
$\|.\|_{p}$ represents $p^{th}$ norm, $\|.\|_{F}$ represents Frobenius
norm[33], $L$ represents the final layer’s weight matrix of a generic machine
learning model. $\delta_{l}^{k}$ represents difference of model weight
parameter matrix for $l^{th}$ layer of $k^{th}$ client.
$\mathbf{w_{l,t+1}^{k}}$ represents model weight for $l^{th}$ layer of
$k^{th}$ client at $t+1^{th}$ iteration. $\mathbf{w_{l,t}^{global}}$ is the
model weight for $l^{th}$ layer of global model at $t^{th}$ iteration.
$\gamma^{k}_{rel}$ is relative federated contribution of client $k$.

For any generic machine learning algorithm, like linear regression, logistic
regression, neural networks, etc, the primary intent is to find a weight
matrix, or a set of weight matrices. These weight matrices are computed using
loss functions and gradient descent approaches, in various formats depending
upon the algorithm. Assuming the representational vector, defined $\beta^{k}$,
with minimum size of the set as $1$, we can define an each element of
$\beta^{k}$ as Frobenius norm of $\delta_{l}^{k}$. Here, $\delta_{l}^{k}$, as
defined previously, represents the element wise difference of weight matrices
(order of subtraction doesn’t matter, as Frobenius norm computes square of the
element). We have considered the element wise difference of both the weight
matrices for each layer, as it is inverse operation to the gradient descent
and weight updates, where we perform addition of improvements, as described in
problem formulation earlier. Frobenius norm is well established method to find
the magnitude of a matrix from origin of a hyperspace $\mathrm{R^{d}}$. When
we compute Frobenius norm for $\delta_{l}^{k}$, it essentially represents the
magnitude of deviation between two weight matrices(global weight matrix of
previous iteration and local weight matrix of current iteration, for layer l).
The vector $\beta^{k}$ represents a set of magnitudes of deviation of local
model’s weight matrices from global model’s weight matrices respectively, as
an independent and individual axis. Finally, in order to calculate value
$\gamma^{k}$ for client k, we calculate 2-Norm, which is the euclidean norm of
$\beta^{k}$. This represents the magnitude of distance from origin, which
quantifies the combined deviation of local model (set of weights) from global
model (again, set of weights) as a scalar quantity.

Inferring $\gamma^{k}$, in case of federated contribution, federated
aggregation server calculates $\gamma^{k}$ for each $k^{th}$ client. If the
federated contribution value is relatively high, that means the given client
has contributed to a higher degree. While describing contribution to a higher
(or lower) degree in federated contribution, it practically quantifies the
contribution in modifying the global model, by training on larger data points,
or by training over data points which are having distant statistical
properties from earlier training data, or may be higher noise in data. This
intuitively can be thought as - the divergence of local model after training
on new data points will be more, if higher gradient descent updates are
performed. This can be because of variance in new data, use of better data
points for local training rounds or greater training size. In case of
divergence being relatively smaller, one can infer about participant using
noisy or unrelated data points, which may not be acceptable for global
federated model. Our framework would thus point at a possible way to fix a key
limitation of the Shapley value framework (which we hope to build the link
with in a future paper) - the fact that it only provides valuations for points
within a fixed data set, and does not account for statistical aspects of the
data and does not give a way to reason about points outside the data set.

##  V Experiments

In the paper, the experiments to validate the hypothesis of using blockchain
smart contracts and federated contribution has been carried out with setting
up a $(5+1=)6$ ethereum blockchain permissioned nodes setup in AWS cloud.
Within this network, one of the node acts as federated aggregation server, and
other three nodes act as federated clients. It is a consortium blockchain
setup, with each individual client nodes own set of data. Figure 1 shows the
architecture representation of the proposed experimental setup. The federated
server node runs a python daemon process which listens to the events generated
by smart contracts on the network. Upon receipt of events and based on event
types, it either sends the global model to every node as a broadcast, or
computes the aggregated version of the global model with latest gradients of
local training, from individual federated clients. On federated clients, a
similar python application is being executed, which listens to events and
sends the encrypted local model, as required. It also acts as a service, which
serves (exposing remote REST based endpoint, which can be consumed by any
other program to predict, based on input data) machine learning model, and
also is responsible for re-training of new batch of data points. The
applications, which are responsible for directly interacting with blockchain
nodes are termed as “dApp”, as depicted in figure 1, which essentially means
decentralized applications.

Federated Aggregator server node deploys both s ‘communication’ and
‘contribution records’ smart contracts. . All of the federated client nodes
leverage the address of these two public contracts as a communication channel
both for publishing events and listening to any generated events as well. The
interface of the smart contract has been discussed in further.

Figure 1: In the above architecture diagram, individual nodes are running
decentralized applications, with processes to serve and re-train data models.
Two smart contracts, one for communication and one for contribution is
deployed on the blockchain. Federated server is responsible to send the
dynamically generated RSA key pair’s public key, which would be used to
encrypt the newly generated AES key of participant, used for model encryption.
Encrypted models are publised on the blockchain. Even though all the
participants can receive the private encrypted model gradients, only the
federated aggregation server can decipher and use the model, as it posses the
RSA private key of respective public key.

###  V-A Data description

In the paper, to test the hypothesis against standard data set, MNIST[34] and
Fashion-MNIST[35] data sets have been used. In both the data sets, it has
$10000$ test data points, $60000$ train data points and $10$ target classes.
We split the training data as $10000$ for initial, “genesis” global model and
remaining $50000$ as training data for federated clients. For both the data
sets, we have performed our experiments in two ways, by splitting our data
sets described below -

  1. 1.

Independent and Identical Data: The data is randomly split and distributed
across all the federated clients, each having $10000$ training data points
with all the $10$ target classes.

  2. 2.

Non-Independent and Identical Data: The data is split and distributed across
all the federated clients, each of the clients having training data with only
$2$ target class.

###  V-B Blockchain smart contract interface

As discussed earlier, we have used two ethereum based smart contracts, one for
communication and one for recording contributions transparently on blockchain.
Interface for both of the smart contracts have been defined as follows -

⬇

1// Communication : Interface

2pragma solidity >=0.8.0 <0.9.0;

3contract Communication {

4 event BCEvent(

5 uint256 timestamp,

6 bool is_encrypted,

7 bytes event_type,

8 bytes body

9 );

10 function publish(

11 uint256 timestamp,

12 bool is_encrypted,

13 bytes memory event_type,

14 bytes memory body

15 ) public returns(uint ack) { }

16}

⬇

1// Contribution : Interface

2pragma solidity >=0.8.0 <0.9.0;

3contract Contribution {

4 uint len = 5; //5 federated clients

5 uint[] memory _clients = new uint[](5);

6 function set_contribution(

7 uint client_id,

8 uint relative_contribution

9 ) public returns(uint ack) {

10 //only owner(federated server)

11 //modifies state of _clients

12 }

13 function get_contributions()

14 public view returns (uint memory) { } }

###  V-C Neural network for image classification

Since the each image data in MNIST and Fashion-MNIST is $28\mathbf{x}28$ gray
scale image, we have used artificial neural network[36] for image
classification. Figure 2 describes the architecture of the neural network in
depth. We have used adam[37] optimizer and sparse categorical cross
entropy[38] as loss function, with $5$ training epochs.

Output (1024) (512) (128) (728) (10) Figure 2: In the architecture, the input
layer contains $728$ neurons, after flattening the image. Output layers
contains $10$ neurons, as the data set has $10$ image labels or target
classes. It contains $3$ fully connected, hidden layers, each having $1024$,
$512$ and $128$ neurons respectively. The hidden layers used relu, and output
layer used softmax as the activation functions.

###  V-D Results

Based on the data, blockchain network with smart contracts and neural network
architecture described in earlier sections, we performed various experiments
to test our hypothesis of computing federated contribution against various
settings like higher contribution of a smaller group of participants, lower
contributions by a subset of participants, noise in local data, while training
by individual nodes. We have also calculated the overall accuracy of image
classification of the aggregated model. In our experiments, we have changed
the size of training samples, as it is the variable of the experiment. For
each set of conditional environment for experiments, we have considered
results for $4$ different cases. The $4$ cases are as (i) MNIST data with non-
IID split (ii) MNIST data with IID split (iii) Fashion-MNIST data with non-IID
split and (iv) Fashion-MNIST data with IID split. A well known and common
observation across all the experimental setting is increase in machine
learning model’s accuracy performance, with increase number of training
samples.

Figure 3 shows the performance of the aggregated machine learning model, from
various clients. We do observe better and stable performance in case of data
being split, across all the clients in IID manner. Figure 4 shows the
federated contribution being increasing with increase in training data sample
size. Also, since all the clients in this setting have contributed equally,
their federated contribution values are quite close. One thing to notice,
which is evident across all experiments (can be observed in the graphs) is,
increase in federated contribution value, with increase in training size. This
essentially validates our hypothesis of federated contribution being dependent
on number of weight updates, which is directly proportional to higher training
data (or training iterations). For distinct visuals, we have shown client 3 in
always green colour, in all the visualizations.

Figure 5 depicts the experiment, where client 3 is under-performing by
training on only $10\%$ of what other participants are training. We can
observe how the federated contribution value for client 3 is very low, as
compared to other participants. Figure 6 whereas shows the opposite, where
client 3 trains on $10$ times more data points, puts in extra effort,
logically, than other participants. This shows higher value in federated
contribution for client 3, as relatively compared to others. Figure 7 is the
final setting, where we added Gaussian noise, with noise value between $0$ and
$1$, in training data of client 3, which essentially shows depletion in
federated contribution of client 3, relative to others.

Figure 3: (a) Accuracy of aggregated model in % vs training data sample size
for MNIST data, split in Non-IID format (b) Accuracy of aggregated model in %
vs training data sample size for MNIST data, split in IID format (c) Accuracy
of aggregated model in % vs training data sample size for Fashion-MNIST data,
split in Non-IID format (d) Accuracy of aggregated model in % vs training data
sample size for Fashion-MNIST data, split in IID format

Figure 4: (a) Federated contribution of equally contributing clients vs
training data sample size for MNIST data, split in Non-IID format (b)Federated
contribution of equally contributing clients vs training data sample size for
MNIST data, split in IID format (c) Federated contribution of equally
contributing clients vs training data sample size for Fashion-MNIST data,
split in Non-IID format (d) Federated contribution of equally contributing
clients vs training data sample size for Fashion-MNIST data, split in IID
format

Figure 5: (a) Federated contribution of highly contributing clients, but
client 3 vs training data sample size for MNIST data, split in Non-IID format
(b)Federated contribution of highly contributing clients, but client 3 vs
training data sample size for MNIST data, split in IID format (c) Federated
contribution of highly contributing clients, but client 3 vs training data
sample size for Fashion-MNIST data, split in Non-IID format (d) Federated
contribution of highly contributing clients, but client 3 vs training data
sample size for Fashion-MNIST data, split in IID format

Figure 6: Federated contribution of lowly contributing clients, but client 3
vs training data sample size for MNIST data, split in Non-IID format
(b)Federated contribution of lowly contributing clients, but client 3 vs
training data sample size for MNIST data, split in IID format (c) Federated
contribution of lowly contributing clients, but client 3 vs training data
sample size for Fashion-MNIST data, split in Non-IID format (d) Federated
contribution of lowly contributing clients, but client 3 vs training data
sample size for Fashion-MNIST data, split in IID format

Figure 7: (a) Federated contribution of highly contributing clients, but
client 3 with noise vs training data sample size for MNIST data, split in Non-
IID format (b)Federated contribution of highly contributing clients, but
client 3 with noise vs training data sample size for MNIST data, split in IID
format (c) Federated contribution of highly contributing clients, but client 3
with noise vs training data sample size for Fashion-MNIST data, split in Non-
IID format (d) Federated contribution of highly contributing clients, but
client 3 with noise vs training data sample size for Fashion-MNIST data, split
in IID format

##  VI Conclusion

In our paper, we studied our proposal of using smart contracts to establish a
fair, transparent, secure and immutable incentivization mechanism in a
consortium network for federated learning. We proposed a novel approach to
calculate a unique scalar quantity, federated contribution, which quantifies
the contribution of each participant for federated learning. Federated
contribution is compatible with the machine learning algorithms which relies
on weight parameters computed by gradient descents. We justified our proposed
approach both empirically and theoretically. For future work in the given
area, one can extend the federated contribution to non-gradient descents
algorithms, or to heterogeneous federated learning. In the proposed method of
calculating federated contribution, and using the relative federated
contribution values for reward (or penalization) mechanism, we validated that
it effectively penalizes under-performing participants, rewards over-
performing participants and penalizes participants with noisy or malicious
data points. This justifies our proposal of considering federated contribution
as an adequate mechanism of quantifying participants’ contribution in the
blockchain based consortium network, with accuracy of the global model as a
proxy of utility in the Shapley value framework. Future work will aim at
building further the conceptual bridge between our weight-based contribution
measure and Shapley values, under modified axioms that reflect the
specificities of federated machine learning settings.

## Acknowledgment

We would like to thank our colleagues Robert Otter, Nicolas X Zhang, Jiao Y
Chang, Tulasi Das Movva, Thomas Eapen for reviews and discussions during the
experimentation and evaluation. We would also like to thank J.P.Morgan Chase
for supporting us in carrying out this effort.

## References

  * [1] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [2] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2009. [Online]. Available: http://www.bitcoin.org/bitcoin.pdf
  * [3] S. Fortunato, “Community detection in graphs,” _Physics reports_ , vol. 486, no. 3-5, pp. 75–174, 2010.
  * [4] O. Goldreich, S. Micali, and A. Wigderson, “Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems,” _Journal of the ACM (JACM)_ , vol. 38, no. 3, pp. 690–728, 1991.
  * [5] B. Bünz, S. Agrawal, M. Zamani, and D. Boneh, “Zether: Towards privacy in a smart contract world,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2020, pp. 423–443.
  * [6] S. Bowe, A. Chiesa, M. Green, I. Miers, P. Mishra, and H. Wu, “Zexe: Enabling decentralized private computation,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 947–964.
  * [7] R. Cheng, F. Zhang, J. Kos, W. He, N. Hynes, N. Johnson, A. Juels, A. Miller, and D. Song, “Ekiden: A platform for confidentiality-preserving, trustworthy, and performant smart contracts,” in _2019 IEEE European Symposium on Security and Privacy (EuroS &P)_. IEEE, 2019, pp. 185–200.
  * [8] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” _arXiv preprint arXiv:1812.06127_ , 2018.
  * [9] V. Buterin, _Ethereum: A next-generation smart contract and decentralized application platform_ , 2014. [Online]. Available: https://github.com/ethereum/wiki/wiki/White-Paper
  * [10] M. Swan, “Blockchain for business: Next-generation enterprise artificial intelligence systems,” in _Advances in computers_. Elsevier, 2018, vol. 111, pp. 121–162.
  * [11] G. Wood _et al._ , “Ethereum: A secure decentralised generalised transaction ledger,” _Ethereum project yellow paper_ , vol. 151, no. 2014, pp. 1–32, 2014.
  * [12] A. Bogner, M. Chanson, and A. Meeuw, “A decentralised sharing app running a smart contract on the ethereum blockchain,” in _Proceedings of the 6th International Conference on the Internet of Things_ , 2016, pp. 177–178.
  * [13] L. M. Bach, B. Mihaljevic, and M. Zagar, “Comparative analysis of blockchain consensus algorithms,” in _2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)_. IEEE, 2018, pp. 1545–1550.
  * [14] Ethereum and Tutorials, “Logging data from smart contracts with events,” 2020\. [Online]. Available: https://ethereum.org/en/developers/tutorials/logging-events-smart-contracts/
  * [15] Solidity and Documentation, “Events in contracts,” 2016. [Online]. Available: https://docs.soliditylang.org/en/develop/contracts.html#events
  * [16] S. Zhou, H. Huang, W. Chen, P. Zhou, Z. Zheng, and S. Guo, “Pirate: A blockchain-based secure framework of distributed machine learning in 5g networks,” _IEEE Network_ , vol. 34, no. 6, pp. 84–91, 2020.
  * [17] Y. J. Kim and C. S. Hong, “Blockchain-based node-aware dynamic weighting methods for improving federated learning performance,” in _2019 20th Asia-Pacific Network Operations and Management Symposium (APNOMS)_. IEEE, 2019, pp. 1–4.
  * [18] U. Majeed and C. S. Hong, “Flchain: Federated learning via mec-enabled blockchain network,” in _2019 20th Asia-Pacific Network Operations and Management Symposium (APNOMS)_. IEEE, 2019, pp. 1–4.
  * [19] X. Bao, C. Su, Y. Xiong, W. Huang, and Y. Hu, “Flchain: A blockchain for auditable federated learning with trust and incentive,” in _2019 5th International Conference on Big Data Computing and Communications (BIGCOM)_. IEEE, 2019, pp. 151–159.
  * [20] Y. Li, C. Chen, N. Liu, H. Huang, Z. Zheng, and Q. Yan, “A blockchain-based decentralized federated learning framework with committee consensus,” _IEEE Network_ , 2020.
  * [21] V. Drungilas, E. Vaičiukynas, M. Jurgelaitis, R. Butkienė, and L. Čeponienė, “Towards blockchain-based federated machine learning: Smart contract for model inference,” _Applied Sciences_ , vol. 11, no. 3, p. 1010, 2021.
  * [22] X. Chen, J. Ji, C. Luo, W. Liao, and P. Li, “When machine learning meets blockchain: A decentralized, privacy-preserving and secure design,” in _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 2018, pp. 1178–1187.
  * [23] B. A. Forouzan and D. Mukhopadhyay, _Cryptography and network security_. Mc Graw Hill Education (India) Private Limited, 2015.
  * [24] G. Singh, “A study of encryption algorithms (rsa, des, 3des and aes) for information security,” _International Journal of Computer Applications_ , vol. 67, no. 19, 2013.
  * [25] G. Wang, C. X. Dang, and Z. Zhou, “Measure contribution of participants in federated learning,” in _2019 IEEE International Conference on Big Data (Big Data)_ , 2019, pp. 2597–2604.
  * [26] M. Sundararajan and A. Najmi, “The many shapley values for model explanation,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9269–9278.
  * [27] P. L. Ventre, M. M. Tajiki, S. Salsano, and C. Filsfils, “Sdn architecture and southbound apis for ipv6 segment routing enabled wide area networks,” _IEEE Transactions on Network and Service Management_ , vol. 15, no. 4, pp. 1378–1392, 2018.
  * [28] N. Khanezaei and Z. M. Hanapi, “A framework based on rsa and aes encryption algorithms for cloud computing services,” in _2014 IEEE Conference on Systems, Process and Control (ICSPC 2014)_. IEEE, 2014, pp. 58–62.
  * [29] G. A. Pierro and H. Rocha, “The influence factors on ethereum transaction fees,” in _2019 IEEE/ACM 2nd International Workshop on Emerging Trends in Software Engineering for Blockchain (WETSEB)_. IEEE, 2019, pp. 24–31.
  * [30] J. O’Hara, “Toward a commodity enterprise middleware: Can amqp enable a new era in messaging middleware? a look inside standards-based messaging with amqp,” _Queue_ , vol. 5, no. 4, pp. 48–55, 2007.
  * [31] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečnỳ, S. Mazzocchi, H. B. McMahan, _et al._ , “Towards federated learning at scale: System design,” _arXiv preprint arXiv:1902.01046_ , 2019.
  * [32] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” _arXiv preprint arXiv:1907.02189_ , 2019.
  * [33] I. S. Dhillon and S. Sra, “Generalized nonnegative matrix approximations with bregman divergences,” in _NIPS_ , vol. 18. Citeseer, 2005.
  * [34] Y. LeCun and C. Cortes, “MNIST handwritten digit database,” 2010. [Online]. Available: http://yann.lecun.com/exdb/mnist/
  * [35] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” 2017.
  * [36] L. Deng, G. Hinton, and B. Kingsbury, “New types of deep neural network learning for speech recognition and related applications: An overview,” in _2013 IEEE international conference on acoustics, speech and signal processing_. IEEE, 2013, pp. 8599–8603.
  * [37] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [38] C. Louizos, M. Welling, and D. P. Kingma, “Learning sparse neural networks through $l\\_0$ regularization,” _arXiv preprint arXiv:1712.01312_ , 2017\.


,bodystyle=, titlestyle=(#1),thickness=1pt,underline=false,
style=M]thmTheorem[section] ,bodystyle=,
titlestyle=(#1),thickness=1pt,underline=false,
style=M]corollaryCorollary[section] ,bodystyle=,
titlestyle=(#1),thickness=1pt,,underline=false,
style=M]definitionDefinition[section] ,bodystyle=,
titlestyle=(#1),thickness=1pt,,underline=false, style=M]lemmaLemma[section]

###### Proof.

###### Revisiting the Learnability of Apple Tasting

###### Abstract

In online binary classification under apple tasting feedback, the learner only
observes the true label if it predicts “1”. First studied by
helmbold2000apple, we revisit this classical partial-feedback setting and
study online learnability from a combinatorial perspective. We show that the
Littlestone dimension continues to prove a tight quantitative characterization
of apple tasting in the agnostic setting, closing an open question posed by
helmbold2000apple. In addition, we give a new combinatorial parameter, called
the Effective width, that tightly quantifies the minimax expected mistakes in
the realizable setting. As a corollary, we use the Effective width to
establish a trichotomy of the minimax expected number of mistakes in the
realizable setting. In particular, we show that in the realizable setting, the
expected number of mistakes for any learner under apple tasting feedback can
only be $\Theta(1),\Theta(\sqrt{T})$, or $\Theta(T)$.

##  1 Introduction

In the standard online binary classification setting, a learner plays a
repeated game against an adversary. In each round, the adversary picks a
labeled example $(x,y)\in\mathcal{X}\times\\{0,1\\}$ and reveals the unlabeled
example $x$ to the learner. The learner observes $x$ and then makes a
prediction $\hat{y}\in\\{0,1\\}$. Finally, the adversary reveals the true
label $y$ and the learner suffers the loss $\mathbbm{1}\\{\hat{y}\neq y\\}$
(Littlestone1987LearningQW). In many situations, however, receiving feedback
after every prediction may not be realistic. For example, in spam filtering,
emails that are classified as spam are often not verified by the user.
Accordingly, the learner only receives feedback when an email is classified as
“not spam”. In recidivism prediction, a person whose is predicted to re-commit
a crime may not be released. Accordingly, we will not know whether this person
would have re-committed a crime had they been released. Situations like these
are known formally as “apple tasting” (helmbold2000apple). In the generic
model, a learner observes a sequence of apples, some of which may be rotten.
For each apple, the learner must decide whether to discard or taste the apple.
The learner suffers a loss if they discard a good apple or if they taste a
rotten apple. Crucially, when the learner discards an apple, they do not
receive any feedback on whether the apple was rotten or not.

Binary online classification under apple tasting feedback was first studied by
helmbold2000apple in the realizable setting. Here, they give a simple and
generic conversion of a deterministic online learner in the full-information
setting into a randomized online learner in the apple tasting setting. In
particular, they show that if $M_{+}$ and $M_{-}$ are upperbounds on the
number of false positive and false negative mistakes of the deterministic
online learner respectively, then the expected number of mistakes made by
their conversion, under apple tasting feedback, is at most
$M_{+}+2\sqrt{TM_{-}}$. Along with these upperbounds, they provide lowerbounds
on the expected number of mistakes for randomized apple tasting learners in
terms of the number of false positive and false negative mistakes made by any
deterministic online learner in the full-information setting. That is, if
there exists $M_{+},M_{-}\in\mathbbm{N}$ such that every deterministic online
learner in the full information setting makes either at least $M_{+}$ false
positive mistakes or $M_{-}$ false negative mistakes, then every randomized
online learner makes at least
$\frac{1}{2}\min\\{\frac{1}{2}\sqrt{TM_{-}},M_{+}\\}$ expected number of
mistakes under apple tasting feedback. Finally, as an open question, they ask
whether their results can be extended to the harder agnostic setting where the
true labels can be arbitrary and not necessarily consistent with any
hypothesis in $\mathcal{H}$.

While the work by helmbold2000apple does provide bounds on the minimax
expected mistakes in the realizable setting, their bounds are in terms of the
existence of an algorithm with certain properties. This is in contrast to much
of online learning theory, where minimax regret is often quantified in terms
of combinatorial dimensions that capture the complexity of the hypothesis
class (Littlestone1987LearningQW; ben2009agnostic; DanielyERMprinciple;
rakhlin2015online). Accordingly, we revisit apple tasting and study online
learnability from a combinatorial perspective. In particular, we are
interested in identifying combinatorial dimensions that tightly quantify the
minimax regret for apple tasting in both the realizable and agnostic settings.
Towards that end, we make the following contributions.

[bodystyle=, ,thickness=1pt,underline=false, style=M]Main Contributions.

  * (1)

We close the open question posed by helmbold2000apple by showing that the
minimax expected regret in the agnostic setting, under apple tasting feedback,
is at most $3\sqrt{\texttt{L}(\mathcal{H})T\log(T)}$ and at least
$\sqrt{\frac{\texttt{L}(\mathcal{H})T}{8}}$, where $\texttt{L}(\mathcal{H})$
is the Littlestone dimension of $\mathcal{H}$.

  * (2)

On the other hand, we show that the Littlestone dimension alone does not give
a tight quantitative characterization in the realizable setting. Instead, we
show that the minimax expected mistakes in the realizable setting, under apple
tasting feedback, is

$\Theta\Bigl{(}\max\Bigl{\\{}\sqrt{(\texttt{w}(\mathcal{H})-1)T}),1\Bigl{\\}}\Bigl{)},$

where $\texttt{w}(\mathcal{H})$ is the Effective width of $\mathcal{H}$, a new
combinatorial parameter that considers the asymmetric nature of the feedback.

  * (3)

Using the bound above, we establish the following trichotomy on the minimax
rates in the realizable setting: (i) $\Theta(1)$ when
$\texttt{w}(\mathcal{H})=1$, (ii) $\Theta(\sqrt{T})$ when
$1<\texttt{w}(\mathcal{H})<\infty$, and (iii) $\Theta(T)$ when
$\texttt{w}(\mathcal{H})=\infty$.

To prove (1), we extend the EXP3.G algorithm from alon2015online to binary
prediction with expert advice. Then, we use the standard technique from
ben2009agnostic to construct an agnostic learner using a realizable, mistake-
bound learner in the full-information setting. To prove the upperbound in (2),
we define a new combinatorial parameter, called the Effective width, and use
it to construct a deterministic online learner in the realizable, full-
information feedback setting with constraints on the number of false positive
and false negative mistakes. We then use this online learner and a conversion
technique from helmbold2000apple to construct a randomized online learner in
the realizable, apple tasting feedback setting with the stated guarantee in
(2). For the lowerbound in (2), we consider a new combinatorial object called
an apple tree and use it to explicitly construct a hard, realizable stream for
any randomized, apple tasting learner. This is in contrast to
helmbold2000apple, who prove lowerbounds on the minimax expected mistakes
under apple tasting feedback by converting randomized apple tasting learners
into deterministic full-feedback learners.

###  1.1 Related Works

Apple tasting is usually presented as an example of a more general partial
feedback setting called partial monitoring games, where the player’s feedback
is specified by a feedback matrix (cesa2006prediction; bartok2014partial).
Related to partial monitoring games is sequential prediction with graph
feedback, for which apple tasting feedback is also special case
(alon2015online). In this model, a learner plays a repeated game against an
adversary. In each round, the learner selects one of $K$ actions but observes
the losses for a subset of the actions determined by a combinatorial structure
called a feedback graph. alon2015online classify feedback graphs into three
types and establish a trichotomy on the rates of the minimax regret based on
the type of graph. In this paper, we extend the online learner presented in
alon2015online to the setting of binary prediction with expert advice to
establish the minimax regret of apple tasting in the agnostic setting. As
mentioned in the introduction, helmbold2000apple were the first to study the
online learnability under apple tasting feedback. In addition to establishing
upper and lower bounds for apple tasting in terms of bounds on the false
positive and false negative mistakes in the full-information setting,
helmbold2000apple also give expected mistake bounds in terms of the size of
$\mathcal{H}$. More specifically, they show that for any hypothesis class
$\mathcal{H}$, there exists a randomized online learner whose expected number
of mistakes, under apple tasting feedback, is at most
$O\biggl{(}\min\biggl{\\{}T,\sqrt{\frac{T\ln(|\mathcal{H}|)}{\ln(1+T/(\ln(|\mathcal{H}|)))}},|\mathcal{H}|\biggl{\\}}\biggl{)}$.
They complement this result by giving a matching lower bound up to constant
factor for classes that satisfy a property termed “ample splitability” (see
Section 2.1 from helmbold2000apple).

In a parallel direction, there has been an explosion of work using
combinatorial dimension to give tight quantitative characterizations of online
learnability. For example, Littlestone1987LearningQW proposed the Littlestone
dimension and showed that it exactly characterizes the optimal mistake bound
of deterministic learners for online binary classification in the full-
information, realizable setting. Later, ben2009agnostic show that the
Littlestone dimension also provides a tight quantitative characterization of
the optimal expected regret in the full-information, agnostic setting. Later,
DanielyERMprinciple define a _multiclass_ extension of the Littlestone
dimension and show that it provides a tight quantitative characterization of
realizable and agnostic mutliclass online learnability under full-information
feedback when the label space is finite. In their same work,
DanielyERMprinciple define the Bandit Littlestone dimension and show that it
exactly characterizes the optimal mistake bound of deterministic learners in
the realizable setting under partial feedback setting known as bandit
feedback. daniely2013price later show that the Bandit Littlestone dimension
also characterizes agnostic bandit online learnability. Beyond binary and
multiclass classification, combinatorial dimensions have been used to
characterize online learnability for regression (rakhlin2015online), list
classification (moran2023list), and multilabel ranking (raman2023online).

##  2 Preliminaries

###  2.1 Notation

Let $\mathcal{X}$ denote the instance space and
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ denote a binary hypothesis
class. As usual, $[N]$ is used to denote $\\{1,2,\ldots,N\\}$.

###  2.2 Online Classification and Apple Tasting

In the standard binary online classification setting with full-information
feedback a learner plays a repeated game against an adversary over $T$ rounds.
In each round $t\in[T]$, the adversary picks a labeled instance
$(x_{t},y_{t})\in\mathcal{X}\times\\{0,1\\}$ and reveals $x_{t}$ to the
learner. The learner makes a (possibly randomized) prediction
$\hat{y}_{t}\in\\{0,1\\}$. Finally, the adversary reveals the true label
$y_{t}$ and the learner suffers the 0-1 loss
$\mathbbm{1}\\{y_{t}\neq\hat{y}_{t}\\}.$ Given a hypothesis class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$, the goal of the learner is to
output predictions $\hat{y}_{t}$ such that its _expected regret_

$\mathbbm{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{y_{t}\neq\hat{y}_{t}\\}-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{y_{t}\neq
h(x_{t})\\}\right]$

is small. A hypothesis class $\mathcal{H}$ is said to be online learnable
under full-information feedback, if there exists an online learning algorithm
whose expected regret, on any sequence of labeled instances
$(x_{1},y_{1}),...,(x_{T},y_{T})$, is a sublinear function of $T$. If it is
guaranteed that the learner always observes a sequence of examples labeled by
some hypothesis $h\in\mathcal{H}$, then we say we are in the realizable
setting.

In the apple tasting feedback model, the adversary still picks a labeled
instance $(x_{t},y_{t})\in\mathcal{X}\times\\{0,1\\}$ and reveals $x_{t}$ to
the learner. However, the learner only gets to observe the true label $y_{t}$
if they predict $\hat{y}_{t}=1$. Analogous to the full-information setting, a
hypothesis class $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ is online
learnable under apple tasting feedback, if there exists an online learning
algorithm whose expected regret, under apple tasting feedback, on any sequence
of labeled instances is a sublinear function of $T$.

[Online Agnostic Learnability under Apple Tasting Feedback] A hypothesis class
$\mathcal{H}$ is online learnable under apple tasting feedback, if there
exists an (potentially randomized) algorithm $\mathcal{A}$ such that its
_expected regret_ ,

$\texttt{R}_{\mathcal{A}}(T,\mathcal{H}):=\sup_{(x_{1},y_{1}),...,(x_{T},y_{T})}\mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right],$

while only only receiving feedback when predicting $1$, is a non-decreasing,
sub-linear function of $T$.

Like the full-information setting, if it is guaranteed that the sequence of
examples is labeled by some hypothesis $h\in\mathcal{H}$, then we say we are
in the realizable setting.

[Online Realizable Learnability under Apple Tasting Feedback] A hypothesis
class $\mathcal{H}$ is online learnable under apple tasting feedback, if there
exists an (potentially randomized) algorithm $\mathcal{A}$ such that its
_expected regret_ ,

$\texttt{M}_{\mathcal{A}}(T,\mathcal{H}):=\sup_{\begin{subarray}{c}(x_{1},y_{1}),...,(x_{T},y_{T})\\\
\exists h^{\star}\in\mathcal{H}\text{ such that
}h^{\star}(x_{t})=y_{t}\end{subarray}}\mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\right],$

while only only receiving feedback when predicting $1$, is a non-decreasing,
sub-linear function of $T$.

###  2.3 Trees and Combinatorial Dimensions

In online learning, the combinatorial dimensions are defined in terms of
trees, a basic unit that captures temporal dependence inherent in online
learning. A binary tree $\mathcal{T}$ of depth $d$ is _complete_ if it admits
the following recursive structure. A depth one complete binary tree is a
single root node with left and right outgoing edges. A complete binary tree
$\mathcal{T}$ of depth $d$ has a root node $v$ whose left and right subtrees
are each complete binary trees of depth $d-1$. Given a complete binary tree
$\mathcal{T}$, we can label its internal nodes and edges by elements of
$\mathcal{X}$ and $\\{0,1\\}$ respectively to get a _Littlestone tree_.

[Littlestone tree] A Littlestone tree of depth $d$ is a _complete_ binary tree
of depth $d$ where the internal nodes are labeled by instances of
$\mathcal{X}$ and the left and right outgoing edges from each internal node
are labeled by $0$ and $1$ respectively.

Given a Littlestone tree $\mathcal{T}$ of depth $d$, a root-to-leaf path down
$\mathcal{T}$ is a bitstring $\sigma\in\\{0,1\\}^{d}$ indicating whether to go
left ($\sigma_{i}=0$) or to go right ($\sigma_{i}=1$) at each depth $i\in[d]$.
A path $\sigma\in\\{0,1\\}^{d}$ down $\mathcal{T}$ gives a sequence of labeled
instances $\\{(x_{i},\sigma_{i})\\}_{i=1}^{d}$, where $x_{i}$ is the instance
labeling the internal node following the prefix
$(\sigma_{1},...,\sigma_{i-1})$ down the tree. A hypothesis
$h_{\sigma}\in\mathcal{H}$ shatters a path $\sigma\in\\{0,1\\}^{d}$, if for
every $i\in[d]$, we have $h_{\sigma}(x_{i})=\sigma_{i}$. In other words,
$h_{\sigma}$ is consistent with the labeled examples in following $\sigma$. A
Littlestone tree $\mathcal{T}$ is shattered by $\mathcal{H}$ if for every
root-to-leaf path $\sigma$ down $\mathcal{T}$, there exists a hypothesis
$h_{\sigma}\in\mathcal{H}$ that shatters it. Using this notion of shattering,
we define the Littlestone dimension of a hypothesis class.

[Littlestone dimension] The Littlestone dimension of $\mathcal{H}$, denoted
$\texttt{L}(\mathcal{H})$ is the largest $d\in\mathbbm{N}$ such that there
exists a Littlestone tree $\mathcal{T}$ of depth $d$ shattered by
$\mathcal{H}$. If there exists shattered Littlestone trees $\mathcal{T}$ of
arbitrary depth, then we say that $\texttt{L}(\mathcal{H})=\infty$.

Remarkably, the Littlestone dimension gives a tight quantitative
characterization of realizable learnability under full-information feedback.
In particular, Littlestone1987LearningQW gives a generic deterministic
algorithm, termed the Standard Optimal Algorithm (SOA), and shows that it
makes at most $\texttt{L}(\mathcal{H})$ number of mistakes on any realizable
stream. Moreover, they showed that for every deterministic learner, there
exists a realizable stream that can force at least $\texttt{L}(\mathcal{H})$
mistakes, proving that the Ldim exactly quantifies the mistake bound for
deterministic realizable learnability under full-information feedback.

Under apple tasting feedback, one can use the lower- and upperbounds derived
by helmbold2000apple to deduce that the Ldim also provides a qualitative
characterization of realizable learnability. However, unlike the full-
information feedback setting, the Ldim alone cannot provide matching lower-
and upperbounds on the minimax expected mistakes under apple tasting feedback.
Indeed, $\Omega(\texttt{L}(\mathcal{H}))$ is the best possible lowerbound one
can hope for in the realizable setting in terms of only on Ldim. However, even
for the simple class of singletons over the natural numbers,
$\mathcal{H}=\\{x\mapsto\mathbbm{1}\\{x=a\\}:a\in\mathbbm{N}\\}$, the minimax
expected mistakes scales with the time horizon $T$ (see Section
LABEL:sec:lbrandomreal). Accordingly, new ideas are needed to handle the
asymmetric nature of apple tasting feedback. As a first step, we go beyond the
symmetric nature of complete binary trees and define a new asymmetric binary
tree called an apple tree. In particular, a binary tree $\mathcal{T}$ of depth
$d$ and width $w$ is an _apple_ tree if it admits the following recursive
structure. An apple tree of width $w\geq d$ is a complete binary tree with
depth $d$. An apple tree with width $w=1$ and depth $d$ is a degenerate binary
tree of depth $d$ where every internal node has only a left child. An apple
tree $\mathcal{T}(w,d)$ of depth $d$ and width $w<d$ has a root node $v$ whose
left subtree is an apple tree $\mathcal{T}(w,d-1)$ and whose right subtree is
an apple tree $\mathcal{T}(w-1,d-1)$. At a high-level, the width of an apple
tree $w$ controls the number of ones any path starting from the root can have
before the path ends. The depth $d$ of an apple tree controls the maximum
number of zeros along any path starting from the root. From this perspective,
one can alternatively construct an apple tree of width $w$ and depth $d$ by
starting with a complete binary tree of depth $d$ and then trimming each path
starting from the root node such that it ends once it contains $w$ ones. See
Figure 1 for some examples of apple trees.

Similar to Littlestone trees, we can label the internal nodes of an apple tree
with instances in $\mathcal{X}$ and the edges with elements of $\\{0,1\\}$. By
doing so, we get an Apple Littlestone tree.

[Apple Littlestone tree] An Apple Littlestone tree of width $w$ and depth $d$
is an _apple_ tree of width $w$ and depth $d$ where the internal nodes are
labeled by instances of $\mathcal{X}$ and the left and right outgoing edges
from each internal node are labeled by $0$ and $1$ respectively.

Figure 1: Shattered Apple Littlestone trees of (width, depth): $(3,3)$ (left),
$(2,3)$ (middle), and $(1,3)$ (right).

The notion of shattering for Littlestone trees extends exactly to Apple
Littlestone trees. Formally, an Apple Littlestone tree $\mathcal{T}(w,d)$ of
width $w$ and depth $d$ is shattered by $\mathcal{H}$, if for every path
$\sigma$ down the tree $\mathcal{T}$, there exists a hypothesis
$h_{\sigma}\in\mathcal{H}$ consistent with
$\\{(x_{i},\sigma_{i})\\}_{i=1}^{|\sigma|}$. Note that, unlike Littlestone
trees, Apple Littlestone trees are imbalanced (see Figure 1). In fact, for an
Apple Littlestone tree $\mathcal{T}$ of width $w$ and depth $d$, there can be
at most $w$ ones along any valid path $\sigma$ down the tree before the path
ends. Therefore, not all root-to-leaf paths are of the same length.
Nevertheless, this notion shattering is still well defined and naturally leads
to a combinatorial dimension analogous to the Littlestone dimension.

[Apple Littlestone dimension] The Apple Littlestone dimension of $\mathcal{H}$
at width $w\in\mathbbm{N}$, denoted $\texttt{AL}_{w}(\mathcal{H})$, is the
largest $d$ such that there exists an Apple tree $\mathcal{T}(w,d)$ of width
$w$ and depth $d$ shattered by $\mathcal{H}$. If there exists shattered Apple
Littlestone trees $\mathcal{T}$ with width $w$ of arbitrarily large depth,
then we say that $\texttt{AL}_{w}(\mathcal{H})=\infty$. If there are no
shattered apple trees $\mathcal{T}$ of width $w$, then we say that
$\texttt{AL}_{w}(\mathcal{H})=0$.

Note that
$\texttt{AL}_{w_{1}}(\mathcal{H})\geq\texttt{AL}_{w_{2}}(\mathcal{H})$ for
$w_{1}<w_{2}$. This is because we can always trim paths with more than $w_{1}$
$1$’s in an apple tree of width $w_{2}$ to get an apple tree of width $w_{1}$.
In addition, for all $w\leq\texttt{L}(\mathcal{H})$ we have that
$\texttt{AL}_{w}(\mathcal{H})\geq\texttt{L}(\mathcal{H})$ and for all
$w\geq\texttt{L}(\mathcal{H})+1$,
$\texttt{AL}_{w}(\mathcal{H})=\texttt{L}(\mathcal{H})$. In general, the value
of $\texttt{AL}_{w}(\mathcal{H})$ for $w\leq\texttt{L}(\mathcal{H})$ can be
much larger than $\texttt{L}(\mathcal{H})$. For example, even for the class of
singletons defined over $\mathbb{N}$, $\texttt{AL}_{1}(\mathcal{H})=\infty$
while $\texttt{L}(\mathcal{H})=1$. Accordingly, unlike the Ldim, the ALdim,
does not provide a qualitative characterization of learnability. Instead,
using the ALdim, we define a new combinatorial parameter termed the Effective
width. In Section 3, we show that the Effective width provides a tight
_quantitative characterization_ of realizable learnability under apple tasting
feedback.

[Effective width] The Effective width of a hypothesis class $\mathcal{H}$,
denoted $\texttt{w}(\mathcal{H})$, is the smallest $w\in\mathbbm{N}$ such that
$\texttt{AL}_{w}(\mathcal{H})<\infty$. If there is no $w\in\mathbbm{N}$ such
that $\texttt{AL}_{w}(\mathcal{H})<\infty$, then we say that
$\texttt{w}(\mathcal{H})=\infty$.

Observe that $\texttt{w}(\mathcal{H})\leq\texttt{L}(\mathcal{H})+1$. In
general, one cannot hope to lowerbound $\texttt{w}(\mathcal{H})$ in terms of
$\texttt{L}(\mathcal{H})$. Indeed, for any finite hypothesis class
$\mathcal{H}$, we have that $\texttt{w}(\mathcal{H})=1$ while
$\texttt{L}(\mathcal{H})$ can be made arbitrarily large. That said,
$\texttt{w}(\mathcal{H})<\infty\Leftrightarrow\texttt{L}(\mathcal{H})<\infty$.
The $\Leftarrow$ direction is straightforward from the properties above. To
prove the $\Rightarrow$ direction, note that if
$\texttt{L}(\mathcal{H})=\infty$, then for any width $w\in\mathbbm{N}$ and
depth $d$, one can always prune a shattered Littlestone tree of depth $d$ to
get a shattered Apple Littlestone tree of depth $d$ and width $w$.

##  3 Realizable Learnability

In this section, we revisit the learnability of apple tasting in the
realizable setting, first studied by helmbold2000apple. Our main result is
Theorem 3, which lower- and upperbounds the minimax expected mistakes in terms
of the Littlestone dimension and the Effective width.

[Realizable Learnability] For any hypothesis class $\mathcal{H}$,

$\frac{1}{2}\min\Bigl{\\{}\max\Bigl{\\{}\sqrt{(\texttt{w}(\mathcal{H})-1)\,T},\texttt{L}(\mathcal{H})\Bigl{\\}},T\Bigl{\\}}\leq\inf_{\mathcal{A}}\texttt{M}_{\mathcal{A}}(T,\mathcal{H})\leq\texttt{AL}_{\texttt{w}(\mathcal{H})}(\mathcal{H})+2\sqrt{(\texttt{w}(\mathcal{H})-1)T}.$

The lower- and upperbounds of Theorem 3 can be tight up to constant factors.
To see this, first consider when $\texttt{w}(\mathcal{H})=1$. In this case,
the lower- and upperbounds in Theorem 3 reduce to
$\frac{\texttt{L}(\mathcal{H})}{2}\leq\inf_{\mathcal{A}}\texttt{M}_{\mathcal{A}}(T,\mathcal{H})\leq\texttt{AL}_{1}(\mathcal{H})$
for sufficiently large $T$. Taking $|\mathcal{X}|=d<\infty$ and
$\mathcal{H}=\\{0,1\\}^{\mathcal{X}}$ gives that
$\texttt{L}(\mathcal{H})=\texttt{AL}_{1}(\mathcal{H})=d$, ultimately implying
that the lower- and upperbounds are off only by a constant factor of
$\frac{1}{2}$. Next, consider the case where $\texttt{w}(\mathcal{H})\geq 2$.
Then, the bounds in Theorem 3 reduce to
$\frac{1}{2}\sqrt{(\texttt{w}(\mathcal{H})-1)\,T}\leq\inf_{\mathcal{A}}\texttt{M}_{\mathcal{A}}(T,\mathcal{H})\leq\texttt{AL}_{\texttt{w}(\mathcal{H})}(\mathcal{H})+2\sqrt{(\texttt{w}(\mathcal{H})-1)T}.$
If $T$ is sufficiently large, then
$\texttt{AL}_{\texttt{w}(\mathcal{H})}(\mathcal{H})\leq\sqrt{(\texttt{w}(\mathcal{H})-1)T}$,
and the upperbound becomes $3\sqrt{(\texttt{w}(\mathcal{H})-1)T}$, a constant
factor away from the lowerbound.

Theorem 3 implies that when $\texttt{w}(\mathcal{H})=1$, a constant upperbound
on the expected regret is possible. In fact, when
$\texttt{AL}_{1}(\mathcal{H})<\infty$, there exists a deterministic online
learner which makes at most $\texttt{AL}_{1}(\mathcal{H})$ mistakes in the
realizable setting under apple tasting feedback (see Appendix
LABEL:sec:updetreal for more details). On the other hand, Theorem 3 shows
that, in full generality, it is not possible to achieve a constant expected
mistake bound under apple tasting feedback in the realizable setting. Indeed,
if $\texttt{w}(\mathcal{H})>1$, then the worst-case expected regret of any
randomized learner, under apple tasting feedback, is at least
$\Omega(\sqrt{T})$. This is in contrast to the full-information setting where
a constant upper bound on the worst-case expected regret in the realizable
setting is always possible, and that too by a deterministic learner (i.e SOA).
Accordingly, Theorem 3 gives the following trichotomy of the minimax expected
mistakes in the realizable setting.

[Trichotomy in Minimax Expected Mistakes] For any hypothesis class
$\mathcal{H}$,

$\inf_{\mathcal{A}}\texttt{M}_{\mathcal{A}}(T,\mathcal{H})=\begin{cases}\Theta(1),&\text{if
$\texttt{w}(\mathcal{H})=1$}\\\ \Theta(\sqrt{T})&\text{if
$2\leq\texttt{w}(\mathcal{H})<\infty$}\\\
\Theta(T),&\text{otherwise}\end{cases}$

In Section LABEL:sec:agn, we will show that
$\inf_{\mathcal{A}}\texttt{R}_{\mathcal{A}}(T,\mathcal{H})=\Theta(\sqrt{T})$.
With this in mind, Corollary 3 shows that when $\texttt{w}(\mathcal{H})\geq
2$, realizable learnability under apple tasting feedback can be as hard as
agnostic learnability under apple tasting feedback. Unfortunately, for most
natural classes we have $\texttt{w}(\mathcal{H})\geq 2$. For example, even for
the class of singletons over $\mathbbm{N}$, it is not hard to show that
$\texttt{w}(\mathcal{H})=2$. On the other hand, for classes containing
hypothesis that rarely output $0$, like the “flip” of the class of singletons
$\mathcal{H}=\\{x\mapsto\mathbbm{\\{}x\neq a\\}:a\in\mathbbm{N}\\}$,
realizable learnability under apple tasting feedback can be as easy as
realizable learnability under full-information feedback.

###  3.1 Upperbounds for Randomized Learners in the Realizable Setting

We prove a slightly stronger upperbound than the one stated in Theorem 3.

[Randomized Realizable Upperbound] For any hypothesis class $\mathcal{H}$,

$\inf_{\mathcal{A}}\texttt{M}_{\mathcal{A}}(T,\mathcal{H})\leq\inf_{w\in\mathbb{N}}\left\\{\texttt{AL}_{w}(\mathcal{H})+2\sqrt{(w-1)T}\right\\}.$

The upperbound in Theorem 3 follows by picking $w=\texttt{w}(\mathcal{H})$ in
Lemma 3.1. Note that if you pick $w=\texttt{L}(\mathcal{H})+1$, then
$\texttt{AL}_{w}(\mathcal{H})=\texttt{L}(\mathcal{H})$ and we get an
upperbound of $3\sqrt{\texttt{L}(\mathcal{H})T}$ on the expected mistakes.

Lemma 3.1 follows from composing the next two lemmas. Lemma 3.1 shows that if
$\texttt{AL}_{w}(\mathcal{H})<\infty$, then there exists a deterministic
online learner, under full-information feedback, that makes at most $w-1$
false negative mistakes and $\texttt{AL}_{w}(\mathcal{H})$ false positive
mistakes. Lemma 3.1 is from helmbold2000apple and shows how to convert any
online learner under full-information feedback into an online learner under
apple tasting feedback.

For any hypothesis class $\mathcal{H}$ and $w\in\mathbbm{N}$ such that
$\texttt{AL}_{w}(\mathcal{H})<\infty$, there exists a deterministic online
learner which, under full-information feedback, makes at most $w-1$ _false
negative_ mistakes and at most $\texttt{AL}_{w}(\mathcal{H})$ _false positive_
mistakes in the realizable setting.

###### Proof.

Input: $V_{1}=\mathcal{H}$ , pick $w_{1}=w$ such that
$\texttt{AL}_{w}(\mathcal{H})<\infty$

1

2for  _$t=1,...,T$_ do

3 Receive $x_{t}$.

4 For each $y\in\\{0,1\\}$, define $V_{t}^{y}=\\{h\in V_{t}\,\mid
h(x_{t})=y\\}$.

5 If $V_{t}=\\{h\\}$ then predict $\hat{y}_{t}=h(x_{t})$.

6 If $|V_{t}^{1}|\geq 1$, and
$\texttt{AL}_{w_{t}}(V_{t}^{0})<\texttt{AL}_{w_{t}}(V_{t})$, predict
$\hat{y}_{t}=1$. Otherwise, predict $\hat{y}_{t}=0$.

7 Receive $y_{t}$ and update $V_{t}\leftarrow V_{t}^{y_{t}}$.

8 If $\hat{y}_{t}=0$ and $y_{t}=1$, then update $w_{t+1}\leftarrow w_{t}-1$.
Else, set $w_{t+1}\leftarrow w_{t}$.

9 end for

Algorithm 1 Realizable Algorithm Under Full-Information Feedback

Suppose $w\in\mathbb{N}$ such that $\texttt{AL}_{w}(\mathcal{H})<\infty$ and
denote $\mathcal{A}$ to be Algorithm 1. We now show that algorithm
$\mathcal{A}$, initialized at $w_{1}=w$, makes at most
$\texttt{AL}_{w}(\mathcal{H})$ false positive mistakes and at most $w-1$ false
negative mistakes. Let $S_{+}=\\{t\in[T]\mid\hat{y}_{t}=1\,\text{ and
}\,y_{t}=0\\}$ be the set of time points where $\mathcal{A}$ makes false
positive mistakes, and $S_{-}=\\{t\in[T]\mid\hat{y}_{t}=0\,\text{ and
}\,y_{t}=1\\}$ be the set of time points where $\mathcal{A}$ makes false
negative mistakes.

We show $|S_{+}|\leq\texttt{AL}_{w}(\mathcal{H})$ by first establishing

$\texttt{AL}_{w_{t+1}}(V_{t+1})\leq\texttt{AL}_{w_{t}}(V_{t})-\mathbbm{1}\\{t\in
S_{+}\\},\quad\quad\forall t\in[T].$ (1)

This inequality then implies that the number of false positive mistakes of
$\mathcal{A}$ is

$\begin{split}\sum_{t=1}^{T}\mathbbm{1}\\{t\in
S_{+}\\}\leq\sum_{t=1}^{T}\left(\texttt{AL}_{w_{t}}(V_{t})-\texttt{AL}_{w_{t+1}}(V_{t+1})\right)&=\texttt{AL}_{w_{1}}(V_{1})-\texttt{AL}_{w_{T+1}}(V_{T+1})\leq\texttt{AL}_{w_{1}}(V_{1})=\texttt{AL}_{w}(\mathcal{H}).\end{split}$

To prove inequality (1), we consider the two cases: $t\in S_{+}$ and $t\notin
S_{+}$. Suppose $t\in S_{+}$. Then, we know that $\hat{y}_{t}=1$ and by the
prediction rule of $\mathcal{A}$ in line 5, we must have
$\texttt{AL}_{w_{t}}(V_{t}^{0})<\texttt{AL}_{w_{t}}(V_{t})$. Since $y_{t}=0$,
we further obtain that $V_{t+1}=V_{t}^{0}$ and $w_{t+1}=w_{t}$ in this case.
This yields $\texttt{AL}_{w_{t+1}}(V_{t+1})<\texttt{AL}_{w_{t}}(V_{t})$, which
subsequently implies
$\texttt{AL}_{w_{t+1}}(V_{t+1})\leq\texttt{AL}_{w_{t}}(V_{t})-\mathbbm{1}\\{t\in
S_{+}\\}$.

Now, let us consider the case when $t\notin S_{+}$. In the case when $t\notin
S_{+}\cup S_{-}$, we have $w_{t+1}=w_{t}$ and $\mathbbm{1}\\{t\in S_{+}\\}=0$.
Thus, we trivially obtain
$\texttt{AL}_{w_{t+1}}(V_{t+1})\leq\texttt{AL}_{w_{t}}(V_{t})-\mathbbm{1}\\{t\in
S_{+}\\}$ since $V_{t+1}\subseteq V_{t}$. Next, let us consider the case when
$t\notin S_{+}$ but $t\in S_{-}$. In this case, we have $w_{t+1}=w_{t}-1$,
$V_{t}=V_{t}^{1}$, and $\mathbbm{1}\\{t\in S_{+}\\}=0$. Thus, to establish
inequality (1), it suffices to show that
$\texttt{AL}_{w_{t}-1}(V_{t}^{1})\leq\texttt{AL}_{w_{t}}(V_{t})$. Suppose, for
the sake of contradiction, this is not true and we instead have
$\texttt{AL}_{w_{t}-1}(V_{t}^{1})>\texttt{AL}_{w_{t}}(V_{t})$. Let
$d:=\texttt{AL}_{w_{t}}(V_{t})$. Note that $d>0$ because there must exist
$h_{1},h_{2}\in V_{t}$ such that $h_{1}(x_{t})\neq h_{2}(x_{t})$. Since
$\texttt{AL}_{w_{t}-1}(V_{t}^{1})>d$, we are guaranteed the existence of apple
tree $\mathcal{T}_{1}(w_{t}-1,d)$ shattered by $V_{t}^{1}$. Furthermore, as
$\hat{y}_{t}=0$ and $|V_{t}^{1}|\geq 1$, the prediction rule implies that
$\texttt{AL}_{w_{t}}(V_{t}^{0})\geq\texttt{AL}_{w_{t}}(V_{t})=d$. Accordingly,
we are also guaranteed the existence of an apple tree
$\mathcal{T}_{0}(w_{t},d)$ shattered by $V_{t}^{0}$. Now consider an apple
tree $\mathcal{T}$ that has $x_{t}$ in its root-node, has a subtree
$\mathcal{T}_{0}(w_{t},d)$ attached to left-outgoing edge from the root-node
and has a subtree $\mathcal{T}_{1}(w_{t}-1,d)$ attached to right-outgoing edge
from the root-node. Since all hypotheses in $V_{t}^{0}$ output $0$ on $x_{t}$
and all hypotheses in $V_{t}^{1}$ output $1$ on $x_{t}$, the tree
$\mathcal{T}$ shattered by $V_{t}$. Since $\mathcal{T}$ is a valid apple tree
of width $w_{t}$ and depth $d+1$, we have that $\texttt{AL}_{w_{t}}(V_{t})\geq
d+1$, a contradiction to our assumption that $\texttt{AL}_{w_{t}}(V_{t})=d$.
Therefore, we must have
$\texttt{AL}_{w_{t}-1}(V_{t}^{1})\leq\texttt{AL}_{w_{t}}(V_{t})$. This
completes our proof of inequality (1).

Next, we show that $\mathcal{A}$ makes at most $w-1$ false negative mistakes.
Let $t^{\star}\in[T]$ be the time point where the algorithm makes its
$(w-1)$-th false negative mistakes. If such time point $t^{\star}$ does not
exist, then we trivially have $|S_{-}|\leq w-2\leq w-1$. We now consider the
case when $t^{\star}\in[T]$ exists. It suffices to show that, $\forall
t>t^{\star}$, we have $t\notin S_{-}$. Suppose, for the sake of contradiction,
$\exists\,t>t^{\star}$ such that $t\in S_{-}$. Since $\hat{y}_{t}=0$ and
$y_{t}=1$, we must have $|V_{t}^{1}|\geq 1$. Thus, the prediction strategy
implies that $\texttt{AL}_{w_{t}}(V_{t}^{0})\geq\texttt{AL}_{w_{t}}(V_{t})$.
Given that $t>t^{\star}$ and $\mathcal{A}$ has already made $w-1$ false
negative mistakes, we must have $w_{t}=1$. Thus, we have
$\texttt{AL}_{1}(V_{t}^{0})\geq\texttt{AL}_{1}(V_{t})=:d$. Note that $d\geq 1$
because there must exist $h_{1},h_{2}\in V_{t}$ such that $h_{1}(x_{t})\neq
h_{2}(x_{t})$. Since $\texttt{AL}_{1}(V_{t}^{0})\geq d$, we are guaranteed the
existence of an apple tree $\mathcal{T}_{0}(1,d)$ of width $1$ and depth $d$
shattered by $V_{t}^{0}$. Next, consider a tree $\mathcal{T}$ with $x_{t}$ on
the root node and has a subtree $\mathcal{T}_{0}(1,d)$ attached to the left-
outgoing edge from the root node. Let $h\in V_{t}$ any hypothesis such that
$h(x_{t})=1$. The hypothesis $h$ must exist because $|V_{t}^{1}|\geq 1$.
Putting $h$ in the leaf node following the right-outgoing edge from the root
node in $\mathcal{T}$, it is obvious that $\mathcal{T}$ is a valid apple tree
of width $1$ and depth $d+1$ shattered by $V_{t}$. The existence of
$\mathcal{T}$ implies that $\texttt{AL}_{1}(V_{t})\geq d+1$, a contradiction
to our assumption $\texttt{AL}_{1}(V_{t})=d$. Thus, $\forall t>t^{\star}$, we
have $t\notin S_{-}$. Therefore, the $\mathcal{A}$ makes no more than $w-1$
false negative mistakes. ∎

We remark that helmbold2000line also give a deterministic online learner in
the full-information setting under constraints on the number of false positive
and false negative mistakes (see Algorithm SCS in Section 2). However, similar
to helmbold2000apple, their algorithm checks the existence of an online
learning algorithm satisfying certain properties. We extend on this result in
Lemma 3.1 by giving an SOA-type algorithm that only requires computing
complexity measures.

Lemma 3.1 is the restatement of Corollary 2 in helmbold2000apple. We restate
and prove this result to highlight the simplicity of the randomized realizable
algorithm and its mistake-bound analysis under apple-tasting feedback.

[helmbold2000apple] For any hypothesis class $\mathcal{H}$, if there exists a
deterministic online learner which, under full-information feedback, makes at
most $M_{-}$ _false negative_ mistakes and at most $M_{+}$ _false positive_
mistakes, then there exists a randomized online learner, whose expected number
of mistakes, under apple tasting feedback, is at most $M_{+}+2\sqrt{TM_{-}}$
in the realizable setting.

###### Proof.

Input: Full-Information Algorithm $\mathcal{A}$, false negative mistake bound
$M_{-}$ of $\mathcal{A}$

1

2for  _$t=1,...,T$_ do

3 Receive $x_{t}$ and query $\mathcal{A}$ to get $\xi_{t}=\mathcal{A}(x_{t})$.

Draw $r\sim\text{Unif}([0,1])$ and predict

Algorithm 2 Conversion of Full-Information Algorithm to Apple Tasting
Algorithm

If $T\leq M_{-}$, then the claimed expected mistake bound is $\geq T$ and thus
trivially holds for any algorithm. So, we only consider the case when
$T>M_{-}$. Let $\mathcal{A}$ be a deterministic online learner, which makes at
most $M_{-}$ false negative mistakes and at most $M_{+}$ false positive
mistakes under full-information feedback. We now show that Algorithm 1, a
randomized algorithm that uses $\mathcal{A}$ in a black-box fashion, has
expected mistake bound at most $M_{+}\,+\,2\sqrt{TM_{-}}$ in the realizable
setting under apple-tasting feedback.

For each bitstring $b\in\\{0,1\\}^{3}$, define $S_{b}=\\{t\in[T]\,\mid
b_{1}=\xi_{t},b_{2}=\hat{y}_{t},\text{and }b_{3}=y_{t}\\}.$ Here,
$b_{1},b_{2},b_{3}$ are the first, second, and third bits of the bitstring
$b$. Using this notation, we can write the expected mistake bound of Algorithm
1 as

######  L 2.

E [ ∑_t=1^T 1{^y_t ≠y_t}] = E [ —S_101—+ —S_001— + —S_110— + —S_010— ].

Since $\hat{y}_{t}=1$ whenever $\xi_{t}=1$, we have $|S_{101}|=0$. Note that
$|S_{001}|\leq N$, where $N$ is the number of failures before $M_{-}$
successes in independent Bernoulli trials with probability $\sqrt{M_{-}/T}$ of
success. That is, $N$ quantifies the number of rounds before $\xi_{t}$ is
flipped $M_{-}$ number of times from $0$ to $1$ in rounds when $y_{t}=1$.
Recalling that $N\sim\text{Negative-Binomial}(M_{-},\sqrt{M_{-}/T})$, we have