← Paper page PAC-Learning for Strategic Classification Ask this paper arXiv ↗

PAC-Learning for
Strategic Classification

When the people being classified can change how they look, and want different outcomes, how much data and computation does learning take?

Ravi Sundaram, Anil Vullikanti, Haifeng Xu, Fan Yao · ICML 2021 (oral)

Press → or click to step through

A classifier meets people who can respond

past data features, labels, preferences; nobody has moved yet learner picks a classifier + − − + − wants +, moves wants −, moves too costly: stays moving changes how they look, not their true label

Goal: a classifier that is right about people’s true labels after they respond.

Rings show how far each person would move. Preferences can point either way, with different strengths; in the paper’s COVID-19 testing example, some people want to be tested and some do not.

Try it: where should the line go?

+ − wants + wants − ring: how far they would move right wrong
right if nobody moves: right after people react:

Illustration with eight made-up people; each true label (+ or −) is inside the circle. The best line once people react is not the best line on paper: the learner must anticipate the moves.

From two extremes to one framework

The question: when can such a classifier be learned from a reasonable amount of data, and computed efficiently?

Throughout, training data are clean (people respond only at test time), and the learner knows each person’s preference and cost of moving.

A new yardstick: the strategic VC dimension

can the classifiers, after people react, produce every labelling of these 3?
one example from the paper ordinary VC 1 adversarial VC 1 strategic VC any size you like same classifiers; richer preferences (Proposition 2)

The largest group that can be labelled every way, counting reactions, is the strategic VC dimension. The data needed grows with it.

It equals the earlier adversarial VC dimension when everyone wants the opposite of their label, but mixed preferences can make it far larger.

The learner: pick the classifier with the fewest training mistakes after simulating everyone’s reaction. When costs are “separable” (as in earlier work) and nobody is indifferent, the strategic VC dimension is at most 2 for any classifiers.

For lines, what matters is whether costs are shared

same cost rule for everyone no harder than without gaming for lines in a plane it is 3, as usual
each person has their own cost rule A B C only A can cross B and C can cross only C can cross a line can single out any group illustration: all three want +, one location

Shared cost rule: the strategic VC dimension of lines is at most one more than the number of features, just as without gaming. Personal cost rules: it can be infinite, even in a plane.

The shared-cost result holds for any bounded preferences and any cost measured by a seminorm (exactly one more than the number of features for a norm), and generalizes the earlier adversarial result for lines.

Computing the best line needs an adversarial flavour

adversarial essentially adversarial any preferences each wants the oppositeof their true label every true − wants + morethan any true + does either direction,any strength same cost rulefor everyone own cost rulefor each person computing ✓ fast computing ✓ fast computing ✗ NP-hard computing ✓ fast computing ✗ NP-hard computing ✗ NP-hard data ✓ enough data ✓ enough data ✓ enough data ✗ unbounded data ✗ unbounded data ✗ unbounded

Only with a shared cost rule and (essentially) adversarial preferences are lines learnable both from data and efficiently.

Computing here means finding a line that makes no training mistakes after reactions, assuming one exists; without gaming this is easy. “Data unbounded” means the strategic VC dimension can be infinite, so there is no finite sample-size guarantee. The hardness is for this standard learner; other algorithms are left open.

What this means

  1. 1One framework for strategic and adversarial classificationPeople may prefer either label, with different strengths and different costs of moving.
  2. 2The strategic VC dimension measures the data neededFor lines with a shared cost rule, gaming adds nothing; personal cost rules can make it infinite.
  3. 3Efficient learning needs an adversarial flavourJust beyond the (essentially) adversarial cases, finding the best line becomes NP-hard.

Paper page · arXiv · ICML talk