PAC-Learning for Strategic Classification
  The study of strategic or adversarial manipulation of testing data to fool a
classifier has attracted much recent attention. Most previous works have
focused on two extreme situations where any testing data point either is
completely adversarial or always equally prefers the positive label. In this
paper, we generalize both of these through a unified framework for strategic
classification, and introduce the notion of strategic VC-dimension (SVC) to
capture the PAC-learnability in our general strategic setup. SVC provably
generalizes the recent concept of adversarial VC-dimension (AVC) introduced by
Cullina et al. arXiv:1806.01471. We instantiate our framework for the
fundamental strategic linear classification problem. We fully characterize: (1)
the statistical learnability of linear classifiers by pinning down its SVC; (2)
its computational tractability by pinning down the complexity of the empirical
risk minimization problem. Interestingly, the SVC of linear classifiers is
always upper bounded by its standard VC-dimension. This characterization also
strictly generalizes the AVC bound for linear classifiers in arXiv:1806.01471.
