• Zoom link : https://snu-ac-kr.zoom.us/j/82412415385?pwd=y603sWTAT91HuMolEFUjEIv8dibQtt.1

We study online strategic classification, in which the learner’s deployed classifier influences the data it subsequently observes because agents can strategically alter their reported features. We consider a linear classification model with norm-based manipulation costs and assume that the agents’ underlying true features satisfy a large-margin separability condition. Our goal is to characterize when meaningful learning remains possible under strategic behavior.

We show that learnability is governed by margin-based threshold phenomena. In particular, there are regimes in which no online method can guarantee finitely many prediction errors, and stricter regimes are required to simultaneously control both prediction errors and strategic manipulation. To complement these limits, we develop a general reduction framework that converts standard online large-margin algorithms into algorithms for strategic classification. Using reported features alone yields guarantees in favorable regimes, while a proxy-data construction extends finite-mistake guarantees to the full learnable range.

Instantiations with perceptron and online maximum-margin methods recover and extend existing results, and show that stronger margin guarantees in the underlying learning algorithm translate directly into stronger guarantees in the strategic setting. We also study additive noise in reported features and show that the associated learnability thresholds depend sharply on the feedback model and on what information about the perturbation is available to the learner. Counterintuitively, learnability thresholds do not vary continuously with the noise level: the introduction of arbitrarily small additive noise can create a strictly harder learning problem than in the noiseless case, producing a discontinuous jump in the threshold for learnability.