Online Linear Classification with Massart Noise
Authors: Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
Venue: ICML 2025 poster (2025)
Keywords: Online Learning
Massart noise
Primary area: theory->online_learning_and_bandits

Abstract: We study the task of online learning in the presence of Massart noise. Specifically, instead of assuming that the online adversary chooses an arbitrary sequence 
of labels, we assume that the context $\boldsymbol{x}$ is selected adversarially but 
the label $y$ presented to the learner disagrees with the ground-truth label 
of $\boldsymbol{x}$ with unknown probability {\em at most} $\eta$. 
We focus on the fundamental 
class of $\gamma$-margin linear classifiers and 
present the first computationally efficient algorithm 
that achieves mistake bound $\eta T + o(T)$.   
We point out that the mistake bound achieved by our algorithm 
is qualitatively tight for 
computationally efficient algorithms; 
this follows from the fact that, even in the offline setting, 
achieving 0-1 error better than $\eta$ 
requires super-polynomial time 
under standard complexity assumptions.

We extend our online learning model to a $k$-arm contextual bandit setting where the rewards---instead of satisfying commonly used realizability assumptions---are consistent, 
in expectation, with some linear ranking function 
with weight vector $\boldsymbol{w}^\ast$.   
Given a list of contexts $\boldsymbol{x}_1,\ldots \boldsymbol{x}_k$, 
if $\boldsymbol{w}^*\cdot \boldsymbol{x}_i > \boldsymbol{w}^* \cdot \boldsymbol{x}_j$, the expected reward of action $i$
must be larger than that of $j$ by at least $\Delta$.  
We use our Massart online learner to design an efficient bandit algorithm 
that obtains expected reward at least 
$(1-1/k)~ \Delta T - o(T)$ bigger than choosing a random action at every round.

Online Linear Classification with Massart Noise
Ilias Diakonikolas' Vasilis Kontonis 2
Christos Tzamos 3 Nikos Zarifis
Abstract
In the online scenario, the learner's objective is to tackle a prediction task by acquiring a hypothesis from a series of examples presented one at a time. The aim is to mini- mize the overall count of incorrect predictions, known as the mistake bound, considering the knowledge of correct answers to previously encountered examples (Littlestone, 1988; 1989; Blum, 1990; Littlestone & Warmuth, 1994; Maass & Turan, 1994). In the context of online linear clas- sification, i.e., when the presented labels can be realized by a linear threshold function, the seminal perceptron al- gorithm (Rosenblatt, 1958; Novikoff, 1962), was the first online learning algorithm.
We study the task of online learning in the pres- ence of Massart noise. Specifically, instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context æ is selected adversarially but the label y presented to the learner disagrees with the ground- truth label of æ with unknown probability at most 1). We focus on the fundamental class of 7-margin linear classifiers and present the first computa- tionally efficient algorithm that achieves mistake bound n/T+ + oT)). We point out that the mistake bound achieved by our algorithm is qualitatively tight for computationally efficient algorithms; this follows from the fact that, even in the offline set- ting, achieving 0-1 error better than v) requires super-polynomial time under standard complexity assumptions.
Realizable and Agnostic Online Learning In (Little- stone, 1988) the realizable online classification setting was defined, where the adversary is allowed to select an arbi- trary datapoint (*) at every round but the label y(t) must be consistent with an underlying ground hypothesis f from a class H. The number of mistakes in the realizable setting was shown to be characterized by the Littlestone dimension LD(H) of the class H. Similarly to the agnostic PAC learn- ing of (Haussler, 1992), in (Ben-David et al., 2009), moti- vated by the fact that often the observed labels are noisy, the setting of online learning with label noise was introduced. In the most extreme case of agnostic (adversarial) label noise where no assumptions are placed on the labels, it was shown that the regret over T rounds is Ö D(vT (P)))) Even though the regret in the agnostic setting was shown to be sublinear in T, the corresponding computational task is far from being well unddrrdoooo.d. In particular, even for simple classes such as linear classifiers efficient online algorithms with sublinear regret would imply efficient algorithms in the offline setting - a well known computationally intractable problem (Guruswami & Raghavendra, 2006).
We extend our online learning model to a k- arm contextual bandit setting where the rewards- instead of satisfying commonly used realizabil- ity assumptions-are consistent, in expectation, with some linear ranking function with weight vector w". Given list of contexts æ .x,, if w' > wn' j. the expected reward of action i must be larger than that of j by at least A. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward least (1 1/k) AT o(T') bigger than choosing random action every round.
1. Introduction
Online prediction has a rich history dating back to the works of (Robbins, 1951; Hannan, 1957; Blackwell et al., 1954).
Online Learning with Massart Noise Investigating regimes beyond the above, worst-case, agnostic setting has been an important area of research with the goal to get im- proved regret (and mistake) bounds but also to allow the design of efficient algorithms. Similar to the definition of Massart or Bounded noise (Massart & Nedelec, 2006) for offline (PAC) learning, in (Ben-David et al., 2009) a semi- random online classification setting was introduced with a focus on improving over the agnostic regret bounds. In this model, while the online adversary is allowed to pick
"Equal contribution 'Department of Computer Sciences, Uni- versity of Wisconsin-Maddisnn, Madison, USA 'Department of Computer Science, University of Texas-Austin, Austin, USA 'Department of Computer Science, University of Athens, Athens, Greece. Correspondence to: Vasilis Kontonis casilis@cs.utexas.cduu Nikos Zarifis < wis..
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Linear Classification with Massart Noise
arbitrary locations present to the learner, the labels that they choose must be consistent with the ground-truth with probability strictly larger than 50%.
et al., 2020; Diakonikolas al., 2021a;b) has successfully bypassed the computational hardness of worst-case agnostic learning and has provided efficient algorithms for linear classification in the presence of Massart noise. However, no efficient algorithm that achieves any non-trivial mistake bound is known for the more challenging online Massart setting of Definition 1.1. In this work, we aim to answer the following fundamental question.
Definition 1.1 (Online Learning with Massart Noise (Ben- David et al., 2009)). Fix a class of concepts C over IRd and a target concept c² E C. An (oblivious) adversary selects a sequence of examples x.(), "..,.."""" and noisy ..l.y.)))) y(?)) such that for all label random variables ....,....
holds that Pr(y(") * c" (a((lt) ax(1)] S 17. At round the learner observes x predicts label g(t, and suffers loss 1 ((j(t) + y( The goal of the learner is to minimize the total number of mistakes, defined as (T) = E Ei= (2 + }())].
Are there computationally efficient algorithms for online linear classification with Massart noise?
t= ,,...,,,, T.
Massart Bandits Going beyond full-information on- line learning, we consider the multi-armed bandit setting: a multi-disciplinary research area that was initiated by (Thompson, 1933) and has received enormous attention in the past 30 years (see (Berry Fristedt, 1985; Cesa-Bianol & Lugosi, 2006; Slivkins et al., 2019) and references therein). In this work, focus on the k-arm contextual bandit setting, where at every round / the learner receives k: contexts 2 ...."..(( (t) chooses an action a = 1,.... k, and receives the reward/loss of their chosen action (the rewards of the other actions are not revealed), In this setting com- mon assumption known as realizability (Filippi et al., 2010; Abbasi- Yadkori et al., 2011; Chu et al., 2011: Agarwal et al., 2012; Li et al., 2017; Foster et al., 2018; Foster & Rakhlin, 2020) prescribes that the expected rewards are parametric functions of the contexts, e.g., E(r: x²(²) w x: for some unknown weight vector w. Using this structural assumption, those works typically reduce the bandit prob- lem to an online regression problem which can often be solved efficiently (for linear and generalized linear mod- els). An orthogonal direction (Langford & Zhang, 2007; Dudik et al., 2011; Agarwal et al., 2014) makes minimal distributional assumptions and reduces the contextual bandit problem to agnostic (offline) classification. Since agnostic classification is computationally intractable (for most non- trivial classes) such approaches do not provide end-to-end efficient algorithms and rely on heuristics to solve the un- derlying classification task. Therefore, existing algorithms for contextual bandits either (i) make strong realizability assumptions and reduce the problem to (linear) regression or (ii) make minimal assumptions but face the computa- tional intractability of agnostic classification. Motivated by the online Massart classification setting of (Ben- et al., 2009), in this work, we propose a semi-random and semi-parametti Bandit model that lies between those two extreme settings and investigate the design of "end-to-end" efficient algorithms.
Remark 1.2 (Regret vs Mistake Bound). In Definition 1.1, often the regret over T' rounds is used, i.c., the expected difference between the mistakes made by the learner and the minimum number of mistakes that any hypothesis h in H could achieve
T 16 A h)))
R(T,h) - M() E
Remark 1.3 (Random vs Massart Noise). We stress that the probability that a label is flipped in Definition 1.1 is at most r (and not equal to 1)). The fact that the flip probability is not uniformly 17 for all examples results in asymmetric noise, which is exactly what makes (even offline) learning with Massart noise algorithmically challenging. In fact, as we point out in Remark 1010, achieving optimal error (or regret) in the Massart setting is computationally hard (which is not the case when the labels are flipped uniformly with proba- bility 7)). Here we will focus on obtaining computationally efficient online algorithms matching the best-known offline guarantees of (Diakonikolas et al., 2019).
(1)
In (Ben-David et al., 2009), an algorithm based on Little- stone's 's Standard Optimal Algorithm is given that achieves mistake bound (T) < minnex ET (1)(x(()) * (*) + (H) log T/(1- - 2 2v/1(1 n)). Therefore, as long as :7 is bounded away from 1/2, a strong separation between the agnostic regret (that grows roughly as Q( ((V))) and the Massart regret was established. However, as discussed in (Ben-David et al., 2009), this and other similar approaches for establishing regret bounds do not yield computationally efficient algorithms as they rely on computing combinato- rial quantities that are least as hard as computing the VC-dimension (Frances& & Litman, 1998).
Linear Classification To investigate the computational aspects of online classification we focus on the fundamen- tal class of linear classifiers or halfspaces, i.c., functions of the form h(x) = sign(w x) for some weight vector w E Rd. In the offline setting, a long line of recent works (Awasthi al., 2015; Diakonikolas et al., 2019; 2020; Chen
Before we describe our with its "noiseless" version. Instead of assuming that the ex- pected rewards are given by a linear function of the contexts, we assume that they are ranked according to their linear
noise model, we start
2

---

Online Linear Classification with Massart Noise
scores, i.e., if w² 8, > w= 2 then the reward of action must be at least that of action j.
1. The adversary picks context ( X and draws a random reward vector r()) from D(t,
Definition 1.4 (Contexts and Linearly Sorted Rewards). Let B be the d-dimensional unit ball. We define X' {(x1...., mx))= ..:...., Bg E B) to be the context space. For simplicity, we view each context as d x k matrix X. Fix M > 0 and let w" E IR' be some unit vector. Given a context (zi,..., Ix)) we say that a reward vector r E [0, M1 is sorted according to wn
2. The learner observes the context X picks action at)) E [K] and receives reward (a(t)-
We also define the full-information setting the same way except from the last step where the learner receives reward ra(i and observes the full reward vector ((t)
Remark 1.8. In what follows, we shall often simplify no- lation by writing D(e) instead of Dit.X) for the reward distribution at round t.
for all i,j (r: - (T:-Ty)(w)) (w)
w" xT) 2 0.
Under the linear ranking setting of Definition 1.4 one can reduce the bandit problem to noiseless linear classification task and design efficient algorithms (based on perceptron or linear programming) that will eventually learn to select the action with the highest reward. Our semi-random model extends the above definition where we require that rewards are only sorted in expectation with some margin A > O.
1.1. Our Results
Our first result answers our main question posed in Section I and gives an efficient online classification algorithm that makes roughly nL' + o(T) mistakes in the Massart noise model of Definition 1.1. Our algorithm only requires that the sequence of examples picked by the adversary satisfies a standard 7-margin assumption. Without the margin as- sumption it is known (Littlestone, 1988) that, even in the noiseless setting, is information theoretically impossible for the learner to do less than T mistakes.
Definition 1.5 (Monotone Reward Distributions). Let X' be the context space and T = N be the set of rounds. Fix some unit vector w* E Rd, MM > 0, and > O. Define a class of distributions D indexed by rounds t and contexts X: D = (D(+X); t E T, X E X}. We assume that each reward distribution D(t.X) is supported on [0, M) We say that the class 'D has monotone rewards with respect to w" with margin A if for all & E T.X E X, i,j E [k] with i * j it holds
Theorem 1.9. Consider the Online Massart Learning set- ting of Definition 1.1. Additionally, assume that the exam- ples picked by the adversary have at least ?-margin with respect to some target halfspace, i.e.,oo all t= =1 1, it holds that || 12 S 1 and |w* xx( (wxx((()) 2 for some unit vector w.. There exists an algorithmn that does M(T) = nīT' + O(T3/4/77 /7) mistakes and runs in poly(d) time per round.
E T- D()
[r: rj w=" 2; > w x.5] 2 A.
Remark 1.6 (Massart Online Classification as a 2-arm Ban- dit). To obtain the online Massart setting we set the re- wards (()) ((1 + y /2, (1 - //2) and the con- texts (1) = -0)). We observe that in that case when (1) satisfies the Massart noise condition of Defini- tion 1.1, holds that conditional on w² > it holds (0)
Our mistake bound matches (when viewed as an offline PAC learning result) the best known error guarantees of the cor- responding offline learners of Massart halfspaces with mar- gin given in (Diakonikolas et al., 2019; Chen et al., 2020). Moreover, the mistake-bound achieved by our algorithm is essentially best-possible when considering computation- ally efficient (statistical query) algorithms: in the recent works (Diakonikolas & Kane, 2020; Diakonikolas et al., 2022; Nasser Tiegel, 2022) that consider offline (PAC) learning with Massart noise, it is shown that, even when the underlying distribution has ---margin, no polynomial- time algorithm can achieve classification error better than n/ h/polylog(1/(t (1-2)) in the Statistical Query framework. By a standard online to offline reduction this readily implies a T/T' lower bound (up to polylog(1 Remark 1.10 (Information -hheoretic vs Computationally Efficient Online Learning). The n/? mistake bound is not information-thhcortiiall optimal: in particular, in (Ben- David et al., 2009)) better, nparmop mistake bounds are given albeit with inefficient algorithms (i.e., with run- time exponential in the dimension d). When considering
(2) r2 ] 2 1 2n. Therefore, Definition 1.5 is satisfied with == =1=1 2m.
that [((r)
We stress that the monotone reward distributions of Defini- tion 1.5 are a cemimparametric model as we do not assume that the expected rewards have some parametric form rather than only require that they are sorted with respect to lin- sorting function. A similar semi-randon linear sorting model was used in (Fotakis et al., 2022) in the context of (offline) learning linear rankings with bounded noise under the Gaussian distribution. We next define our contextual bandit model.
- (1)) factors).
Definition 1.7 (Contextual Bandits with Monotone Re- wards (Massart Bandits)). Fix some unit vector w" E Rd4, 7, A, M > 0. and a class of monotone reward distributions DD (see Definition 1.5). At round t:
3

---

Online Linear Classification with Massart Noise
computationally efficient algorithms, as do here, there is strong evidence (see the SQ lower bounds of (Diakoniko- las & Kane, 2020; Diakonikolas et al., 2022)I) that the r/f' mistake is essentially best possible. Before our work no computationally efficient algorithm was known that could beat the random guessing benchmark (that makes 2/2 mis- takes). Moreover, we remark that, even in the offline setting of linear classification under Massart noise, the first compu- tationally efficient that achieved classification error 7 (the offline equivalent of n/T mistakes) was only given in the relatively (given the history of the problem) recent work (Diakonikolas et al., 2019).
of arms a
3..., al (2)
E [k] that obtain expected reward
E (alt))
E
k AT - OTTM
Our algorithm for the k-arm bandit setting relies on the observation that, assuming that we could observe all rewards
(1) then one could treat the labeled pairs (ar)² 2.
(1) (())
as real-valued versions of online linear classification with Massart noise and provide it as input to our online learning algorithm. As is common in bandit problems, to adapt this iull-information" approach to the bandit setting, we pick a random action with small probability at every round that provides us with unbiased estimates of the full reward vectors. For more details we refer to Section 3. Finally, we remark that for the special case of 2-armed bandits our result implies the following corollary.
Our algorithm is partieularly simple: we perform online gradient descent on sequence of reweighted Leaky-ReLU loss functions. The Leaky-ReI.U U loss has been successfully used in several works on learning with Random Classifica- tion and Massart noise (Bylander, 1998; Diakonikolas et al., 2019; Chen et al., 2020). In the online setting however simply using (online) gradient descent on the Leaky-Rel. does not suffice: even though the adversary is restricted to select examples with margin with respect to some ground- truth halfspace, they can still select examples very close to the decision boundary of the current hypothesis which would cause online gradient descent to get stuck or con- verge to sub-optimal solutions. To overcome this issue, we reweight the Leaky-Rel.U loss by the margin of the cur- rent example according the current hypothesis vector, see Algorithm 1. We are then able to show that standard regret guarantees for Online Convex optimization can be translated to obtain mistake bounds in the presence of Mas- sart noise, see Lemma 2.2. Finally, we remark that our technique is also valuable for the offline setting: the re- cent works (Chandrasekaran et al., 2024; Diakonikolas & Zarifis, 2024). building on the ideas of this paper, were able to design sample-optimal algorithms for offline Massart classification.
Corollary 1.12 (Monotone 2-arm Contextual Bandits), Con- sider the monotone reward online setting of Definition 1.5. In the bandit setting, Algorithm 3 produces a sequence of arm choices a ..... (T) E {1,2] that obtain expected reward
E
T Σ rl
(t)
(a
2 E
Σ
T
+ 2
2
1=1
1 AT - ((MP) /7)
2
Corollary 1.12 is generalization of our online learning result of Theorem 1.9: indeed, using Remark 1.6, we obtain that the expected reward is equal to MT), where (T) are the expected mistakes. Thus, Corollary 1.12 implies that T - (() > T/2 (2/2)T (2222/++++)) +T( and, using the fact that A 1 2n and M 1, we get that MT) S TÿT + oTT). Given the hardness result for improving upon n/T regret for online Massart classification that we already discussed we conclude that our reduction from Bandit to Online Massart is tight for 2-armed bandits.
We next present our result on semi-random "Massart" k- arm setting presented in Definition 1.5. In addition to the A "reward-margin" assumption of Definition 1.5, similarly to our online classification result of Theorem 1.9, we require a y cecommtriic-arginn assumption for the contexts with respect some halfspace. We give efficient bandit algo- rithm, see Algorithm 3, that is able to accumulate expected reward roughly AT more than playing random action at every round.
1.2. Notation
For n E Z,, let [n] == (1.. We use lowercase boldface characters for vectors. We use x for the inner product of x,y E Rdd. For x E Rdd ||x||| denotes the f2-norm of x. For a set of vectors k. X = (.1,...,x1]) X,-, denotes the difference between the vectors 2;, Zy. i.e., X.-j = -;-20 Dzj. We use 1 1{A} denote the characteristic function of the set A. We use the standard O()), 0,), asymptotic notation. We use Ex-D [X] for the expectation of a random variable X according to the distribution D and Pr[E] for the probability of event E. For simplicity of notation, we omit the distribution when is clear from the context.
Theorem 1.11 (Monotone k-arm Contextual Bandits). Con- sider the monotone reward online setting of Definition 1.5. Moreover, for some unit vector w" E Rd, assume that for all 1, it holds that for all i <|x("012 || S 1 and for all i + j. ww. x!!) -w- x 100) 2 7. There exists a bandit algorithu that runs in (dly(d) time per round and selects a sequence
4

---

Online Linear Classification with Massart Noise
2. Online Learning with Massart Noise
Algorithm 1 Online Learning Massart Halfspaces
In this section, we provide an algorithm for online learning halfspaces with Massart noise. The learner iteratively pro- cesses a sequence of covariates and associated labels (z, y) provided by the adversary, chooses label corresponding to the current decision vector w. and then updates (even if the label was correct) the decision vector using a carefully cho- sen convex loss. Our loss is based on a modification of the Lea loss, i.e., LeakyReLU (t) é (1 - Ajtl(t > 0}- + A (t < 0}. First, we show an equivalent expression for the Leaky-ReLU loss.
1. Ā - 2n - c, T f//4 and (0) = e1.
2. For = ,
;T:
(a) Adversary selects point (+)) E R and generates label y(t)
(b) Learner observes a:()) and chooses label g()) sign(w(() x01)
(c) Learner gets label y(t).
(d) Set
( (w) = Ci(w x01);
Fact 2.1. Let (ta)yReLU,(t) A (1- Att > 0} + ft < 0}. It can be equivalently expressed as LeakyReLU, - 1/2((11 - 21] +1).
max max(|20(1) =0())
(e) Run Online Convex Optimization on (')(.).
Proof. Note that it holds (n > 0} = (t + 121)/2 and tist < 0} = (t- 1t)//2. Therefore by plugging these we obtain
identities in the definition of LeakyReI.U,,
Proof. Denote E = A - A, with e < A/2 and let T S cy/2. Let (FET)) be a filtration adapted to stochastic sequence w((1) We note that the expectations in this proofs are with respect the random variables y(). First, we show that the optimal decision vector w" " gets a negative loss on expectation.
the result. 0
In our algorithm, we use as loss the LeakyReLU, x (yyy where t E E and y E {=1}. For the sake of brevity in notation, we define Cs (t: y) = (1- (-ty), i.e.
Ca(t:)) 3) & (1/2) - yt).
Claim 2.3. It holds EycolC3 (w" x(1); | FQ) s
We provide some intuition behind our choice of the Leaky- ReLU loss. Notice, that in Definition 1.1 we have the label consistency which corresponds to the condition Ely]sign(w" x) 2 (1 2ny) == A. This is clear, from the fact that y * sign( ww" .x) with probability at most 17 and that, Ey = E, [sign( w= xx) (1 {v sign(w" æ)} - [1 + sign( w- x}}] = sign( w-' x1 - E * sign( =)))), therefore Ely]sign(w)) w-' . x² 2 A. The Leaky-ReLUU loss has the property that E, (a
- (c/2)) s00)
Proof. Recall that C (x(t:) = (1/2) - yt), therefore, we have that
E IC (w" g(t)
x (0) ;)))
| F(0]
1
A
lw*
(t)
E (t F(W) (1)))
x; y) < 0 (see Claim 2.3), which we can later use to design a loss for our problem. However, optimizing this loss function exclusively does not guarantee minimal regret. To this end, we define the loss function k,, (w, y, .² =
2
1
A
[v y(o)
E
F=(0) [ Isign(w" x (1)0))) x (0)
2
1
Ca (ww-ww To sim-
$
A)
(1
max{ uu (T)
C3 (0) max()u(0)))1))111)
plify the notation, we define (w)
where we used that E, (y (v(() | Flojsigg("" xo(1)) 2 A. 0
where T, A are fixed and the other parameters are chang- ing through the iterations of our algorithm. Subsequently, we demonstrate that minimizing the regret associated with these reweighted chosen loss functions concurrently yields substantive guarantees for the regret in the context of Defi- nition 1.1.
We first show that EI (()) )) S -Tye/2. Us- ing the tower rule, we have that E|ΣTT1 p(() (w")] = Σ Eleo (w=) I FOO. From Claim 2.3, we have that E Eyeo (Cx(-w- (. S (e/2)) (0). Hence,
-T
we have that
Lemma 2.2. Assume that a sequence (t) is produced by a (possibly randomized) online algorithm A with the guar- antee that E E T (w)(()) -Et ( (w=)) < R(T). with ((0) (wv) C3 (w xn (1) (5) Then, for R(T,e,7,7) maxx wo (0)))
Σ (t) (w*) F((1
(1)
T.
1 . ((()
S <((1/2)
(87)) it holds T((e/2) + (87)/(E7) + R(T)
[=1 max (n()) 2x(1) =0,)
Σ E[ (sign(w (9 (0) + y (0 < Tn+ R(T,
S
(e7//) Σ
T
max max((w(l) x(()),7)²
1
(2)
5

---

Online Linear Classification with Massart Noise
where we used that /w0 x01 2 y from the assumptions. Recall that 33 (w- x; v) = (A/2) ysigu((w x)) w æ/. Let (y) (1/2) ysign(w(!) x))))). Using the
Ei sign(w!() x00)) E (ly( on both sides of In- equality 4 and using that g( (Elyl) S 2 for all E [77, we have:
tower rule, we get
Σ( ( sign(w(() ( (x Ely((1))
E
(1)
Σ pl (10')
T
(A sign(w(()) x ) Ely(11)
KEJ
T
(20(t) sc(*))
Σ
9
(Ely
19
1)
1
S (T) + 2|J1.
(6)
max( w0(1) 2x (+()),T)
where we have used that Σter ( - sign (w
- =e(e0)
) Ely("!) < 2| and that 12, la I 0 as discuseed above. Equivalently, using Inequality 5, we obtain the fol- lowing bound over all rounds L = 1..... T: E sign(w(() (9) (1) Efy(0) S -2((T) (T) Using that sign (wol (9) - (0) by = 1-21 (sign( 0zxl)) +
We define J to be the set of rounds where the (20 1 xz(1) is smaller than the threshold T, i.e., J = [t: (wo()) c0())) S <T). We have that
(() and A = - 2n we get that
(t) (0(1))
Σg 1 E (4) tgJ
max( ()(+)) max(|2o(() =0(1),7)
T
((ign(() ( . x (0)) + y (
=mgh (Eyy()) F) 2 -(T -1T-1/ (3)
S T(n +) + R(T) + 16( + T)t((e))-
and that Σies g¹ (Ely | F(O te
ma on (1).) I
Before proceeding with the proof of Theorem 1.9, we make use of the following fact about the online gradient descent on convex functions to bound the R(T) of Lemma 2.2.
-1/1/2. Moreover note that from Inequality 2, it
holds that Σies - -E(( (wx)) 2 (e7)/(2T)[]] and that
Engs 2((("((w)) 2 0. Therefore, we get that
Fact 2.4 ((Hazan, 2016)). Let g(t) be convex function and let D = diam(W) and let G = max, || (+)()) Online gradient descent with step size: X = D/(GvT) guarantees the following for all T 2 1:
Σ (EJ
EL w ]] | 2 2T NEJ
T Σ
-
12-111
and by using our assumption that + S 6922, we get that Eie, ([(()) - Eig, E(e() 2 [J](et)/(47) (47). Using the assumption for the regret guarantee, we have that E (w)()) < R(T) + E ((0 (w)()) which
T R(T) Σ (w)
min Σ w
400 S GD/3VT.
equivalent to
Proof of Theorem 1.9. Using Fact 2.4, we get that R(T) = D(VT/T), therefore from Lemma 2.2, we get that the ex- pected total regret is bound above by E (1)ggn(wo()) (0)) * y²) I nT + 7( T). where (c/2)T + R(T) + (R(T) + T To minimize this quantity, we set 7 O(cl+5n) for any C > 0 and = ((T-1/(4+2))
Σ E(el (w) {) & R(T) 2
R(T,e,
(w - Ele(t) (w")(ww)) (w))))
Σ E(e(0) (w")) [[e()((ww)
/7) gives R(T, e, 7,T) S 73/4 (3/4-0(() 1144000//. By taking Ç close to 0 and get the result.
(4)
3. Contextual Bandits with Monotone Rewards
Using that 1, 2 (IJ) - 7)/2 from Inequality 3, that 12 < -IJ((e))/(477 from above and that La < 0 from Claim 2.3, we have that
In this section, we describe an algorithm for the setting of Definition 1.5. To this end, we use generalization of the LeakyLeRU loss we used in Theorem 1.9. This loss is described in Algorithm 2. First we show that our loss satisfies some properties required by our main algorithm to work. The proof can found at Appendix A.
M < (R(T) + (T))))/(er)
(5)
Finally, from the regret guarantees, i.e., Inequality 4, we have that Eig E[((t( < R(T). Recall that that (00) (Ely)) = (ā Ely]sign( ( (w) (.())). By adding
Claim 3.1. The loss {(w) computed by Algorithm 2 is con- vex and 2 max(A, Lipsship
6

---

Online Linear Classification with Massart Noise
Lemma 3.2. Let wol be the sequence produced by algo- rithm Algorithm 3 in the bandit setting of Definition 1.5 with exploration probability It holds
Algorithm 2 Compute G(w; X, v,),a), where is the argument and X, v, a parameters.
E
(Gw X (0)) aa G(w"; x
(0 (0))
Generate reward differences and context for every
j (L). y = =Ta" 5.
S SOKMVTA/O))
2. If u = 0: Return the loss
where the expectation is over the randonmess of Algorithm 3 and the randomness of the reward vectors r(t) ~ D(0.
{(w) = G(w;; X, u, - - w Xa- iJj
fta
3. Otherwise:
Proof. We first show that for any reward vector r()) the loss g(t) (w) that we construct at every round an unbiased estimate of the corresponding full-information loss function G(w; X(1,, w0(), ,r(), (4))). We show the following claim, see Appendix A for the proof.
(a) For every j E {1....,k] set:
2j X + psign X a-3 Xa-3
0)00111122
(b) Return the loss
Ca (w 25: v,) v ,2,
((w) = G(w; X, U.T,
Claim 3.3 (Unbiased Loss Estimate). For any w E R it holds
fza
E [e(0) [(()(w)))) (w) F=() (00] G(w; x (1), (0()) (1)) (1)). e09,3t0
We have that the loss (()) = G(w;; ( un()) 7:(1) (0) constructed at each step t of Algorithm 3 is convex since it is the convex combination the zero loss and the convex losses G(w; ( ((() r, (! (see Claim 3.1) for differ- ent reward vector vectors r (each realization of the random variable g(t) corresponds a different reward vector r). From Fact 2.4 and Claim 3.1 we have that the sequence w!!) produced by Algorithm 3 achieves expected regret
Algorithm 3 Bandits with Monotone Rewards
1. (0) -1
2. For I:
(a) Adversary picks context (1) (x) T and samples reward p((() (())
(b) If ((()) 0: Learner picks uniformly random
E
(0) (1) (((() (9 -G x(1), n(0
((10 (((0,a()))))
a (1)
(c) Otherwise: Learner picks (+) argmax, (
<O(KMVTA/O)
(d) Learner flips coin c(t) with HEADS probability q.
Next, we prove generalization of Lemma 2.2 for the k-arm setting. It shows that minimizing the regret over the loss functions, bounds the expected reward our setting.
(e) If HEADS:
Learner picks uniformly random action g(0)
ii Learner gets reward p(()) (3(9)) and defines the fake reward vector (t))
Lemma 3.4. Let ((() be a stochastic process in RRd adapted to the filtration (F(t) such that
(i) (i)
(A: 1) ((((0)
if = g(t)
E
Σ ((ml (()) (0)) ((()) a0)))
M - (3(00)
i + g(t)
1=1
iii. Set (()((w) (w) = G(w; ((), (t) (() (t).
Σ G(w ((1) ( x1()) (20))a00))
S SR(T).
If TAILS: Learner gets reward ((t) (t) and sets (()) 0.
Then, for R(T, y, A, (R(I)/K)(L + 1/(7A)) + TM/A, it holds that
(g) Learner performs Online Convex Optimization with loss (())))).
E
ale))
2 E
Σ
M
C
+ (k- 1k-11
-R(T,7, A,T,,,,,AAR A,K)

---

Online Linear Classification with Massart Noise
Proof. We denote as A the event that w(() f 0 and p 7/2. 2. We first observe that by adding psign w xoox" x() a(") w to
A Therefore we can decompose r a(t) as follows
the difference (()) -j we do not affect the choice of the the
(4) a0
optimal weight vector w" and our guess w()), We observe
k
1=1
that w- = "ign(w"" -x(() -x)0- (Iw* X x pw
(0)
(1)
k
1
sign (w (1)
(t) a(1) ay) all (0)))
+ jta(!)
w /1|20 12) 2 7 - 2 0, therefore sign(w" w- (0)
k
sign(w" (w" 0 ). For wi()) the similarly note that w
Furthermore, note that when we are in the event (A the learner chooses a random action, therefore, using In- equality and the equality above, we have that the expected reward
x()) =) sign(ww (w a( - - (1(0(1))22
(1)
First, show that the optimal decision vector w gets negative loss expectation (see Appendix A).
Claim 3.5. It holds that
E
(t) at
E
(1)
k
E y
Σ e00 (wo")))))
(wo)
- A 1((A0))))
A(T J) (2R(T)/K)
k
Using Claim 3.7 and setting R(T, 7, A,A,) (R(T)/k)(1 + 1/(7A)) + TM/A, we complete the proof of Lemma 3.4.
Next, we bound the contribution of the loss of the (()) (See Appendix A for the proof).
The proof of Theorem 1.11 follows from Lemma 3.4 and Lemma 3.2, see Appendix A for details.
Claim 3.6. It holds that
T
E
e w
(1)
Σ
Σ
(1/2)(A
4. Conclusions and Open Problems
1=1 (1)
In this work we considered online linear classification in the Massart or Bounded online classification model of (Ben- David et al., 2009). Under a standard (and necessary) margin assumption, we gave the first efficient algorithm for this problem achieving mistake bound of Ty7 + oT). This bound is essentially optimal due known hardness results in the Statistical Query model (Diakonikolas et al., 2022). We extended our online learning setting to k-arm Bandit model that lies between the commonly used regression- based, realizable and the pessimistic agnostic classification contextual bandit models. In this model, we utilized our online Massart learner to obtaín an efficient bandit algorithm that obtains roughly (1 - 1/k)) AT more reward than playing at random every round. We observed that our reduction tight for the case of 2 arms (given the aforementioned SQ hardness results for learning with Massart noise). However, for > 2 arms it is unclear whether this reward bound is best possible, as the gap between playing at random and playing the best arm at every round may be much larger than A. We leave this as an interesting open problem for future work.
sign(w
x
(1)
E[(r.
(1)
-r, ()))))))(
a(
Let J Et_ 1((4())) we bound from above (See
Appendix A for the proof).
Claim 3.7. It holds that
J s (R(T) + TM 1))/((k- 1))AA).
By plugging Inequality 8 and using Claim 3.5 in the assump- tion for the regret guarantee, we get that
T
Σ Σ
((g (() [444)((-sssnnuuu a()) -3)
1= j$a(t)
Eir a00 - -111 2R(T).
(7)
Finally, we need to bound from below the term (() reward of each round r02 with the regret of the loss (7). Note that if the learner chose the action (*) that means that (t))) x( (t) - 2 for all j given that we are in the event
E E alts] For this reason, we need connect the
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. This work is theoretical in nature and focuses on advancing fundamental knowledge. As such, it
8

---

Online Linear Classification with Massart Noise
does not directly raise any societal or ethical concerns that warrant speriaa consideration.
Chandrasekaran, G., Kontonis, V., Stavropoulos, K., and Tian, K. Learning noisy halfspaces with margin: Mas- sart is no harder than random. In The Thirty-eighth An- nual Conference on Neural Information Processing Sys- tems, 2024.
Acknowledgements
ID was supported NSF Medium Award CCF-2107079, ONR award number N00014-25-1-2288 and an H.I. Romnes Faculty Fellowship. VK was supported in part by by NSF Award CCF-2144298. CT was supported by NSF Award CCF-2144298. NZ supported in part by NSF Medium Award CCF-2107079.
Chen, S., Koehler, F,, Moitra, A.. and Yau, M. Classification under misspecification: Halfspaces, generalized linear models, and connections to evolvability. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
Chu, W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statisties, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
References
Yadkor,, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Diakonikolas, I. and Kane, D. M. Hardness of learning halfspaces with massart noise. CoRR, abs/2012.09720, 2020.
Agarwal, A., Dudík, M. Kale, S., Langford, J., and Schapire, R. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pp. 19- 26. PMLR, 2012.
Diakonikolas, I. and Zarifis, N. A near-optimal algo- rithm for learning margin halfspaces with massart noise.
The Thirty-eighth Annual Conference on Neural In- formation Processing Systems, 2024. URL https: / /ppenevview net/ forum? aaw.iiddddaa2252222222
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algo- rithm for contextual bandits. In International Conference on Machine Learning, pp. 1648-1646. PMLR, 2014.
Diakonikolas, I., Gouleakis, T., and Tzamos, Distribution- independent pac learning of halfspaces with massart noise, In Wallach, H., Larochelle, H., Beygelzimer, A., d' Alché Buc, F., Fox, E., and Gamett, R. (eds.), Advances in Neural Information Processing Systems 32, pp. 4751- 4762. Curran Associates, Inc., 2019.
Awasthi, P., Balcan, M. F., Haghtalab, N., and Umner, R. Ef- ficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference Learning The- ory, COLT 2015, pp. 167-190, 2015.
Diakonikolas, I, Kontonis, V., Tzamos, C., and Zarifis, N. Learning halfspaces with tsybakov noise. arXiv, 2020.
Ben-David, S., Pál, D., and Shalev-Shwartz, S. Agnostic online learning. In COLT, volume 3, pp. 2009.
Diakonikolas, I., Kane, D. M., Kontonis, V., Tzamos, C., and Zarifis, N. Agnostic proper learning of halfspaces under gaussian marginals. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021a.
Berry, D. A. and Fristedt, B. Bandit problems: sequential allocation of experiments (monographs on statistics and applied probability). London: Chapman and Hall, 5 (71-87):7-7, 1985.
Diakonikolas, I., Kane, D. M., Kontonis, V., Tzamos, C., and Zarifis, N. Efficiently learning halfspaces with tsybakov noise. STOC, 2021b.
Blackwell, D. et al. Controlled random walks. In Pro- ceedings of the international congress of mathematiiians volume 3, pp. 336-338, 1954.
Diakonikolas, I., Kane, D., Ren, L., and Sun, Y. Sq lower bounds for learning single neurons with massart noise. Advances in Neural Information Processing Systems, 35: 1,, 2022.
Blum, A. Learning Boolean functions in infinite attribute space. In Proceedings of the Twenty-Second Annual Sym- posium on Theory of Computing, pp. 64-72, 1990.
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J., Reyzin, L., and Zhang, T. Efficient optimal learning for contextual bandits. arXiv preprint arXiv:1106.2300 2011.
Bylander, T. Worst-case analysis of the Perceptron and exponentiated update algorithms. Artificial Intelligence, 106, 1998.
Filippi, S.,, Cappe, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
Disnchi,,,hi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.

---

Online Linear Classification with Massart Noise
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and ef- ficient contextual bandits with regression oracles. In International Conference Machine Learning, pp. 3199- 3210. PMLR. 2020.
Massart, and Nedelec, E. Risk bounds for statistical learning. Ann. Statist., 34(5):2326-2366 October 2006.
Nasser, R. and Tiegel, S. Optimal SQ lower bounds for learning halfspaces with massart noise. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1047-1074. PMLR, 2022. URLhttps: /ptppeeeeocgggseeeeeeeeepee mlr press/ 1.78/nasserran html.
Foster, D., Agarwal, A., Dudík, M., Luo, H., and Schapire, R. Practical contextual bandits with regression oracles. In International Conference Machine Learning, pp. 1539-1548, PMLR, 2018.
Fotakis, D., Kalavasis, A., Kontonis, V., and Tzamos, C. Lin- ear label ranking with bounded noise. Advances in Neural Information Processing Systems, 35:15642-15656, 2022.
Novikoff, A. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematcal Theory of Automata, volume XII, pp. 615-622 1962.
Frances, M. and Litman, A. Optimal mistake bound learning is hard. Information and Computation, 144(1):66-82) 1998.
Robbins, Asymptotically subminimax solutions of com- pound statistical decision problems. In Proceedings of the second Berkeley symposium mathematical statistics and probability, volume 2, pp. 131-149. University of California Press, 1951.
Guruswami, V. and Raghavendra, Hardness of learning halfspaces with noise. In Proc. 47th IEEE Symposium Foundations of Computer Science (FOCS), pp. 543-552. IEEE Computer Society, 2006.
Rosenblatt, F.
The Perceptron: probabilistic model for information storage and organization in the brain. Psy- chological Review, 65:386 407866407,, 1958.
Hannan, Approximation bayes risk in repeated play. Contributions the Theory of Games, 3:97-139, 1957.
Slivkins, A. al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1- 2):1-286, 2019.
Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications. In- formation and Computation, 100:78-1555 1992.
Thompson, W. On the likelihood that one unknown prob- ability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285 284-294, 1933.
Hazan, E. Introduction to online convex optimization, Foun- dations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Langford, J. and Zhang, T. The epoch- epoch-greedy algorithm for multi-armed bandits with side information. Advances neural information processing systems, 20, 2007.
Li, L., Lu, Y., and Zhou, D. Provably optimal algorithms for generalized linear contextual bandits. In Interna- tional Conference on Machine Learning, pp. 2071-2080. PMLR. 2017.
Littlestone, N. Learning quickly when irrelevant attributes abound: a new tineso-treehoold algorithm. Machine Learning, 2(4):285-31 318, 1988.
Littlestone, N. Mistake bounds and logarithmic linear- threshold learning ulgorithms. PhD thesis, University of California at Santa Cruz, 1989.
Littlestone, N. and Warmuth, M. The weighted majority algorithm. Information and Computation, 108(2):212- 261, February 1994.
Maass, W. and Turan, G. How fast can threshold gate learn? Hanson, S., Drastal, G., and Rivest, R. (eds.), Computational Learning Theory and Natural Learning Systems, pp. 381 11-444 MIT Press, 1994.
10

---

Online Linear Classification with Massart Noise
Supplementary Material
A. Omitted Proofs from Section 3
A.I. Proof of Claim 3.1
We prove the following:
X, v,r, at) generated by Algorithm 2 is convex and 2M max(A, p/ppssccch Claim A.I. The loss {(w) = G,,;
Proof. First, E(.) is convex because is sum of convex functions. Moreover, note that the derivative is
Asign(w (w: 2z) Zjz
V((w)
Σ
|.
jza
and note that |y| S max; [x]] and |zy1|2 $ 2 p since all the x; have norm most 1. Hence, ||V((u)]]2 is upper bounded by k max; [rs] maxx(1//u zil) S 2k max; tri//p.
A.2. Proof of Claim 3.5
We provide proof for the following claim:
Claim A.2. It holds that Ey EyyEi (u))))) ((A(0))).
Proof. Using the tower rule, we have that
T
T
E
2 (w"))
E 1 ( (w))){{A()) [
E=1
We first show that E (e(( w )) (A(0)) < 0. Recall that Ca(t:)) = 2 (Aad) yt). By taking the expectation over in
the Ey,Caa( (-ww" = y (1)
].
we get that
ElCa(- ww- (0)
2 10,
= 2 (A 2 - [[ ( --/0 122 200). x
(t) Recall that by the Definition 1.5, we have that El(r al r (1) |sign(wo x(1)
all -3) 2
A and as we discussed above
sign(w" 2 sign(w"
(+) alt) -)). Therefore we have that
[ (99) - -r - w" 200) 2 2=)22/2/ >//"" 2
which gives that Ey(Ca(-w" (1), (1) s 0 and hence E, (w())(()w"))) (4 s 0. Next, with similar arguments as = 1 before we have that [e) (w") (w))) s ((AS)((A))()) which completes the proof.
A.3. Proof of Claim 3.6
We prove the following:
Claim A.3. It holds that
T
E
w (t) = Σ Σ (A/2)(A
1=1 (1)
(!)
x(1)
(())
El(r alt) - -r +))))1)1AA00
a(t)

---

Online Linear Classification with Massart Noise
Proof. Note that in the case that the event (A9)() the loss of (x()) zero. Recall that it holds that Ca (w)l)) z/2;11²)) (1/2) - yj ()))((((() 2 )= )) un())
|. To simplify the notation, let 9j (u, ( = (1/2) 0j sign(ur(!) =/ 20
Using the tower rule, we get
T
E
((0) (w (w)
(2)
(Ely, 10) 1) w)( . 1(400)
gj
(w(t) 1
j
Σ Σ 9 (E (1((0))
(8)
Moreover, since it holds that sign(w!() (0) = sign(w (w( x . _)) we have 9j (Elv,-) D = (1/2)(A - sign(w(()) (w ((t) = 1l,,")). Hence, have that
0
E Uj 1)
(A sign(w -x) -1 E((r!!) a(t)) - ())
A.4. Proof of Claim 3.3
We restate and prove the following:
Claim A.4 (Unbiased Loss Estimate). For any w E R it holds
(w)) FF0,, e(t) g(e)
E
r(0] [(0))())
G(w; (1) (t)) "0,"1""')))
Proof. Since at every step of Algorithm 3 construct the loss G(w; ((), (f) ((t), ((() (t).,, using Algorithm 2, we denote (t) (t)
by y ((t)) j the reward difference vector of the adapted reward vector Morcover, recall that we denote
yj = rle) ).. Notice that ÿ (*) is a random variable that depends on the uniformly random action g The loss separately. We start with the case where (9 * 0 and we denote this event as At9, Recall that 2/ x(t) - + psign (1( " ((()))/l)//)))) (()))l/)))) [|2 is the vector containing the
(1) (1)
depends whether the (1()) 0 not so, consider each
context differences as computed Algorithm 2. Taking the expectation with respect the random coin flip c(t) obtain:
((tt) (w) F(9) 10)
1
E [G(w; (11,, (,,( (888)
7()) .o..aaa )))((())) FEO), [00] =
=
ele) (800))
Cs(w 2/010/)) 1(A0)) F( (())
(1))
Egto [Ca (w
;
-34)) F(() p((1) 114
E (88)
Σ (
Σ fealt
wl 2,
(w((t) 2
where for the last equation we used the linearity of expectation and the fact that the action (1), the event A0 and the weight vector (-th iteration (t) do not depend on z(t) conditional on F((., We now observe that the loss Ca (1; y) (L/2)(A]t) yt) is linear in y. Therefore, using again the linearity of expectation, we have that
E CC (w: 2 z(y)))())) g(t)
(t)
F((), (()) = Ca(w 2
E 3(o)
FF()) (11))
Next, we consider the case where (*) 0, and we call this event (49)(0, We have that by taking the expectation with
12

---

Online Linear Classification with Massart Noise
respect the random coin flip e0) we obtain:
E
(w))
xl0] ,10,,000
F(),
| [G(w; ((1,, ,800
(w()),((())) (000,,=".000)0)(((()(0))
(0))))((A)))) (FO) x100)
ett) ,000
E B
Σ itt
11) , I((9)((0)) F | x(0))(0)]= =- Σ X
X._
E B
F( r (())11(1)))))
where for the last equation we used the linearity of expectation and the fact that the action (0)) and the event A do not depend on g(t) conditional on FF())
To finish the proof we have to show that the adapted reward difference vector 7d is an unbiased estimate of the true reward difference vector y() Since we pick the action 3(9) uniformly at random from (1.....k) k), we have that the i-th coordinate of the adapted reward vector F is equal
F()) (+)] To (
1))
+ 1 (MM-)!) k s4i
Therefore, we have that the expected difference 8 is equal to
E g(c)
F=t1) r (+) = 7 (A: - 1)r (1)
a(e)
+ k
Σ (M - (10) (
- (k: 1)r
k
1
1
Σ
(M - )!))
$fa(())
1 (k k
1)r
(tt)
(t) 1 (t)
K. F(k (k: 1)
1
+ - ="a00 a(o) a30
(1)
(t)
[, yj
(6)
Therefore, combining the above equations, we conclude that
E (w)) | |F(1, ( G(w]))((;;X'' x(0) (())) r(() ((t) at)))
et0 (868)
This completes the proof of Claim 3.3.
A.5. Proof of Claim 3.7
We restate and prove the following claim.
Claim A.S. It holds that J S (R(T) + TM 1))/((k 1)7AA).
Proof. From Inequality 8, we have that
T ((0) (wo(0)
T
= Σ Σ
gj 1I)
(4)
j*a(()
2 M(k - 1) - J1/2.
Furthermore, sing the assumption for the regret guarantee, we have:
T
T
E
2
(w)
2 (10") (w²) $ R(TT)
1=1
Hence, using Claim 3.5, we get the result.
A.6. Proof of Theorem 1.11
We restate and prove Theorem 1.11.
Theorem A.6 (Monotone k-arm Contextual Bandits). Consider the monotone reward online setting of Definition 1.5.
Moreover, for some unit vector un Rd assume that for all t, holds that for all |x(1)) ||2 S and for all i + j.
13

---

Online Linear Classification with Massart Noise
2 7. There exists a bandit algorithm that runs in poly (oly(d) time per round and selects a sequence of arms a ..... (T) [ki] that obtain expected reward
lur. X! " X ; )
E
(1
E
(
k AT - OCT
Proof of Theorem 1. Algorithm 3 in each iteration, either with probability q makes random choice or with probability 1 - chooses the best action according to the current decision weight vector (or a random action if w!!) = 0). Therefore we have that
E ol
(1)
(1
E
E
(t)
Using Lemma 3.4, we get that
E
pl0)
E
(
k
==1
9) k
(1
AT (1 RT, 7, A,A,))
k
where R(T, y. A)), CMMVT/qmaxL/// By maximizing we get A 1/TT1/((M/((2))) and q M/(rAA). Therefore get that the expected reward
(R(T)/A((1 + 1/(7A)) TM/A. From Lemma 3.2 we have that R(T) (k
E
(+)
E
AT (KA) /7.
14


Reviews:
[{"review_id": "rY5nfBNIm7", "reviewer": "Reviewer_WUUa", "summary": "The paper studies online linear classification with massart noise. The paper designs computationally efficient algorithms for online linear classification with Massart noise. The paper also extends this model to k-arm contextual badntit setting.\n\n## update after rebuttal\nAfter rebuttal, I maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer WUUa for the positive feedback on the clarity and soundness of our theoretical results. We will fix the typos pointed out. In response to the reviewer’s question about the use of the Leaky ReLU:\n\nThe standard LeakyReLU loss penalizes points that are further away from the decision boundary more than the points that are close. By reweighting with the margin we equalize the contribution of all points to the objective leading to minimizing misclassification error. Making the reweighting depend on the current vector w would result in a non-convex objective but treating it as a constant everytime results in an online sequence of convex objectives and we prove that our method converges to the desired solution. This is explained in lines 181-191 (left column) of the submission.", "claims_and_evidence": "In general, the claims are supported by sufficient evidence. The theoretical results seem sound.", "methods_and_evaluation_criteria": "The performance measure, the mistake bound, makes sense as it is the measure that is studied in the most similar works.", "theoretical_claims": "I checked the general soundness and read all the proofs.", "experimental_designs_or_analyses": "The paper does not include experiments.", "relation_to_broader_scientific_literature": "The contributions of this paper fall within the broader field of Online Linear Classification under Massart noise. The most relevant prior work is by Ben-David et al. (2009), who proposed inefficient algorithms. By contrast, this paper presents efficient algorithms.", "essential_references_not_discussed": "I don’t know any specific part of the literature that is not addressed.", "other_strengths_and_weaknesses": "1. The paper is well written.\n2. This paper gave the first efficient algorithm achieving a mistake bound of $\\eta T+o(T)$ in online linear classification with Massart Noise.", "other_comments_or_suggestions": "There is a typo: 234:  |t| - t  ->  |t| + t.", "questions_for_authors": "1. Could you explain why you define a loss function step d in algorithm1, what is the problem of using LeakyReLU directly?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IirdxbrzPt", "reviewer": "Reviewer_UTxa", "summary": "This paper considers an online learning setting where context-label pairs are generated with Massart noise.\nMore specifically, while in standard online classification, both the context and label are generated adversarially, the authors consider a setting where the context is generated adversarially, but the label is determined based on the context at that time and is subject to Massart noise.\n\nThey first derive a mistake bound for this online classification setting that matches a computational lower bound in the offline setting.\nTechnically, they achieve this by considering a new loss function for the online learning algorithm, in which a LeakyReLU function is weighted by the margin of the sample at each time step, which allows them to establish the above mistake bound.\n\nBy leveraging this technique, they further derive a desirable mistake bound for the $k$-armed contextual bandit under assumptions weaker than realizability for the reward function.\nWhen the number of arms is 2, this mistake bound matches existing results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. We will fix the typos and address the reviewer’s suggestions to improve clarity.", "claims_and_evidence": "Yes, all propositions and claims in the paper are accompanied by proofs or corresponding references.", "methods_and_evaluation_criteria": "Yes, the proposed algorithms are variants of existing algorithms in online classification and are thus valid.  \nMoreover, the evaluation criteria (mistake bound and expected reward) are standard in the literature.", "theoretical_claims": "Yes, I have reviewed the proofs in the main body and confirmed their validity with no issues.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "In the traditional online (linear) classification setup, the setting where both the context and label are generated adversarially has been extensively studied.\nHowever, the traditional assumption that the label is generated completely independently of the context is overly pessimistic.\nTo address this issue, the authors introduce the Massart noise assumption, which has been well-studied in the offline setting, and consider a scenario where there is some dependence between the context and the label, and this is an interesting aspect of this paper.\nFurthermore, instead of directly using the LeakyReLU function, which is known to be effective in existing studies, they consider a variant weighted by the margin of the sample at each time step.  \nBy doing so, they establish a mistake upper bound that matches a computational lower bound, and this is of interest to the community.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "This paper is overall well written.  \nIn particular, the problem setting, algorithms, definitions, and main results are presented in a highly clear manner.  \nOther strengths are discussed in Relation To Broader Scientific Literature.  \n\nA minor weakness is the presence of numerous apparent typos.  \nFor example,\n- In Line 72, the phrase \"chooses an action $\\alpha = 1, \\dots, k$\" is unclear.  \n- In Line 80, $\\mathbb{E}[r_i | x^{(t)}]$ should be $\\mathbb{E}[r_i | x_i^{(t)}]$.  \n\nAdditionally, some notations are quite confusing.  \nFor example,\n- In Fact 2.1, the expression $1/2 ((1-2\\lambda)|t| - t)$ is difficult to interpret.  \n- In Fact 2.4, the regret upper bound $GD/3 \\sqrt{T}$ is presented in a fraction format that makes it unclear.  \n\nIt would be desirable to revise these points for clarity.", "other_comments_or_suggestions": "no", "questions_for_authors": "no", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"], "ethical_review_concerns": "a"}}, {"review_id": "FGpUwP6V5a", "reviewer": "Reviewer_WzcY", "summary": "They present a computationally efficient alg that achieves mistake bound \\eta T + o(T) where \\eta is the probability of flipping the ground truth label in the Massart Noise model. Their algorithm is based on performing online gradient descent on a seq of reweighted Leaky-relU loss functions.\n\nNext, they consider a semi-random k-arm contextual bandit problem, where given a list of contexts, they are consistent with some halfspace $w^*$, in expectation. That is, given a list of contexts $x_1,\\cdots, x_k$, given that $w^* x_j > w^* x_i$, the expected reward of action I is larger than action j in expectation by at least \\Delta. They used their online Massart learner to obtain an efficient bandit algorithm that obtains roughly (1−1/k)∆T more reward than playing at random at every round. Question: what is a lower bound here, in terms of what is the maximum reward possible?", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer WzcY for the positive feedback on the paper's novelty. We respond to the reviewer’s questions below. \n\n**$\\bar{R}$ in Lemma 2.2**: Thank you for pointing this out. $\\bar{R}$ refers to the regret bound used in the online gradient descent analysis.\nVector $u$ in Lines 245-260: The vector $u$ in Lines 245-260 was meant to represent an auxiliary vector, which is independent of the current vector $w$ in computing the gradients. The value of the vector $u$ is chosen to be the vector $w$ but we define it in this way so that the reweighting does not change the gradient wrt $w$.\n\n**Function $G$ in Algorithm 2**: In Algorithm 2,  $G$ represents the loss function being minimized at each step of Algorithm 2. Its specific form, incorporating the reweighted LeakyReLU loss and bandit feedback, is constructed in steps 2 and 3b of Algorithm 2. We use \\ell(w) as a shorthand for the instance of this loss function $G$ at a particular step, simplifying the presentation of the regret analysis.\n\n**Lower Bound Question:**\nThe theoretical maximum expected reward achievable by any algorithm (even computationally inefficient ones or those with oracle access to the true separator $w^*$) corresponds to always selecting the optimal arm based on the current context $x^t$. If we assume, without loss of generality, that arm 1 is the optimal arm in expectation for every round $t$ the maximum possible expected reward is $E[\\sum_{t=1}^T r_1^t]$.\nEstablishing tight bounds on the maximum achievable reward specifically for computationally efficient algorithms in this precise semi-random setting is challenging, and related questions remain open even in offline contexts. For example, in the special case where $k=2$ and $r_i^t\\in\\{\\pm 1\\}$, the expected reward gain of $(1/2)\\Delta T$ achieved by our algorithm is indeed a meaningful quantity. As discussed in Remarks 1.6 and 1.10, this relates directly to the mistake bound achievable in the underlying binary classification problem. Given the known computational hardness results (as stated in the aforementioned remarks in the submission), the maximum expected reward that can be achieved by computational efficient algorithms is at least $\\Delta T$.", "claims_and_evidence": "Their results are definitely novel and interesting, although I did not check all the proofs.", "methods_and_evaluation_criteria": "Theoretical paper, and the claims seem reasonable to me.", "theoretical_claims": "I did not check all the proofs but the claims seem reasonable to me.", "experimental_designs_or_analyses": "Theoretical paper", "relation_to_broader_scientific_literature": "For the class of \\gamma-margin linear classifiers they present the first computationally efficient algorithm that achieves mistake\nbound \\etaT+o(T).", "essential_references_not_discussed": "I cannot think of anything that is missing.", "other_strengths_and_weaknesses": "Their results are definitely novel and interesting, although I did not check all the proofs. In terms of writing of the paper, at some places, it was very hard to understand what is going on, here are some comments:\n\nLemma 2.2., you did not define \\bar{R}. \nLines 245- 260, what is u? It is not defined.\nAlg 2, what is the function G?\n\nAlthough the results are novel and interesting, I think the write-up can be improved a lot.", "other_comments_or_suggestions": "Same as above.", "questions_for_authors": "Same as above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2ZwEKRz52N", "reviewer": "Reviewer_qMz2", "summary": "The paper studies online linear classification under massart noise where noisy label might be flipped with a rate of $\\eta$. In the case where the dataset is separable with a margin of $\\gamma$. The paper used a scaled leakyRelu function as the surrogate loss and guarantees a mistake bound of $\\eta T + O(T^{3/4} / \\gamma)$. The binary classification tasks can be extended to $k$-armed bandit setting under the assumption of rewards being monotonic and separated by $\\Delta$, an expected reward $(1 - 1/k) \\Delta T - o(T)$ is recovered. The later result is a generalization of the first when $k = 2$, with a slight worse dependence on $o(T)$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer qMz2 for the positive feedback on the paper's writing and clarity of intuition. We will fix the typos pointed out by the reviewer.\n\n**Clarification on $\\bar{R}(T)$ Derivation:** We apologize for the confusion regarding the derivation involving $ \\bar{R}(T)$ around Line 310. The bound indeed stems from applying Fact 2.4 (Online Gradient Descent regret bound). In our setting, the parameter values are as follows: The domain diameter (D) is equal to 1. \nThe gradient norm $G$ is related to the Lipschitz constant of our reweighted loss, \nwhich is $O(1/\\tau)$.\nSubstituting these into Fact 2.4 gives the bound $O( \\sqrt{T}/\\tau)$.\n\nWe acknowledge the inconsistent reuse of the symbol $\\eta$ for both the Massart noise level and the step size (Fact 2.4). We will change the notation for the step size throughout the paper.\n\n**Restrictiveness of Assumption (Definition 1.5):** The reviewer correctly notes that our assumption of pairwise separability by $\\Delta$ for all pairs of arms in the bandit setting is stronger than the more standard assumption requiring only separability between the best arm and all other arms. Relaxing our assumption to the standard \"best vs. others\" gap introduces significant technical challenges in adapting our Massart noise learner. While this is a very interesting and important direction, we leave it open for future work.", "claims_and_evidence": "The paper claims focusing on computational efficient algorithm with provable guarantee rather than previously established algorithm scales with $O(\\sqrt{T})$ but incomputable. The claim is supported by main theorems.", "methods_and_evaluation_criteria": "The paper used classical and well acknowledged metric in the filed, mistake bound and reward bounds, for evaluation", "theoretical_claims": "All checked", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "the paper contributes to provide new computational efficient online algorithm with theoretical guarantee for linear classification with labels subject to Massart noise. The bound matches with previous offline result.", "essential_references_not_discussed": "well referenced.", "other_strengths_and_weaknesses": "The paper is well written and easy to follow. The intuition of selecting LeakyReul with appropriate parameter is clearly demonstrated.", "other_comments_or_suggestions": "- typo line 234 left '+' instead of '-' followed by $|t|$.\n\n- typo, eqn start from line 312 left: indexing with $t$ instead of $i$\n\n- I did not follow at line 310 right panel, proof to Theorem 1.9. In particular, by definition of $R(T)$ in line 308 right and definition of $\\bar R(T)$ in line 268 left. It seems conclude $E[R(T)] \\le O(GD / \\sqrt{T}) = \\bar R(T)$ with appropriate $G, D$ being substituted. What choices allowed the claimed bound $\\bar R(T) = O(\\sqrt{T} / \\tau)$\n\n- Another confusion of above might arise at $\\eta$ had clashed interpretation: step size in Fact 2.4 and noise level in Definition 1.1; then $G$ is related to $\\eta$ (in the noise sense)...", "questions_for_authors": "The required assumption in definition 1.5 seems very restrictive if we are considering $k$-armed bandit, as it requires pairwise $\\Delta$ separability. $\\Delta$ separability between every arm and the best arm is common. I wonder whether definition 1.5 can be lifted to the standard assumption.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies online linear classification and contextual bandits in the presence of Massart noise. In this case, the paper gives an algorithm that is o(T) away from the best possible offline algorithms. There are a few weaknesses, such as the lack of a discussion on possible lower bounds, and a further comparision with more recent offline works (some of which the authors say are inspired by this paper). 

The authors should take into account the feedback from the reviewers and rebuttal in preparing the revision.
Decision: Accept (poster)