Learning Losses for Strategic Classification

That learning outcomes might be compromised by agents responding to published classification rules with strategic manipulations of their feature vectors was first pointed out over a decade ago (Dalvi et al. 2004; Brückner and Scheffer 2011) and has received substantial interest from the research community in recent years initiated by a study by Hardt et al. that differentiated the field from the more general context of learning under adversarial perturbations (Hardt et al. 2016). That study considered strategic responses being induced by separable cost functions for utility maximizing agents and studied the resulting decision boundaries for certain classes of classifiers. Recent years have seen a lot of interest in better understanding the interplay of various incentives in settings where a decision rule is published and thereby has an effect on how the entities that are to be classified might present themselves to the decision-maker. In particular, various externalities to this scenario have been analyzed. A general cost to society formalized in form of a “social burden” incurred by the costs of enforced feature manipulation, has been shown to occur when institutions anticipate strategic responses (Milli et al. 2019; Jagadeesan, Mendler-Dünner, and Hardt 2021). Further, it has been demonstrated how such a burden may be suffered to differing degrees by various subgroups of a population that may differ in their capabilities to adapt their features in ways that are favorable to them (Milli et al. 2019; Hu, Immorlica, and Vaughan 2019), raising concerns over fairness in such scenarios.

Recent studies have extended the original game-theoretic model of a classifier publishing intuition and best responding subjects. For example, a recent work studied how strategic modification can also be a positive effect and how that should be taken into consideration by the institution (Haghtalab et al. 2020). Such a perspective has been connected to underlying causal relations between features and classification outcome and resulting strategic recommendations (Miller, Milli, and Hardt 2020; Tsirtsis and Rodriguez 2020). Further, a very recent study has explored how the model of a best responding agent may be relaxed to better reflect empirically observed phenomena (Jagadeesan, Mendler-Dünner, and Hardt 2021).

Much of previous work considers the scenario of classification with strategic agents on a population level. A few recent studies have also analyzed how phenomena observed on samples reflect the underlying population events (Haghtalab et al. 2020). Notably, very recent studies provided first analyses of learning with strategically responding agents in a PAC framework (Zhang and Conitzer 2021; Sundaram et al. 2021). The former work studied the sample complexity of learning VC-classes in this setup and analyzed effects on sample complexity of enforcing incentive compatibility for the learned classification rules. Our work can be viewed as an extension of this analysis. We propose to combine aspects of incentive compatibility and minimizing negative externalities such as social burden in form of a novel loss function that may serve as a learning objective when strategic responses are to be expected.

Our sample complexity analysis is then hinging on techniques developed in the context of learning under adversarial perturbations, a learning scenario which has received considerable research attention in recent years (Feige, Mansour, and Schapire 2015; Cullina, Bhagoji, and Mittal 2018; Montasser, Hanneke, and Srebro 2019, 2021). While the learning problems are not identical, we present how strategic behaviour can be modeled as a form of “one-sided adversarial perturbation” and inheritance of resulting learning guarantees.

In Section 2 we review our notation and then introduce our new notion of strategic loss and motivate it. Our main contributions can be summarized as follows:

Strategic manipulation loss

We propose a novel loss function for learning in the presence of strategic feature manipulations. We carefully motivate this loss by relating it to concepts of social burden and incentive compatibility (and their potential trade-offs with accuracy) in prior literature.

Sample complexity analysis

We analyze (PAC type) learnability of VC-classes with the strategic loss. We provide sufficient conditions (and examples of when they are satisfied) for learnability with a proper learner. By drawing connections and adapting results from learning under adversarial perturbations to our setup, we also show that, while proper learnability can not always be guaranteed, every VC-class is learnable under the strategic loss with an improper learner.

Robustness to inaccurate manipulation information

We investigate the impact of using an approximate manipulation graph to yield a surrogate strategic loss function for cases where the true manipulation graph is not known or not accessible. For this, we introduce a novel similarity measure on graphs and show that if graphs are similar with respect to our notion then they yield reasonable surrogate strategic losses for each other (Theorem 6).

Learning the manipulation graph

We explore the question of whether it is possible to learn a manipulation graph that yields a good surrogate strategic loss. We identify a sufficient condition for a class of graphs ${\mathcal{G}}$ being learnable with respect to our previously defined similarity measure for graphs (Theorem 7), which in turn guaranteed the learning of a reasonable surrogate loss.

All proofs can be found in the appendix of the full version.

We employ a standard setup of statistical learning theory for classification. We let $\mathcal{X}\subseteq\mathbb{R}^{d}$ denote the domain and $\mathcal{Y}$ (mostly $\mathcal{Y}=\{0,1\}$) a (binary) label space. We model the data generating process as a distribution $P$ over $\mathcal{X}\times\mathcal{Y}$ and let $P_{\mathcal{X}}$ denote the marginal of $P$ over $\mathcal{X}$. We use the notation $(\mathbf{x},y)\sim P$ to indicate that $(\mathbf{x},y)$ is a sample from distribution $P$ and $S\sim P^{n}$ to indicate that set $S$ is a sequence (for example a training or test data set) of $n$ i.i.d. samples from $P$. Further, we use notation $\eta_{P}(\mathbf{x})=\mathbb{P}_{(\mathbf{x},y)\sim P}[y=1\mid\mathbf{x}]$ to denote the regression or conditional labeling function of $P$. We say that the distribution has deterministic labels if $\eta_{P}(\mathbf{x})\in\{0,1\}$ for all $\mathbf{x}\in\mathcal{X}$.

A classifier or hypothesis is a function $h:\mathcal{X}\to\mathcal{Y}$. A classifier $h$ can naturally be viewed a subset of $\mathcal{X}\times\mathcal{Y}$, namely $h=\{(\mathbf{x},y)\in\mathcal{X}\times\mathcal{Y}~{}\mid~{}\mathbf{x}\in\mathcal{X},~{}y=h(\mathbf{x})\}$. We let ${\mathcal{F}}$ denote the set of all Borel measurable functions from $\mathcal{X}$ to $\mathcal{Y}$ (or all functions in case of a countable domain). A hypothesis class is a subset of ${\mathcal{F}}$, often denoted by ${\mathcal{H}}\subseteq{\mathcal{F}}$. For a loss function $\ell:{\mathcal{F}}\times\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ we denote the expected loss for a distribution $P$ as ${\mathcal{L}_{P}}$ and the empirical loss for a sample $S$ as ${\mathcal{L}_{S}}$. We use standard definitions like PAC learnability, sample complexity, and approximation error. For further elaborations on these definitions, we refer the reader to the appendix for an extended definitions section or a textbook (Shalev-Shwartz and Ben-David 2014).

To motivate our proposed loss, we here discuss several scenarios where, we’d argue, minimizing the strategic loss leads to a more desirable learning outcome than learning with a binary loss, while taking strategic manipulations into account. As discussed above, a common approach to modeling classification in a setting where strategic manipulations may occur is to assume that all agents will best-respond to a published classifier. That is, if $h(\mathbf{x})=0$, $h(\mathbf{x}^{\prime})=1$ and $\mathbf{x}\to\mathbf{x}^{\prime}$, then the agent with initial feature vector $\mathbf{x}$ will effectively receive classification $1$. A natural modeling is then to consider the effective hypothesis $\hat{h}$ induced $h$ (see Equation 1) and aim to minimize the classification error with the effective class $\hat{{\mathcal{H}}}=\{f\mid f=\hat{h}\text{ for some }h\in{\mathcal{H}}\}$ (Zhang and Conitzer 2021). However it has been shown, that the VC-dimension of $\hat{{\mathcal{H}}}$ may be arbitrarily larger than the VC-dimension of ${\mathcal{H}}$, and may even become infinite (Zhang and Conitzer 2021). When learning this effective class $\hat{{\mathcal{H}}}$ with respect to the binary loss (which corresponds to aiming for performative optimality), this will imply that the class is not learnable. By contrast, we will show below that any class of finite VC-dimension remains learnable with respect to the strategic loss (Theorem 5).

It has also been shown that the negative effects in terms of sample complexity of considering the effective hypothesis class can be avoided by considering only incentive-compatible hypotheses in ${\mathcal{H}}$, that is outputting only such hypotheses that will not induce any feature manipulations in response to the published classifier (Zhang and Conitzer 2021). While this avoids the growths in terms of VC-dimension, it may prohibitively increase the approximation error of the resulting (pruned) class as we show in the example below. We would argue that this illustrates how low sample complexity, in itself, is not a sufficient criterion for learning success.

The following example illustrates how our loss function can be viewed as incorporating the notion of social burden directly into the loss.

It is well known that a class ${\mathcal{H}}$ is learnable (with respect to the set of all distributions) if the loss class induced by a $0/1$-valued loss function $\ell$ has finite VC-dimension. In the case of the binary classification loss, this is in fact a characterization for learnability (and the VC-dimension of the loss class is identical to the VC-dimension of the hypothesis class ${\mathcal{H}}$). In general, bounded VC-dimension of the loss class is a sufficient condition for learnability (the VC-dimension provides an upper bound on the sample complexity), but it is not a necessary condition (it doesn’t, in general, yield a lower bound on the sample complexity of learning a class ${\mathcal{H}}$ with respect to some loss $\ell$). We start by reviewing these notions for the classification loss and then take a closer look at the loss class induced by the strategic loss.

Let $\ell$ be a loss function and $h$ be a classifier. We define the loss set $h_{\ell}\subseteq\mathcal{X}\times\mathcal{Y}$ as the set of all labeled instances $(\mathbf{x},y)$ on which $h$ suffers loss $1$. The loss class ${\mathcal{H}}_{\ell}$ is the collection of all loss sets (in the literature, the loss class is often described as the function class of indicator functions over these sets). In the case of binary classification loss ${\ell^{0/1}}$, the loss set of a classifier $h$ is exactly the complement of $h$ in $\mathcal{X}\times\mathcal{Y}$. That is, in this case the loss set of $h$ is also a binary function over the domain $\mathcal{X}$ (namely the function $\mathbf{x}\mapsto|h(\mathbf{x})-1|$). For the strategic loss on the other hand, the loss set of a classifier $h$ is not a function, since it can contain both $(\mathbf{x},0)$ and $(\mathbf{x},1)$ for some points $\mathbf{x}\in\mathcal{X}$, namely if $h(\mathbf{x})=0$ and there exists an $\mathbf{x}^{\prime}$ with $\mathbf{x}\to\mathbf{x}^{\prime}$ and $h(\mathbf{x}^{\prime})=1$. For a class ${\mathcal{H}}$ we let ${\mathcal{H}}_{\ell^{0/1}}$ denote the loss class with respect to the binary loss and ${\mathcal{H}}_{{\ell^{\to}}}$ the loss class with respect to the strategic loss.

It is easy to verify that for the binary loss, the VC-dimension of ${\mathcal{H}}$ as a collection of subsets of $\mathcal{X}\times\mathcal{Y}$ is identical with the VC-dimension of ${\mathcal{H}}_{\ell^{0/1}}$ (and this also coincides with the VC-dimension of ${\mathcal{H}}$ as a binary function class (Shalev-Shwartz and Ben-David 2014); VC-dimension is often defined for binary functions rather than for collection of subsets, however, this is limiting for cases where the loss class is not a class of functions).

We now show that the VC-dimension of a class ${\mathcal{H}}$ and its loss class with respect to the strategic loss can have an arbitrarily large difference. Similar results have been shown for the binary loss class of the effective class $\hat{{\mathcal{H}}}$ induced by a manipulation graph (Zhang and Conitzer 2021). However the binary loss class of $\hat{{\mathcal{H}}}$ is different from the strategic loss class of ${\mathcal{H}}$ and, as we will see, the implications for learnability are also different.

On the other hand, we prove that the VC-dimension of the strategic loss class ${\mathcal{H}}_{{\ell^{\to}}}$ is always at least as large as the VC-dimension of the original class.

Standard VC-theory tells us that, for the binary classification loss, any learner that acts according to the ERM (Empirical Risk Minimization) principle is a successful learner for classes of bounded VC-dimension $d$. For a brief recap of the underpinnings of this result, we refer the reader to the supplementary material or for further details to (Shalev-Shwartz and Ben-David 2014). In the case of general loss classes with values in $\{0,1\}$, the VC-dimension does not characterize learnability. In particular, we next show that the VC-dimension of the strategic loss class does not imply a lower bound on the sample complexity.

In the previous section, we have seen that the loss class having a finite VC-dimension is a sufficient (but not necessary) condition for learnability with respect to the strategic loss. We have also seen that the VC-dimension of ${\mathcal{H}}_{{\ell^{\to}}}$ can be arbitrarily larger than the VC-dimension of ${\mathcal{H}}$. To start exploring what determines learnability under the strategic loss, we provide a sufficient condition for a class to be properly learnable with respect to the strategic loss.

Note that for a hypothesis $h$, the strategic loss set $h_{\ell^{\to}}$ can be decomposed into the loss set of $h$ with respect to the binary loss and the component that comes from the strategic manipulations. Formally, we can define the strategic component loss.

For the loss sets, we then get

$$h_{{\ell^{0/1}}}=\{(\mathbf{x},y)\in\mathcal{X}\times\mathcal{Y}~{}\mid~{}h(\mathbf{x})\neq y\},$$

and

	$\displaystyle h_{{\ell^{\to,\perp}}}=\{(\mathbf{x},y)\in\mathcal{X}\times\mathcal{Y}~{}\mid~{}$	$\displaystyle h(\mathbf{x})=0$
		$\displaystyle\land\exists\mathbf{x}^{\prime}:\mathbf{x}\to\mathbf{x}^{\prime},\ h(\mathbf{x}^{\prime})=1\}.$

This implies

$$h_{{\ell^{\to}}}=h_{{\ell^{0/1}}}\cup h_{{\ell^{\to,\perp}}}$$

for all classifiers $h\in{\mathcal{F}}$, and thereby

$${\mathcal{H}}_{{\ell^{\to}}}=\{h_{{\ell^{0/1}}}\cup h_{{\ell^{\to,\perp}}}~{}\mid~{}h\in{\mathcal{H}}\}.$$

By standard counting arguments on the VC-dimension of such unions (see, for example Chapter 6 of (Shalev-Shwartz and Ben-David 2014) and exercises in that chapter), it can be shown this decomposition implies that $\mathrm{VC}({\mathcal{H}}_{{\ell^{\to}}})\leq d\log d$ for $d=\mathrm{VC}({\mathcal{H}}_{{\ell^{0/1}}})+\mathrm{VC}({\mathcal{H}}_{{\ell^{\to,\perp}}})=\mathrm{VC}({\mathcal{H}})+\mathrm{VC}({\mathcal{H}}_{{\ell^{\to,\perp}}})$. Thus, if both the class ${\mathcal{H}}$ itself and the class of strategic components have finite VC-dimension, then ${\mathcal{H}}$ is properly learnable by any learner that is an ERM for the strategic loss:

Whether the class of strategic components has finite VC-dimension intrinsically depends on the interplay between the hypothesis class ${\mathcal{H}}$ and the graph structure of the manipulation graph. In Observation 1, we have seen that the graph structure can yield the strategic component sets to have much larger complexity than the original class. In the appendix, Section B, we provide a few natural examples, where the VC-dimension of the strategic components is finite.

Theorem 4 provides a strong sufficient condition under which any empirical risk minimizer for the strategic loss is a successful agnostic learner for a class of finite VC-dimension. We believe, in many natural situations the conditions in that theorem will hold, and analyzing in more detail which graph structure, combinations of graphs structures and hypothesis classes or classes of cost function lead to the strategic component sets having finite VC-dimension is an intriguing direction for further research.

We close this section with two results, both stated in Theorem 5, on the learnability under the strategic loss in the general case where the VC-dimension of the strategic component sets may be infinite. First, there are classes and manipulation graphs for which no proper learner is (PAC-) successful, even in the realizable case. Second, for any class of finite VC-dimension and any manipulation graph, there exists an improper PAC learner. These results follow by drawing a connection from learning under the strategic loss to learning under an adversarial loss (Montasser, Hanneke, and Srebro 2019). In the general adversarial loss setup, every domain instance $\mathbf{x}$ is assigned a set of potential perturbation $\mathcal{U}(\mathbf{x})$, and the adversarial loss of a hypothesis $h$ is then defined as

$$\ell^{\mathcal{U}}(h,\mathbf{x},y)=\mathds{1}\left[{\exists\mathbf{x}^{\prime}\in\mathcal{U}(\mathbf{x}):h(\mathbf{x}^{\prime})\neq y}\right].$$

The strategic loss can be viewed as a one-sided version of the adversarial loss, where the perturbation sets differ conditional on the label of a point, and where $\mathcal{U}(\mathbf{x},1)=\{\mathbf{x}\}$, while $\mathcal{U}(\mathbf{x},0)=\{\mathbf{x}^{\prime}\in\mathcal{X}\mid\mathbf{x}\to\mathbf{x}^{\prime}\}$. The following results on learnability with the strategic loss then follow by slight modifications of the corresponding proofs for learning under adversarial loss.