Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

• DOI: 10.48550/arxiv.2407.11619
• Publication Date: 2024-07-16
• Authors: S. Farzad Ahmadi; Kunhe Yang; Hanrui Zhang
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Computer Science - Computer Science and Game Theory; Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)

We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. model set feasible manipulations by directed graph over feature space, and assume learner only observes manipulated instead original ones. introduce Strategic Littlestone Dimension, new combinatorial measure that captures joint complexity hypothesis class manipulation graph. demonstrate it characterizes instance-optimal mistake bounds for deterministic learning algorithms realizable setting. also achieve improved regret agnostic setting refined agnostic-to-realizable reduction accounts additional challenge not observing agents' features. Finally, we relax assumption knows graph, assuming knowledge is captured family graphs. derive both all manipulate according same within family, graphs are chosen adversarially consistently modeled single family.