  We study the fundamental mistake bound and sample complexity in the strategic
classification, where agents can strategically manipulate their feature vector
up to an extent in order to be predicted as positive. For example, given a
classifier determining college admission, student candidates may try to take
easier classes to improve their GPA, retake SAT and change schools in an effort
to fool the classifier. Ball manipulations are a widely studied class of
manipulations in the literature, where agents can modify their feature vector
within a bounded radius ball. Unlike most prior work, our work considers
manipulations to be personalized, meaning that agents can have different levels
of manipulation abilities (e.g., varying radii for ball manipulations), and
unknown to the learner.
  We formalize the learning problem in an interaction model where the learner
first deploys a classifier and the agent manipulates the feature vector within
their manipulation set to game the deployed classifier. We investigate various
scenarios in terms of the information available to the learner during the
interaction, such as observing the original feature vector before or after
deployment, observing the manipulated feature vector, or not seeing either the
original or the manipulated feature vector. We begin by providing online
mistake bounds and PAC sample complexity in these scenarios for ball
manipulations. We also explore non-ball manipulations and show that, even in
the simplest scenario where both the original and the manipulated feature
vectors are revealed, the mistake bounds and sample complexity are lower
bounded by $\Omega(|H|)$ when the target function belongs to a known class $H$.
