Online Strategic Classification With Noise and Partial Feedback
Authors: Tianrun Zhao
Xiaojie Mao
Yong Liang
Venue: NeurIPS 2025 spotlight ()
Keywords: strategic classification
online optimization
learning halfspaces with noise
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: In this paper, we study an online strategic classification problem, where a principal aims to learn an accurate binary linear classifier from sequentially arriving agents. For each agent, the principal announces a classifier. The agent can strategically exercise costly manipulations on his features to be classified as the favorable positive class. The principal is unaware of the true feature-label distribution, but observes all reported features and only labels of positively classified agents. We assume that the true feature-label distribution is given by a halfspace model subject to arbitrary feature-dependent bounded noise (i.e., Massart Noise). This problem faces the combined challenges of agents' strategic feature manipulations, partial label observations, and label noises. We tackle these challenges by a novel learning algorithm. We show that the proposed algorithm yields classifiers that converge to the clairvoyant optimal one and attains a  regret rate of $ O(\sqrt{T})$ up to poly-logarithmic and constant factors over $T$ cycles.

Online Strategic Classification with Noise and Partial Feedback
Tianrun Zhao, Xiaojie Mao, Yong Liang
School of Economics and Management, Tsinghua University, Beijing, China, 100084 ztr23@mails wellls.ssnnghine tsinghua. edu. en, maoxj tsinghua.edu cn, 1 liangyongdsem. tsinghua.edu edu.
Abstract
In this paper, we study an online strategic classification problem. where a princi- pal aims to learn accurate binary linear classifier from interactions with sequen- tially arriving agents. For each agent, the principal announces a classifier. The agent can strategically exercise costly manipulations on his features to be classi- fied as the favorable positive class. The principal is unaware of the true feature- label relationship, but observes all reported features and only labels of positively classified agents. We assume that the true feature-label relationship is given by halfspace model subject to arbitrary ceature-depende but bounded noise (i.e., Massart noise). This problem faces the combined challenges agents' strategic feature manipulations, partial feedback observations, and label noise. We tackle these challenges by a novel learning algorithm. We show that the proposed al- gorithm yields classifiers that converge to the clairvoyant optimal classifier and attains a regret rate of O(VT) up to poly-logarithmic and constant factors over T cycles.
Introduction
Strategic classification studies the problem of learning robust classifiers in presence of self-interested strategic agents. When subjugated to decision-making aided by classification algorithms, agents may strategically modify their observable features to game the classification algorithms making decisions that best serve the agents" goals. For example, bank may use classification to determine whether loan applicants are qualified to grant approvals. The applicants prefer positive classification and loan approvals, they have the incentive to modify their profiles (e.g.. credit score), potentially at certain costs, without actually improving their financial status. It is crucial that classification algorithms used for decision-making be robust such strategic manipulation.
Besides the strategic feature manipulation, another common challenge in classification-basee decision-making is that the eecision-maken may only observe the true labels of agents who have received the positive decision. For example, the bank can observe the true financial qualification only for applicants who have already been classified as qualified and granted loan approvals, but has no chance to observe the true qualification of rejected applicants. This type of partial feedback is sometimes called one-sided
often only observes partial feedback. In particular, the
feedback, apple-tasting feedback [c.g.. Harns et all MUZK Helmbold all 2000 or selective label feedback [e.g.. Lakkaraju et all 20L7 Chen eia 2025].
In this paper, we study an online strategic classification problem with partial feedback. In this problem, a principal (decision-makee interacts with sequentially arriving agents. The principal
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

announces a binary linear classifier to each agent and makes the decision according to the agent's s reported feature that may differ from the truth due to strategic manipulation. Following the existing literature, we assume that the agents manipulate their features to maximize the net utility from the classification decision and the cost of feature manipulation. We assume that the agents' true feature- label relationship is characterized by linear halfspace model with arbitrary feature- reature-dependent but bounded noise (i.c., Massart noise). This model is widely adopted in the learning theory literature (see references in Section I) The principal does not know the true feature-label relationship, but needs to learn accurate binary classifiers from observations of agents' reported features (but not the original true features) and the true labels of only positively classified agents.
Notably, this problem faces the combination of three challenges: agents' strategic feature manipu- lations, partial label observations, and label noise. First, because of strategic feature manipulation, the agents' true features may not be faithfully observed by the principal, which impedes the learn- ing process. This is particularly challenge in the online setting, as the agents' strategic behaviors depend on the classifiers announced to them, so their behaviors change over time as the classifiers evolve. Second, the principal can only observe true labels from positively classified agents, without feedback from negatively classified agents. This means that the principal can learn only when a pos- itive classification is made, while the strategic agents are incentivized to manipulate their features to achieve positive classification. Third, the label noise results in noisy feedback, which further complicates the learning process.
Our work contributes to the literature along the following dimensions. First, to the best of our knowledge, our work is the first to study online strategic classification under Massart noise and partial feedback. This advances the literature of learning halfspaces under noise [e.g.. Zhang et all 2020, Diakonikolas et all 2020] to the strategic setting. Moreover, within the online strategic clas- sification literature, our halfspacc model with Massart noise extends the noise-free model of deter- ministic feature-label relationship in Ahmadi aL [202T], Shen aL [2022]] and complements the fully adversarial setting [Dong et all. 2018. Cheneeal 2020J. Second, we propose novel learning algorithm that effectively addresses the aforementioned three key challenges. This algorithm has an initialization cetiiiiattoo-efiinnete refinement----eeeeeeee -eaaneemeeetaanemmentt pipeline, proceeding in batches and iterations. It features several key components: 1) localization scheme that iteratively improves the classifiers via online linear optimization, using data within increasingly narrow bands around the classification boundary; 2) a projection-based method to construct proxy features from agents' reported features; 3) pair- wise contrastive inference technique to infer information of the localization bands by contrasting data from pairs of carefully constructed classifiers. Third, we rigorously prove that the proposed algorithm yields classifiers that converge to the clairvoyant optimal one and attains a regret rate of O(VT) up to poly-logarithmic and constant factors over T cycles.
1.1 Related Literature
Strategic classification, introduced by Hardi ct all [2016]. has gained in- creasing attention. The existing literature has studied strategic classification in both offline settings [e.g., Hardt et all, 2016, Sundaram et all 2023, Levanon and Rosenteld 2021] and online settings. In online strategic classification, principal sequentially interacts with strategic agents, aiming to learn accurate classifiers in the presence of strategic feature manipulation. Some literature models agents' strategic behaviors by a manipulation graph that defines agents' feasible feature manipula- tions [Ahmadı et all 2023, 2ORE) Cohen al, R022,, Shao et all, 2025)). Meanwhile, other literature considers agents that maximize the utility net the cost of feature manipulation. For example, Dong al [2018] derive conditions on the manipulation cost function that enable convex optimization techniques to achieve a sublincar regret rate under different fractions of strategic agents. Chen el all [ consider a ristance-based manipulation cost function and zero-one loss function. Our work considers the same cost function and loss function. However, Chen et at [2021] studies a fully ad- versarial setting, while our work studies stochastic setting where agents' true features and labels follow some probability distributions. Our work is closely related to Ahmadi et all [2021]]] and Shen atal [2022]] as we study similar models for agents' strategic behaviors and linear classifiers. How- ever, their works focus on the noise-free setting with a deterministic feature- label relationship, while our work tackles label noise.
Strategic Classification
Notably, nearly all prior studies focus on full feedback settings, whereas our work studies partial feedback setting. One exception is Hamns all [023), where the feedback can be observed also

---

only under a positive decision. However, they consider continuous feedback following a linear regression model with ientree-nddeeedentt noise and target a different objective. In contrast, our work considers binary classification feedback and studies a halfspace model with potentially feature- dependent bounded noise, which directly extends the models in Ahmadi et all [202TI], Shen et all [202]]]
Learning Halfspaces with Noise Our paper adopts halfspace model with the label flipped at potentially feature-dependent bounded probability, i.e., Massart noise [Massart and Nédeled [003]. Recent studies find that even in the absence of strategic agent manipulations, learning halfspaces under Massart noise presents significant challenges IZhang et all, 2020, Diakonikolas et all 2019. 20211 2023]. The key challenge stems from the nonconvexity of the 0-1 loss function that charac- terizes the misclassífication error. A standard approach to overcome the non-convexity of 0-1 loss in classification to use a convex surrogate loss function [Bartlett et all, 2006). However, Awasthi
cf al [ show that popular algorithms such as SVM or hinge loss minimization fails to learn halfspace that achieves arbitrarily small excess eттоr under Massart noise. More generally, Dre a akomkolas. all [M]]]] show that one cannot achieve non-trivin con-trivial misclassification error for learning halfspaces under Massart Noise by optimizing convex surrogates. Instead, "localization" scheme has been proposed to learn halfspaces under variety of noise models [e.g.. IShen, 2021a Awasthi all 2017. Zhang and Li, 2021, IShen, 2021E, Awasthi et all 201Z]. In particular, Zhang et al. [2020] and Diakonkkolas at [202]]] apply localization to learn halfspaces with Massart noise. The core idea is to iteratively improve classification via convex optimization, using data within increas- ingly narrow bands around the classification boundary. This localization scheme focuses more on data near the classification boundary, as data far away from the boundary tend to be less informative since they can be either easily correctly classified or misclassified mainly due to noise. However, naively extending this localization scheme to strategic classification poses significant challenges, because data points close to the classification boundary are the most prone to feature manipulation. Our work effectively overcomes these challenges by leveraging carefully constructed proxy data and novel pairwise contrastive inference approach.
1.2 Notation
We employ the following notation throughout the paper. Boldface letters such as x, r, w denote vectors. The operator ||. lpp denotes any lp norm of a vector. The inner product of two vectors denoted by (,-) and the angle between two vectors is represented by 0 (s,), i.e., (V1, v2) =
arccos I for VV1, V2 Rd. Symbols Id and Sd denote the d-dimensional Euclidean unit ball and sphere, respectively. (d))) denotes the ball with radius R 0. For any positive integer N, [N] represents the set (1, ...., J). The indicator function I[-) gives the value 1 if the event within the parentheses holds and the value 0 otherwise.
(v1.v2)
2 Problem Setup
We consider a setting where a principal repeatedly interacts with sequentially arriving agents (e.g.. applicants). Without loss of generality, time is discretized into T cycles, where one agent arrives in each cycle i [T]. The agent characterized by feature-label pair (x,, where x; Rd denotes a d-dimensional feature vector and y {+1, -1} denotes the agent label (i.e., qualified or not). At the beginning of each cycle E [T], the principal announces a classifier h.(-) the admission rule for the arriving agent. The agent may strategically manipulate and report feature value r, + x; to the principal at some costs, aiming to get admitted (i.e., classified as the positive class, h,(r.) = +1).
The principal observes the reported features rt, makes the classification decision he (r:) accordingly. and observes the true label y/s only when this agent is admitted. Importantly, the principal has no chance to observe the true label of rejected agents. Based on the data of reported features and admitted agents' labels, the principal aims to learn accurate classifiers over the T eycles.
Distributional Assumptions We assume that the feature-label pairs (X1, y/)................... (xr. yr) are independently and identically distributed (i.i.) draws from a common population denoted by (x, v). We need first impose some distributional assumptions on (x. y))
3

---

Assumption 1 (Halfspace with Massart noise), There exists a Boolean-valued function h" (x)x
sgn((w x)) for a coefficient vector w with || 1l2 and a noise level bound 1j E [0, 1/2), such that y = he (x) with probubility 1 - (x) and y (x) with probability nx(x,, where n)(x) characterizes the potentially Peature-dependert noise satisfying S r7(x) S 1) almost surely.
Assumption 0 is a standard assumption in the literature of learning halfspaces without strategic manipulation [c.g.. Zhang et all 2021. Diakonikolas all 2020, Massari and Nedeled, 2006]. It allows for arbitrary feature-dependent label noise with an upper bound nj E [0, 1/2), and relaxes the assumptions in some existing strategic classification literature that assumes a noiseless halfs- pace model y h (x) and that the positive and negative classes are strictly separated by margin le.g., Ahhmai et ali 2021, Shen et all 20244] Our assumption can more aptly model real applica- tions where label noises are common and even feature-dependent. Nonetheless, unlike the existing literature, we need to simultaneously handle both the strategic manipulation and label noise.
Assumption 2 (Regular feature distribution). Fix constants R, L1, L1,, U1, U2. 6, Q > O, and let xy denote the projection of x onto any subspace V C IR and @v denote its probability density function. The distribution of features satisfies the following regularity conditions for any 1-dimensional subspace V1 S R and any 2-dimensional subspace V2 CR²:
1. dv,, (Xvr) 2 Lı and (v,((v,) 2 L2 for any XV, E EV EV)BBBRR Xv; 1/2 (
2. Φv, (xv,) S U1 and Φv, (Xv,) S U2e-81xx 81xvzllz 222 for any xv, E V1, X122 E V/2
3. For any t > 0 and unit vector w E Sd, we have that PI] (w.x) 2 t S exp Qt).
In Assumption A. condition requires that the densities of any 1-dimensional and 2-dimensional projections of feature x are lower bounded around the origin. Condition 2 indicates that these densities have proper upper bounds. Condition 3 requires that the inner product of with any unit vector w has a sub-exponential tail bound. These conditions generalize the feature distribution conditions in a large body of literature on learning halfspaces with noise [e.g.. Diakonikllas el all 2020, 2021. Zhang et al, 2020. Dasgupta, 2003. Yan and Zhang, 20TA Shen. 2021a. Awasth ef all 2010 This existing literature typically assumes that the feature has isotropic log-concave distribution, such as a uniform distribution over a unit sphere. In Appendix A. we show that Assumption @ accommodates even non-isotropic log-concave distributions, including many common distributions such as uniform, Gaussian, exponential, logistic distributions, etc. Notably, we impose distributional assumptions the feature-label pairs, which differ from and complement the fully adversarial setting in the literature [e.g.. Dong et all 2018, et all, 2020, Ahmadi et all, 2024).
Agent Feature Manipulation We assume that each agent gains utility of +1 for admission (classified as +1) and -1 for rejection (classified as -1). An agent with true feature x may re- port his feature [2022], we assume that this misreporting or manipulation incurs a cost Cost(x x, r) 2||x - r|l2/7, where y >0 0 indicates the maximum manipulation distance. Therefore, upon the principal announc- ing classifier i(.), the agent's optimal reported feature that maximizes the net utility would be r' r*(x, h) argmax,eR h(r) 2||x --r-ll l|22/y.
to sway the classifier's 's decision. Following Shen et all [0221]] Ahmadi et all
Given the linear model in Assumption II we restrict the principal's 's classifier h to linear classifiers parameterized by (w, m) E Sd IR, i.e., h(r)- = sgn((w, r) + m) In this case, an agent's 's optimal reported feature is given in the following lemma eShenetall 2022,, Ahmadi et all, 2021].
sgn((w.. (w. r) + m), the optimal reported feature Lemma 1. Given announced classifier h(()) = -ggn( for an agent with true feature x is
x x,
(ww, + m)w, - + < 0;
(x,
To)
otherwise.
The Clairvoyant Optimal Classifier Under the manipulated feature in Lemma II the misclas- sification rate of a classifier h can be measured by Err(h) == P(ā(r" R)) * v). We hope to characterize clairvoyant optimal classifier achieving the minimal misclassification rate: h+ E argming.p4--(11)) Err(h). To this end, we first connect a classifier h under the manipulated feature r with a hypothetical classifier h under the corresponding true feature x.

---

For any (w, m) E S xR, the output of h(r) sgn(( + for) = (x, h) is identical to the output of h(()) = sgn((w, x) + m) for any x E IR..
Proposition 1.
According to Assumption M. the optimal classifier in absence of manipulation is h*(xx)
sgn((w", (0p0("""'' x)). Following Proposition M1 we can achieve the same classification by a correspond- ing classifier subject to manipulation, which gives the clairvoyant optimal classifier. This structural knowledge of a clairvoyant optimal classifier will guide our algorithm design in Section B.
Corollary 1. The classifier hr(r) = sgn( (w", r) -7) minimizes Eir(h) = (((((r"(( (x, h)) + y).
Notably, the clairvoyant optimal classifier on the manipulated feature has higher threshold to classify an agent into +1 than the corresponding optimal classifier h 1x(x) sgn( (en((w,,) x)) on the true feature x. Indeed, the principal would like to raise the bar for positive classification, in order to avoid errors due to unqualified agents (label -1) who game the classifier by manipulating their features.
Principal's Regret Over the T cycles, the principal learns sequence of classifiers h (hi...., (r)). where each fy only depends on the observed data of reported features and admit- ted agents' labels prior to cycle t. The goal is to achieve small cumulative misclassification rate over all cycles. This equivalent to achieving a small total suboptimality gap, or regret, relative to the clairvoyant optimal classifier. Formally, the regret is defined as:
(I) This regret corresponds to the "Stackellergg regret" in the strategic classification literature, where the term ""Stackelherg" emphasizes that agents consistently choose their best feature manipulation in response to the principal's announced classifiers [Dong et al], 2018, Khen et all 2020, Ahmadi aall 2023]. In the next section, we will propose learning algorithm that effectively tackles the combined challenges of agents' feature manipulations, partial feedback observations, and label noise.
Reg = Σ Err(h,) - T x Err(h").
We prove that this algorithm achieves a /T-regret rate up to poly-logarithmic and constant factors.
3
The Algorithm
3.1 Overview of our Algorithm
Algorithm 1: Main-Algeeee Algorithm
Input: Maximum manipulation distance 7, noise level hound 77, lengths {Tima] (Tx {Tx) bandwidths {be ) jk-o stepsizes {ax > feature dimension d
Wo Initialization(" (Tint)
// See Algorithm
W1 Refinement( (Wo, 7, To. bo, d))
// See Algorithm
for k + 1 to K do
Wk+1 Batched-Eanan EnhheeedEnnannemen((y w1, k, Th. bx, Ouk,
// See Algorithm
Our main Algorithm,, outlined in Algorithm II, comprises three sub-algorithms: Initialization Algorithm (Algorithm 2). Refinement Algorithm (Algorithm E) and a Batched Enhancement Al- gorithm (Algorithm H). These algorithms are executed sequentially to generate sequence of coef- ficient vectors such that the corresponding classifiers converge to the clairvoyant optimal classifier as specified in Corollary II Specifically, partition the horizon of T cycles (one agent arrives in each cycle) into consecutive batches indexed by & E {init, 0, 1, 2, ... ,........ K). Index "init" and "0" de- note the batches executing the Initialization and Refinement Algorithms, respectively, while indices "1" to "K" represent the K batches that run the Enhancement Algorithm iteratively. Each batch k takes the result of the previous batch & 1 as input. Cycles in each batch kt are further grouped into iterations indexed by i E 21 Tx}. where each iteration i performs an update for the coefficient vector w. At the end of batch k. the algorithms output the (normalized) average vectors of the T& iterations in the batch. During Refinement, each iteration consists of only one cycle. In contrast, during Initialization and Enhancement, each iteration contains two cycles, denoted by the superscript j 1 or 2 to differentiate between the first and second cycles within the same iteration. Note that the indices (ks, i, can be mapped to the corresponding cycle i, for convenience, we will use these indices in the remainder of this paper.
5

---

Initialization Refinement
Batched Enhancement
27ini
To
2T1
2T2
27:
Wo
Wi
W2
Ws We
Wh L(w" wes1) S t / w.h.p.
(w" ; Wo)
<(w wi)
Z(w", wa)
2(w", wa) L(w wa) S x/16 S 7 w.h.p. w.hpp
2 91( 27))
I x/4
S 1//8 w.h.p.
w.h.p.
w.h.p
Figure 1: Roles of the three sub- sub-algorithms
The roles of the three sub-algorithms are summarized in Figure M. First, the Initialization Algorithm runs for Tint O (In (1111111 27))) iterations (with mii cycles) find a coefficient vector Wo such that 0 (w*, Wo) I 2 with high probability (see Proposition 2 Second, the Refinement Algo- rithm takes Wo Wo/ |woll2 as the initial vector and runs for To O (d In ((1 2n))) iterations (with To eycles) to obtain refined vector W1 such that 0 (w", w1) I z with high probability (see Proposition B).. Third, the Batched Enhancement Algorithm runs for K O (log, (1 / d'In T)) batches, where each batch & enhances its initial coefficient vec- tor Wa through Tg O
2 iterations (with 2T, cycles), yielding vector Wk+1 such that 0 (w" Wk+1) S şoTड with high probability (see Proposition B).. The specification of the algorithms involves absolute constants to which are derived from the parameters in B.Sl A...
Assumption Detailed calculations are available in Appendix
3.2 Initialization
Algorithm 2: Initialization
Input: Iteration length Timte for <- to Taw
Uniformly draw Winit E gd for j to do Declare ( (r) (-1)3-1sgm (Wimi.i, r)), agent (x ( arrives and reports iimi.
Make classification decision (i) (1(2),)) and collect label Mini, 7,00 A
(r
Tim Eim En Voni min ((-1)(5-) imii, Vint.
return Wo
The initialization algorithm runs for Tini T/(11 2n))) iterations. In each iteration, we randomly explore coefficient vector Winit E Sd and offer two opposing classifiers based Winit to two successive agents. Using the reported features Finit, Fini.; and true labels (1) (2) of all positively classified agents over the Tim iterations, we construct an initial coefficient vector Wo-
The design of our initialization algorithm stems from the well-known "averaging" technique for learning halfspaces [Servedia 2001]. In the non-strategic, noiseless and full feedback setting, y(w",x, x) = (w",yx) 2 0 for all (x, y) E Rdd x {+1), ). so y/x forms an acute angle with the optimal normal vector w* almost surely (since the set {x (w*,x)
0} is zero-measure). Anal- ogously, in the noisy feedback setting, we have (w", TE [E(yx). > O, so [yyxx] forms an acute angle with w* In a non-strategic and full feedback setting. the literature uses the sample average of yx to approximate Elgx] as an initial estimate of w* IKhang et al, 2020J. However, this estimator is unavailable for us because of agents' feature manipulation and the partial feedback setting. Instead, our algorithm declares pairs of opposite classifiers. We collect and average the yr of agents whose reported feature falls above the hyperplane. Note that these agents report their features truthfully (r = x), so we are able to form Wo from these agents' yr proper approximation of [[/xx]. We can show that, for large enough T, Tiit- this vector Wo forms an acute angle with the optimal w with high probability.
Proposition 2. For some constants Co. Cj > 0, when Algorithm runs for Timr Co InTn//(1 21) iterations, its output wo satisfies (w", Wo) c1(1 27)) > 0 and 0 (w", wo) < 3 with probability at least - 2/T2.

---

3.3 Refinement of the Initial Coefficient Vector
Algorithm 3: Refinement
Input: Initial vector Wa, noise level 77, iteration length To, bandwidth bo, step size cop, feature dimension
d
Initialization :oo1 = wo/ wooll
for <- 1 to To do
Declare classifier lo.:
(eoo..,, r)), agent (xo.i, yo.i) arrives and reports ro.:
Make classification decision (ro.s) and collect label yo,, if ho. =
Compute gradient: go., -,,,,, (30., 1) + (1 r7) (yo --] < (wo.i, bo)
Set constraint set: Wo = (w/ ||w|2 1, (w, Wo) 2 c1 2
Update w: Wo,++1 = arg wiw (go,i, w) + oa 1)p-1)
www-a,sl where p In(8d)
In(8d)
Normalize: Wo.++1 Wo,442/1 Wo.+41ll 1/2
Compute mean vector: W1 1 E Wo,1
To
return w1 W1/l
The refinement algorithm adopts a "localization" scheme to refine the output Wo of Algorithm E to better approximate w In every iteration i, we consider only data within band 0 < (Wo,i,) S bo adjacent to the boundary of the current classifier (r) sgn( (Wo... r)). Agents this band are positively classified and have no incentives for feature manipulation, allowing us to observe both the true feature x r and the true label y. Moreover, this effectively probes the localized region Do. fx 0 < (Wo.i. x) S bo) in the true feature space. Similar "localization" is widely used in the literature of learning half-spaces with label noises (see references in Section II), since data near the classification boundary is the most informative, while data far from the boundary are either correctly classified with ease or are misclassified mainly due noises, providing little information.
We formulate online linear optimization problem with constructed losses {w + (w, go.;)) j==1 over a proper constraint set Wo = {w [w|2 2 S 1, (W, Wo) 2 (1 2-)]- This con- straint set, according to Proposition DL contains w with high probability. We then solve this problem by online mirror descent with a stepsize Og and regularizer ||w- -wo.il
1) for p (n(8d)/(In88/) - 1). perform proper normalization in each iteration, and normalize the aver- age of all iterates to obtain the output W1. By focusing on the band (r 0 < (Wo,,, S bo), can perfectly observe ro.; Xn,; and you and the gradients go coincide with the counterparts in Zhang et al. [2020]] As a result, we can follow their analysis to bound the error of the output wi.
Proposition 3. For the constant C1 in Proposition E and some constants C22 C3. C4 > O, when the initial vector We satisfies (w", Wo) 2 c1(1- (1-27) and Algorithm B runs with bandwidth by =c²(1- 2n1)² for To czd d(In T)2 /(1 277) iterations with step size ogg C4 / c (ddd(d)/((TTT In)). then its output W1 satisfies (w*, w1) S /4 with probability at least 3/T².
The main idea in proving Proposition B is outlined as follows. By the theory of online convex optimization, we can upper bound the cumulative regret for the constructed loss in this stage, i.e.. Ee (Wo. 8o.i) - (w*.go.:). This regret bound, together with a bound on E.e (Wo. go..) and concentration bound on Σte (w*, - leads to high probability upper bound on Io E [(w*, [ww",go..)) ]. Moreover, it can be shown that E 0 (w", w), up to some proportional factors. This is why we expect to obtain a high probability upper bound on w.). Importantly, the gradients go.i are carefully constructed to ensure that (wo,,, | is small and meanwhile E [(w", -Bo, upper bounds 0 (w", Wo,))
is lower bounded by
Notably, while Algorithm El collects true feature-label data and implements localization by focus- ing on local bands around the origin-crossing classification hyperplanes ho, 's. this approach can be costly. According to Lemma II unqualified agents with true features x satisfying -y S (Wo, x) < would manipulate their features to achieve positive classifications, resulting in constant instanta- neous regret. Fortunately, Algorithm runs for only Ö(I T)) eycles, so this refinement algorithm obtains an improved coefficient w for the next stage at the cost of at most only Ö(I T) regret.
It can be verified that go is the gradient of Leaky ReLu loss restricted to the band Do.s-
7

---

3,4 Batched Enhancement: Proxy Features and Pairwise Contrastive Inference
Algorithm 4: Batched Enhancement
Input: Maximum manipulation distance initial vector Wk. noise level f). batch index k, iteration length Tr. bandwidth b2. step size axs feature dimension d
Initialization 1 Wk
for to T& do
Construct classifiers (r) sgn((Wa...r) 7) and (E. sgnn))=sn((((() (wn,( - bn)
for j to 2 do
(3) (F) arrives and reports (t) Declare classifier k... agent (x Me,t
k,, Make classification decision (1) (I),.) and collect label wh. if h (r(2)) =1
Construct proxy data: (1.+) Proj (r2)) = 1,rk E ( xc.
(1.-)
x, Proinc, ( ( -1, E D(?)
7 Use the proxy data to compute the gradient: gi, = - -((hh, &n.
((,+t) + (x
x
(2.-))
Update: Wh.++1 + arg milwwew (Bt.,, w) + 1 ww. where la(8d)
(m(8k) T the constraint set
2(p-1)
W/ = [w] ||w]l2 l2 S 1, (w, W.. 2 cos 0e), starting angle 0x = 2411
Normalize: Wk,++1 = We,i+1/ 1..41//1 /1tt://///,,111111 We,++1ll2
10 Compute mean vector We+11 = 7% E/1 WA.1
11 return W = W/t1/// W/+1122
In the non-strategic and full feedback sctting, after obtaining the refined coefficient w1. Zhang et all [202]] further improves it by solving sequence of adaptively constructed online lin- ear optimization problems minwews E ge.)) with gk, [- (ye. - 1) (1 x (Uk., - < using local data within increasingly narrow bands {x -b < (WH... S by] around the classifi- cation hyperplanes. This process can geometrically reduce the error of the coefficient estimates, outputting final classifier that approaches the optimal classifier after enough batches. The key in- gredient underlying this guarantee is that the gradients g are well constructed so that (We,.. gk.i)l small and meanwhile E [(w", -ga,a) upper bounds A (w*, Wk.;) (see discussions below Proposi- tion (). One may consider directly implementing this batched enhancement approach in our strategic classification. In particular, one may again use classifiers (r) sgn((we.j.
W.k.i.k.
by) via mirror descent over t = 1..., K batches,
(W..i, r)) and focus on the band xx,+ {x 0 < (Wk,s, x) S by in each batch & and iteration i, since this enables us to collect the true feature-label data and probe the localized region Dr. However,
discussed at the end Section ExG this approach may result in constant instantancous regret in every cycle due to unqualified strategic agents, so that (T)) regret accumulates over the OTT) cycles in this stage.
To avoid excessive errors due to feature manipulation, we can instead employ classifiers hr,((r) sgn( sgn((w,,,, 7), mimicking the form of the clairvoyant optimal strategic classifier ht and raising the bar for positive classification to tackle strategic behaviors (see Corollary M). However, this gives rise new challenges: is unclear how construct the gradients ga.i and probe the localized regions Dr.,. since both depend on the true features, but all agents in the localized regions DA. misreport their features. This means that we know neither which agents' true feature values belong to the regions Dx.s nor their true feature values. To tackle these challenges, we propose two key ideas: proxy features and pairwise contrastive inference.
Proxy Features Even if we assume, for the sake of argument, that we can identify agents whose true features lie in DR.s. their true feature values remain unobservable, since they all misreport their features to secure positive classification (so their reported feature values fall on the hyperplane of the announced classifier). To resolve this, construct proxy features from the reported features.
Specifically, consider an agent with true feature value x E DR. and reported feature value r. This agent will manipulate his feature to get positively classified, and thus we can observe his true label. If his true label is y +1, then we construct his proxy feature as the projection of r onto the upper boundary of DA.a, i.e., x = Projø,, (r) = r + (be- (Wk,s, r) Wk. On the contrary, if his true label is y -1 then construct his proxy feature & the projection of onto the lower
8

---

boundary of DR,6, i..., x = ProjDe, (r) = r- r-k,,, Wk,5. As result, this agent's proxy feature value, like his true feature value, also belongs to DR. and the proxy feature value under positive label (i.e., projection onto the upper boundary of Dr.i) is more aligned with the direction of positive classification than the proxy feature value under negative label (i.e., projection onto the lower boundary of DR.;). See the illustration in Figure a()).
Using the proxy features, we can approximate the ideal gradient gk.s by proxy gradient gk,s [-njrroj (T (We, 1) + (1 rj) ProiDe. (Tx,,) (UK. = -x)] E DE..). Although this may not exactly recover the ideal gradient, it is still effective, in that ((Wa.) is small and E [(w", 1 - 2 E [(w", gx] also upper bounds 0 (w.) (see Appendix (A.5). Therefore, we use the proxy gradients B in the algorithm to achieve similar guarantees. Nevertheless, these proxy gradients require knowing whether an agent's 's true feature value belongs to the localized region x or not, which is still infeasible in our setting. This motivates our second key idea.
Pairwise Contrastive Inference We propose to offer two classifiers (i (r) = sgn (en((w, r) - 7) and h ( (r) =
r) - - - 6x) successively in each iteration. Under classifier h ((](r) (r), we consider only agents with reported features in D fr Y S (Wk. r) S y + b while under classifier ((](()), (r), we consider only agents with reported features in D {r: (WE,;; + These agents are all classified into the positive class, so their true labels are observed. Moreover, according to the feature manipulation rule in Lemma II these agents have true feature values in D = fx 0 S (W).,.) S 7 + b and D = fx by S (WA,,, S 7 + bb respectively. Since DA.; of the data within the region D of interest by contrasting the data within D and the data within D We call this pairwise contrastive inference approach, which is illustrated in Figure (kb).
(1) R,i up to measure-zero set, we can expect to infer distributional properties
We can use this approach to infer the two key components in the proxy gradient ga Note
Proib.. (Ix,)) = X,,, E Du.i) = E x ()) (1++) Projo.. (T2 VE.i = 1, E D!! for j = 1.2. This means that we can use
(1,+) (2.+)
where
h,i
(1.+)
x (2.+) unbiasedly infer one key component of B in expectation. Similarly, we can
kii
construct x (1.-) x.i infer the other component. This gives our gradient estimate ga, in Al-
gorithm @ Line satisfying that [[w,, .). = E [ -). also upper bounds 0 (w", w..)..
After getting the gradient estimator gr. we again conduct online mirror decent with a regularizer similar to that in Algorithm B and constraint set W/- {w] /|wl|2 S 1, (w, w*) 2 cos 0x), where 0-- = ..T.. Then we output the normalized average coefficient vector Wk+1 for the next batch. Our constraint set ensures that 0(W.. Wx) S 1//2+11 for all E [7k]. Then, when the input vector We satisfies 0 (w*, W&) I क n we have 0(w', w..;) < 0( ((w* ww) + O(WE,i, wx) < n/22 by a triangular inequality shown in Appendix A.3, Lemma I This statement is critical: First, it controls the expected cumulative error in batch l to be O (+t Te). Second, the condition that 0(w", WK.s S n/2², together with our localized online mirror descent method, ensures that batch k outputs vector W that satisfy 0( ((w*, W&+1) S m/2 with high probability (see Proposition B), which is in turn required by the next batch.
Proposition 4. For some constants cs, Co, C7 > O, when Algoritiu El runs with an initial vec- for Wk satisfying 0 (w", W&) < O2 = T/22+11 bandwidth by = cs (1 27)2- for Tg = co4h(1 (1 + 1)d d(In 2)2 2n) iterations with step size an = vd // In T),, its output Wk+1 satisfies 0 (w*, Wk+1) < 0x+1 Gs with probability at least 1 - 6/T².
Proposition A shows that Algorithm enhances its input by reducing the error by half in every batch, generating sequence of coefficient estimates (w&) k with geometrically decaying errors. Notably,
we achieve the enhancement by classifiers (((1) (2(2) that use at least y classification thresholds and are hence more resilient to errors due to strategic classification, which results in only a sublinear regret, as we will show in Theorem MI.

---

(12)
0 (1) h,
(11)
(7)
(a) Proxy Feature
(b) Contrastive Inference
true feature x with label +1
true feature with label -1 reported feature r with label +1
reported feature r with label +1
proxy feature with label +1
proxy feature with label +1
region (x (w*, x) 2
region (x [w", x) <
the band of interest D2. (x 0 S (W... but
hyperplane of optimal classifier (x(x) (gm(((".))
hyperplane (e) agn((W...)))-- -))
Lyperplane classifer (e) (Wi..: -7- bu)
Figure 2: (a) The gray arrows indicate how agents with true feature values (circles) within the band Da. manipulate their features (triangles). The blue and red arrows indicate how we construct proxy features (squares) from the reported features of agents with labels -1 and - respectively. (b) By (1) declaring classifiers 2,, and h collect data from agents with true values in D and D
respectively, through which infer the information for agents in the region Dx,5 of interest.
4 Regret Guarantee
We now provide formal regret guarantee of Algorithm M. showing that it achieves a sublinear regret dependent on the noise level îj and feature dimension d. Theorem 1. For any instance of our online strategic classification problem with noise level ij, max- imum manipulation distance ", and feature dimension d, the expected regret of classifiers from Algorithm 0 over T cycles satisfies
(h: O (dIndx (In 27) v(r x -27))
We prove the theorem by analyzing the regret incurred by each of the three sub-algorithms in Sec- tion The full proof outlined in Appendix A. We also conduct numerical experiments to evaluate our proposed algorithm, with results presented in Appendix A.21
5 Concluding Remarks
In this paper, study an online strategic classification problem under Massart Noise with partial feedback. The settings are of practical relevance yet theoretically challenging. We introduce a novel algorithm that concurrently learns a linear classifier and manages instantancous prediction errors. The algorithm leverages localization to mitigate the complexities induced by Massart noise, The strategic manipulation of agents poses critical challenge by limiting access reliable training data; thus, the core innovation of our approach lies in using carefully designed classifier pairs to collect some proxy data and contrasting their data for effective learning. This pairwise contrastive inference approach with proxy data effectively addresses the challenges in online strategic classification. This paper has some limitations. First, our algorithm is specifically designed for Massart Noise. Second, this paper assumes that agents' utility functions are homogeneous and known to the principal. Third, we adopt as an objective the traditional classification accuracy metric. Future research directions include extending the algorithm overcome these limitations.
Acknowledgement
The authors thank the anonymous review team for their insightful comments and suggestions. Yong I Liang acknowledges the support from the National Natural Science Foundation of China (72325001). Xiaojie Mao acknowledges the support from the National Natural Science Foundation of China (72322001 and 72201150) and the National Key R&D Program of China (2022D0016670),
10

---

References
Saba Ahmadi, Hedych Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference Economics and Computation, pages 6-25, 2021.
Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds on online strategic classification. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 22-58, 2023,
Saba Ahmadi, Kunhe Yang, and Hanrui Zhang. Strategic littlestone dimension: Improved bounds on online strategic classification. Advances in Neural Information Processing Systems, 37:101696- 101724, 2024.
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190. PMLR, 2015.
Pranjal Awasthi, Maria Florina Balcan, and Philip Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log- concave distributions, 2013.
Peter L. Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006.
Jiafeng Chen, Zhen Li, and Xuan Mao. Learning with selectively labeled data from multiple decision-makers. In Proceedings of the 42nd International Conference on Machine Learning, 2025.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 2020.
Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Learnability gaps of strategic classifica- tion. In The Thirty Seventh Annual Conference Learning Theory, pages 2024.
PMLR,
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. Advances in Neural Infor- mation Processing Systems, 18, 2005.
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeendeet pac learn- ing of halfspaces with massart noise. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with massart noise under structured distributions. Conference on Learning Theory, pages 1486- 1513. PMLR, 2020.
Ilias Diakonikolas, Daniel M Kane, Vasilís Kontonis, Christos Tzamos, and Nikos Zarifis. Effi- ciently learning halfspaces with tsybakov noise. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 88 101, 2021.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zaritis. Online learning of halfs- paces with massart noise. arXiv preprint 240. 2024.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Eco- nomics and Computation, pages 55-70, 2018.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016.
Keegan Harris, Chara Podimata, and Steven Wu. Strategic apple tasting. Advances in Neural Information Processing Systems, 36:79918 1000118-7994,. 2023.

---

David P Helmbold. Nicholas Littlestone, and Philip M Long. Apple tasting. Computation, 161(2):55-139. 2000.
Information and
Adam Klivans, Philip M Long, and Alex K Tang. Baums algorithm learns intersections of half- spaces with respect to log-concave distributions. In International Workshop Approximation Algorithms for Combinatorial Optimization, pages 588-600. Springer, 2009.
Himabindu Lakkaraju, Jon Kleinberg, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. The selective labels problem: Evaluating algorithmic predictions in the presence of unobservables. In Proceedings of the 23rd ACM SICKDD international conference on knowledge discovery and data mining, pages 275-284,200 2017.
Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In International Confer- ence on Machine Learning, pages 6243-6253, PMLR, 2021.
László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algo- rithms. Random Structures Algorithms, 30(3):307-335 2007.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning, The Annals of Statistics, 34 (5):2326-2366, 2006.
Francesco Orabona. modern introduction to online learning. 2023.
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Rocco Anthony Servedio. Efficient algorithms in computational learning theory. Harvard University, 2001.
Shai 2007.
Online learning: Theory, algorithms, and applications. Hebrew University.
Han Shao, Shuo Xie, and Kunhe Yang. Should decision-makers reveal classifiers online strategic classification? In Forty-second International Conference on Machine Learning, 2025.
Jie Shen. On the power of localized perceptron for label-optimal learning of halfspaces with ad- versarial noise. In International Conference on Machine Learning, pages 9503-9514. PMLR, 2021a.
Jie Shen. Sample-optimal pac learning of halfspaces with malicious noise. In International Confer- ence on Machine Learning, pages 9515-9524. PMLR, 202
Jie Shen. Pac learning of halfspaces with malicious noise in nearly linear time. In International Conference on Artificial Intelligence and Statistics, pages 30-46. PMLR, 2023.
Lingging Shen, Nam Ho-Nguyen, Khanh-Hung Grang-Tran, and Fatma Kinę-Karzan. Mistake, manipulation and margin guarantees in online strategic classification, 2024.
Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-learning for strategic classification. Journal of Machine Learning Research, 24(192):1-38, 2023.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Conference on Learning Theory, pages 4526-4527. PMIR, 2021.
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, edi- tors, Advances in Neural Information Processing Systems, volume 33, pages 7184-7197. Curran Associates, Inc., 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract accurately reflects the paper's contributions and scope by stating that the paper addresses the online strategic classification problem and proposes novel learning algorithm that converges to the optimal classifier and achieves a regret rate of (vVT) (up to poly-logarithmic and constant factors). It also clearly outlines the combined challenges of agents' strategic feature manipulations, partial label observations, and label noises.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
In Section 5 we acknowledge our limitations and point out some future direc-
tions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex, system might not be used reliably to provide closed captions online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions clearly stated in Assumption M and Assumption A We provide a complete proof in our appendix and provide proof sketches Section and
Section !
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We use Python 3.9 to conduct our numerical experiments. All settings and results are listed in Appendix A. We guarantee that our results are genuine and credible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper provides the code and data required for the experiments in the sup- plementary material. The code is well-organized and well-documented, which facilitates the reproduction process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
ottpaa/ccac.sooaaaaaaaaaoooooooo Policy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details of our numerical experiment is listed in Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We present the mean regret rate of all algorithms, calculated across 10 inde- pendent experimental replications in Appendix A.2 The experimental findings are consis- tent with the theoretical assurances provide in Section B!.
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We state in Appendix A that all experiments can be conducted locally using a standard CPU without requiring specialized hardware, making reproduction accessible and straightforward.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wwrripsscccppbiccccc
Answer: [Yes]
Justification: Yes, the research performed the paper conforms with the NeurlPS Code of Ethics. The paper does not involve human subjects or sensitive personal information, so issues like privacy and consent are not applicable. The research focuses on developing an algorithm for strategic classification under specific noise conditions, and it does not present any foreseeable risks of harm, discrimination, or other unethical consequences outlined in the Code of Ethics. Our numerical experiment only uses simulated data, so does not involve any deprecated datasets or copyright violations.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
16

---

The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss in Section MI that agents' strategic feature manipulation can hurt a certain classification rule, and we design an algorithm to prevent this, which a poten- tial positive societal impact. This algorithm aims to enhance the fairesss and accuracy of automated decision-making systems, potentially reducing financial losses from misclassifi- cations. While the research focuses foundational aspects and does not directly address all potential negative societal impacts, we acknowledge the importance of considering such implications as the technology evolves.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The research in this paper focuses on developing an algorithm for online strategic classification and does involve the release of data or models with high misuse risks, such pretrained language models, image generators, or scraped datasets. Therefore, no specific safeguards for such releases are applicable.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
17

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The research in this paper focuses developing novel algorithm for online strategic classification. We do not use any existing assets such as code, data, or models from external sources. All methods and experiments designed and implemented by us, so there are no original owners or licenses to credit.
Guidelines:
The answer NA means that the paper does existing
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode, com datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
The research in this paper does not release any new assets such as datasets, code, models. Therefore, new assets are introduced that would require documenta- tion.
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The research in this paper does not involve crowdsourcing experiments or research with human subjects. Therefore, there are no instructions, screenshots, or com- pensation details to provide.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This research does not involve crowdsourcing research with human sub- jects. Therefore, there are no risks to participants, disclosures, or IRB approvals to report.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the L.M is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methodology of this research does not involve the use LLMs as any important, original, non-standard components. LLMS were not utilized in develop- ing the algorithms or conducting the experiments.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM for what should or should not be described.
19

---

A Technical Appendices and Supplementary Material
A.1 Feature Regularity Conditions and General Log-concave Distributions
The literature on learning halfspaces with noise typically assumes that the feature vector x has an isotropic log-concave distribution [Balcan and Long 20K, Awasthi et etall, 2017, ZZhang et all 2020. Shen, 1.23) The log-concave and isotropic log-concave distributions are defined as follows.
Definition 1 (Isotropic cog-concave distribution [Loväsz and Vempala, 20077). A random vector 2 over Rd with probability density function (x(.) follows a log-concave distribution if In @x(+) is concave. Moreover, is isotropic if [z] = 0 and [zz"] =
The following lemma summarizes some important properties of (isotropic) log-concave distributions that have been proved by literature.
Lemma 2. Suppose z E Rd with probability density function (x(-) follows log-concave distribu- tion. Then, the following holds.
(a) (Klivans et [2009] Lemma 5.17) For assume that E [z = C², then for every 0, 0, > 1) S CCt+
Moreover, if is isotropic, then,
(b) (Lovász and Vempala [20074] Lemma 5.2) d2(z) 2 Bi(d) (i(d)oor for all 0 S ||z||2 S 1/9, where
(d) 2 -d
(c) LLovász and Vempala 2007 Lemma 5.5) For d = 1, (z(2)) 1.
(d) (Klivans et al [200 Lemma 7 For d 2 2, (z) S B2(d)e Asdd)alll, where 32(d)
280 e and (d(d) 2(d-1)(20d-1)) 1)) 1772
Following Lemma D, one can show that any mean-7ero isotropic log-concave distribution satisfies the regularity conditions in assumption Ø Importantly, in this part, show that the regularity conditions can hold even for a mean-zero log-concave distribution that not isotropic. In this case, eigenvalue bounds the covariance matrix of the distribution determine the corresponding regularity parameters.
Lemma 3.
Let x Edd (d 2 2) have zero mean and cog-concave distribution. Suppose the eigenvalues of its covariance matrix = [xx]] are all bounded within [>, A. for some positive
constants X. X, then the distribution of x satisfies the regularity conditions in assumption R. with for
(1) parameters L1 Vx . L2 x R LVA. U1 = +xx U2 (2
(2)
== (2)2)
Vx
81 (1), 3, (2), (2). given in Lemma 2
A.2 Numerical Experiments
In this subsection, conduct numerical experiments to evaluate our proposed algorithm. To high- light the challenges posed by Massart Noise and strategic behavior, and to demonstrate the effective- ness of our algorithm, we compare its regret against two benchmarks: (1) the Strategic Perceptron algorithm from Ahmadi et al [2021], designed for noiseless online strategic classification, and (2) the PAC learning algorithm for halfspaces with Massart Noise from Zhang all [2020], designed for non-strategic classification. Note that these benchmarks are both originally designed for full feedback settings, whereas work focuses on partial feedback. We evaluate the performance of these benchmark algorithms both when they have access to full feedback (while our algorithm does not) and when they only use partial feedback as our algorithm.
We test the algorithms under two different settings, with key parameters outlined in Table MI Each setting is replicated 30 times, and report the average regret for each algorithm. Our analysis includes a performance comparison of the different algorithms and an investigation how various problem parameters influence our proposed algorithm.
Benchmark against Strategic Perceptron by Ahmadi all [021 understand the impact of Massart Noise, we compare our algorithm with the Strategic Perceptron algorithm from Ahmadi

---

Table I: Numerical experiment settings.
Index
xx
7xx)
? W
Setting
Standard Normal
7(x) = 71 exp( (xx])) 7(x fj
(1,0)
Sctting 2
Unit Ball
0.1
0.1
(1.0)
all [2021]]. This algorithm provably achieves only finite number of mistakes under a noiseless model where the feature-label relationship is deterministic and the true and negative classes are strictly separated by positive margin. Ahhmadi et [202T]] modify the classical Perceptron algo- rithm by setting higher threshold for classifying an agent positive and proxy surrogate features estimate the agents' true features. Their proxy feature is defined as follows.
Definition 2 (Xt, proxy feature, Ahmaadeetaa [_02T]].. For given classifier h(.) = sgn( +)),, an agent (x, y) reports his feature as according to Lemma I x, in Ahmadi el al [2021] is defined as
Then the corresponding proxy feature
Fr
(w,r,) = and yt =11
X
(2)
rr
otherwise.
Algorithm 5: Original Strategic Perceptron with Full Feedback (Ahhmadı all [2021]]
Accept the first agent without declaring any classifier then W2 Fı
if yı
else
W2
W2 W
for
, do
Declare classifier hr(r)) sgn((wi, 77), receive agent response
Classify the agent as Úe (re)))
if yt # Ut then
11
W441 <- Wr + YI.., We+t + we41/llWeelll
12
else
< Wr
Their original algorithm, designed for the full feedback setting, presented in Algorithm 5 Algo- rithm f below directly adapts this algorithm to our partial feedback setting. Specifically, instead of using all data points that incur misclassification for update, the refined algorithm uses only posi- tively classified agents with true labels -1 to adjust the coefficient vector.
Algorithm 6: Strategic Perceptron with Partial Feedback
Accept the first agent without declaring any classifier then
yn
W2 < rı
else
Wy
W2 W2/ll
2 ,T do
Declare classifier (x) sgn((we,r) 7), receive agent response r. if (w, r1) 2 then
10
Accept the agent and receive his true label ye
else
Reject the agent without getting his true label if 1/
then
14
W <- Wr N we+1 <- W Wt+1//lweet /lleellll
15
else
W4+1 < We
21

---

8000
5000
6000
4000
Regret
3000
2000
2000
1000
0
10000
20000
30000
40000
50000
10000
20060
30000
40000
50000
(a) Setting
(b) Setting 2
Strategic Perceptron with Full Feedback Strategic Perceptron with Partial Feedback
Our Algorithm
Figure 3: Average regrets our algorithm and two Strategic Perceptron-based benchmark algo- rithms over different time horizons 7 under the two settings listed in Table M Results are based on 30 independent replications of the experiment.
Figure B illustrates the average regret of each algorithm over 50,000 cycles in both settings listed in Table II We observe that our algorithm's 's regret grows sublinearly, while the two benchmarks' regrets may accumulate linearly. The original Strategic Perceptron with full feedback (the dashed red line) demonstrates slightly better performance compared its partially Ceedback-modified coun- terpart (the dashed green line). However, the improvement remains marginal, suggesting that our partial feedback setting is not the primary cause of the Strategic Perceptron's 's failure. Intuitively, the ineffectiveness of the two benchmarks stems from their sensitivity to noise when updating with data from all admitted agents. When 0(w,, w:) relatively small but (W,, re) (equals (w,, xx) when (We, r.) > 7) is large, the algorithm is more likely to admit a 'wrong' agent (y/+ = 1 but h(r,) = L) due to noise rather than inaccurate classifier. Since the perceptron algorithm updates are based on mistakes (Rosenblatt (19581), the presence of noise increases the probability of misleading up- dates for the classifiers. In contrast, algorithm explores small band near the decision boundary, whose bandwidth decreases proportionally to 8(w", wx). k = 1,2..... across batches. Within this band, wrong admissions are more likely due to suboptimal classifiers than noise, making the update more effective. This enables our algorithm to gradually converge to the optimal decision.
Benchmark against Non-Strategic Learning under Massart Noise by Zhang et al. [2020] Next, to highlight the impact of agents' strategic behavior, we compare our algorithm against the algorithm proposed by Zhang et al. [202]] (see Algorithm Z) which is designed for adaptively learn- ing halfspaces with Massart Noise the non-strategic classification setting. Their algorithm also adopts localization scheme that focuses on data within an increasingly narrow band near the clas- sification boundary and uses online mirror descent in batches for classifier updates. However, they do not consider the impact of agents' strategic behavior. We test the performance of their algorithm under strategic manipulation in both full feedback and partial feedback settings. The two settings differ in: 1) whether the principal feedback) or not (partial feedback) and 2) the algorithm chooses different bandwidths for updates, namely, {r| -b <. (W Tk.x) < by} for the full feedback setting and {r 0 (Wk, Tk,)) S by for the partial feedback setting.
collect labels of those who are negatively classified (full
As shown in Figure HL after a common pure exploration phase, the regret of the non-strategic learning algorithm in both full feedback and partial feedback settings grows linearly. This because the non- strategic learning algorithm ignores agents' strategic manipulation. Consequently, true negative agents may misreport their features to be positively labeled. In contrast, our algorithm accounts for agents' strategic behavior and is able to efficiently learn the ground truth distribution.
22

---

Algorithm 7: Non-Strategic Learning under Massart Noise
Input: Feedback setting F' noise level bound 1), lengths {Limt] o bandwidths {bx
18 step
sizes {az ) feature dimension d (imt)
Wo Seraatggic-Reiimmmeeet 1;; Wo, To, bu, Okp, d)
See Algorithm
W1
// See Algorithm
for k f 1 to K do
W Non-Strategic--atthhee Fraacched-F F. wi, 7, TR, bR, Ork d) // See Algorithm IE!
Algorithm 8: Non- Non-Strategic- Strategic- Initialization
Input: Feedback setting F., iteration length Zinit
for to iu
Uniformly draw W E gd
Declare (r) = (Wiini,.., r)), agent (Ximit, Mair..) arrives and reports Fini, Make classification decision Iean, (xiin,s)
if F "ftll"" then then
collect label 1init.
P
="partial" then collect label onny if i (Ximite)
F "full" then
return Wo Tha Ima
10
Yuui, Minit,
F "partial" then
return Thes i=1
Em
Tiuir Vimit,) ((Wuirss Fimita) >> 0)
Algorithm 9: Non-Strategic- Strategic-Refinement
Input: Feedback setting F" Initial vector Wo, noise level 17, iteration length To, bandwidth bo, step size oo. feature dimension d
Initialization Wo,1 = wo/l[wollz
for 1 to To do Declare classifier jo.; hr) = sgn( ((Wo,i, r)), agent (Xo.;, 30.s) arrives and reports ro, if F "full" then
Make classification decision Jo,1 (roi(ro,s) and collect label yo.s
Compute gradient:
go.:
[- [- (yo.: 10.1) (1 ro, (vo., (o.1))[(--a ro,s) I bu)
F "partial" then
Make classification decision $o.1 ho. and collect label yo,, only if jo.+ =
Compute gradient:
go.; -iroro (yo,: 10.1) + (1 ro. (go.: * fo. 1) < (w..,, S bo)
Set constraint set: Wy = (w/ || S (w, Wo) 2 c1 2n)
10 Update w: Wo,011 = arg min (go.., w) + ww where In(8d)
2(p-1)
In(8d)
Normalize: Wo,++1 wa. wo.s+1/l2
12 Compute mean vector: W. T5 ETo Wo,r
13 return wi = Wi/l
Impact of Different Parameters We examine three groups of additional settings analyze the impact of different parameters. For each group, we test both settings from Table M The average regret over 30 independent experiments for each group is depicted in fig. 5 up 50,000 cycles.
We first examine how different maximum manipulation distances = 0.1, 0.2, 0.5 affect the regret of algorithm. As depicted in Figure (al) and (a2), larger values result in higher regret. Intuitively, a larger permits more agents to manipulate their features, so the strategic manipulation problem becomes
severe. This causes all algorithms to have worse performance.
Next, we vary the feature space dimension, setting w' be (1 (d 2), 1,0,0,01 (d 4), and (L, O, O, O, 0, 0) (d 6), respectively. The average regret across different time horizons is shown in
23

---

Algorithm 10: Non-Strategic-Batchee Enhancement
Input: Feedback setting F, initial vector Wa, noise level fj, batch index k iteration length Ts, bandwidth by, step size ag, feature dimension
Initialization: W Wx
for i <- to T3 do
Declare classifier ( sga( "ga((wa,s,, r)), agent (xK,s) wk.s) arrives and reports rk,
P "full" then
Make classification decision Ut., ha. (TR.)) and collect label yk. Compute gradient:
gt,s [-ijre, xII (yo.: = Dn,,) + (1 17) (No * (x,))) S (wo,s: ro,s) & bp)
if F "partial" then
Make classification decision Uee = hu, (Fe,s) and collect label yk,s only if ge.
Compute gradient:
gA, [-ijra, (1o.: DK,5)
rl) (yo.1 # úr, () (wo.s, ru.)) bu)
Update: Wh.++1 + minwews (Be.,, w) + wk. where p 1n(84)-1 the constraint set
In(8d)
2(p-1)
W/ [w] ||w S 11 Wall2 & Oz. starting angle 02 g0tr
10 Normalize: Wa,c41 = We,ti1/ W
11 Compute mean vector W4+1 = Th Σ Wh.s
12 return Wk41 = We+1// W//111
4000
2000
3000
Regret
Regret
1000
1000
0
10000 20000 30000
40000
50000
0
10000 20000 30000 40000 50000
T
T
(a) Setting
(b) Setting 2
Son-Strat PAC Learning under Massart Noise with Full Feedback
Non-Strategic PAC Learning under Massart Noise with Partial Feedback
Our Algorithm
Figure 4: Average regrets of our algorithm and Non-strategic learning based-benchmark algo- rithms over different time horizons 7' under the two settings listed in Table MI Results are based on 30 independent replications of the experiment.
fig. [ (bl) and (b2). As expected, the d yields the highest, consistent with our regret bound.
setting yields the lowest regret, while d 6 setting
We finally investigate the impact of the noise level 7 on our algorithm's convergence in fig. B (cl) and (c2), setting r) 0.1, 0.2 and 0.4. Surprisingly, the impact of the noise level manifests in opposite trends across the two settings. In setting 1, higher noise level results in greater regret when large enough. Conversely, setting increased noise levels lead to a lower regret rate. This discrepancy might stem from the fact that, the noise level rises, the learning accuracy of the clairvoyant optimal classifier diminishes. Given that regret defined as the difference in cumulative error between algorithm's classifiers and the clairvoyant optimal ones, the noisier environment could potentially narrow this gap.
A.3 Technical Lemmas
In this subsection, we list some technical lemmas as instruments for our further proofs.
Properties of Regular Distributions

---

3000
2000
Degiet
2000
1500
Degues
0.1
1000
2000
0.1
01
18000
20000
30000
40b00
506000
10000
20000 30000
40000
50000
10000 20000 30000 40000 52030
(al) Impact y in Setting
(b1) Impact of in Setting
(cl) Impact of ij in Setting 1
5000
4000
2000
0.5
3000
Degget
2000
2000
0.1
1000
02
10000 20000
30000 40000
50600
10000 20000 30000
40000
50000
10000 20000
30000 40000 50000
(a2) Impact of in Setting 2
(b2) Impact of dl in Setting 2
(c2) Impact of fj in Setting 2
Figure 5: Average regrets of our algorithm over different time horizons T on various parameters. Results are based on 30 independent replications of the experiment.
Lemma 4. Suppose that the distribution of a random vector x ~ Dx satisfies the regularity condi- tions outlined in Assumption 2, then, it has the following properties.
(a) For Vw St and 4 L1 min R, b) S P (0 S (w, x) b) S Usb.
(b) There exist positive constants Cg, Cg > 0, such that for any two unit vectors V1, V2 E ES", if
0 I 8 (V1, V2) S 2. then c&P (sen( (V1.x)) + (Vn((v2,x)) < (V1, v2) S cyl (ven((v1.x)) + sgn ((2,, x)))
(3)
Proof. (a) Since (w,x) forms projection of onto a certain 1-dimensional hyperplane, property (a) trivially holds by conditions and in Assumption
(b) Letz = ((V1, x) ()2, which is projection of x onto a 2-dimensional subspace 1/2 spanned by V1 and V2- Let Φv, (.) and Dv,den its density and distribution, respectively. Let Gy, zz| sgn(zz) ) o sgn(zz)), then,
PxWD, (sgn((v1,x)) +
= PANDDS (z E Gva))
(2) dz
JXEGY
L2 dz
12120(v1,
where the first inequality holds by condition I of Assumption 2 that L S dv, (z) for all |ll| S R.
The last inequality holds by an observation that LxeGv, dz 2 R²0(v1, v2). Hence, we prove the first inequality of (E).
To prove the second inequality of (C), for Ve >> we have
PXDDA (gn((v1,,)) * sgn((v2, (V2,
FeNDiS (z E Gv,)
FANDU, (z E Gv,, ||z||2 +P (1 (1z||2> >)
I JEECSSNBP() (v, + PX (V1, > + (V2,x) e)
- Φv, (z) + PXXDD_ (1 (V1, x) > () + (1 >)
< U2D (V1, 2exp(1 - Qc),
25

---

where the last inequality holds by the fact that Φv (z) S U2 exp(-6dlzz))) - U2 according to Assumption condition and Px~~Dx (w, x) > 6) S exp(1 - Qc) for vw E gd according to
Assumption | Condition 3. Taking 1-In(0(v1.2) vel) then we have
U2
P Dx~D2_ (sgn((v1: x)) & svn((v2. x))) =
+ (v1,
Q²
Thus, we complete the proof the second inequality in (3)
Probability Tail bounds
Definition 3. ((a, b) -ssbexponential, Waunwrigt MITS
Definition 2.7) A random variable X with
mean μl [X] is (a, b) subexponenniill, for AA
6
0²1²2
E [exp(A(X - w))] - exp
2
Lemma 5. ((or, b)ssubbepooenttia tail bound, another form of Wainwright (2019). Proposition 2.9)
Suppose (a, b...subbepponettial random variable with mean E. [ nb then with probability at least 5,
1 + ln u V 20 In
1
5
also, with probability at least
1 1 3 3
X2#- V 20 In
26 In
Lemma 6. (A Bernstein-type type bound i.idd random variables, another form of Wainwrigtt [2011]] Equation (2)) Suppose {X) = is sequence of i... (a, subexpponnntiil random variables, then, with probability at least 6.
Σx,
E E[X
+ 0
2N In
2b 1b
and, with probability at least
8,
Σ
x,
E X.
ov 2N
2b 5
1=1
Lemma 7. (A Bernstein-type bound for a martingale difference sequence, another form of Wain- wright [2079], Theorem 2.19) Suppose {X N 1= is sequence of conditionally (a, bJ-subeexponetial random variables adapted from filtration (F.) iec.
o²X²
1 1
(exp(A(X; -
FF-) exp
E
2
b b
Then, with probability at least - 5,
N
1
EXS
Σ
B F.-1 oo
2N In
2b In
8.
and, with probability at least 1 - 8,
1
1
Σ x
E [ F.-1] a
2N
2b
26

---

Lemma 8. AAzma-HHeffitan ss Inequality, another form of Waimwright [2019]. Corollary 2.20)
Suppose fi=1 sequence adapted from filtration { such that X; E [a. bl, Then, with probability at least - 6,
N Σ
1 a)p Fi-]+
1
5
E [[x;]
- Nin
8
i=1
i=1
and, with probability at least 1 - 8,
N
Σ Σ
B|1, Fi-1- - (6-b)))) a)v
1 N
1 In
1
2
We show in the following lemma how to determine the parameters (a, b) prescribed in Definition B by a given probability tail bound.
Lemma 9. Suppose a random variable satisfies P P(XX 2 a) Cexp(- for given C, v
then X is (6zvI+ + 2C, -uyespubexo..li.alll Also, if is a random variable that satisfy |Y| S M,
then, XY is (6Muv1 + 2C, 6Mv) subexponetxx..
Proof. First, consider X||s moment generating function E [e^Ix]] for AA > O, we have
[
/
(cAIX) 2 4
B
P
du
too
In u
S +
[X|
du
4000
S +1+0
u - du.
From the above inequality, we get that IE [c>|x]]]
<
Cav I-
Set X < x if < d J.
30 as
E
f + =
-
we have:
E [|X
e [x
< E
< 11+2C.
(4)
Now we introduce a new random variable X" that is an independent copy of X, then we can bound [exp(A(X [x]))] by Jensen's inequality, E [exp(X(XX E
X x])) (exp(A(XX - X'))
Therefore, we only need to bound E [exp(A(X x'))]. For AA
Ge Gv
E [
X'
8 E
(X X
E [exp(AA(X X')]
(2i)!
E
X 28 22
3
11
21 (1+ 2C')
2
(2i)!
1=1
= =1+ +1+(1+2C)
(3nA)² < 1 + 2(1 + 2C3
i=1
(6uv) 220)
S Sexp(2(1 + (CC)3)))) exp
where the first equality holds by Taylor expansion, the second equality holds since [X x'y] 0 for all i's that are odd. The first inequality holds by the fact that |x =²''² < 2: [|x] + |x'l") for all 2 1, and that X and X' have the same distribution. The second inequality holds by (8) The
third inequality holds since _
[3=Aj² (3 < 2 x (3vx)² when X E [- ov ez The last
incquality holds by the fact that 1 + ee for E R.
27

---

Thus, by definition of (ubexosabbxp,nnniiaa, subexponentall.
we conclude that X is (6vv1+2C,,6)
Now we prove the subexponential property XY. Since | S M and IP (|X 2 a) S Cexp(-
P P(XYY 2 a) S [
2 M
S C exxp (-
Mv
Replacing by Mv, conclude that XY is (6Mrv1 1 2C, subexponbalpo
Lemma & directly accommodates our regularity assumption and leads to the following corollary.
Corollary 2. (Subexponential property of regular distributions) Suppose is random variable that satisfies Assumption Q then, for V w TB,, (w,x) x) is 16 subexxponentii..
Q Q (
Proof. By Assumption A Condition 3. PP[ (w,x) 2 < exp(1 - Q() for V > 0. Then by
Lemma R. set e, o. then, 6 2C G/I+2e
6v Q: we conclude that is
Q
q
16 Q
subexponential.
gk.s)) and (Wx,), w*) Recall that in the non-strategic set- ting, we shall adjust the coefficient by solving a sequence of adaptively constructed online regret min- imization problems min Σ (w, gk.a) E (w", gk,s) with g = --Tps,, II (yk, 1) batches, using local data within increasingly narrow bands DR.: {x 0 (W..i. x) < 6x J. The key ingredient un- derlying this guarantee is that the gradients gt.; are well constructed so that (Wi..) gt.s)l small and meanwhile E [(ww.. -
The relationship between E [[w
(1 xI (yA.i -x)] DR.)) mirror descent over O....
-g,,i) upper bounds A (w*, Wk,)). Here, we show the relationship between [(w". + and 9 (Wi, w*) for l 1. ... K, which is critical in the guarantees of Algo- rithm E and Algorithm g!.
Fix batch & and iteration i, connect EE [ g). and (Wi. w*) we introduce new vari- able (w..( in (B). Later, we will show how E [(w", -k.i)) upper bounds fk.: and how fa.( approximates (WK.s. w").
(w..)).)) E (w" x) [I(("", x) 0) x E DR.a)-
(5)
Now, show that E I(w", Bk.i)l can upper bound fk.i(we.)) by the following lemma.
Lemma 10. Given a unit vector Wa.s Sd and an agent with true feature- pair (X De..). For gk, I-fpxx (yu, 1) + (1- x))x, (Me, -1)][(xx,; Du,s) and fw. (wa()),) defined in
(5). The following holds.
E [www, -g (1 277) (Wk.)) Dr.)).
Proof. First, for convenience, rewrite gk, as the following.
gk,i = [-ipxs, [ = 1) + +1 x)x (yv.1 = - 1x)] E Dk.))
= =--Jun. UK. + (2-)) :)) xx, xxx,, E Dk.)).
28

---

Then, we have
E [(w",
-Bk,i)]
E
w*
2 UR,
1
)1)
XR.i
1(x,, E Da.s)
2
1
E
w"
2 U
17
XR,5 XR.i E Dais P P( E Da.)) +
2
1
IE [(w"
xs..) E [uAke
Xky E DR, P (x E DE,))
2
2 /) ((w" xx.i) x E Dr. (x E Dk.))
2 - 7) E (w" xx.) || X E Du. E Dk.i)
2 1) [(w" xx.i) Xa. E Da.i) E Dk.i)
(1 27) E (w" xx.) I [IW((( xx.a) < 0) X Pa,iI Da.))
(1 - 2n) fa.i (Wk,;)P (x E DR.)),
where the second and third equality hold by the law of iterated expectations, and the inequality holds as the following.
E yy
x (1 n7 (sgn)) (emn((w (w",, xx.i)) ((xx,,)sgn(((" xx,())
(1 2x)(x )sgn( (w", xx,))
2 (1 2r))sgn( ((w". xx,)))
Next, in the following lemma, we show that (W,,) measures the closeness of w and Wa.i- Lemma 11. For fixed batch and iteration if 0 (w*, wk.) = Φ. then the following holds.
4 and d E 1. When O < be S B
Abe
7.. we have R 2
L2 R2
Sm,((W,))
32U,
2. When 0 by S and @ E [2. π
1bx R
we have
L2
(w,(WK,)) 2
R2 (T Φ)-
32U,
Proof. We prove the two cases respectively. For Case 1, define the region G1 {x|0 S xW S bk, - Rsin (w* x) S have the following
R Riin Φ}. see Figure B as illustration. We
(w* x)
[[(w", x) <0)I(0 < (Wk,, $ bb)l
E (w" x) [ G1)
Rsin of [x E G.)
4
RØP (x Gi)
8
L2
32
where the first inequality holds since G1 S {x 0 < (WK.), x) < b, (w*,x) x) < 0}. The third in- equality holds by the fact that sin o 2 for 0 < o < g. And the last inequality holds by the claim that IP (x G1) 2 T. Rhg which we will show later.
29

---

A
B
Figure 6: Illustration of region G1 (the red region) in Case 1. Which satisfies Gi
[x 0 S (w,x) S bys - Rin @ (w*, x) S - Rsin Φ).
Hence, we can establish the lower bound of fi., by:
Sk,((
E (w*, x) T [[W"", x) <0] 0 S (We,i,)) S bk]
B1 (w*, x) [[((w, x) < <0] (0 S (WR,i, x) S bx)]
PO I (Wk,i, x) S bk)
32 Lo pbp
P S (w S bk)
L2 &²
32U1
where the last inequality holds by Lemma H. property (a).
Now we show the claim that (x E G1) 2 LggRb.. For given vector x, we first project
down to the subspace V/2 S IR2 spanned by w and W.. and denote the projected value z =
((w", xxw",)), xw).
Without loss of generality, let (0,1) and w (sin c cos Φ). As illustrated in Figure the parallelogram ABCD denotes the region GG, where ( + tan a by. D (1 tan : Since is the farthest point to the origin with respect
(2,,0). B R,).).. C
to the Euclidean Norm, and ( tan bx 11 < (1 R+ tan be)l,, 1 R + hy + by S
br.
i + by 3 + by < R. then for all E {z= (z1, =2) - R & S S - sin Φ, 0 22 < b 1
we have ||z||2 I R. Also, the area of parallelogram ABCD is by 1 = 1 Rbb. In addition, by Assumption 21 condition 1, the density Φv, (z) of projected value satisfies @v (z) 2 Lg for all z E 1/2 n (R). Hence, we can lower bound P (x G1) by
1 ((xEG)) L2 Rb: 4
1
4 L Rbg.
The proof of Case {x 0 S (Wa,i, x) S bb, - z Rtinn[ Φ) S (w", S - ReinnT - Φ)} (see Figure M. We re- place @ in the proof of Case by d. by choosing A (- R,, 0). B (- R, 0).
similar to that of Case 1. Define the region G2
C C= (- oy
(- ian(=- by and then we complete the proof.
Lemma I directly leads the following corollary.
Corollary 3. (fw, Wi.)) < 5, and (w,,(We,)) S 1606,
La R²O,, then 0(w", Wx.e) S 3..
Proof. We conduct a case analysis.
1. If (w", ,Wks)
<
4b. then by our setting of by in Algorithm B and Algorithm !
R
0 (w", WK.s)
4b H
0
30

---

G
B
A
w'
Figure 7: Illustration of region G2 (the red region) in Case 2. Which satisfies G2 [x 0 S (Wk,i, I bb, sin Φ) (w*, x) I Rsin( 6)}.
2. If 4bg
I 0 (w", Wk.) < R20 (w*, Wk,)). combing it with the condition that (w,,( -oot R20,, we have O(w', Wk.) I 0g
2 then by Lemma I we have fk.((Wk.)) >
5
L
Other lemmas We also outline some other lemmas that are used in the subsequent proof.
Lemma 12. (Triangular inequality of angles) Suppose vectors x, y, z E I2 satisfy A (x, and 0 < 0 (x, (x,z) z)
S
I x 2' then,
0 (x. - 0 (x. 2) 0 (y. 2) - 0 (x, 0 (x, 2)
Proof. Without loss of generality, assume that ||x||2 |ly | First, we decompose vectors y and into components along the direction of and perpendicular to x, respectively, as:
y cos (x, y))x s0 (0 (x, y))y 1xx
z cos(0 (x, 2))x + sin (x, x))
where yix and Zix unit vectors that perpendicular to Hence, have
cos(@ (y,z)) (y, co y)) cos(8 (x, z)) + sin y)) sin(0 (x, z)) (y v1,2)),
where the second equality holds since (x,y = (x, z = 0. Since y and 2 are both unit
vectors, by Cauchy-Schwarz inequality, -1 S (y 21) < Also, since I 0 (x,y) I and
0 < A (x, < 2. we have sin(0 (x. y)) sin (x, z)) 2 0. Putting all together, we have:
cos(O (y, 2)) S cos(0 () (o (x, z)) + sin(0 (x, y)) s0 (x, 2))
(6)
cos(0 (x,y) 0 (x, 2)),
and
cos(@ (y,z)) 2)) cos( (x,y)) cos (x, 2)) sin(0(x,))) (x, sin(O (x, 2)) cos(@ (x.y) + (x, z)).
Since cos(x) is decreasing in E [0. m] and cos (x) 0 (x, y) 0 (x, z) from (6), and 0 (y, 2) < 0 (x,y) y) + 0 (x, 2) from (α)
(oos-x)) for all x E R. we get 1 (y,
Lemma 13. Given a random vector x ~ Dx that satisfy Assumption Q then with probability at least 1 5,
|x| S o (1+ d (
Proof. We bound |x||c glement-wisely. Given x Dx and j E [d], let zy be the j-th coordinate of x. Let elil E Rd denote the unit vector whose j'th coordinate is while other coordinate 0, then, by Assumption A condition 3, for V 0
P (|a 2 a) = =P (( (el), 2 2a) S Eexp(1 Qa).
31

---

Taking union bound over all coordinates, we have
P [||x||>> a) dexp(1 Qa)-
Taking a = (1 In (1)) in the above inequality and hence we complete the proof.
A.4 Proofs for Section
In this subsection, we outline some important results to describe the relationships between classifier 1(-) for unmanipulated features x and classifier for reported features r (x h). which is critical for the subsequent algorithm design.
Proof of Proposition II
Proposition 1. For any (w, m) E Sd x R. the output of h(r) = sgn((w,r), +m tm-)))or rx identical to the output of h(x) = sgn((w. x) + m) for any x Rd.
Proof. For fixed w Sd and m classes according to their true features x: {x (w, + < 0}, {x 0 S (w,x) + m < <) and {x (w, x) m 7). Then, discuss their classification output by h(x) and h(r) with respect r' (x, h), respectively.
R, we categorize the agent population into three
1. When (w, x) + m < 0, h(x) -1 At the same time, ().x) m - < -7, by Lemma I1 agent in this region will report his feature truthfully, i.e., r = x. Thus, h(r) = sgn((we (w, r) + m - 7) = sgn( (w, x) + m - 7) = 1. Hence, we have h(x) = h(r) = for Vx {x (w, x)
0}.
2. When 0 < (w, x) + < h(x) 1. At the same time, -7 S (w,x) + m < 0, by
Lemma M1 agent in this region will manipulate his feature as = x + (7 m - (w. x))
Thus, h(() = sgn((w (w.r) + m -7) sgn((w, x + (7 m (w, x)) + m - 7) = 1.
Hence, we have h(x) = h(r) = for vx E [x 0 < (w,x) + m < <7}.
3. When (w, x) + m 2 7. lxx) = 1. At the same time, (w, x) + m - 2 0, by Lemma II agent in this region will report his feature truthfully, ie., = x. Thus, h(r) = sgn( (w, r) 7) 1. Hence, we have 1(x) h(r) 1 for Vx
7) sgn((w gen(w, x) +
{x (w, x) + m 1221 7)
Inferring agents' true features from their reported features Proposition II directly leads the following corollary. enabling us to infer an agent's 's true features x given a classification rule h(-) and his corresponding reported features r.
Corollary 4. For given announced classifier i((-) = sgn ((w, :) + m) and agent response then, his true features x satisfy the following.
1. if (w,r) + m # 0, then x r;
2. if (w, r) + m = 0, then -7 < (w, x) +
A.5 Proofs for Section
In this subsection, we show the theoretical guarantees of Algorithm D, Algorithm B and Algorithm R| respectively.
Theoretical Guarantees of Algorithm P A key observation in the non strategic and noiseless classification scenario is that y (w", x) > holds for all y). Consequently, xy always forms an acute angle with the optimal normal vector w*. Considering agents' strategic responses and the bandit feedback setting, we introduce Lemma too to show that, under our construction Algorithm is an unbiased estimator of E[xy].
32

---

Lemma 14. In Algorithm D we have
10 Wol E[[y]]
Proof. In Algorithm D at iteration i, the principal declares classifier (1)) (r) sgn( (Winit r))
and h
initt (r)
(2)
sgn( (on((-Wiiie Winiia r)), and receives response (1)
Finiti and Finiti respectively. By
(2)
Corollary B
we get that siai (
Winitii iiiii 0)
x Ximli II (( (Winiti: Xiniti
(1)
and
(2) "init,
Winit,is iinit.)
(2)
xiii. -iinit, Xinits
(2)
0).
Also,
i Minits
(1)
and
initi Miniti)
(2)
are i..dd drawn from D, hence,
E
(1) (1)
Winit.i I "imiti
(1) ) > 0) + r (2) (2)
iiniiiinnti I ((- Winit.i, F iimii
(2)
> =0]
E Xinit
(1) (1) II ( (init. x inii.
(1)
0) + Xini Mimin
(2) (2)
Xini. ((- Winit,
(2)
0)
pxyT (( ((WiiiLi; x)
> 0)] + E [xyT ( ((Winit. x) < 0)]
[xy]
Thus, we have
Thn
[oo]
1
E
r (1) (2).
(2)2 ((Winis:
initii > =0)
((-Wint::: (.(2) Fintii Fiiit.
(2) (2) (2)
> 0
Tinit
i=1
EE [xy)
Now we show that Wo constructed by Algorithm Q has a positive inner product with the optimal coefficient w with high probability.
Proposition 2. For some constants co, C1 > 0, when Algorithm E runs for Timi co cn 2n7) iterations, its output Wo satisfies (w', Wo) > C1(1 2nj > and 0 (w*, wo) S T with probability at least 2/72.
2
Proof. First, considering the non-strategic classification problem, we establish a lower bound of Bl(w", x) yl as the following.
[((w* x) y]
E [Fyy x] (w", x)]
= E [[(1 (sx)))snn(( (ww
- n(x)sg(((w' - (w",x),
E [[1 227(x)) (w xx)x xx]]]
(8)
2 (1 27) || (w" .x)
2 (1 - 21 Ri?
where the first equality holds by the law of iterated expectations. The second equality holds by the definition of Massart Noise. The third equality holds since sgn((w", x) (w". x)) = (w* x) The
first inequality holds because 7)(x) I π. Vx Rdd. Now we prove E (w* x) L R for the last inequality as the following: let Xv: = (w*, x) denote a 1-dimensional projection of x. Then,
by Assumption A condition 1, Φv (xv)) L1 for all -R < Xv; < R. Hence, have
R Xv. on (xv) dxv, 2 L, x 2 /
n rdx = R2
E w x) 2 2
Second, considering agents' strategic response, we find unbiased estimator of IE [[(("* "ww,,"' x) v]
Tha EE The (1) I (( (iiit,. Finit. > 0)
through samples. By Lemma
E4 Wo =
mi Vinit,
(2) (2) (2) TI iinit,i; r "inii, Smn, Vimil
> 0) is an unbiased estimator of E. [xy]. Therefore, I. [(w", [W)]
E (ww x) y] 2 (1 L,
33

---

Finally, using the results of concentration inequalities, we establish the high proba- (1)
bility bound of (w*, Wo).
By Corollary
M.
w",
(I) init,s
II Winit, I init,
w
x i
W x iiiiti/
0)
and
W F init,
Winiti r
(2) inii,
w"
X init,
(2)
I
Winit, init,
Then, by Assumption D condition and Lemma E. we get (1) Winit, Finit.
0).
that both
w'
init,./
Vinit
(1)
0 and
(w" (w",
:Fimit.)) Vinit. ((-wiit,t r "init.? > 0)
(2)
(2)
16 6 Q
subexponential. Thus, by Lemma E. we have that with probability at least 1 72.
Q
I'm
w 'iiitt/ Vinit. (( (Wiitt,s: I Finitss
> 0)
T init
Tin
32
In InT
E [(w* x)) yII ((iiii,
> 0]] -0]-
T
init
Q
Tinit
Q
Tini
and with probability
1
T
Tux
1
w", iin..
Vinit ((-
(--init.s inii,,
(2)
0)
T
Iii
iiiit
i=1
(10)
Thet
32
In
24 In T
E [[(w", x) (oll(Wmm..s x) < <0]
T
Tini
Q Tini
i=1
Taking the union bound for ( and (IC),, then, with probability at least
2 7
Thn
(w) =
w", r init.s/
Vimat
(( (Winit,i, (1) "init
> 0)
Timi
Tis
1
w= r imit. Vinit." ((-((( ((-Wini.))) (Winit,,
(2) in "init,
> 0)
+
Tiit
1=1
1
Tha
32
In
24 In T
E [(w", x) yT(( (Winit, x) 0]]
Tini
Q Tiii
V
Q Tini
i=1
32 In
24 I
+ Tini
E [((w", x) yll( (Winit, x) <
Timi
Q Tim
1=1
64
I
48 In T
= =E[(w", " x) vl
Q
Timi
Q Tinit
64
In T
48 In T
2 (1 2T)
Q
V
Tina
Q Tini
2 (1 L,
2
The first inequality holds by H and
The second inequality holds by Lemma 1.] The
last inequality holds by setting Tim
20736 I (1-27)* At then
64
In (1 27j) L, R² and
Q
V
Tax
48 T Q Tim < (1 (1-227) 27) R2 for large enough T. Thus, we complete the proof of Proposition A
n
Theoretical Guarantees of Algorithm B Recall that in the i'th iteration of Algorithm R. we de-
clare classifier (r) sgn( (Wo, r)) and construct the gradient as gu,; [-fjro, (No 1) (1 - r (Yo, = [1) < (Wo,s, ro,s) & bo). In Lemma [L we establish the high probability upperbound of Tee Bl(w", - -Bo,))) Fo by To (w*, -Bo.)
34

---

Lemma 15. In Algorithm G with probability at least - 1/T2, we have
Ta
E (ww, -g.
Fo S
(w*
Bo.1)
1=1
i=1
24
+
1 + 2pbo
/ To In + In
8
where p max U, exp(o),
U/ exp(6)
Proof. Since
(w*, xo,1) 11 (0- < (Wo,i, X0,i) S bo) (5 (7 ri)). first estab- xo,x) I(0 < (Wo, X0,1) S bo).
lish the probability tail bound of (w".xo,)
We partition Xo,; into two orthonormal vectors, for notational convenience, we omit the subindex 0, of xp.; and let X|w denote the ingredient of Xo,; that is parallel to Wo,i, i.e., x|w (Wo.i, Xo.i) Wo,i and x Xl denote the ingredient of X0, that is vertical Wo,s, i.e., XLw = X0, X w. Then,
(w", xo.;) I(0 S (Wo,s, xo,1) S bb)
( Xl|w) I(0 (Wo.:: Xo.i) S bn) + (w" x xIw) I(0 (Wo.s, xo.s) S bo)
(11)
(b)
Thus, have to bound part (a) and (b) in (II),, respectively. First, we bound part (a)
(I") T(O < (Wo.s, Xo.i) s bo)
(w", (Wo.s, Xo.s) wo,s) T(O S (Wo. Xo,i) S bo)
< bo (w", wo.))
(12)
bu:
where the first equality holds since X/w (Wo.i: Xo.i) Wo,i- The last inequality holds by the Cauchy- Schwarz Inequality. Next, we bound part (b) in (I.)) For ||wo,a w 1l2 S and a > bo, we have
P (w*, x 110 < (Wo,sr Xo.s) S bo) 2 bb)
P (w xiw) 2 bo. 5 (Wo,,, xo,)) S bo) P (1 (wiw,, Xo,i 2 a bo. 0 < (Wo.s. Xo.1) - bu)
where we prove the second equality follows
(w" x ww) <wiw>> xlw) (wiiwx x
(wiw: x0,s) = (WI xIw) + (WIw. x/Iw).
since ( (wimo x x(w) = ( (wiw> x(Iw) = O. we have (w", xiw) = (Wiw Xo.s)
Denote X : [ww la Xo.1) and = (Wo.s Then, (X, Y) forms a projection of X wiw onto 2-dimensional subspace Vz spanned by |[w_all and Wa,s- Let Φv, denote the density of (X,Y). By Assumption D condition 2, we have Øv, (X,Y) < U2 (xx(-))((X,Y)l11))
35

---

U2 exp(==6 x + ). Hence, we can bound the above probability by
P (1 ( 1100 S (Wo.i. Xo.1) S bo) 2 - -bb)
wi
2 a bo
P
[ wwilz 11
xx.os)
[ willl
0 5 (Wo, xu,i) S bo
1v (x NdxYY
a-ho
|w lw
$ U/
exp 1-OVX++Y2 dxdY
(13)
+00
< Uzbu
exp( -XXidXX
Tw Twiw
U2 bo exp
-5 up
[wi ll
U2 exp (8)
bo cxp
5
The last inequality holds by the fact that ||w* wo,illa S ro. which implies ||wiwlla ll2 S ro. and
that by < = 2, which implies exp
s8 ra
< cxp (8). Combing (I2) and (L3). for a > bo.
((ww", I(0 & (Wo.s. xo.1) s bb) > a) $ (1 (w xww) 1(0 $ (Wo, x0,1) S bu)l 2 a - bo)
U2 exp(o)
-8 ro
by exp
(14)
For 0 < a bo.
IP (((w, xo,1) T(0 S (Wo,s xo.1) S a) S ([[[ T(O S (Wo, xo.1) S bo)l > 0)
< P(0 S (Wo. xo.i) S bo)
s Uibo
bo d- ro
(15)
s Usbo exp
exp
8
S U1 exp(6)he exp
a
The third inequality holds by Lemma HI property (a). The fourth inequality holds for 0 < < bo-
The last inequality holds since by construction, bn < ro 2.
Let max { U1 exp((), Uzexp(6) by (14) and we conclude that for V a > 0,
(88 a
PP (I(O < (Wo,s, x) & bb) (w". x) > a) S pbu exp
(16)
To
Thus,
P (1 (w", -Bo,) 2 a)
1 -1))) 1)) 2a)
P (w", xo.:) I(0 < (Wo, xo.i) S (b)
500.
< P (1 (w", xx,x) I(0 < Xo,, < bo) 2
<pbu cxp (-1%)
where the first inequality holds since 1/2 yo. ( -7 S 1. In the last inequality, since ||Wo, w' < ||wo,ll2 + ||w'|l ||2 2, take ro 2 in (IEG) and get the upper bound.
36

---

By Lemma B. is (
12
VI 2pbu, 12) suuexponential. By Lemma A we can get that
8
with probability at least (1 T2)
To
To (w" Bo,+) + V /1+ 2pho To In +
48
El(w", -8.0)) [o,
S
In
5
The following lemma establishes high-probabiling upper bound for the average of fo.: (Wo,)) over To iterations.
Lemma 16. In Algorithm G. if (w*, Wo) 21 L R², then there exist some con- stants C22 c3, C4 O, when setting bandwidth bo c2 2n)², ieration number To
valnd c3 (I d In d(Iu (l), step size on = C4 VIahT' then with probability at least 1 3/T², we have
1 To
(o,,( S min {1, (1 - L2)) 2880U1
To
Proof. Recall that in the non-strategic setting. ghi xo (so. = -1] (xo.: E Do.s), where Do.; = {x|0 S (Wo, x] S bo} is just the localization region. Since the announced classifier is hr,((r) = sgn( (go.i... by the construction of go in Algorithm B and Corollary
1- (Vo.: =)
have
go.
[- i (No, = 1) + - ro -1]] (0 < (Wo,s, ro.s) S bo)
oxo,, II (yo,+ 1) + (1 xo. (Vo.) -1]]i (xo, E Do.))
go.i-
Then, by Lemma I we have
E [(w", x = E [(w", -go.))] 2 (1 27j) So. (ooo:.((o... (Wo.)) (x E Do.s).
(17)
We proceed to establish the high probability bound of Σ E [(w", probability at least 1 - 1/T2, we have
-...)) -
By Lemma D. with
To
To
48
Σ (l(",, -Bo,))) Fo, 1=1
- -8..) + v 1 2pbo v To In +
In
(18)
8
where p = max/
{
U1 exp(d), U2 expld)
8
Next, we move on to upper bound mirror decent.
Σ ===1 (w*, 3 through a nonstandard regret analysis of online
Let B(v1, v2) = 1- || v21l denote the Bregman divergence w.r.t. --p-T l| where
p In (Sd)-I- In each iteration i, the regularizer, B(, wo. is 1-strongly convex with respect to
In (8d)
||- lpp [see Shalev-Shwarz [Р[лл]]] From the analysis of online mirror descent [see Orabona [0023)
Lemma 6.9], with step size ag, we have
aj go
(aogo. Wo,i w*) S B(w", Wo,s) B(w", Wo,
where q = In(8d) 2. Summing the above equality over i [To], get
To
To
a
(oogo.s. Wo.s w") < B(w", Wo.1 - B(w", wo.1.+1) +
go.
2
1=1
Dividing both sides by ag, and moving Ete (Wo, B RHS, get
1 [Bw",, wo.1) - BB(w", wo, +
(w', -Bo.)
Wo,is
8o.:)
g
an
==1
Ta (Wo Bo,i) +
To
1 B(w", Wo.1) +
Ong
ag
2
(19)
37

---

Now we need to bound the three terms in the RHS of (L9) respectively. First, we bound B(w", Wo,1) B(w*, Wo)
B(w", Wo.1) l|w* - woll (2) w woll (b) d||w= wo (c) 2(p -
S 2dIn(8d),
(20)
2(p - 1)
2(p - 1)
where inequality (a) holds by the fact that ||x||e S ||x||| for all p > 1 and x E Rd, Inequality (b)
holds since ||x|| v /d|2x|12 for all x E Rd. Inequality (c) holds since || - -wolz I ||w]12- p- In(8d) < In(8d).
[|woll2 2 and
Next, we bound
Σ To ci=1
Wu,s, Bo.s).
Since (-Wo, g0,1)
(Wo, Xo,s)
(5 ( [8]=n)][(0 I < (Wo.,, Xo.s) S bo). then
I (-W,, B0,+) S bo and E [ io, Bo,s)l
bn (x E Do.s). by Lemma & with probability
at least 1 - 1/T we have
To
To
Wo.d:
80,x)
W 8o.s) Fo,t-1] To E K
i=1
(21)
bo
Pr(x Do.s) + bo / ITT
Finally, we bound E |o lgg
Since
igo
I 2//o,, we only need to upper bound
Σ /lgo,i Iee which satisfies
[[(
(-2 vo. + (2 (2-7) X0.5
llo
S (wo. Xo.)) S bo)
S
By Lemma D we have with probability at least - 1/ToTe,
3 In
olo I (1 +1+1mii (I+Id((661))) S
Thus, taking the union bound over i [To], we have with probability at least 1/T²,
To
3
2
11.
To x
In
Q2 Tl)
Q
Hence, with probability at least 1/T2,
To
To
36
2
Σ
go. 113
Q2 (l)
(22)
Combining (1))
(20),
and (22) together, and taking the union bound, we get with probability
at least 1 - -
To
(1 - 2n)
lo.(Wo.))PP (x E Do.s)
t=1
E l(w". -ga,i)
< Σ (w*, Bo,) + 8
To
24
V + 2pbp V To In +
48
In T
(23)
2d (ndd)
To Pr(x E Do.s) + bn / In +
180g
+ bp
To(n T)2
00
Q2
1=1
24
48
V 2pbn / To In +
ITT,
8
38

---

where p max { U1 exp(o), U2 _= By Lemma property (a), and the fact that bo < R. we
have l,b0 s P (x Do,s) S U1bo, dividing both sides of (23) by (1 2rj) Lo To we get
To
(w.s(
To 1=1
1
(dd)(8d)
U1
In T
1800
<
bo + (1-2f))4 V
+
(In T)²
00
(1 L1b0l
(1 (1-21)) 1-21)
To
(1 22) L100
24
InT
48
In
VI+ + 2pbo
+ (1 - -2ij) bn
V
+ (1- 2r 11 bn
To
To
By our setting. bo
min {1. R2) (1 (1-29) L, L,
c2(1
2n)
To
28800?
U9 finish the proof.
576 (n( c3 (T-2 d d(In 7y2, ao 3/Tbm
C4
v Valnd VT T
then we
The following lemma established by Zhang et al. [2020] indicates that by the construction of the
constraint set Wo, any two vectors in Wo form an angle that is no bigger than 'T 2 (1 2 R2. R2.
Lemma 17. (Zhang al (2020), Lemma 19) For any
vectors 11
Wo
{w [//] S 1, (w, Wo) 2 (1 2nj) R2) we have 0 (u, S π - [11 27j I R².
We use the following corollary to show that, in the t'th iteration, a small value of fo.: indicates that Wo,; and w" are close.
Corollary 5. !fw" Wo and fo.:(Wo.)) < min (1, Ta Re) #(1 21)- then 0 (w*, wo,) fo 3200,
Proof. We first exclude the case that (w", Wo.s) 5. which we prove by contradiction. Suppose 0 (w", wo,s) z. By Lemma MV and our choice of bo, (w*, wo,)) S (1-)))) < π bo.
From Lemma I. we get (Wk,) 2 L R² (I 0 fww", wx,:)). Together with the condition that (Wo,)) x #11- ((1-26) 2, L2 we have 0 (w", Wo,s) > To L,
2 27) L, R?3
3200; which is contradiction. Thus, we conclude that (w*, Wo,s) S -
Next, since fo,((Wo.) 0 (w", wo,:) S
221 32001
R2 1600, 2' by Corollary B. setting Ou 2. then
6o 5 T0
Putting all pieces together, now are able show the main theoretical guarantee of Algorithm GL Proposition 3. For the constant Ci in Proposition @ and some constants C22 C3, 0, when the initial vector Wo satisfies (w", wo) 2 01 (1- - 27)) and Algorithm E runs with bandwidth by = 02
2nj)² for To = en d(In T)2/(1 - 27) iterations with step size og = (l//dddd(////onnnn then its output w1 satisfies (w*, W1) S x/4 with probability at least 3/T².
Proof. In Algorithm EL the constraint set choose for gradient update is Wo {w| ||w/2 <
1, (w, wo) 2 ci (1 - } where ci = L.
I R?, since (w*, wo) 2 c1(1 27j), we can conclude
that w Wo.
Next, Lemma IG shows that with probability at least -3/22
To Σ
fo.(Wo.) S min [1 R?) T(1 - 27)) R2R2
(24)
To 1=1
2880U
Let Ao denote the set {il fo. (wo.))
min {1, L, R22
x(1-2f) L, 3200,
Combing (24). we have:
min (1, 11,,,177 123 7(1 27) L2
1
To
AAol
7(1 27) L2
Jo.
2
min { [1, L, 122)
28800,
To
To
320U,
i=1
39

---

Solve the above inequality and we get Idol From Corollary
To I 3.
0o 2.2 we know that when E Ao. 0(w", wo,s) S x Thus,
TO
1
To
cos(O (w", woo,))
2
Aol
COS
π
|Aol
To
To
10
To
Aol
(1
1
π
|Aol
1
To
2
10
To
1
1
1
1
9
2
10
cos
where the first inequality holds since cos decreasing in x [0. T] and cos -1. The sec- ond inequality holds since cos x 2 1 1x²² for all E [0, T.. The last inequality holds since
(1 (1-1) ()) (1 2
0.73 > 0.71 cos (H) By the concavity of cos(0 (w",,)) ,)), using
Jensen's 's inequality, we conclude that when the above inequality holds, we have
To
Wo. ))
To
cos
0
w
1 To
cos (ww", wo, 2 cos
πT
To
Thus, can get that with probability least 1 3/T², Algorithm B returns vector wt such that 0(w*, wi) S T.
Theoretical Guarantees of Algorithm g The following lemma shows that if, batch k iteration we can identify agents whose true features lie in the localization region Da... and we use proxy features to construct a proxy gradient ga,;, then E [(w", -gs,))] upper bounds E [(w", -gaa)] (and hence upper bounds 0 (w*, W).))).
Lemma 18. Given a classification rule h(x) = sgn(( r) + ma,)) with fixed Wk. E Sd and arbitrary ma.i < O, an agent (Xs, Uk.i) reports his feature as rR, according to Lemma W Construct proxy data as
x (Tri + (bk- (... (un, Xk, E DE.)) kii = (rk.i - (Wk.i, We.)) (yk, = 11, E Dk.)),
and define the gradient
| + (1- 1)) 11 1(xar Da..).
B
Then, we have
E [[(w", -B..)) 2 E E((ww, -gx.))]
Proof. First, by Lemma II given Wk,i for V XR,i E Rdd, we have
Fk.s + (bk- (W (w..)....)) W = Xx,s + (by - (W Xk.a) Wk.s
and
Th (Wa.s, Ik..) Wh.s Xb.i - (Wk. Xx.)) Wai
Therefore, when Xk.i E DR.4 = [x| 0 < (Wa,).)) S bx). we have the following
w=, x (w", .k. (bs- (Wk.), Th. Wa. II (VA, 1, Xk,i Dk.a)
(w",, Xx,i + (bE (Wa,,, Xx. wi. I (WH, = XA.i E Di.s) [(w", xx.s) + (bs (Wa,,, xx.i)) (w", Wx.s)) (yR.F = 1, Xk, E DR.))
(25)
2 xx.)) (Vik. = 1, Xk.i E Dk.)).
where the inequality holds since
> O and (Wi,), x..)) (xxx, Dk.)) S by-
40

---

Similarly,
w= x
(w" .Kk, (Wi,s, rk.)) WK.t) I (yRR -1, xt,t E Dk.s)
(w" Xx,i (Wi,e, WE,1) II (yk., -1, XK,i E Dk.i)
(26)
kww,, (w,)),,,)) - (.,,ixx...) (w", Wa, (BN., = -1, X E DR.))
I (w* xx.,) (UK, = -1, X DA.i).
where the inequality holds since (w",, Wa.s) > O and (W.,))e)) [xxe, E Da.e) 2 0. Combing (25) and (ZG), we have
E [(w BK,,
BB ( w" xttt) ) (1-1) xEit
n ((w", ,xxx)) (yKKi 1, Xx,i E DRGS)) - (1 -01-00 [()",((", xx,, (uk, = -1, XR,i E Da.e))
(ww,, -k,,i)
The following lemma shows that by pairwise comparing agents' responses under two different de- clared classifiers designed in Algorithm g we can unbiasedly estimate the proxy data desired by Lemma IH and hence construct a gradient estimator ga,s, accordingly.
Lemma 19. Given t.. X and B defined in Lemma IA for the proxy data X (1,t), (1,-) x(a+), (2.
and gradient estimator $ defined in Algorithm we have ki
(1++)
(2,+)]
E
= E
k
and
(1,-)
x/, - = E {
E
Moreover,
E [[W", -Bx,)) = E [(w", BB.i))-
Proof. For fixed normal vector Wk.s and bandwidth by. recall that D (x|0= S (WK,), x) S 7 + by} and D (x by S (Wi,,; x) S + bR). Then, we can ver- ify that Dx, ( (22)) By Corollary H. we have k.s
x |ra, + (bR- (Wa,s Fn.))
W = 1, Xx,i E Da.i)
|xC. + (bk- (Wa. XA.
w (yK. = 1, Xk.s E DR.i),
82, [TK.i (WA TR.e)
Wi.l Il (yR.i = -1, Xx.i E DR.i)
[
(Wk. Xk.s)
W.. I (Mee, 1, Xk.i E Dk.i).
(1,-)
RA
(1)
+
be
Wk. k.
Wk.i
[kk = S (WK,i, T..
(1)
S 7 + bz
X
(1)
+
bk
(WR. (1)
WR.i
1 (v() 1, X E D
(1)
2,
(1.-)
Wh.
Wk.s
(1) -1, 7 S W k..)
(1)
5 + bz)
(1)
(1) 1, X
(1) (D!))
WA.
WK.
(2.+)
(2)
bk
Wh. 1R
(2)
Wki I (yk. 1, (W.,) (2)
(2)
rk.
7 + bb.
x
(2)
b
Wk.s (2)
Wk.1 I ( (k
(2) = 1, x <D(2)
(2--)
R,1
Wk. h.
Wx.i
I ( 11, WW. (2)
k.d
? + bn
Wk.i k.s/ Wk.t
(2)
I (v(e
(2) 1, x E (2))
41

---

Also, (N5,5 wh.!) and (xi,s M3. are drawn i.i.d. from D. thus,
(1)
(2) (2))
& (1,+) (2,+)]
= [[x [x
+ (be- - (WE..: X Xx.s (1)
WR.i 11 (1) (1) Ukii = 1, xxi D/ ]
B
[x(]] + (bx (Wa,., / Whis 11 (Db = 1, x D (E
E
E [x + (by- (Wa,), ()),::))).:. II
y 1, x D
E
[x + (bn. (Wa,
y= E D
E [[x + (bx (W...))
1, x Da,i)l
E
x
(1,-) (2.-))
Similarly, we can show that IE
X R,
/,. = E [x.d Therefore,
(1++) x(2.+)) )} (1 --)) { (w"' (1 - -x(()))
E [((w,
ER,Nil
=
w x/,i
= =
(w",, x
x({)) }
- 7))B \ww, x
k,
l(w". x
Next, we establish the high probability bound of Σ Bl(w", -Bx,) Ee (w", -g..))
FRAi-1] by
Lemma 20. At batch io of Algorithm A when ||w" --"--way -w.illl S rk for Vi E [Tk), then with probability
at least - 2/T2, we have
Tx E Bl(w", gk..) FR S
Σ (w",
gk.))
24
48
+
1 2p(r + by rr Th In +
In T,
8
8
where p = max/ { U, cxp(o), U2 exp(6)
Proof. First, we partition (w",-gn,i into two parts, as the following
(w*,- -8,,1)
w= [(( Kk.i
(1,+) (2.+))
(1 (x (1,-) -
-x(0
(27)
w", mxx
(1,+) - - x) ( (2,1)) ww,, mx (2
(2,-) k.s - (1 x2 Rit
Since the randomness in part (a) arises from one sample, while the randomness in part (b) arises from another independent sample, parts (a) and (b) are independent. Therefore, we can bound them separately. We first discuss the high-probability tail bound of part (a).
We partition xpx((1 b.i (1,+) (1 ()- into two orthonormal vectors. For notational convenience, we omit the subindex k, and let X/w denote the component of x that is parallel to Wk, i.e., X/w = (W.. x) Wk.s. and xiw denote the component of x that is orthogonal to Wk. i.e., X = x X/|w Then.
w², "T",px(1""" (1,+) -1)x((1) ())((1-))
(px((ttt)) - -))x (1,-1) w*
+ (w",, w* (Tse(hit) -(1 7)x (1.-))
(28)
|/w
Lw
(a1)
(a2)
42

---

Hence, we have to bound part (al) and (a2) in (28), respectively.
To bound part (al) in (28), we have
w* x ((,+t) ) w",
(2) Fllw + bb -
----wwai (Wait (2..) We.s) (Jhi = -1,75 S (Riis Tk.s/ S bx
w', Flj
(1) + (be - -F(w²) 1 U/o
(1) =1,75 (waris (1)
Tk.s)
S s7+ + bs)
=(w", w. I Ukis 1 Whi r x/,)) x + bb))
Sba
(29)
where the last inequality holds because (w* wkii) S |/2ll// S 1. Similarly,
w 1/m
)((1)))))
(1) w", r "[w (WA,6:
k.. WE.s) (1ii) -1, (Wa..: x2.)) = 7 + bb)
(1))
w' F'l =(I
(1))
I yi,,s = =11, (WR.i++2) 7 + bz)
(1)
(30)
0.
Combing (29) and 60), we can bound part (al) as
w",
(X (1 (1- (1))))))))) 1|w/
(1,+)
S bx.
(31)
Next, we bound part (a2) in (28). From Lemma II we get that
Ww (rl.) +
(2)
(bx (W..s (1)
WK.s) TT = (r122 - ( (wkss=h))) Wk.))
(1))
=x >
= (1)
w
hence,
w* (xx -11 ()) ((:-))
1w
(22)
17 ( w. (F(1)
1k + 6bx (Wh.s (2) WH.s)
11 11 Bkit = 1, 5 (Wh, 1. (1))
S + bz)
(1 7) w=, (p(2) - ( (Wn,i (1))
k. kki)) Wk.s) w 11 UBk, -1, 75 ( (Wh,is (1)
/k.s/ S S + bn
1/ ( (w (2 > I (v/3]] =
(1) (D!1) - (1 11) ( (w",>P) (2) ) II ( 11, x E D
xx,
(w", x xIw)
(1)
1 (1)
(1 (1-1) n)) II xx. E D
3k
2
where the second equality holds by Corollary !
Since
(1)
(1 7))
s we only need to establish the high probability bound of E (( for a > bk we have
(1) w w x
(1)
PP
w x Lw
4 E ((1
(1)
2 a bb)
IP
((( ( x Lw >
(1)
2 a
bR. 0 5
We,i x x.
S r + by)
TP
(((w [(WIww
x (1)
b, >
2 a bR 0.
(Wi, x k.i)
S 7 + bb))
where the last inequality holds because
(w., xxxx = (win x x(x) )
(w/ w//w> x Iww
wi w: x x w w x x> ) + wiw:: (wimx>(H)) ( (wi: (1)
x
Let X =
[w Xk. and Y = (Wa.s: xx.)). Then, (X, Y) forms a projection of X1.; onto a wis and Wa.s- Let Φv, denote the density of (X, Y). By
wi
2-dimensional subspace V/2 spanned by [wLwll
43

---

condition 2 of Assumption D (X, I U2 exp(_=81(x, 122)), thus, we can bound the above probability by
to0
IP (((",x ( [x D
(2abba) bx)
(X,Y)dXdY
a-bp
1w 12
I U2
exp(-OvX'>
-80 X2 + y3)dXaY
bp
Iwiullz 12
I U2(y + +ba)
exp(- (1x-6))XX
1
U2(7 + bb))
by
exp
6
[ w
U2(7 + bk)
bk
exp
rk
U2 U2exp(0)(T + bk)
exp
-8 rkk
where the third inequality holds since ||w" - Wk. nx < 2.2 which implies last inequality holds since by < r'k by our setting.
[ ll2 S rk. The
(Bboh (2 - -m)] s for a 2 bb. we have
Since
(1 w (m'xx(x) (
1
Dw) 2 za- - bk)
IP
17
I (x
2
2
(32)
PP (1 (1(w,xxf) (1) ) I (x/1) ( 2 (0-ba)) bk)
U2 Uxcxp(()(7 + (ba)
-8 a
-
)
cxp
8
rkk
Combing (32) and (3II, we get that for a 2 bk.
P (1 ( k
(1,+)
(1- (1-))(()))) 2 a S P (1/ w", (TEE - -(1 11>))(11111
(1,-)
2 bz)
U2 exp( + bk)
exp --5
rk
(33)
For 0 bys
(1 (w", mpx (1,-) - (1 -1- ))
22) S PP
(w", (w", -7xE - (1 -11-)))(11-)) | 0)
(1,+)
(1.)111)))))
< P (1)
X E (1)
kit
(34)
< U1 (7 + bb)
(88 a
S U1 exp(5)( + bk) exp
Tk
Where the third inequality holds by Lemma A property (a) and the last equality holds since a < by <
Tkk
Combing (E and (2)) we establish probability tail bound of (a) in (2
for Va
0 and =
{ Ui exp(o), Ug exp(X) we have
max
PP ((| (=",mx(1' (1.+) - (1 ()x (1--))
(-0 a
2 za) S p(r + bx) exp
rk
Following the same technique, we can bound part (b) of (27)) for a > 0b::
P (1 (w', (xx(((t)) (2.+) (1 (1-1)) (1--)a((-)) ) N aa pyeexp
(-
rk
44

---

By Lemma & part (a) and part (b) in (27) are (g 2p(7 by)rk, grk) -sueeponentiill thus,
by Lemma A we get that with probability at least 1/72.
E w* k, (1,+) - -1 () )) FREE-1]
(35)
w xx (1+t)
(1 1)xx
12
V 2p(7 + bx)r TalnT
24 Th I,
and with probability at least 1 - 1/T2.
Ta
Σ
E
w
-7x (2x+t
(2.+)
x FR.
(36)
Tp
w",
7|x
(2.+)
- (1 n)x k
(2,1)
)
12
+
InT 24
Th In
8
1=1
Taking the union bound of (355) and (36), we get that with probability least 1 12/T2?
T Bl(w
Th
24
48
FR, S
(w", Ba,)) +
2p(7 +
Ta In + bo
" I.
8
1=1
We then show that by our construction ga.s Σ Wk., g8.) also has high probability upper bound.
Lemma 21 (High probability bound of Σ (- (-Wa, (-W.))BB..)). At batch k, with probability at least 1 - 2/T we have
T
Whii 8k,)) S Tibs _
P (x E Da.s) 27jbs v TnlnT.
Proof. Since Sk,i
(x
(1++)
8 + (1 - (x(11))) - -x((--) and we have the
(2,+)
(1,+)) Wa. k2
bell(111 (1) 1) E Df!)),
(2++)
beI(
(2) 1)I(x (2) D(?.)
Wk,i k,6
(1,-))
x((-1)
WR,i; X1,
Thus.
E B[( -Br.i) TibLE
T 1y= 11 x DD
T 1, DR.))
P DR.)).
Also, since x((1 and (1,-) are calculated by one sample while (2,+) and (2.-) &
kii
& are calculated
by another independent sample, we can reformulate (Wk, -8x.) the following:
(Wh,s: Be.s) (W..
(1.+) R
(1.-) (1 77) x k.d
WK,,, x (2,t) -11 x)x
(37)
(e)
(b)
where (a) and (b) (377) are independent. Thus, we establish the high probability bound of parts (a) and (b), respectively.
45

---

(Wa.d: (x2.111)) (1 1)x;(/1)))))
For part (a),
ribk. so by Lemma & with probability least
11/722
Th
- -00 k1 (1-))
Wk.i: 78 (1,+)
E (W., 78 12 --)))) FRS-1]
1=1
+ ribx V Th. In
Similarly, for part (b), with probability at least 1/T2.
Wkii, Tp3 (2,+)
E
7x (2,+) - (1-1)x(;-)) Fei-1
(38)
Tibk Th In
Combing part (a) and (b) above, and taking the union bound, we get that with probability at least 1 2/T
Tr (
Wk.s 8k.1) S
Wh.s BR.S)
+ 27jb VTy InT
Tc
rbbk
Pr(y 1| DR.) DR.)) 27/b /T In
(39)
Tk
S nbb
Pr(x Ds.I) 27bb V Ta InT.
The following lemma shows high probability upper bound of ΣT= 18...
Lemma 22 (High probability bound of Σ 1lxx In Algorithm Ø with probability at least 1 2/T2.
Tx
144 1
144 Q2 Qt T.nTT.
Proof. For = (8d) > 2, |g S g lle.. hence, we only need to establish the high probability bound of lige ll bo. By our construction of gk.i.
(x(1111)) (1++)
x (2.+)) -
+ (x()
x x(:-1)
(1++)
+ (1 - 77)
x k
+
(2,+) RRi
1000 + +11
(2,-))
[x k.
+ (b&
Wh.i
WK. I(VR, 1)[(x
(1) (
(1 7)
(xx)
Wk.s
W(, -1)[( (0 ((
+ + |x ?
+ (bx
Wh.d x (2)
|w..ll(uu. 1)1(x( (1
10
+ (1 7))
Wk.i Xki
We..)l(BR. = -1) E Dx.))
< x
+
(2)
+ 2(7 + bz).
From Lemma R we get that ,wihh probability at least 22
R
(1)
s Φ (1 In(dI(13))
(40)
46

---

and with probability at least 1
1
T
(2)
1
(1 In(dT(33)
(41)
Taking the union bound of (8I)) 1
we get that with probability at least T.27
2 2
In(dT, + 2(x bx)-
Q
Taking union bound over all iterations i [Tk], we have that with probability at least 1 - 2/T
2 In(dT; + 2(7 + bu) 1 Th @2 in(rr))
2
36
B & S
Th
Q
+
Q2 (ln
Thus, we conclude that with probability least - 2/T2.
Tx
Tx
144
&
2
12 S
Th (In
Q²
1=1
Given the starting angle of batch k as 0g = 26+1. the following lemma establishes the high proba- bility upper bound of the average of fu,i(WE,s).
Lemma 23, Algorithm at every batch
21,2..... K). if 0(w*, "ow,,w" wx) S Og. there ex- ists some constants C5 Cb: 07 > when setting bandwidth by C5 - iteration number vdde
Tk = cg (1- 21))
(n+1)d'nddn' 4h, step size Okk = C7 Tx In then with probability at least T the
following holds
Th fw..) s
L R2R
(42)
T
12800U,
Proof. Combing Lemma II Lemma II and Lemma 19 we have (1 (1- (1-27) Se. DE.)) S
E [w", gg,+)l. hence, it suffices to upper bound Σ E [(ww -B.,)))-
First, upper bound Th E ((w", -Kk,)) by Ei= (w*, -B.,))
By our setting of constraint set, cos(@ (Wk,i, wx)) = (We,s, Wx) 2 cos fg. since cos 9 is decreasing
in f E [0, n), hence, we have 0 (Wk.s, Wx) I 6z. thus, |[ wall2 I (W..i. w&) < 0g. Also. [w w S 9 (Wk, w*) I dr. by Lemma I2 |[ w*ll2 S 20g. According to Lemma
rk 20g. then with probability least 1 2/T², the following holds:
T B(w,, (x.) FR.
Tx (w",
48 VV
96 T. I
+ bb
70,
6g In T.
(43)
Next, we move upper bound Σ Th mirror decent. Let B(v1, V2) 1) [1 v2ll? denotes the Bregman divergence w.r.t. 2-- In (8d)
(w* x through nonstandard regret analysis of online -
I| where p
In (84)-1 In each iteration i, the regularizer, B(,, Wk,i-1) 1-strongly convex
with respect to
Ip [see Shalev-Shwartz [2002]]. From the analysis of online mirror descent [see Orabona 2023) Lemma 6.9], with step size ag, we have
a
(ORBB,, Wa,i w*) < B(w*, Wk.s) B(w", wk.
L 9
Where q In(8d) > Summing the above equality over i e [Tk], we get
Th
Th |
(arges, Wkii - w*) 5 B(w", WK.1) - B(w", Wx.T.+1)
11
47

---

Dividing both sides by ab, and moving E/= Th
(Wi, (k.s) .) to RHS, we get
(w', 8k) =
[B(w', Wk.1) - B(w", Wx:T++1)]
Wket Bk,s) +
l1
aKk
2 ==
Th WEii Ba,))
Th
S Ok
B(w
Wk,1) +
+
04ky
l1
(44)
Now we need to bound the three terms in the RHS (H4) respectively. First, we bound B(w", Wk.1) B(w*, Wk).
B(w", WR.1) || |w - w (a) |w wxll? (b) d w wxlB (e) d dlIn(8))
(45)
2(p-1)
2(p 1)
2(p 1)
2
Where inequality (a) holds by the fact that ||x||> S ||x|| for all p > and Rd. Inequality (b) holds since ||||| I Vd||x]|2 for all x E Rd. Inequality (c) holds since l|w"~wxkll 22 S 0 (w", w S
8x-
Next, we bound Σ (- Whi Bk.i). By Lemma 211, we have that with probability at least 1 - 2/TT.
Wk. S riby Σ P (x DR.))
2rjby, VTa.l In
(46)
1=1
Finally, we bound Σ
| I By Lemma 27 we have with probability at least - 2/T?,
i=
144 Q2 (ln
(47)
Combining
(8.5)
and (17). and taking the union bound, we get that with probability at (I
least 1
6/7
T2
27)
faa (w P Da.)
Th
<
E [(w", -Bai))
1=1
(48)
1
In (8
72
7bb
P (x E Da.)) + 27Th / Th In
Q (l
O/k
48
96
+
V + 2p(7 + by 10,
Ta I +
5 0g I.
5
By Lemma H. property (a), and the fact that by I h < R, we have L,b7 S P E Da.i) & Uibe. dividing both sides of (48) by (1 27) Tybe, get
The
d dln(8d)) (g))
U
27
IT
72az
(In (49)
< 0%k 2(1 27) Tibbb
+
(1-27)L
21
by +
(1 - 21 V
Q² L
48
V1 2p(7 + bx)
Ok
In
96
0% In T
8(1 Tq
bk
V
Tk
8(1
27)) J.
by Tk
By our setting, by
(1 Ln Loa 172
38400U7
0k
C5
1-20
2
Tk
576= 21+2p( by Indd T)²
26
co
(I+1)dln d(In d(n 2)2
(1-2n)*
12/T: In
Vd
vTh In
then we get our proof.
48

---

Based on Lemma DX we establish the main theoretical guarantee of Algorithm in Proposition P
Proposition 4. For some constants c,, Co. C7 > O, when Algorithm @ runs with an initial vec- for Wk satisfying 0 (w", Wa) S O2- = ///2+1, bandwidth by = cs 2rj)2 for Tç = cr4 (r + 1)d dn(I / 211)* iterations with step size og = c7 c en (T In T), its output Wk+1 satisfies (w", Wk+1) I 0x+1= 8x with probability at least 1 - 6/T²
Proof. For the given unit vector wa that satisfy 0(w", S 0g S 7, we have
O(w", W&)
8k
w w S 2sn
sin
S Ok.
The first inequality holds since |w 2|2 = || = 1. The second incquality holds since sin æ is
increasing in [0, 3.. the last inequality holds since sin S for all 0 S x S +
By our choice of Wk, for every iteration i, we have cos (Wk... Wk)) = (Wa. we) 2 cos(fx). thus, since cos is decreasing for 0 S S r,, then 0 (Wa,s: W&) S G₁, hence,
0(w", WxRR) S 0 (w", w&) (W&s Wx.e) S 20
(50)
where the first inequality holds by Lemma 1 By Lemma IM with probability at least 1
6
7
L, Let A = {i E [Zi]] fa. 2 1600, 1r202. Thus, Th ET= fn,((WE,)) S 128000
La
L2
L2 L2 |Ag
Th Σ (w.,))))
12800U1
16001 Te
[Aal Ta i' E Ag satisfy f(w", WK.)) S 5.. Other iterations Therefore.
From the above inequality and we get
S 80
and thus
LAul T
2
79
By Corollary [. the iterations
80
E A& satisfy (w", wk.) S 20g by (50)).
L
|Aa
co (w", wh.))) 2 cos
0
+ cos(20)
T
Tk
79
1
1
82
X
+
1
482
50
80
2
80
1
2
0
0
50
2
20
2
82
20
2
0os
where the second inequality utilizes the fact that cos 2 1- f2² and the last inequality holds since
cos x 5 1 f²2 for
< x
S J.. By the concavity of cos(0 (w*,,)) when 0 ((w", wk.s) S _ we
have
( (ww w-
1 Th
Wk: )
Th
0g
cos(0 (w", wk+1)) = cos
cos(O (w*, wk.)) 2 cos
Tk i=1
T
2
Since cos r is decreasing in E [0, r). we have O(w", w
0g
2
A.6 Proofs for Section
In this section, we outline the proof of Theorem MI which is the key theorem of this paper.
49

---

Theorem 1. For any instance of our online strategic classification problem with noise level i max- imum manipulation distance ", and feature dimension d. the expected regret of classifiers h from Algorithm 1 over T cycles satisfies
(b: T)) = (dlnd (In ((1-))(1-22))) v(r 1)dInd (1-))))))))
-21)²
Proof. To derive the regret bound in Theorem MI we decompose the total regret Reg(h; 7') as defined in (1)) into two parts according pure exploration phase versus exploration-exploiaaion phase, and then we move on to decompose the regret in the events. We upper bound each of these parts separately. First, we define the two phases and the events used in the regret decomposition.
exploitation phase according to certain
Definition 4. Define the set TPE {t [ < 2Tmir + To} as the pure exploration phase, where Timt and To are number of iterations in Algorithm Q and Algorithm & Define the set phase. Define the event
TEE {E m2i ini To <t S T} as the sxploration-expliiante Einit = ((Wo. w") 2 co(1 2 where co is constant defined in Proposition E For k f0,1,2... K}. define the event Ek {8 (Wk+1. w")) 2 Define the event E Emii N ED [E(KK] El as the "clean event".
In Definition E. the pure exploration phase TPE corresponds to all cycles in the Initialization and Refinement Algorithm, and the exploration-exploitaaion phase TEE corresponds to all cycles in the Enhancement Algorithm. By Proposition Ø Proposition BI and Proposition g the events defined in Definition I satisfy the following properties:
2
(Sinit) 2 1
(51)
72
3
IP (Eu Eiiit) 2 1
(52)
T
P (E& Hence, taking the union bound by (5Il). (b2) and (5:3), we get that the probability of clean event satisfy
(k-1, Sinit) IP (Ek (k- ) 2 T
Ak E [K]
(53)
2
3
6
( P
Einit
Eo
Ek kE[K]
N
x
1
1
1
7
T
T2
T
Then, we decompose the total regret as
Reg(h; T) Reg(h: TPE) + Reg (h: TEE, + Rog(h: TEE,
(54)
where E denotes the complement of e, and the three parts of (54)) is represented as the following:
Reg(h: TPE) = Σ Eir(h.) - TPE x Eir(h"),
TETPE
(h; TEE,E) Σ
[Err(ha) Err(h*) 1(s)
Reg h: TE = Σ
EEr(hh) - Err(h*) 1(2)
The first term in (54) denotes the expected regret incurred during the pure exploration phase. The sec- ond term captures the expected regret incurred during the exploration-exploitttoo phase, given that the clean event holds. The last term characterizes the expected regret incurred during the exploration- exploitation phase, given that the clean event does not hold.
Now upper bound the three parts of (54)) respectively. For the first term Reg (h; TPE), the regret incurred in a single cycle is at most I, and the length of pure exploration phase is [Teel = 2T + +To then, the expected total regret during these time can be upper bounded by
E (e: TPE)
Σ ОEТPE
15 2T mi
To O (cs - (1-2n)s d d(nd(T))))
1
(55)
50

---

where the last equality holds by our setting that Tiit o ( In)) and To
o ( In
Then, we upper bound the expectation of the second term Reg(h; TEE, e). which is the cumula- tive regret incurred under the clean event during the Enhancement procedure. Let Rega (h; TEE, s) denote the regret in each batch & {1,2, K during this procedure under "clean event" i.e. Reg TEE, e) Σ k=1 Rega. (h; TEE, e), then only need to upper bound E Regg TEE, e)
for each batch lo E (1. 2, ... K). which is characterized as
E Rega (h; TEE, $)
T
2
Err Err(h k.i)
Err(h*) E (s)
jm1
Th
(r) Err(h*) e)
Th
E [I sgn (( (WR. (22 -7) # vk.)) - I (sgn -((sgn ((w"
r.(,.,))) -7) # ( e)
E sgn ( (We.t =k.1 7 -bx) # vk..)
(sgn ( (wr' ((2:)) ->) # ) E
2x
Σ 1=1
II sgn ( (w..i, (1) ) + wb.) - I sgn
((wt,x (ssg(((w"
+ U E)
=
[I sgn ( (Wa, x..)
(2) bz) * w 11 sgn ( ( xx=,
E
# yk.s
E
(56)
(2,-) Where (1,+) and kRi are the counterfactual agent responses under the optimal classifier.
The
first equality holds by the fact that E [XI [X 1 (E) (s) + |0] [() = 0) IP (E)
E [[X] s) (E). The inequality holds since < P (E) S 1. The last equality holds by Proposition
For the first term within the summation in the RHS of (5r)) we have
T sgn ( * wio) - T (sgn sgn (ww,x(1)) # #vh!) s)
$ IP (sgn (ww,,x) + sgn ((w,,: |E)
(57)
C10
2
where Cin is a positive constant. The first inequality holds by the triangular inequality, the last equality holds since by Lemma A property (b), and Proposition R..
51

---

For the second term, we have
(2) 2,1
(2)
( ( )
E
sgn
bk:
# yk.
sgn
(2)
(2)
(kit (w..i.xaii) + ( [
E
sgn
bk
* yk
sgn
+ (
( x,",xx,1 (
+ x
+
sgn
Wk, x b,3
sgn
S E
sgn
bk + sgn
Wk. x
(58)
+
[I
sgn
Wh,,
x k,2
(2)
* sgn
[ xxx
IP (0 05
WR.6.
X
(2)
< b/:
+ P (sgn
((w", x)) ) * sgn ((We,),)) [e)
C10
C11
2n)
C10
S1bb +
2
2
2
where C11 0 is a positive constant. The first incquality holds by the triangular inequality, the last inequality holds by Lemma @ property (a) and (b), and Proposition !!
Summing (577) and (5 over [Tk], and then we can upper bound (5G) by
Tc
E Rega (h; T))
Σ
0(1)
+ +(1) 1 27
2
2
1=1
Tg
(1 11-211 -2
=0(
+ 0(1)
2
24
0
(1-21) (7 + 1 1)d In d(In dd
Since T = |Tral + |TEEl and (Trel = O(d d(In T)2), then |TEE = 0(7). Also, the exploration-exploittion phase corresponds to all cycles run in Algorithm EL hence 2 > Tk
[TEE (T). By Ta 400
(1-2))((7 (7 + 1)d In d(In we get the total number of batches
as K log, (o I) d(In 7y² )) Then, can upper bound the cumulative regret during the explorationeexploitaion phase under "clean event" as
(1-2n))T
K
Reg((:: TEE. $)
Σ
E Rega (h; TEE,E)
log. (0
2n [r+1)d diin mo2
( (1 (1- 2n) (7 1)dn (59)
Σ
2º
1
0 ((1
v (7 1)d
24)3
Finally, we upper bound the third term in (544 as
E Reg
h: (TTEEEE)
E
(Err(he) Err(h*) I())
TET
(60)
Σ I()) = |TEE (()) ST 7 6
<
LeTRR
By combining the upper bounds of (55)), (59), and (60), we finish the proof.
A.7 Proofs for Appendix A.I
Before proving Lemma & we need to first prove some intermediate lemmas. the following lemma, we show that any log-concave distributed random vector with zero mean and positive definite covari- ance matrix can be linearly transformed into a new random vector with an isotropic log-concave distribution.
52

---

Lemma 24. For any random vector x E B that follows log-concave distribution with E2 [x] 0 and IE xxx" E, where E is positive definite, the transformed random vector Σ xx that follows an isotropic log-concave distribution.
Proof. We first prove that -ースx is isotropic. Since E [xx"] Σ, E is positive definite,
then E
zz Σ
E
xx"
I =
I. Also, since E [x]
0, then
2
Next, we show that the probability density function of is log-concave. Suppose the corresponding probability density functions of x and are Φx (-) are the (.), respectively. Since Φx (+) is log- concave, then for V a E [0, 1] and X1, X2 Rd
ln (0x (x1)) (1 a) (xx (x2) S In (ox (ax) + (1 x2))
Then, for Y E [0, 11 Z1, 22 E Rdd
In ((oz (z)) ))) (1 a) (l0z (z2)))
an det [ Øx (Eiz)) + a) in dot (Σ3 dx (I
(x (2t21) + (1 - a)ln In (ox (I + In del [33
+x (a (1 a) )>>>))))) + In (det (Σ1) )>:))
In
In (Øz (az) (1 a) z2))
Thus, Φz(-) is isotropic log-concave.
The next lemma outlines the relationship between the eigenvalues the covariance matrices for nigh-ddmensional random variable before and after is projected onto lower-dimensional subspace.
Lemma 25. Let x be an arbitrary d-dimensional random variable with a positive definite covari- matrix E, whose maximum and minimum eigenvalues are X and respectively. Let Ve arbitrary d' d'-dimensional subspace with d' S d. Let XVy denote the projection of x onto Vo with covariance matrix IV whose maximum and minimum eigenvalues are AV. and Xv. respectively. Then, Avg. S. X and Av. 2 A.
Proof. Let P E Iddxd denote the projection matrix of x, i.e., prP and p = XV then, Σv = PP.P. Hence, by definition maximum eigenvalue, we have
TT EV VTV V
TPTTPP
ĀVG. = max
vz0. vERd
max vęO VERA
VT'v u T n u1
TTEP
X.
max v20, veRd
Pv
o uERd
where u = Pv.
Ev,, v VTV v TPTTPP
T PP'
A = min
min
v, veRd"
v40 veRd"
VTV
n TE
min
min
X.
vy0, veRd vT PT
O ugRd
u u
where u Pv.
Now are ready to prove Lemma
53

---

Lemma 3. Let x E R (d 2 2) have zero mean and log-cono aogccceaaee distribution. Suppose the eigenvalues of its covariance matrix = E [xx] are all bounded within (2, x) for some positive
constants 2. X, then the distribution of satisfies the regularity conditions in assumption D. with [2(2]
parameters L1- (1 (1),,, (2), given in Lemma P
v3 L2 B1 (2) R V U1
1 U2
8 9s(21
VX Q for
V2
Proof for Lemma E For arbitrary 1-dimensional subspace Ví C RR and 2-dimensional subspace V22 C IR², let XV; and X12 denote the projected vectors on V1 and 122 with covariance matrices Ey; and Vvg, respectively. Let λv, and λv, denote the maximum cigenvalues of Σv, Ev, and λy, and Av, denote the minimum eigenvalues of Dv, VV,,, respectively. Then by Lemma 25 we have
Z \v. À Xv2, À S 2v, and À S Av. Let Let zv, L XV,, zv, 2 Xv2 Then, Zv, and 2V; have isotropic log-concave densities, denoted as Øzn and &ev,, respectively.
We first determine L1, L2 and R prescribed in Assumption D1 Condition 1. For all | S AV.. XV, probability density function Oxv, (.) satisfies
xxv, (xvi) = Oov, (2v. xv,) det (Im²)
{1)
(1
2
2
(61)
Av
Vx
|inn xv |
Now
||zvi l|
||xvi ll2 S
Then, the first inequality in
Vav,
VA
(2
(6Il) holds by Lemma D. property (b) and det
2
The second inequality holds by
Lemma A
Similarly, for all || 112 S /X, Xv, probability density function (-v( satisfies
@x13 (xv;) = Φavz (2ivz xvxx) det (2:7))
(2) (2
2
2 X
(62)
Av:
Now | 112 = 2v2 XV2 112 S V2vz
||xvalla S
Then, the first inequality in (bx)
VA
g
holds by Lemma E property (b) and det
(21))) 2
The second inequality holds by Lemma 25
Av2
Combining (6ll and (62), we have L1
(1(1) vX
L = 8:(2) R= JVA
Then, we determine UI, U2 and 8 prescribed in Assumption E Condition 2. For dxv, ()), we have
Φxv, (xv, Oev, (x xvi) det (zvz)) S VAn
1
S Vx*
where the first the inequality holds by Lemma A property (c) and det (2Tz²) S
The second
72n
inequality holds by Lemma 25 Thus, U1 1 Vx For Φxvg (.), we have
Vin XV2 11)
(2()) exp
-Ba(2)
Φxng (Xv3) = Dave (Iiz' xvs) det (215)) 5
Av,
(2) exp
(x(2) ||xva112
VXvg
Av,
(2( exp
8a(22)
||xvi
VX
where the first inequality holds by Lemma A property (d) and det
(MTg))
The second
inequality holds by /
2 1 |xx,, llg The last inequality holds by Lemma 25
XV2
Avz
54

---

Thus, we have U2
P2(2) 8 8a(21
Finally, we determine Q prescribed in Assumption RL Condition For arbitrary w E B4, (w, x) forms a 1-dimensional random variable whose probability density function is log-concave. Let XV{ = (w, x) denote the projected random variable and of = E x Xvi
denote its variance.
Then, by Lemma 2 property (a), for every
P( >) Se v Se Va+1, where the second inequality holds by oz 2 Av 2 A. Thus Q Vx.
55


Reviews:
[{"review_id": "P3P3E1IbOT", "reviewer": "Reviewer_Q4JY", "summary": "They study online strategic classification(SC) with massart noise and a partial feedback model (only receive feedback when the example is labeled as positive). In online strategic classification, in each round the principal deploys a classifier and then an agent in round $t$ arrives. The agent with feature set $x$ best-responds to the deployed classifier in order to maximize their utility, that is the classification that they receive in their manipulated state $x'$ minus the cost of manipulation, i.e., movement from $x$ to $x'$. Usually in SC, the true label is revealed after the principal announces their classification based on the deployed classifier; however, here they assume partial feedback, that is the true label is only revealed if the agent is classified as positive. For example, if a student is admitted in the college, after that the principal would see if her decision was good or not (the student was actually a positive  example (good student) or not.)\n\n Massart noise is when the actual label of the points are flipped with some feature-dependent probability $\\eta(x)$, where all values $\\eta(x)$ are bounded (at most $\\eta\\leq 1/2$). Some of the previous work in SC assumes the clean examples( before manipulation) are linearly separable, the Massart noise relaxes this assumption and considers the scenario where most of the points are linearly separable.\n\nThey show sublinear regret in the setting of online SC+Massart Noise+partial feedback. Their techniques are mostly a generalization of Zheng et al.2020 to a strategic setting. There are three steps in their algorithm: initialization, refinement, and batch contrastive inference step. In each step, they find a linear classifier $w$ that gets closer to the opt classifier $w^*$. (lines 206-217 do a great job of summarizing these steps.)\n\nI think the main difference with Zheng et al is in the last step of batched enhancement, where they solve a sequence of adaptively constructed online linear optimization problems to refine the reported classifier $w$. Here, they need to estimate the gradients $g_{k,i}$ (you need to define what $g_{k,i}$ is, I didn't find its definition.) However, these gradients depend on the true features, but all agents in the localized regions D_{k,i} misreport their features. So, here they need to use proxy features and estimate the true location of the agents by projecting the reported feature set to the upper or lower boundary of $D_{k,i}$. They would argue that using these proxy features, the gradients will be well-constructed and hence they would converge to the optimal $w^*$ after bounded number of iterations.[This proxy feature construction is a trick also used in earlier work in online SC.]", "questions": "Line 168, why do you need the multiplicative factor of 2?\n\nI don’t understand lines 218-220. What is the relationship between batches, indices and t?\n\nTrying to understand lines 232-245, in the first paragraph, it says that you are considering the band above the classifier where the points have no incentive to move. Then in the second paragraph, it says there are challenges due to the strategic nature of the points. Could you please clarify? It seems a bit contradictory.\n\n\nIn line 6 in Alg 2, perhaps you can add an explanation on how you construct w_0?", "limitations": "yes, no potential negative societal impact", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I appreciate the write-up and technical details of the paper. In my opinion, this is mostly a combination of the techniques from Zheng et al 2020 on learning half-spaces under label noise and the techniques from Ahmadi et al. on online learning with strategic input, where they use proxy features to update their linear classifiers. They employ a similar idea to adapt the algorithm by Zheng et al. to a SC setting. I have explained this in detail in the summary. Please correct me if I am wrong.", "was_revised": true, "final_justification": "The rebuttal has addressed some of my concerns and I decided to raise my score from 4 to 5.", "rebuttal": "We appreciate that you like our write-up and technical details. We provide our feedback as follows.\n- Comparison with Zhang et al. (2020) and Ahmadi et al. (2021):\n\nWhile both Zhang et al. (2020) and Ahmadi et al. (2021) inspire separate components of our algorithm, we hope to clarify that our work considers a  fundamentally different setting. In particular, naively extending the algorithms in those papers cannot resolve the challenges unique to our setting. \n\nZhang et al. (2020) propose an algorithm to learn halfspace under Massart noise with full feedback, without strategic manipulation. According to Zhang et al. (2020), under a noisy setting, data points near the classification  hyperplane are the most informative for learning the classifier.  Therefore, they utilize a key technique, known as “localization”, that uses only data within a small band near the classification  hyperplane. However, our problem involves agents' strategic manipulation. If we ignore the strategic manipulation from agents and naively adopt Zhang et al. (2020)'s method to announce classification hyperplanes, then agents whose true feature resides near the announced classifier, qualified or not, will strategically misreport their feature to be positively classified.  In particular, the unqualified agents who get positively classified through strategic manipulation lead to high regret.\n\nAhmadi et al. (2021), on the other hand, investigate the problem of linear classification under agents' strategic manipulations with full feedback. Compared with their setting, ours involves Massart noise and partial feedback. If we directly extend Ahmadi et al. (2021)’s method to address agents' strategic manipulations by elevating the classification hyperplane parallelly by $\\gamma$, then all agents with true features within $\\gamma$ distance below the announced classification  hyperplane will strategically manipulate their features onto the classification hyperplane (see Figure 1(a) in our paper). These manipulating agents consist of both agents whose true features are within the localization band and agents whose true features are outside the band, and their reported features all lie on classification hyperplane. So it is difficult to tell whose true features are indeed within the localization band. This poses significant challenges to applying the localization technique.\n\nIn short, the joint consideration of label noise, agents' strategic manipulation behavior, and partial feedback introduces challenges that are not present in the existing literature. Our key contribution consists of a novel contrastive inference method with proxy features to address these non-trivial challenges. By declaring two parallel but slightly different classification hyperplanes and comparing agent responses under these two classifiers, we can simultaneously make  inferences about true features within the localization band and largely discourage the unqualified agents from feature manipulation. This idea is unique and novel and has not been considered by the previous works. \n\n- The definition of the gradient:\n\n We will follow your suggestion and add an explicit definition of the gradient $g_{k,i}$. It is derived from the gradient of Leaky-ReLU loss function, which is defined as $ \\text{ LeakyRelu } _ { \\bar\\eta }(-y\\langle{w},{x}\\rangle) $, where $ \\text{LeakyRelu} _ {\\bar\\eta}(z)=(1-\\eta)z\\mathbb{I}({z\\ge 0})+\\eta z\\mathbb{I}({z<0}) $. Specifically, $ \\mathbf{g} _ {k, i}=[-\\bar{\\eta} \\mathbf{x} _ {k, i} \\mathbb{I}\\left(y _ {k, i}=1\\right)+(1-\\bar{\\eta}) \\mathbf{x} _ {k, i} \\mathbb{I}\\left(y _ {k, i}=-1\\right)] \\mathbb{I}\\left(\\mathbf{x} _ {k, i} \\in D _ {k, i}\\right) $ as we defined in Lines 270-271.\n   In our previous submission, we only briefly mentioned the loss function in a footnote, without giving its formal definition. This is because it did not appear in our subsequent theoretical analysis. \n   Instead, all of our analyses are based on the linear formulation in terms of the gradients. \n   Take the refinement stage as an example. The theoretical analyses thereof involve upper bounding $\\sum_{i=1}^{T_k}\\langle w_{0, i},g_{0,i}\\rangle - \\sum_{i=1}^{T_k}\\langle w^\\star,g_{0,i}\\rangle$, lower bounding $\\sum_{i=1}^{T_k}\\langle w_{0, i},g_{0,i}\\rangle$ and relating $ \\langle w^\\star,-g_{0,i}\\rangle$ to the angle between $w_{0, i}$ and $w^\\star$. These only need to leverage the form of $g_{0, i}$, without regard to its connection to the Leaky-ReLU loss.\n\n- The reason for requiring the multiplication factor of 2:\n\nConsider a general manipulation cost $c\\|x-r\\|_2$ for a generic constant $c$, where $x$ and $r$ are true and reported features, respectively. Note that the payoff that an agent can gain from the classification outcome is either $+1$ or $-1$, so the  manipulation distance $\\|x-r\\|_2$ is at most $2/c$. For notation simplicity, we set $\\gamma = 2/c$ as the largest manipulation distance, leading to $c = 2/\\gamma$. This is the source of the multiplication factor $2$. \n\n- The relationship between batches, indices and the global time $t$:\n\nWe partition the horizon of $T$ cycles into consecutive batches indexed by $k \\in \\{\\text{init}, 0,1,2,\\cdots,K\\}$. Batch $k$ has $T_k$ iterations indexed by $i\\in \\{1,2,\\cdots,T_k\\}$, where each iteration $i$ contains one or two cycles and performs only one gradient estimate followed by a single parameter update. The superscript $j= 1 \\text{ or } 2$ distinguishes the two cycles inside the same iteration during Initialization and Enhancement. During Refinement, each iteration issues only one cycle. To map any $(k,i,j)$ to the global time-step $t$, we use the closed-form formula $t = 2(i-1)+j $, if $k=\\text{init}$; $t = 2T _ {\\text{init}}+I$, if $k=0$; $t = 2T _ {\\text{init}}+T _ 0+2\\sum _ {k'=1}^{k-1}T _ {k'}+2(i-1)+j$, if $k \\in \\{1,2,\\cdots, K\\}$.\n\nWith this mapping, every variable indexed by $(k, i, j)$ can be immediately translated to its corresponding global time $t$. \n\n- Explanation for lines 232–245:\n\nThese two sentences are indeed a bit confusing. Let us clarify here. \nIn our Refinement algorithm, we set the classification hyperplane as if there is no feature manipulation ($\\tilde h_{0,i}(r)=\\text{sgn}(\\langle w_{0,i},r\\rangle)$). Then, agents with true features above the hyperplane are already classified as positive, so they have no incentive to manipulate their features ($x_{0,i}=r_{0,i}$). \nIn other words, we can directly observe the true features of agents within the localization region ($\\{x|\\ 0<\\langle w_{0,i}, x_{0,i}\\rangle\\le b_0\\}$). This is the “band with no manipulation” mentioned in the first paragraph. In contrast, agents with true features within $\\gamma$ distance below the hyperplane ($\\{x| -\\gamma\\le\\langle w_{0,i},x_{0,i} \\rangle < 0 \\}$) do have an incentive to project their features onto the hyperplane and report the projections. These are the “strategic” agents that cause high instantaneous regret during the Refinement phase. Indeed, with this, we can still run the localization approach as usual following Zhang et al. (2020) and refine the coefficient estimate, while bearing the cost of misclassifying unqualified agents. In the camera-ready version, we will remove the sentence \"Nonetheless, strategic feature manipulation and partial label ... challenges to the localization approach\" in the second paragraph to avoid confusion. \nFurthermore, to control the regret, we limit the length of Refinement phase to only $\\tilde O(\\ln T)$ cycles. For the rest of the decision horizon, we have to balance the need to update classifiers using data with true features within the localization region and the need to prevent high regrets due to unqualified agents' strategic manipulation. This is achieved by our novel Enhancement algorithm based on proxy features and pairwise contrastive inference.\n\n- Explanation for the construction of $\\bar w_0$: \n\nWe apologize that there is actually a typo in Line 6, Algorithm. The correct expression should be $$\\bar w_0=\\frac{1}{T_{\\text{init}}}\\sum_{i=1}^{T_{\\text{init}}}\\sum_{j=1}^{2}r_{\\text{init},i}^{(j)}y_{\\text{init},i}^{(j)}\\mathbb{I}\\left((-1)^{(j-1)}\\langle{w_{\\text{init},i}}{r_{\\text{init},i}^{(j)}}\\rangle>0\\right) \\ .$$ \nLet us explain the intuition for this construction. In the non-strategic, noiseless and full feedback case, $y\\langle{w^\\star},{x}\\rangle = \\langle{w^\\star},y{x}\\rangle>0$ for all $(x,y)$, so $yx $ always forms an acute angle with the optimal normal vector $w^\\star$. Analogously, under the noisy feedback setting, we should have $\\langle w^\\star, \\mathbb{E}[yx]\\rangle > 0$ so $\\mathbb{E}[yx]$ forms an acute angle with $w^\\star$. \nNow, consider our strategic  and partial-feedback setting. When we declare a classifier $\\tilde h (r)=\\text{sgn}(\\langle w,r\\rangle)$, agents whose true features are originally above the hyperplane ($\\langle w,x\\rangle>0$) have no incentive to manipulate their feature and will report truthfully ($r=x$), then $yr$ is exactly $yx$. Therefore, $r_{\\text{init},i}^{(1)}y_{\\text{init},i}^{(1)}\\mathbb{I}\\left(\\langle{w_{\\text{init},i}}{r_{\\text{init},i}^{(1)}}\\rangle>0\\right)+r_{\\text{init},i}^{(2)}y_{\\text{init},i}^{(2)}\\mathbb{I}\\left(\\langle{-w_{\\text{init},i}}{r_{\\text{init},i}^{(2)}}\\rangle>0\\right)=x_{\\text{init},i}^{(1)}y_{\\text{init},i}^{(1)}\\mathbb{I}\\left(\\langle{w_{\\text{init},i}}{x_{\\text{init},i}^{(1)}}\\rangle>0\\right)+x_{\\text{init},i}^{(2)}y_{\\text{init},i}^{(2)}\\mathbb{I}\\left(\\langle{-w_{\\text{init},i}}{x_{\\text{init},i}^{(2)}}\\rangle>0\\right)$ provides information for $\\mathbb{E}[yx]$. By averaging them over the $T_{\\text{init}}$ cycles, we get the estimator $\\bar{w} _ 0$ that well approximates $\\mathbb{E}[xy]$. So we expect that $\\bar{w} _ 0$ forms an acute angle with $ w^\\star $ with high probability if $T_{\\text{init}}$ is large enough. \n\nThank you again for your comments. We will incorporate our discussions into the camera-ready version to clarify the issues you raise."}, {"review_id": "e5bagLxM9Y", "reviewer": "Reviewer_SBKe", "summary": "This paper explores binary classification in a strategic online setting, where a classifier must immediately label incoming agents. Crucially, it receives noisy feedback only for positively classified agents (\"apple tasting\"). The feature-label relationship uses a linear half-space model with bounded noise, and the classifier aims to minimize regret against the best fixed omniscient classifier.\n\nFollowing prior work, the authors first show that for half-spaces, agents' best responses can be characterized, proving that an omniscient classifier yields identical outputs whether features are true or manipulated.\n\nThey then propose a three-component algorithm. First, an \"exploration\" subroutine uses contrasting classifiers to find an initial normal vector close to the optimal one. Second, a \"localization\" subroutine refines this vector by focusing on informative data near the classifier's boundary, where true features are observable due to no manipulation incentives. Despite new complications from strategic reporting, they solve an online linear optimization problem using techniques akin to learning with label noise, achieving only logarithmic regret in this phase.\n\nThe third and most novel component tackles strategic manipulation in this refined localization. As manipulable classifiers lead to high regret from misreporting, they introduce a modified classifier that sets a higher bar for positive classification. To address the unobservability of true features in key regions, they develop proxy features to mimic true ones for gradient construction, and pairwise contrastive inference. The latter uses two successive classifiers to statistically infer information about unobservable true data in critical localized regions, and which in turn enables estimation of gradients.", "questions": "If I understand correctly, our results hold for a sequence of myopic buyers. I am wondering whether you had some thoughts regarding a repeated game where a single agent aims to maximize the sum of positively classified points (over cycles). I guess that this can be modeled as a Stackelberg game and that it is also a consideration for the model without noise and with two-sided feedback.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper tackles a tougher version of online strategic classification, to accommodate partial, noisy feedback. A key and novel strength of the paper is the development of pairwise contrastive inference to address strategic reporting from the agents. In particular, by employing two slightly different classifiers in succession and contrasting the observed data from each, they cleverly infer statistical information about the true, unobservable features in critical regions. Moreover, the integration of proxy features, designed to mimic true features from reported ones, further strengthens their approach by allowing the construction of effective proxy gradients. In general, I appreciated the technical novelty the authors developed in this paper.\n\nEven the “localization” procedure, which has already been developed for the non-strategic counterpart of the problem, is here devised in a clever way. Namely, it handles strategic interaction via an instantiation of Online Mirror Descent and suffers only logarithmic regret.\n\nThe exposition is clear and, despite its technical depth, the treatment maintains conceptual clarity at all points of the main body. The authors explicitly explain what the algorithm subroutines are needed for, and where each piece of the analysis comes into play.\n\nOverall, the contributions and presentation are strong, novel and well-conveyed. The authors design a single algorithm that simultaneously handles strategic feature reports and partial, noisy feedback, suffering $\\sqrt{T}$ regret, essentially providing conclusive answers for the analyzed setting.\n\nThere is a typo in line 168: inccurs —> incurs.", "was_revised": true, "final_justification": "Thank you for the response to all of my questions and comments. They explain everything I asked clearly and made me understand even better where the additional challenges in future work lie. I, thus, confirm my score.", "rebuttal": "We are grateful that you find our contributions and presentation ''strong, novel and well-conveyed''. We also sincerely thank you for your thought-provoking question. Our response is as follows.\n\n- Repeated games with a single and non-myopic agent:\n\nOur work indeed focuses on a sequence of myopic agents, who always follow the best response to the declared classifier. Specifically, agents with true features within $\\gamma$ distance below the classification hyperplane will project their true features onto the hyperplane as their reported feature, while other agents will report truthfully (Lemma 1). Our algorithm heavily leverages the structure of this best response, both in the proxy feature construction and pairwise contrastive inference. The learning problem becomes much more difficult when the principal repeatedly interacts with the same agent. This is because the agent may have complicated forward-looking behaviors that drastically deviate from the myopic best response described in our Lemma 1. In particular, the agent may report features that do not appear immediately optimal to mislead the principal's learning algorithm, thereby securing future advantages. Under the noisy setting, the agents' feature manipulation direction may be even opposite to the myopic optimal direction, slowing down the learning of the optimal classifier. While one may model the agent's behaviors by a dynamic programming (DP) model, analyzing the DP model and developing effective learning algorithms appear much more challenging. This is a totally different but very interesting problem that warrants future study.\n\n- We also thank you for pointing out our typo. We have corrected it in our paper."}, {"review_id": "ojFbgZnYRj", "reviewer": "Reviewer_pYbv", "summary": "The paper studies online binary linear classification when agents strategically manipulate their features to achieve positive prediction at quadratic cost, and the learner only sees labels of positively classified agents. The authors assume that the true feature-label relationship is a halfspace model subject to arbitrary but bounded (Massart) noise. Additionally, the distribution of features is assumed to satisfy regularity conditions for 1-dimensional and 2-dimensional projections, including lower and upper density bounds and a sub-exponential tail bound for the inner product of features with any unit vector. This assumption appears in prior works on learning halfspaces with noise.\n\nThe proposed algorithm consists of three phases: initialization, refinement, and batched enhancement, utilizing proxy features and pairwise contrastive inference. A regret bound of $\\tilde O(\\sqrt T​)$ is provided. Numerical experiments support these theoretical findings.", "questions": "1. Do you have any intuition for how your algorithm or regret bounds might change under other noise settings?\n2. Do you have an idea on how to extend the partial feedback setting to more complex classes, e.g., finite VC classes (even without noise)?\n3. Are there any guarantees if the budget parameter $\\gamma$ is unknown or must be estimated online?\n4. Any guarantees on more general cost functions (e.g., linear, or other convex costs)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\n- The problem addressed, online strategic classification with partial feedback, is interesting.\n- The inclusion of Massart noise makes a great addition, and demonstrates the generality of the algorithm.\n- The way the paper handles the challenges of strategic feature manipulation, partial feedback, and label noise is a central contribution. The specific techniques used, constructing proxy features and using pairwise contrastive inference, are novel aspects of their proposed algorithm.  In particular, for gradient estimation without true features, gradient estimates over bands around the boundary are needed. Yet, agents in those bands misreport, so the authors (i) construct proxy feature points from the reports and (ii) use pairwise contrastive inference with two shifted classifiers to unbias these estimates.\n- The paper is well-written.\n\n*Weaknesses* \n- Usually, in online strategic classification, adversarial settings are considered, whereas this paper makes some distributional assumptions. That said, this setting is also interesting.\n- Only quadratic cost is considered.\n\n*Comments*\n- The paper mentions [Ahmadi et al., 2023, 2024], but it does not mention a closely related work by Cohen et al. 2024 [1], which is chronologically \"in between\", nor a more recent, subsequent relevant work by Shao et al. 2025 [2].\n- The paper provides overviews and discussions of the Initialization, Refinement, and Batched Enhancement algorithms. However, I suggest that the authors provide even more discussion about them, particularly given the complexity of the methods. \n\n\n[1] Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Learnability gaps of strategic classification. COLT 2024.\n\n[2] Han Shao, Shuo Xie, Kunhe Yang. Should Decision-Makers Reveal Classifiers in Online Strategic Classification? ICML 2025.", "was_revised": true, "final_justification": "I have read the rebuttal and still think the paper should be accepted.", "rebuttal": "We are grateful that you find our work interesting, novel and well-written. We also sincerely thank you for your insightful questions. We provide our feedback as follows.\n\n- Citations: \n\n Thank you for providing the two related papers. We will add these two papers to our ''Related Literature'' section.\n\n- More discussions on each algorithm:\n\n We agree that we should add more discussions on the algorithms. Due to space constraints, we provide our explanations for the significance of each sub-algorithm in the answers to Reviewer SQmo, and plan to update our manuscript accordingly.\n\n- Intuitions for how the algorithm and bound will change under other noises:\n\nHere we provide some thoughts on online strategic classification under adversarial noise (the nature confines the overall error rate of the `best' halfspace to be at most $\\bar\\eta$, but samples may not necessarily be i.i.d.) and malicious noise (the nature randomly draws an instance from the underlying feature-label distribution with a fixed probability $1-\\bar\\eta$ while returning an arbitrary feature-label pair with probability $\\bar\\eta$). We conjecture we could tackle these noises again based on our proposed idea of localization, proxy feature and contrastive inference, with a slight difference in the design of loss function and the gradient. Their regret bounds are also expected to be similar to ours. \n\nHere is our rough intuition. Shen (2021, 2023)\nadapts the algorithm in Zhang et al. (2020) to learning halfspaces under these alternative types of noises (in non-strategic and full-feedback setting).\nThe resulting algorithms again use online mirror descents with \"localization\" and their theoretical guarantees under these alternative noises are similar to that in Zhang et al. (2020) under Massart noise. Moreover, the type of noise does not appear to influence our construction of proxy features and contrastive inference. Therefore, we conjecture that we can adapt our algorithm to these alternative noises while attaining similar theoretical guarantees. We leave this extension for future study. \n\n- Extending the partial feedback setting to more complex classes:\n\nIn our setting, we use the contrastive inference method to tackle the partial feedback setting. By contrasting positively-classified agents' responses under two slightly different classifiers, we can fine-tune our classifier and simultaneously maintain a relatively high accuracy of our declared classifiers. However, this method relies on the clear characterization of agents' best responses and a gradient-based optimization algorithm to update the classifier, both of which depend on the linear structure of classifiers. When adapting to more general settings, it may be hard to characterize the agent's strategic manipulation and directions for updating the classifiers in a closed form.  These challenges may prevent us from directly extending our setting to more complex classes.\n   \n  In addition, as you noted, online strategic classification problems within finite VC classes are typically examined under adversarial settings with full feedback. In particular, their approaches often involve discretizing the  hypothesis class into multiple experts and then implementing a weighted-majority voting scheme across these experts (see, e.g., Ahmadi et al., 2024; Cohen et al., 2024). However, this cannot be extended to partial label observation setting, either. Specifically, in the adversarial setting with partial feedback, nature can hurt the principal's learning algorithm by keeping generating agent examples that will be classified as negative. This time the principal will never observe the agents' true label due to partial observation, and thus has no chance to update the classifier. \n\n- Setting with unknown budget $\\gamma$: \n\nIn our paper we consider the setting that the manipulation budget (or manipulation radius/maximum manipulation distance) $\\gamma$ is known, which is a common practice in the literature (Chen et al. (2020), Shen et al. (2024)). However, considering unknown $\\gamma$ is a quite interesting direction of  future study. Ahmadi et al. (2021) proposed a strategic perceptron algorithm with unknown manipulation budget. Their key idea is running a binary search to find a proper estimate on this budget. However, this idea relies heavily on their assumption that the positive and negative classes are strictly separated by a margin without any noise. Their algorithm design requires either knowing the value of margin having an estimation process on it. These requirements cannot be fulfilled in the noisy setting without any margin. Therefore, it is hard to extend their binary search approach to our setting with unknown $\\gamma$.\n\n- Guarantees on more general cost functions:\n\nOur work can be easily adapted to any norm-formed manipulation cost with the regret guarantee unchanged. The way for adaptation is similar to that by Shen et al. (2024). In this setting, given a classifier $\\tilde h(r)=\\text{sgn}(\\langle w,r\\rangle+m)$ and agent manipulation cost $\\text{Cost}(x,r)=\\frac{2}{\\gamma}\\|x-r\\|$ for any norm $\\|\\cdot\\|$, an agent with true feature $x$ will report $r^\\star(x,\\tilde h)$ that satisfies  $r ^ \\star (x , \\tilde h ) = x -\\frac { \\langle w , x \\rangle+m } { \\|w\\| _ \\star } v(w) $ if \n$-\\gamma\\|w\\| _ * \\le \\langle w , x \\rangle + m < 0 $; and otherwise, $r ^ \\star (x , \\tilde h ) = x$,  where $ \\|\\cdot\\| _ * $ denotes the dual norm of $\\|\\cdot\\|$, and $v(w)\\in \\arg \\max_{\\|v\\|\\le 1}\\langle w,v\\rangle$. From the above expression we know that when extending the $\\ell _ 2 $ norm cost to general norm cost, the key modification is changing agents' manipulation direction (from $w$ under $\\ell_2$ norm  to $v(w) / \\|w\\| _ * $ under general norm) and converting the distance under the general norm to that under $\\ell_2$ norm (multiplying a $\\|w\\|_*$ factor on the general norm-based distance). Therefore, when designing proxy features and contrastive inference, we can accordingly change the projection direction and adjust the offset. These modifications do not change our key idea of algorithm design. \n\n- The title: \n\nOur final title is \"Online Strategic Classification with Noise and Partial Feedback\". We will finalize this in our camera-ready version.\n\nThanks for your interesting questions about potential extensions of our work. We will add these as our future work direction to the manuscript.\n\nShen, J. (2021). On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In International Conference on Machine Learning (pp. 9503-9514). PMLR.\n\nShen, J. (2023). PAC learning of halfspaces with malicious noise in nearly linear time. In International Conference on Artificial Intelligence and Statistics (pp. 30-46). PMLR.\n\nZhang, C., Shen, J., & Awasthi, P. (2020). Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33, 7184-7197.\n\nAhmadi, S., Yang, K., & Zhang, H. (2024). Strategic littlestone dimension: Improved bounds on online strategic classification. Advances in Neural Information Processing Systems, 37, 101696-101724.\n\nCohen, L., Mansour, Y., Moran, S., & Shao, H. (2024). Learnability gaps of strategic classification. In The Thirty Seventh Annual Conference on Learning Theory (pp. 1223-1259). PMLR.\n\nChen, Y., Liu, Y., & Podimata, C. (2020). Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 15265-15276.\n\nShen, L., Ho-Nguyen, N., Giang-Tran, K. H., & Kılınç-Karzan, F. (2024). Mistake, manipulation and margin guarantees in online strategic classification. arXiv preprint arXiv:2403.18176.\n\nAhmadi, S., Beyhaghi, H., Blum, A., & Naggita, K. (2021). The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation (pp. 6-25)."}, {"review_id": "DpWLLowtf2", "reviewer": "Reviewer_SQmo", "summary": "This paper considers the strategic classification model with following extension: candidates arrive online and the principal only observes the manipulated features and the label only if the candidate was classified positively. Candidate features originate from an unknown distribution and are not exactly separable by a linear hyperplane - rather, the labels can be noisy wrt to the plane (Massert noise that is correlated with features). Like other works in the online strategic setting [Chen, 2020], they assume agents can manipulate within some radius. The key departure from existing online model is the observability of the labels conditioned on acceptance.\n\nThe key technical contribution of the work is providing an online algorithm that achieves $\\sqrt{T}$ regret with respect to the offline optimal, which can be informally characterized as shifting the optimal non-strategic classifier by the width of the manipulation radius. The algorithm composed of three parts: an initialization phase where the principal positively classifies both sides of the plane (on every other step) to collect data. A refinement stage that explores a boundary near the initialization phase - both of these can incur large regret and thus runs for log(T) time. Lastly, the large part of the algo runs where the enhancement is over batches and proxy features are used to approximate the gradient (in lieu of costly exploration).", "questions": "- Do you have any thoughts on the setting where each agent's manipulation radius $\\gamma$ is different? So one can either think of this as being an unknown (perhaps too hard) or belonging to some range. I know prior literature also makes this assumption -- so not a major criticism -- but I am curious about it since afaik the clairvoyant classifier in this setting can no longer be easily characterized.\n\n- Could you explain why in the refinement stage, why we need to consider strategic manipulation and form a linear optimization problem. My understanding is that we set a threshold b and agents within b margin (according to true features) of the current classifier are positively classified. Can this not be achieved by shifting the boundary by \\gamma?", "limitations": "I don't see any negative social impact of this work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "With strategic classification paper, I find the model to be crucial and I find the model here to be fairly reasonable and well justified. Indeed in many settings only positive labels are observed for their true label. While this is the main difference from existing works, I don't think it's a negative as it does lead to a meaningful/challenging problem. I also found the paper to be focused in answering the crucial question of sub-linear regret. Overall, I think it's a good paper.\n\nMy main criticism would be in the exposition of the paper - especially in the theory section. For example, in the initialization part of the algorithm, it is not clear what the significance of the acute angle perspective is. Some diagrams or high-level description of the main ideas would help for the first and second components of the algorithm.", "was_revised": true, "final_justification": "I had a positive view of this work and the author rebuttal maintained this perspective.", "rebuttal": "We sincerely thank you for finding our model crucial, reasonable and well-justified and acknowledging that our paper is good. We also appreciate your thoughtful comments. We provide our feedback as follows.\n\n- Explanation for the significance of each algorithm:\n\nWe agree that we should explain the sub-algorithms in more detail. Here let us provide further explanations for the significance of each sub-algorithm below, which we also plan to add to our manuscript. \n\nInitialization Algorithm. The Initialization Algorithm aims to output an initial vector $\\bar w_0$ such that the inner product of $\\bar w_0$ and the coefficient vector of the optimal classifier $w^\\star$ is lower bounded by a positive constant ($\\langle w^\\star, \\bar w_0 \\rangle\\ge c_1(1-2\\bar\\eta)>0$) with high probability (notably, we want to clarify that the angle between $\\bar w_0$ and $w^\\star$ should be strictly less than $\\pi/2$, not just less than or equal to $\\pi/2$). This guarantee is crucial for the subsequent Refinement stage. The Refinement Algorithm relies on the localization technique, which in turn requires that the hyperplane deployed in every round remains close to the optimal one. However, since $w^\\star$ is actually unavailable, for each coefficient vector $w_{0,i}$ in Refinement, we cannot measure $\\langle w^\\star , w_{0,i}\\rangle$ directly. Instead, we constrain every $w_{0,i}$ to lie in the set $\\mathcal{K}_0 = \\{w|\\ \\langle w, \\bar w_0 \\rangle\\ge c_1(1-2\\bar\\eta)\\}$, which, by construction, contains $w^\\star$ with high probability. Thus, every hyperplane used in Refinement remains provably close to the optimal one, enabling effective localization without ever seeing $w^\\star$.\n\nRefinement Algorithm. The Refinement Algorithm aims to output a vector $w_1$ such that the angle between $w_1$ and the coefficient vector of the optimal classifier $w^\\star$ is less than or equal to $\\pi/4$ with high probability. This guarantee is important for the subsequent Enhancement stage. The Enhancement Algorithm relies on the effective construction of proxy features, which in turn requires that the angle between the coefficient vectors $w_{k,i}$ deployed in each iteration always forms an acute angle with $w^\\star$ ($\\theta(w_{k,i},w^\\star)\\le \\pi/2$). Still, since $w^\\star$ is actually unavailable, we cannot directly measure $\\theta(w_{1,i},w^\\star)$ in batch 1. Instead, we constrain every $w_{1,i}$ to lie in the set $\\mathcal{K} _ 1 = \\{ w |\\ \\langle w,  w _ 1 \\rangle \\ge \\cos (\\pi / 4) \\}$, which is equivalent to $\\theta(w_{1,i},w_1)\\le \\pi/4$ for all $i\\in[T_1]$. Then, by the triangular inequality of angles as we have proved in Appendix A.3, Lemma 12, if $\\theta(w_1,w^\\star)\\le \\pi/4$ and $\\theta(w_1,w_{1, i})\\le \\pi/4$, then $\\theta(w_{1,i},w^\\star)\\le \\pi/2$ for all  $i\\in[T_1]$, enabling the construction of proxy feature.\n\nEnhancement Algorithm. During the Batched Enhancement phase, each batch $k$ receives an initial vector $w_{k}$ from the last batch, which is required to satisfy $\\theta(w^\\star,w_{k})\\le \\pi/2^{k+1}$. Next, in each iteration $i$ of batch $k$, we constrain the deployed coefficient vector $w_{k,i}$ to lie in the set  $\\mathcal{K} _ k = \\{ w \\mid \\langle w, w _ k \\rangle \\ge \\cos \\left( \\pi / 2^{k+1} \\right) \\}$, which means $\\theta(w_{k,i},w_k)\\le \\pi/2^{k+1}$ for all $i\\in[T_k]$. Then, by the triangular inequality of angles as we have proved in Appendix A.3, Lemma 12, we can show that $\\theta(w^\\star,w_{k,i})\\le \\theta(w^\\star,w_{k})+\\theta(w_{k,i},w_{k})\\le \\pi/2^{k}$. This statement is quite critical: On one hand, it controls the expected cumulative error in batch $k$ to be $O(\\frac{1}{2^k}\\cdot T_k)$. On the other hand, the condition that $\\theta(w_{k,i},w_k)\\le \\pi/2^{k}$, together with our localized online mirror descent method, ensures that batch $k$ outputs a vector $w_{k+1}$ that satisfies $\\theta(w^\\star,w_{k+1})\\le \\pi/2^{k+2}$ with high probability, which is required by the next batch.\n\n- Discussions on unknown or heterogeneous maximum manipulation radius $\\gamma$:\n\nIn our paper we consider the setting that the manipulation radius (or manipulation budget/maximum manipulation distance) $\\gamma$ is known, which is a common practice in the literature (Chen et al. (2020), Shen et al. (2024)). However, considering unknown or heterogeneous $\\gamma$ is a quite interesting direction of future study. \n\n\nFor a homogeneous unknown $\\gamma$, \nAhmadi et al. (2021) proposed a strategic perceptron algorithm with an unknown manipulation radius. Their key idea is running a binary search to find a proper estimate on this radius. However, this idea relies heavily on their assumption that the positive and negative classes are strictly separated by a margin without any noise. Their algorithm design requires either knowing the value of the margin or having an estimation process for it. These requirements cannot be fulfilled in the noisy setting without any margin. Therefore, it is hard to extend Ahmadi et al. (2021)'s binary search approach to our setting with unknown $\\gamma$. \n\n\nIf the maximum manipulation distance is heterogeneous but known, then adapting our algorithm seems straightforward. That is, each agent arriving at time $t$ has a maximum manipulation distance $\\gamma_t$ that potentially differs from other agents' manipulation distances, but every $\\gamma_t$ is known to the principal prior to decision-making. In this case, our construction of proxy feature and pairwise contrastive inference can directly use the known $\\gamma_t$   for each agent, in place of the previous homogeneous $\\gamma$.\n\n- Explanations on the Refinement stage: \n\nAs we have explained at the beginning, we need the Refinement Algorithm to output a vector $w_1$ such that $\\theta(w_1,w^\\star)\\le \\pi/4$ with high probability, which is crucial for the subsequent Enhancement Algorithm. \nTo achieve this, we form an online linear optimization problem with localization following Zhang et al. (2020). Zhang et al. (2020) show that in the non-strategic setting, this approach can effectively learn halfspaces under Massart noise. Our refinement stage applies classifiers as if there is no manipulation and focuses on the localization region right above the classification hyperplane. Agents within the localization region are naturally positively classified so they would truthfully report their features. Therefore, we can  collect true data within the localization region, enabling the approach in Zhang et al. (2020) with theoretical guarantees. However, although this can collect true data within the localization region, it is fairly costly. This is because unqualified agents below the classification hyperplanes are incentivized to manipulate their features to get positively classified, resulting in high instantaneous regret. Fortunately, the total regret in the Refinement stage is controlled because this stage lasts for only $O(\\log T)$ cycles.\n\nHowever, this cannot be achieved by simply shifting the boundary by $\\gamma$. Although shifting the boundary by $\\gamma$ can prevent excessive manipulation from unqualified agents, it also causes challenges for targeting the localization region in terms of the true features. In this case, all agents with true features within $\\gamma$ distance below the announced classification  hyperplane will strategically manipulate their features onto the classification hyperplane (see Figure 1(a) in our paper). These manipulating agents consist of both agents whose true features are within the localization band and agents whose true features are outside the band, and their reported features all lie on classification hyperplane. So it is difficult to tell whose true features are indeed within the localization band. Our Enhancement algorithm manages to resolve this issue by combining proxy features and pairwise contrastive inference. \n\nWe appreciate your insightful questions and suggestions. We will integrate our discussions into the camera-ready version to clarify the points you have raised.\n\nChen, Y., Liu, Y., & Podimata, C. (2020). Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 15265-15276.\n\nShen, L., Ho-Nguyen, N., Giang-Tran, K. H., & Kılınç-Karzan, F. (2024). Mistake, manipulation and margin guarantees in online strategic classification. arXiv preprint arXiv:2403.18176.\n\nAhmadi, S., Beyhaghi, H., Blum, A., & Naggita, K. (2021). The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation (pp. 6-25).\n\nZhang, C., Shen, J., & Awasthi, P. (2020). Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33, 7184-7197."}]

Author rebuttal:

Meta-review: This paper makes a strong and timely contribution by studying online strategic classification with Massart noise and partial feedback, a practically motivated and technically challenging setting, with impact on both learning theory and fairness communities. Reviewers highlight that the authors successfully combine techniques from strategic classification and noisy online learning while introducing new tools such as pairwise contrastive inference and proxy feature gradients. The work delivers the first sublinear regret guarantees in this setting, which several reviewers view as a conclusive result.
The writing could be improved in places, particularly in explaining intuition behind the algorithmic steps, but overall the paper is technically solid, well-motivated, and advances the state of the art.
Decision: Accept (spotlight)