Online Linear Classification with Massart Noise

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.

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. The gradient norm $G$ is related to the Lipschitz constant of our reweighted loss, which is $O(1/\tau)$. Substituting these into Fact 2.4 gives the bound $O( \sqrt{T}/\tau)$.

We 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.

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.

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:

The 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.

We thank the reviewer for the comments. We will fix the typos and address the reviewer’s suggestions to improve clarity.

We thank Reviewer WzcY for the positive feedback on the paper's novelty. We respond to the reviewer’s questions below.

$\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. Vector $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$.

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.

Lower Bound Question: The 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]$. Establishing 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$.