# Strategic Classification Made Practical

Sagi Levanon  Nir Rosenfeld

###### Abstract

Strategic classification regards the problem of learning in settings where
users can strategically modify their features to improve outcomes. This
setting applies broadly and has received much recent attention. But despite
its practical significance, work in this space has so far been predominantly
theoretical. In this paper we present a learning framework for strategic
classification that is _practical_. Our approach directly minimizes the
“strategic” empirical risk, achieved by differentiating through the strategic
response of users. This provides flexibility that allows us to extend beyond
the original problem formulation and towards more realistic learning
scenarios. A series of experiments demonstrates the effectiveness of our
approach on various learning settings.

Machine Learning, ICML

##  1 Introduction

Across a multitude of domains—from loan approval to online dating to hiring
and admissions—predictive machine learning models are becoming imperative for
informing decisions that affect the lives of humans. But when people benefit
from certain predictive outcomes, they are prone to act strategically to
improve those outcomes. This has raised awareness as to the idea that standard
learning algorithms may not be robust to such behavior, and there is a growing
recognition as to the prevalence of this phenomena. Given the breadth of
domains in which strategic user behavior is likely, practical tools for
learning in strategic settings are of considerable importance.

In this paper we study practical aspects of learning in the setting of
_strategic classification_ (Brückner & Scheffer, 2011; Hardt et al., 2016). In
this problem, users respond to a published classifier by strategically
modifying their features (at some cost) to improve their predicted outcomes.
As a concrete example, consider a bank offering loans. The bank would like to
approve a loan only if it is likely to be returned, and to aid in decision-
making, the bank trains a classifier to predict loan returns. Applicants,
however, would like their requests to be approved—regardless of their actual
credibility. To promote their interests, they can modify their applications
(at some cost) to best align with the bank’s classification rule. From the
bank’s perspective, such modifications can invalidate model predictions, and
the primary goal in strategic classification is to design learning algorithms
that are robust to this form of ‘gaming’.

Note that gaming is caused _by the model itself_ , indirectly through how it
shapes user incentives, and to its detriment. In this sense, strategic
classification exemplifies how machine learning can be amenable to Goodhart’s
Law, a principle in policymaking stating that “when a measure becomes a
target, it ceases to be a good measure”. Strategic classification thus
succinctly captures a natural form of tension that arises between a learning-
based system and its users. There has been much recent work on this topic,
studying aspects such as generalization (Sundaram et al., 2020; Zhang &
Conitzer, 2021), equilibrium dynamics (Perdomo et al., 2020), online learning
(Dong et al., 2018; Chen et al., 2019; Ahmadi et al., 2020), causality
(Kleinberg & Raghavan, 2019; Shavit et al., 2020; Bechavod et al., 2020;
Miller et al., 2020), and social perspectives (Hu et al., 2019; Milli et al.,
2019; Chen et al., 2020).

But despite this flurry of recent work, algorithms for strategic
classification are not in widespread use. The key reason for this is that work
in this space has been predominantly theoretical. This has several practical
implications. First, for mathematical tractability, strong assumptions are
made (e.g., that the cost function is fixed and known). But the robustness of
these methods to violations of their assumptions is not well understood.
Second, methods tend to be crafted for very particular learning settings, and
do not easily extend beyond the narrow context in which they are originally
studied. Third, currently available algorithms lag far behind recent advances
in machine learning methodology; they are prone to issues of scale,
expressivity, and runtime, and lack the flexibility and modularity that
current approaches readily provide (e.g., the ability to seamlessly “add a
layer” or change the loss function). Combined, the above limitations indicate
a clear need for an approach to learning in strategic classification that is
effective and practical. Our work aims to take a first step towards addressing
this need.

The core idea of our approach is to encode into the learning objective a
_response mapping_ that models how users respond to a given classification
rule. By anticipating how inputs will be strategically modified under a given
model, our approach optimizes directly for predictive performance under
strategic behavior. We refer to this as _strategic empirical risk
minimization_ (SERM). The challenge in optimizing the SERM objective is that
models of user response typically involve an argmax operator, which can be
non-differentiable and even discontinuous. Our solution is to replace the
argmax operator with a differentiable proxy, and for this we draw on recent
advances in differentiable optimization solvers (Amos & Kolter, 2017; Djolonga
& Krause, 2017; Agrawal et al., 2019a, b; Berthet et al., 2020; Tan et al.,
2020; Agrawal & Boyd, 2020) and adapt them to our purpose. The resulting
_strategic response layer_ provides the main building-block of our framework.

Using the flexibility our framework provides, we propose and showcase multiple
ways in which the framework can extend beyond the original formulation of
strategic classification and towards more realistic learning scenarios. We
make use of the modular nature of our approach to explore various extensions
aimed at addressing potential practical concerns. These include: supporting
complex predictive models (e.g., recursive neural networks), supporting
structured cost functions (e.g., constraining movement to a manifold), and
relaxing the assumption of a fixed and known cost function (we handle
adjustable and unknown costs).

The primary goal in strategic classification is to learn strategically-robust
predictive models, but several works have raised concern as to the adverse
social outcomes this may entail (Milli et al., 2019; Hu et al., 2019; Chen et
al., 2020). This may not be surprising given that learning focuses entirely on
optimizing predictive accuracy. To address these concerns, here we argue for a
broader perspective that considers the trade-off between system and user
interests. Borrowing from welfare economics, we take the perspective of a
‘social planner’ tasked with balancing between these interests, and show how
our approach can extend to target any operating point along the pareto front.
To do this, we cast strategic classification as a problem of _model selection_
, and propose novel forms of regularization that promote favorable social
outcomes for various notions of ‘social good’. Because strategic
classification is not a zero-sum game, the incentives of the system and of its
users are not entirely antagonistic. As we show, this permits much social
benefit to be gained at only a small cost in accuracy.

In summary, our paper makes the following contributions:

  * •

Practical framework. We propose a novel learning framework for strategic
classification that is practical, effective, and flexible. Our approach allows
to differentiate through strategic user responses, thus permitting end-to-end
training.

  * •

Flexible modeling. We show how the flexibility of our approach allows for
learning in diverse strategic settings. We effectively apply our approach to
multiple such settings of practical interest.

  * •

Socially-aware learning. We propose several forms of regularization that
encourage learned models to promote favorable social outcomes. By capitalizing
on certain structural aspects of the problem, our regularization effectively
balances between system and user interests.

We conduct a series of experiments demonstrating the effectiveness of our
approach. With respect to the above points, each of our experiments is
designed to study a different practical aspect of learning. The experiments
cover a range of learning environments using real and synthetic data. Our
results show that learning in strategic classification can be practical,
effective, and socially responsible. We will make code for our framework and
experiments publicly available.

##  2 Related Work

The literature on strategic classification is growing at a rapid pace. Various
formulations of the problem were studied in earlier works (Brückner &
Scheffer, 2009; Brückner et al., 2012; Großhans et al., 2013), but most recent
works adopt the core setup of Hardt et al. (2016), as we do here. Research in
this space has mostly been oriented towards theory, with recent work extending
PAC theory to this setting (Sundaram et al., 2020; Zhang & Conitzer, 2021). We
complement these by placing emphasis on practical aspects of learning.

Several papers consider the social impacts of strategic classification. Milli
et al. (2019) study the social burden imposed by optimizing for accuracy. Chen
et al. (2020) study the connection between strategically-aware learning and
recourse. Hu et al. (2019) focus on fairness and show how classifiers can
induce inequitable modification costs that affect utility. Our work ties these
together, providing means to _control_ the tradeoff between classifier’s
accuracy and the social outcomes it induces through regularization (see Sec.
3.4).

A parallel line of work studies how learned models affect actual (rather than
predictive) outcomes. Some works analyze how models should promote users to
invest effort effectively (Kleinberg & Raghavan, 2019; Alon et al., 2020),
while others tie learning to the underlying casual mechanisms of the
environment (Perdomo et al., 2020; Bechavod et al., 2020; Shavit et al., 2020;
Miller et al., 2020). We remain within the original, purely predictive problem
formulation, but view the extension of our approach to such settings to be
intriguing as future work.

##  3 Method

##### Learning setup.

Denote by $x\in{\cal{X}}\subseteq{\mathbb{R}}^{d}$ features representing user
attributes (e.g., a loan application profile), and by
$y\in{\cal{Y}}=\\{-1,1\\}$ their corresponding labels (e.g., loan returned or
not). Let ${p}(x,y)$ be a joint distribution over features and labels. The
primary goal in learning is to find a classifier
$h:{\cal{X}}\rightarrow{\cal{Y}}$ from a class $H$ that achieves high expected
accuracy. For this, we assume access to a sample set
${\mathcal{S}}=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ sampled i.i.d. from ${p}(x,y)$,
on which we train. At test time, however, $h$ is evaluated on data that is
prone to modification by users. In strategic classification, users modify
their features using the _response mapping_ :

${\Delta}_{h}(x)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}h(x^{\prime})-c(x,x^{\prime})$
(1)

where $c$ is a known cost function. Test data includes pairs
$({\Delta}_{h}(x),y)$ where $(x,y)\sim{p}$, and the goal in learning is to
optimize predictive accuracy under this induced distribution.

As is common, the classifiers we consider will be based on score functions
$f:{\cal{X}}\rightarrow{\mathbb{R}}$ via the decision rule
$h_{f}(x)=\operatorname{sign}(f(x))$, and learning will be concerned with
optimizing over a class of parametrized score functions $F$. We write
${\Delta}_{f}$ to mean ${\Delta}_{h_{f}}$, and for clarity, omit the
notational dependence of the classifier $h_{f}$ on $f$ when clear from
context.

##### Game-theoretic formulation.

Strategic classification can be formulated as a Stackelberg game between two
players—the _system_ and a population of _users_. First, the system learns
from ${\mathcal{S}}$ a classifier $h$. Then, given $h$, users respond via
${\Delta}_{h}$. The payoffs are:

System: $\displaystyle\quad\mathbb{P}{\left[{y=h({\Delta}_{h}(x))}\right]},$
(2) Users:
$\displaystyle\quad\mathbb{E}{[{h({\Delta}_{h}(x))-c(x,{\Delta}_{h}(x)}]}$ (3)

Payoff to the system (Eq. (2)) is the probability of classifying manipulated
points correctly. Payoff to the users (as a collective) is their expected
utility (Eq. (3)), for which ${\Delta}$ as defined in Eq. (1) is a best-
response.

###  3.1 Strategic Empirical Risk Minimization

A naïve approach would be to train a classifier to predict well on the (non-
manipulated) input data, and use it at test time on manipulated data. The
caveat in this approach is that strategic behavior causes a discrepancy
between the (marginal) input distributions at train and test time. Strategic
classification therefore introduces a form of _distribution shift_ (Quionero-
Candela et al., 2009), but with the unique property that shift is determined
by the predictive model itself, albeit indirectly through its effect on user
responses.

Our approach will be to account for this shift by directly optimizing for the
induced distribution. Noting that the system’s payoff in Eq. (2) can be
rewritten as $1-\mathbb{E}{[{\mathds{1}{\\{{y\neq h({\Delta}_{h}(x))}\\}}}]}$,
we set our objective to the empirical loss over the _strategically-modified_
training set:

$\min_{f\in F}\sum_{i=1}^{m}{L}({\Delta}_{f}(x_{i}),y_{i},f)+\lambda{R}(f)$
(4)

where ${L}(z,y,f)=\mathds{1}{\\{{y\neq h_{f}(z)}\\}}$ and ${R}$ is an optional
regularizer. In practice we replace ${L}$ with a tractable surrogate (e.g.,
binary cross-entropy), and we will return to the role of regularization in
Sec. 3.4. We refer to optimizing Eq. (4) as _strategic empirical risk
minimization_ (SERM). Note that $f$ plays a dual role in the objective: it
determines how inputs are modified (via ${\Delta}_{f}$) and how predictions
are made on those modified inputs (via $h_{f}$).

###  3.2 Differentiating through strategic responses

A natural way to approach the optimization of Eq. (4) is using gradient
methods. The challenge in this approach is that ${\Delta}$ is an argmax
operator and can therefore be non-differentiable. Our solution to this will be
to use a differentiable proxy for ${\Delta}$, drawing inspiration from recent
advances in _differentibale optimization solvers_. Such solvers map
parametrized optimization problems to their (approximately) optimal solutions
in a manner that is amenable to differentiation, and so can be used as
optimization “layers” integrated into neural architectures.

Our approach will be to implement the response mapping ${\Delta}$ as a
differentiable optimization layer. In particular, we make use of _convex
optimization layers_ (Agrawal et al., 2019a), but since we seek to maximize,
we will construct _concave_ layers. A concave optimization layer ${g}(\theta)$
maps concave optimization problem instances to their argmax: the input to the
layer, $\theta$, defines the “parameters” (and hence the instance) of a
template optimization problem, and the output of the layer is the solution
under this parameterization. In our model, ${g}$ will play the role of
$\Delta$, and $\theta$ will include features $x$ and the learnable parameters
of $f$.

The response mapping ${\Delta}$ as defined in Eq. (1) is not concave, and to
apply concave optimization, we construct a concave proxy, denoted
${\tilde{{\Delta}}}$, as follows. To begin, assume for simplicity that $h$ is
linear, i.e., $h_{w}(x)=\operatorname{sign}f_{w}(x)$ with
$f_{w}(x)=w^{\top}x+b$. Next, since $\operatorname{sign}$ is discontinuous, we
replace it with a smooth sigmoid $\sigma$ of the following form:

$\sigma_{\tau}(z)=\frac{1}{2}\sqrt{\left({\tau}^{-1}x+1\right)^{2}+1}-\frac{1}{2}\sqrt{\left({\tau}^{-1}x-1\right)^{2}+1}$

Here ${\tau}$ is a temperature parameter: as $\tau$ decreases, $\sigma$
approaches $\operatorname{sign}$. Our particular choice of sigmoid follows
from the fact that $\sigma$ can be written as a sum of convex and concave
functions. This motivates our final step, which is to apply the convex-concave
procedure (CCP) (Yuille & Rangarajan, 2003). CCP is an approach to solving
convex-concave optimization problems by iterating through a sequence of
concave-relaxed problems, a process that guarantees convergence to local
maxima. We focus on convex costs (e.g., linear or quadratic) so that CCP can
be applied to the entire response function.111Most of the literature considers
convex costs (and linear classifiers). This includes the experimental setting
of Hardt et al. (2016). Using CCP, we obtain reliable concave proxies of
responses at each input. This gives us our differentiable proxy of the
response mapping, which we refer to as a _strategic response layer_ , defined
as:

${\tilde{{\Delta}}}(x)=\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}{\texttt{CCP}}(\sigma(w^{\top}x^{\prime}+b))-c(x,x^{\prime})$
(5)

Here CCP denotes the concave proxy obtained at the last iteration of the
procedure.

To compute the forward pass, we run the CCP procedure using any standard off-
shelf convex solver, and compute the argmax w.r.t. the final proxy.222There
are many such tools available, and for reasonably-sized inputs, the
computation overhead is small. For the backward pass, we plug the final proxy
into the differentiable convex solver of Agrawal et al. (2019a) to get
gradients for ${\tilde{{\Delta}}}$ w.r.t. $w,b$.

###  3.3 Extensions

####  3.3.1 Nonlinear classifiers

The concave solver can handle only score functions $f$ that are linear in the
optimization variables. But $f$ need not be linear in the input features $x$;
rather, it can be linear in any high-dimensional representation of the inputs,
$z={\phi}(x)$, $z\in{\cal{Z}}$, such as those obtained from the final hidden
layers of neural networks. This holds as long as both $f$ and $c$ are defined
over this representation (i.e., points move in representation-space).

####  3.3.2 Flexible costs

The core setting of strategic classification assumes costs are fixed. But in
some settings, it is reasonable to assume that the system has some control
over the cost function. We model this as allowing the system to modify an
initial cost function $c_{0}$ to some other cost $c\in{\cal{C}}$ from the
class ${\cal{C}}$, with this incurring a penalty of ${r}(c_{0},c)$. The goal
is now to jointly learn the classifier _and_ the modified cost. Denoting by
${\Delta}_{f}^{c}$ the response mapping for classifier $f$ and cost function
$c$, we can extend the learning objective as follows:

$\min_{c\in{\cal{C}}}\min_{f\in
F}\sum_{i=1}^{m}{L}({\Delta}_{f}^{c}(x_{i}),y_{i},f)+{r}(c_{0},c)$ (6)

By utilizing its flexibility in choosing $c$, in this setting the system has
the capacity to obtain better predictive performance than when optimizing the
objective in Eq. (4).

####  3.3.3 Unknown costs

Strategic classification assumes that the cost function is known, but this may
not hold in practice. Here we consider a setting in which the system does not
know the true cost $c^{*}$, but has a reasonable estimate $c_{0}$. We model
the system as believing that $c^{*}$ lies in some set
$C(c_{0})\subseteq{\cal{C}}$ around $c_{0}$, and propose a worst-case approach
in which the system aims to perform well simultaneously on _all_ $c\in
C(c_{0})$. We propose the following minmax objective:

$\min_{f\in F}\max_{c\in
C(c_{0})}\sum_{i=1}^{m}{L}({\Delta}_{f}^{c}(x_{i}),y_{i},f)$ (7)

####  3.3.4 Moving on a manifold

The Manifold Hypothesis is a convention stating that high-dimensional data
tend to lie on or near a low-dimensional manifold. Typically the manifold is
unknown; but even if it is known, common cost functions tend to permit
arbitrary movement and so cannot account for this structure. Here we show how
our approach can incorporate (approximate) manifold constraints into learning.
We begin by learning a _manifold bundle_ $({M},{T})$ composed of a manifold
model ${M}$ and a tangent function ${T}(x)$ that returns the subspace tangent
to ${M}$ at $x$.333Many tools exist for learning bundles; e.g., Rifai et al.
(2011a). Since tangents $T(x)$ are linear objects that provide a first-order
approximation to the manifold at $x$ Our approach is to add them as linear
constraints to the optimization of the response mapping (i.e., the argmax in
${\Delta}$ is taken over $x^{\prime}\in T(x)$). This ensure points move only
on the tangent, thus approximating movement on the manifold.

###  3.4 Regularizing for social good

Our discussion of strategic classification thus far has been focused on a
single objective: predicting accurately in the face of strategic gaming. This
promotes a clear interest of the system, but neglects to account for the
effects of learning users. Returning to our loans example, note that any
predictor inevitably determines the degree of _recourse_ , defined as the
ability of users that are denied a service (e.g., a loan) to take reasonable
action to reverse this decision (Ustun et al., 2019; Gupta et al., 2019; Joshi
et al., 2019; Chen et al., 2020; Karimi et al., 2020b). Recourse is clearly
beneficial to users, but in many cases, its facilitation is also beneficial to
the system (for discussion see Ustun et al. (2019); Venkatasubramanian &
Alfano (2020); Karimi et al. (2020a)).

In this section we show how our framework can be used to train models that are
both accurate _and_ promote favorable social outcomes. Relying on the
observation that different models can induce very different social outcomes
(Heidari et al., 2019), we cast learning as a problem of _model selection_ ,
where the selection criterion reflects some notion of ‘social good’ (e.g.,
recourse). Model selection is implemented through regularization and below we
present novel forms of data-dependent regularizers ${R}(f;{\mathcal{S}})$
targeting various notions of social good from the literature.

Intuitively, we expect regularization to be useful because _strategic
classification is not a zero-sum game_. In other words, predictive models that
provide similar payoff to the system may differ considerably in their payoff
to users; we argue that the system has the freedom, as well as the
responsibility, to carefully choose between these. Viewing learning from the
perspective of a ‘social planner’ interested in balancing between system and
user interests, our regularization approach provides the means to achieve good
balance. Varying the amount of regularization $\lambda$ provides solutions
along the Pareto front, with $\lambda=0$ corresponding to the strategic
classification equilibrium in Eq. (2).

##### Expected utility.

Since the payoff to users in Eq. (3) is given by their gained _utility_ ,
${u}_{\Delta}(x)=h({\Delta}(x))-c(x,{\Delta}(x))$, a straightforward notion of
social good is their _expected utility_ , $\mathbb{E}{[{{u}_{\Delta}(x)}]}$.
Note that ${\Delta}$ is a best-response but it is utility-optimal _relative to
$h$_, and it is easy to construct an example showing that under the accuracy-
optimal predictor utility can be arbitrarily low.444 Consider $d=1$, with
points $(-\epsilon,-1)$ and $(\epsilon,1)$. Let
$c(x,x^{\prime})=|x-x^{\prime}|$. The classifier $h(x)=\mathds{1}{\\{{x\geq
2}\\}}$ causes all positive points (and only positive points) to move. The
payoff to negative points is $-1$ and the payoff to positive points is
$-1+\epsilon$. To encourage models that provide users with high utility, we
set:

${{R}_{\texttt{util}}}(f;{\mathcal{S}})=-\sum_{i=1}^{m}{u}_{\Delta}(x_{i})$
(8)

and plug into the learning objective in (4), where in practice we again
replace ${\Delta}$ with ${\tilde{{\Delta}}}$ and optimize as in Sec. 3.2.

##### Social burden.

In their paper on the social cost of strategic classification, Milli et al.
(2019) study _social burden_ , defined to be the minimum cost a positively-
labeled user must incur in order to be classified correctly. Within our
framework, we can regularize for social burden using:

${{R}_{\texttt{burden}}}(f;{\mathcal{S}})=\sum_{i:y_{i}=1}\min_{x^{\prime}:f(x^{\prime})\geq
0}c(x,x^{\prime})$ (9)

which we can also implement as a convex optimization layer for linear $f$ and
convex $c$ (the constraint is linear in $x,w$).

##### Recourse.

Recourse refers to the capacity of a user who is denied a service to restore
approval through reasonable action (in our case, low-cost feature
modification). Since ${\Delta}$ is a best-response, we say a user with
$h(x)=-1$ is _granted recourse_ if $h({\Delta}_{h}(x))=1$. The random variable
negating this condition is
$\mathds{1}{\\{{h(x)=-1\,\land\,h({\Delta}_{h}(x))=-1}\\}}$, and we regularize
using its smoothed approximation:

${{R}_{\texttt{recourse}}}(f;{\mathcal{S}})=\sum_{i=1}^{m}{\sigma}\left(-f(x)\right)\cdot{\sigma}\left(-f({\Delta}_{f}(x))\right)$

##  4 Experiments

Figure 1: A comparison of our SERM approach to a ‘strategy-blind’ baseline
across multiple datasets, predictive models, and settings. Left: A
reproduction of the setting of Hardt et al. (2016) on the spam dataset with
mixed linear-quadratic cost. Center: Learning RNNs for financial distress
time-series data. Right: Comparing across multiple datasets and degrees of
gaming (controlled by cost scale $t$).

In this section we empirically demonstrate the utility and flexibility of our
approach on a diverse set of tasks and settings. Our goal is to demonstrate
how our framework supports learning in settings that extend beyond the basic
setting of strategic classification, and each experiment extends the core
setting of Hardt et al. (2016) in a way that targets a certain aspect of
practical concern. The Appendix includes further details, additional
experiments, and illustrations.

##### Experimental setup.

Across all experiments we use four real datasets: (i) spam555Data can be
obtained from the authors of Costa et al. (2014)., which includes features
describing users of a large social network, some of which are spammers (used
originally in Hardt et al. (2016)); (ii)
credit666https://github.com/ustunb/actionable-recourse, which includes
features describing credit card spending patterns, and labels indicating
default on payment (we use the version from Ustun et al. (2019)); (iii)
fraud777https://www.kaggle.com/mlg-ulb/creditcardfraud, which includes credit
card transactions that are either genuine or fraudulent (Dal Pozzolo et al.,
2015); and (iv) financial
distress888https://www.kaggle.com/shebrahimi/financial-distress, which
includes time-series data describing businesses over time along with labels
indicating their level of financial distress and whether they have gone
bankrupt. All datasets include features that describe users and relate to
tasks in which users have incentive to obtain positive predictive outcomes.
Some experiments use synthetic environments, described below.

We compare our approach (SERM) to a strategy-blind baseline that falsely
assumes points do not move, achieved by training on the same model class but
using standard, non-strategic ERM. When appropriate, we also compare to the
strategic algorithm of Hardt et al. (2016), and to other context-specific
variants of our approach (e.g., naïve or oracle models). All models train on
non-strategic data, but are evaluated on strategic data. As a benchmark, we
use the strategy-blind model evaluated on non-strategic data (i.e., where
points do not move).

Our focus is mostly on linear classifiers as these are naturally interpretable
and hence justify the form of strategic behavior considered in strategic
classification. For time-series data, such as in experiment in Sec. 4.3, we
use recursive neural networks (RNN). For optimizing our approach we use Adam
with randomized batches and early stopping (most runs converged after at most
7 epochs). User responses were simulated using ${\Delta}$ from Eq. (1) with
$\tau=1$ for training and $\tau=0.2$ for evaluation. Tolerance for CCP
convergence was set to $0.01$ (most attempts converged after at most 5
iterations). All methods use a 60-20-20 data split, and results are averaged
over multiple random splits.

###  4.1 Core setting

Our first experiment begins with a reproduction of the experimental setting of
Hardt et al. (2016). They use the spam dataset and consider linear-separable
cost functions
${c_{\text{lin}}^{{{v}}}}(x,x^{\prime})=\max\\{0,{v}^{\top}(x^{\prime}-x)\\}$
with a specific hand-coded ${v}\in{\mathbb{R}}^{d}$. Their algorithm only
supports separable costs, and for linear-separable costs, returns a linear
classifier. Linear costs, however, are unstable under evaluation since points
can move at zero cost whenever ${v}^{\top}(x^{\prime}-x)\leq 0$. Hence, they
train with ${c_{\text{lin}}^{{{v}}}}$, but evaluate on a mixture cost:

${c_{\text{mix}}}(x,x^{\prime};{\gamma},{v})=(1-{\gamma})\cdot{c_{\text{lin}}^{{{v}}}}(x,x^{\prime})+{\gamma}\cdot{c_{\text{quad}}}(x,x^{\prime})$

where ${c_{\text{quad}}}=\|x^{\prime}-x\|_{2}^{2}$ and ${\gamma}\in(0,1]$
(they use ${\gamma}\in\\{0.1,0.3\\}$). Our approach supports general convex
costs and so is able to learn using the ‘right’ cost function (i.e., that is
used in evaluation) for any ${\gamma}$.

Figure 1 (left) shows performance for increasing ${\gamma}$. Benchmark
accuracy on non-strategic data is 81%, but once strategic movement is
permitted, performance of the strategy-blind model drops to $\sim 54\%$ (data
is balanced so chance $=\%50$). The algorithm of Hardt et al. (2016)
anticipates strategic behavior but (wrongly) assumes costs are linear.
Accuracy for ${\gamma}\approx 0$ improves to some extent ($\sim 69\%$), but
remains far below the benchmark. However, as ${\gamma}$ increases, performance
quickly drops to 50%. In contrast, by correctly anticipating strategic
behavior, SERM restores accuracy almost in full for ${\gamma}\geq 0.2$ ($\sim
80\%$).

Figure 2: Trade-off curves of accuracy vs. various measures of social good:
expected utility, social burden, and recourse. Points correspond to varying
degrees of regularization ($\lambda$). For all measures, mild regularization
improves social outcomes at little or no cost to accuracy.

Next, we evaluate our method on additional datasets, focusing on quadratic
cost (as it does not require hand-coded parameters), and varying the degree of
‘gaming’ by scaling the cost by a factor of $t\in\\{0.5,1,2\\}$. Figure 1
(right) compares the performance of SERM to the strategy-blind baseline. As
can be seen, SERM outperforms the blind model by a significant margin and
closely matches the non-strategic benchmark for all datasets and degrees of
gaming.

###  4.2 Regularization for social good

We evaluate our approach of regularizing for social good (Sec. 3.4) on credit,
which has been used in a recent paper on recourse by Ustun et al. (2019). Here
we study how accuracy and social good trade-off under SERM by varying the
amount of regularization $\lambda$. Figure 2 shows results for expected
utility (left), social burden (center), and recourse (right). Each point in
the plots corresponds to a model trained with a different $\lambda$. Results
show that all three measures of social good exhibit a super-linear tradeoff
curve: with mild regularization, a large increase in social good is obtained
at little or no cost to accuracy. This highlights three interrelated points:
that incentives in strategic classification are not fully discordant; that
multiple models can achieve high accuracy; and that of these, our approach to
model selection through regularization is effective at selecting models that
promote favorable social outcomes.

###  4.3 Beyond linear models

We apply our approach to time-series data in financial distress and for our
predictive model we use non-linear recurrent neural networks (RNN) . Each
example in the dataset describes a firm over $t$ time steps using a sequence
of feature vectors ${\bm{x}}=(x^{(1)},\dots,x^{(t)})$, where
$x^{(k)}\in{\mathbb{R}}^{d}$ describes the firm at time $k\leq t$ and $t$
varies across examples ($1\leq t\leq 14$). Labels determine whether the firm
has gone bankrupt at time $t$, and we assume users can modify features only at
this final timepoint $x^{(t)}$. This mimics a setting in which the history of
the firm is fixed, but its features at the time of arbitration can be
manipulated (at some cost). We implement $f$ as a fully-connected RNN with
layers:

$h^{(i)}=\varphi(Wx^{(i)}+Vh^{(i-1)}+a)$

where model parameters $W,V,a$ are tied across layers and activations
$\varphi$ are sigmoidal for all layers but the last, which is used for
prediction. We set the embedded dimension to $10$. Plugging into Eq. (1), the
response mapping becomes:

${\Delta}({\bm{x}})=\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\,\operatorname{sign}(w^{\top}x^{\prime}+v^{\top}h^{(t-1)}+b)-c(x^{(t)},x^{\prime})$

with quadratic cost. This is a special case of Sec. 3.3.1 with
${\phi}(x)=(x^{(t)},h^{(t-1)})$. Since $f$ is linear in $x^{\prime}$ and $c$
is convex in $x^{\prime}$, our CCP approach can be applied (Sec. 3.2).

We experiment with varying history lengths by taking suffixes of fixed size
$k$ of each ${\bm{x}}$. Figure 1 (center) shows results for increasing suffix
lengths $k$. As can be seen, SERM outperforms a blind RNN by roughly $15\%$
for all $k$ and nearly matches the non-strategic benchmark for $k\geq 2$.

Figure 3: An illustrations of various extensions of the role of the cost
function $c$. (Left) Flexibility: cost is linear (arrows show direction) and
is initially ${v}_{0}$, but the system can invest effort to change it.
Learning produces a cost $\hat{{v}}$ that is near the optimal ${v}^{*}$, with
which SERM achieves near-optimal accuracy. (Center) Robustness: Cost is
quadratic (circles show diameter of maximal movement), but the system has only
an estimate $v_{0}$ of the true cost $v^{*}$. Learning aims to be minmax-
optimal with respect to all costs $v\in V$ near $v_{0}$ (ring shows the set
$V$). SERM again learns a near-optimal classifier. (Right) Manifold
constraints: Points are allowed to move only on the quadratic manifold that is
unknown (and hence not encoded in $c$). Our approach is to first learn the
manifold, and then use derived tangents as constraints in optimizing
${\Delta}$. This approximates movement within the manifold and allows SERM to
learn well.

###  4.4 Beyond oracle cost functions

In this section we move beyond the assumption of a fixed and known (‘oracle’)
cost function and study the extensions presented in Sec. 3.3. We use stylized
2D synthetic data that allows us to visually illustrate how our approach
behaves in these extended settings. In each setting we compare SERM to
appropriate _naïve_ and _oracle_ baselines, specified below.

##### Flexible cost functions.

In this setting we assume that the system can modify an initial cost to some
extent. Data is generated by a mixture of two ‘narrow’ MVN distributions with
means $\mu=[-0.5,0]$ (for $y=-1$) and $\mu=[0.5,0]$ ($y=1$) and diagonal
covariances with $\Sigma_{11}=0.1$ and $\Sigma_{22}=1$. We use linear-
separable cost ${c_{\text{lin}}^{{{v}}}}$ (for stability we mix using
${\gamma}=0.005$) and set the initial cost to ${v}_{0}=[0.5,0.5]$. The learner
has flexibility to choose any ${v}\in
V=\\{{v}^{\prime}:\|{v}^{\prime}-{v}_{0}\|_{\infty}\leq 2\\}$. For a naïve
baseline we consider a model that does not modify the cost, i.e., uses
${v}={v}_{0}$. The oracle baseline uses the optimal ${v}^{*}=[2,0]\in V$.

To learn with flexible costs, we use the approach presented in Sec. 3.3.2 and
jointly optimize model parameters $w,b$ and cost parameters ${v}$. Results are
shown in Figure 3 (left). If no strategic movement is allowed, then the
optimal linear classifier having $w=[1,0],b=0$ achieves $\sim 100\%$ (non-
strategic) accuracy. However, with strategic movement under ${v}_{0}$, the
_strategically-optimal_ classifier has weights $w=[0.5,0.5],b=1$. These are
indeed the weights learned by the naïve baseline, which achieves 0.72%
accuracy. However, for ${v}=[1,0]$, the optimal classifier has $w=[1,0],b=1$,
and an oracle baseline that has ${v}^{*}=[1,0]$ learns these weights and
achieves 100%. Our flexible approach learns a near-optimal cost
($\hat{{v}}=[2.3,0.6]$) along with the corresponding optimal model, achieving
97% accuracy.

##### Unknown cost functions.

In this setting we assume that points move according to a ground-truth cost
function that is unknown, and that the system has only an rough estimate of
this cost. Data is generated by a mixture of two symmetric MVN distributions
with means $\mu=[-0.6,0]$ (for $y=-1$) and $\mu=[0.6,0]$ ($y=1$) and diagonal
covariances $\Sigma_{11}=\Sigma_{22}=0.1$. We use an a-symmetric quadratic
cost in which dimensions can differ in scale,
${c_{\text{quad}}^{{v}}}(x,x^{\prime})=\sum_{i=1}^{d}v_{i}(x_{i}-x^{\prime}_{i})^{2}$,
parameterized by $v\in{\mathbb{R}}^{d}$. The ground-truth cost is set to
$v^{*}=(0.5,0.5)$ and the initial estimate to $v_{0}=(2,2)$. Here the oracle
baseline learns using $v^{*}$, and naïve baseline learns under the false
assumption that $v_{0}=v^{*}$.

To learn under an unknown cost, we use the robust minmax approach presented in
Sec. 3.3.3 and train a predictor $f$ to be minmax-optimal w.r.t. a belief set
$V$, which we set to $V=\\{v\in{\mathbb{R}}^{2}:\|v_{0}-v\|_{\infty}\leq
1.7\\}$ (note that $v^{*}\in V$). In this setting optimization is simplified
since it suffices to maximize $v$ over the reduced set
$\\{v_{\text{min}},v_{\text{max}}\\}\subset V$, where in our case
$v_{\text{min}}=[0.3,0.3]$ and $v_{\text{max}}=[3.7,3.7]$. Figure 3 (center)
illustrates the results of learning in this setting. The benchmark on non-
strategic data is $\sim 100\%$, as is the performance of the oracle model on
strategic data. The naïve model obtains 74% accuracy using $v_{0}$. SERM
optimized using the minmax objective achieves $91\%$ accuracy.

##### Manifold constraints.

In this setting we work with a cost function is known and fixed, but assume
that points can move only within a low-dimensional manifold that is unknown to
the system. We use a 1D manifold that satisfies $x_{2}=-x_{1}^{2}$ and
generate data points $x=(x_{1},x_{2})$ using $x_{1}\sim U([-5,5])$ and set
$x_{2}$ according to the manifold constraints. Labels are
$y=\operatorname{sign}(x_{1})$ and the cost is quadratic.

To learn under unknown manifold constraints, we follow the approach outlined
in Sec. 3.3.4, where in the response function ${\Delta}$ the (unknown)
manifold constraints are approximated using (estimated) tangent constraints.
Here, manifold tangents have a close form solution, but for completeness we
pursue a more general approach and learn them. In particular, we learn the
manifold using a contractive autoencoder (CAE) (Rifai et al., 2011b) with 2
stacked hidden layers of width 20 and sigmoidal activations. CAEs minimize
reconstruction error under a regularization term that penalizes Jacobian
absolute values. Balancing between these two forces encourages learned
embeddings that permit movement only in directions that are useful for
reconstruction, i.e., along the manifold. Jacobians also provide manifold
tangents, and we compute these as proposed for manifold tangent classifiers
(MTC) in Rifai et al. (2011a).

Figure 3 (right) shows results for this setting. The problem is separable and
so optimal non-strategic accuracy is 100%. A naïve baseline which does not
account for manifold constraints wrongly assumes points can move freely across
the $x_{1}$-axis and places all weight on this axis. This false assumption
reduces accuracy to 52%—much lower than that of a blind baseline, which
achieves 89%. Our SERM approach augmented with MTC tangents over an estimated
CAE manifold reaches 98% accuracy.

##  5 Conclusions

In this paper we proposed a practical approach to learning in strategic
classification. By differentiating through user responses, our approach allows
for effective and efficient learning in diverse settings. Key to our approach
were differentiable optimization solvers; we are hopeful that future advances
in this field could be utilized within our framework to support more elaborate
forms of user responses. Strategic classification has so far been mostly
studied under a theoretical lens; our work takes a first step towards making
learning practical, with the aim of promoting discussion amongst
practitioners, applied researchers, and those interested in social aspects of
learning. Our approach to regularization serves as a reminder that strategic
classification is a game for two players, and that learning can, and should,
aid in promoting the interests of all parties involved. We believe that a
responsible approach to applied strategic classification can be beneficial to
both systems and the users they serve.

## References

  * Agrawal & Boyd (2020) Agrawal, A. and Boyd, S.  Differentiating through log-log convex programs.  _arXiv preprint arXiv:2004.12553_ , 2020.
  * Agrawal et al. (2019a) Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z.  Differentiable convex optimization layers.  In _Advances in neural information processing systems_ , pp. 9562–9574, 2019a.
  * Agrawal et al. (2019b) Agrawal, A., Barratt, S., Boyd, S., Busseti, E., and Moursi, W. M.  Differentiating through a cone program.  _arXiv preprint arXiv:1904.09043_ , 2019b.
  * Ahmadi et al. (2020) Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K.  The strategic perceptron.  Available at https://arxiv.org/abs/2008.01710, 2020.
  * Alon et al. (2020) Alon, T., Dobson, M., Procaccia, A. D., Talgam-Cohen, I., and Tucker-Foltz, J.  Multiagent evaluation mechanisms.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 1774–1781, 2020.
  * Amos & Kolter (2017) Amos, B. and Kolter, J. Z.  Optnet: Differentiable optimization as a layer in neural networks.  In _International Conference on Machine Learning_ , pp. 136–145, 2017.
  * Bechavod et al. (2020) Bechavod, Y., Ligett, K., Wu, Z. S., and Ziani, J.  Causal feature discovery through strategic modification.  Available at https://arxiv.org/abs/2002.07024, 2020.
  * Berthet et al. (2020) Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F.  Learning with differentiable perturbed optimizers.  _arXiv preprint arXiv:2002.08676_ , 2020.
  * Brückner & Scheffer (2009) Brückner, M. and Scheffer, T.  Nash equilibria of static prediction games.  In _Advances in neural information processing systems_ , pp. 171–179, 2009.
  * Brückner & Scheffer (2011) Brückner, M. and Scheffer, T.  Stackelberg games for adversarial prediction problems.  In _Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pp. 547–555, 2011\.
  * Brückner et al. (2012) Brückner, M., Kanzow, C., and Scheffer, T.  Static prediction games for adversarial learning problems.  _The Journal of Machine Learning Research_ , 13(1):2617–2654, 2012.
  * Chen et al. (2019) Chen, Y., Liu, Y., and Podimata, C.  Learning strategy-aware linear classifiers.  _arXiv preprint arXiv:1911.04004_ , 2019.
  * Chen et al. (2020) Chen, Y., Wang, J., and Liu, Y.  Strategic recourse in linear classification.  _arXiv preprint arXiv:2011.00355_ , 2020.
  * Costa et al. (2014) Costa, H., Merschmann, L. H., Barth, F., and Benevenuto, F.  Pollution, bad-mouthing, and local marketing: The underground of location-based social networks.  _Information Sciences_ , 279:123–137, 2014.
  * Dal Pozzolo et al. (2015) Dal Pozzolo, A., Caelen, O., Johnson, R. A., and Bontempi, G.  Calibrating probability with undersampling for unbalanced classification.  In _2015 IEEE Symposium Series on Computational Intelligence_ , pp. 159–166. IEEE, 2015.
  * Djolonga & Krause (2017) Djolonga, J. and Krause, A.  Differentiable learning of submodular models.  In _Advances in Neural Information Processing Systems_ , pp. 1013–1023, 2017.
  * Dong et al. (2018) Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z. S.  Strategic classification from revealed preferences.  In _Proceedings of the 2018 ACM Conference on Economics and Computation (EC)_ , pp. 55–70, 2018.
  * Großhans et al. (2013) Großhans, M., Sawade, C., Brückner, M., and Scheffer, T.  Bayesian games for adversarial regression problems.  In _International Conference on Machine Learning_ , pp. 55–63, 2013\.
  * Gupta et al. (2019) Gupta, V., Nokhiz, P., Roy, C. D., and Venkatasubramanian, S.  Equalizing recourse across groups.  _arXiv preprint arXiv:1909.03166_ , 2019.
  * Hardt et al. (2016) Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M.  Strategic classification.  In _Proceedings of the 2016 ACM conference on innovations in theoretical computer science_ , pp. 111–122, 2016.
  * Heidari et al. (2019) Heidari, H., Nanda, V., and Gummadi, K.  On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning.  In _36th International Conference on Machine Learning_ , pp. 2692–2701, 2019.
  * Hu et al. (2019) Hu, L., Immorlica, N., and Vaughan, J. W.  The disparate effects of strategic manipulation.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*)_ , pp. 259–268, 2019.
  * Joshi et al. (2019) Joshi, S., Koyejo, O., Vijitbenjaronk, W., Kim, B., and Ghosh, J.  Towards realistic individual recourse and actionable explanations in black-box decision making systems.  _arXiv preprint arXiv:1907.09615_ , 2019.
  * Karimi et al. (2020a) Karimi, A.-H., Barthe, G., Schölkopf, B., and Valera, I.  A survey of algorithmic recourse: definitions, formulations, solutions, and prospects.  _arXiv preprint arXiv:2010.04050_ , 2020a.
  * Karimi et al. (2020b) Karimi, A.-H., von Kügelgen, J., Schölkopf, B., and Valera, I.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach.  _Advances in Neural Information Processing Systems_ , 33, 2020b.
  * Kleinberg & Raghavan (2019) Kleinberg, J. M. and Raghavan, M.  How do classifiers induce agents to invest effort strategically?  In _Proceedings of the 2019 ACM Conference on Economics and Computation, (EC)_ , pp. 825–844, 2019.
  * Miller et al. (2020) Miller, J., Milli, S., and Hardt, M.  Strategic classification is causal modeling in disguise.  In _International Conference on Machine Learning_ , pp. 6917–6926. PMLR, 2020.
  * Milli et al. (2019) Milli, S., Miller, J., Dragan, A. D., and Hardt, M.  The social cost of strategic classification.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*)_ , pp. 230–239, 2019.
  * Perdomo et al. (2020) Perdomo, J. C., Zrnic, T., Mendler-Dünner, C., and Hardt, M.  Performative prediction.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020.
  * Quionero-Candela et al. (2009) Quionero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D.  _Dataset shift in machine learning_.  The MIT Press, 2009.
  * Rifai et al. (2011a) Rifai, S., Dauphin, Y. N., Vincent, P., Bengio, Y., and Muller, X.  The manifold tangent classifier.  _Advances in neural information processing systems_ , 24:2294–2302, 2011a.
  * Rifai et al. (2011b) Rifai, S., Vincent, P., Muller, X., Glorot, X., and Bengio, Y.  Contractive auto-encoders: Explicit invariance during feature extraction.  In _Icml_ , 2011b.
  * Shavit et al. (2020) Shavit, Y., Edelman, B., and Axelrod, B.  Causal strategic linear regression.  In _International Conference on Machine Learning_ , pp. 8676–8686. PMLR, 2020.
  * Shen et al. (2016) Shen, X., Diamond, S., Gu, Y., and Boyd, S.  Disciplined convex-concave programming.  In _2016 IEEE 55th Conference on Decision and Control (CDC)_ , pp. 1009–1014. IEEE, 2016.
  * Sundaram et al. (2020) Sundaram, R., Vullikanti, A., Xu, H., and Yao, F.  Pac-learning for strategic classification.  _arXiv preprint arXiv:2012.03310_ , 2020.
  * Tan et al. (2020) Tan, Y., Terekhov, D., and Delong, A.  Learning linear programs from optimal decisions.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Ustun et al. (2019) Ustun, B., Spangher, A., and Liu, Y.  Actionable recourse in linear classification.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , pp. 10–19, 2019.
  * Venkatasubramanian & Alfano (2020) Venkatasubramanian, S. and Alfano, M.  The philosophical basis of algorithmic recourse.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , pp. 284–293, 2020.
  * Yuille & Rangarajan (2003) Yuille, A. L. and Rangarajan, A.  The concave-convex procedure.  _Neural computation_ , 15(4):915–936, 2003.
  * Zhang & Conitzer (2021) Zhang, H. and Conitzer, V.  Incentive-aware pac learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021.

##  Appendix A Experimental details

###  A.1 Data

Across all experiments we use four real datasets:

  * •

Spam999Data can be obtained from the authors of Costa et al. (2014).. This
dataset includes features of authentic users and spammers from a large social
network, and was used in Hardt et al. (2016). The data includes $n=7,076$
examples and $d=15$ features. Features include number of words in the post,
number of phone numbers in the post and number of followers of the user. The
data is balanced, i.e., there is an equal number of positive ($y=1$) and
negative ($y=-1$) examples.

  * •

Credit101010https://github.com/ustunb/actionable-recourse. This dataset
includes features describing credit card spending patterns, along with labels
indicating default on payment. We use the same version used in the recourse
paper by Ustun et al. (2019), and adopt their preprocessing procedure (see
link). The original dataset includes $n=30,000$ examples and $d=11$ Features.
Features include age, amount of bill statement and history of past payments.
For training time purposes, in our experiments we used a random balanced
subset of 3,000 examples, as we did not notice any changes in performance for
larger sample set sizes (which is plausible given that $f$ is linear and $d$
here is small).

  * •

Fraud111111https://www.kaggle.com/mlg-ulb/creditcardfraud (Dal Pozzolo et al.,
2015). This dataset includes credit card transactions that are either genuine
or fraudulent. The original data includes $n=284k$ examples and $d=29$
features. Due to confidentiality issues, feature information is not provided.
The original dataset is highly imbalanced, and for our experiments we take all
available negative examples and uniformly sample a matching number of positive
examples, giving a total of $n=984$ balanced examples.

  * •

Finance121212https://www.kaggle.com/shebrahimi/financial-distress. This
dataset includes time-series data describing firms along with an indication of
their level of financial distress (denoted $\mathtt{fd}$). Each series ends
either at the maximal time step of $t=14$ or earlier if the firm has gone
bankrupt. Bankrupcy is declared when $\mathtt{fd}<-0.5$, and we use this
definition to determine labeles $y$. The data includes $n=422$ time-series
examples, with each time step within each example described using $d=83$
anonymized numerical features.131313The data includes a single categorical
feature, which we discard. The ratio of positive (i.e., non-bankrupt) examples
is 67.7%. Time-series lengths are in the range $t\in\\{0,\dots,14\\}$
(inclusive), with mean=8.7 and median=4.9.

Features in all datasets were standardized (i.e., scaled to obtain a mean of
zero and standard deviation of one) on the train set. To ensure consistent
behavior in term of the effect of the cost function on movement, features in
each datasets were further divided by $\sqrt{d}$ where $d$ is the (per-
dataset) number of features.

###  A.2 Training and tuning

For all experiments we use a 60-20-20 split into train, validation, and test
sets, respectively, and all results are averaged over multiple random splits.
For optimization we use ADAM, where within each epoch use randomize batches of
size 24 for financial distress and fraud 64 for credit and 128 for spam chosen
according to their respective number of examples, and early stop w.r.t.
accuracy on the validation set. For all methods, learning rates were set
according to the validation set. For $\sigma$ we set $\tau=1$ for training and
$\tau=0.2$ for testing, and set the CCP tolerance to 0.001, but note results
are robust to variations in these.

###  A.3 CCP procedure

We use our own implementation of CCP, based on Shen et al. (2016), and using
the publicly-available SCS
solver141414https://web.stanford.edu/~boyd/papers/scs.html for solving the
concave sub-problems appearing in each iteration. Algorithm 1 includes
pseudocode for our procedure. We use the notation:

$\sigma_{\cup}(x;f)=\frac{1}{2}\sqrt{\left({\tau}^{-1}f(x)+1\right)^{2}+1},\qquad\sigma_{\cap}(x;f)=-\frac{1}{2}\sqrt{\left({\tau}^{-1}f(x)-1\right)^{2}+1},$

for the convex and concave parts of $\sigma$, respectively.

Algorithm 1 CCP forward pass

1: Initialize $t=0,\delta=\infty$

2: $x^{0}=x$

3: repeat

4: $t=t+1$

5: $g=\nabla_{x}\sigma_{\cup}(x^{t-1};f)$ {linearized convex term at
$x^{t-1}$}

6:
$x^{t}=\operatorname*{argmax}_{x^{\prime}}g^{\top}x^{\prime}+\sigma_{\cap}(x^{\prime};f)-c(x,x^{\prime})$
{get argmax of current concave proxy}

7: until convergence

8: $g^{t}=\nabla_{x}\sigma_{\cup}(x^{t};f)$ {final linearized term, to be used
for backward pass}

9: return $x^{t},g^{t}$

In practice we terminate when $\|x^{t}-x^{t-1}\|_{2}\leq\mathtt{tol}$ or after
at most $t=100$ iterations. In our experiments we used $\mathtt{tol}=0.001$,
but the vast majority of instances terminated after $t=5$ iterations. The
algorithm returns two objects: the approximate argmax $x^{t}$ used in the
forward pass, and the linearization $g^{t}$ (of which $x^{t}$ is an exact
argmax) used to parameterize the convex optimization layer to enable a
backwards pass.

###  A.4 Runtime evaluation

In this section we present results on the runtime of our method. Presumably
the main overhead in our approach is computing the CCP solution and surrogate
in the forward pass. Note however that while each call to solver may be
expensive, jointly solving for all examples in a batch (i.e., solving $k$
independent problems in one call, where $k$ is the batch size) can greatly
reduce this overhead. All experiments were run on a single laptop (Intel(R)
Core(TM) i7-7500U CPU @ 2.70GHz 2.90 GHz, 16.0 GB RAM).

To evaluate this, we run an experiment on synthetic data and for varying batch
sizes. We use scikit-learn’s make_classification function, using 750 train
samples, 250 validation samples, $d=5$ features, balanced classes, and 0.01
label noise. 4 (two left-most plots) show runtime results for increasing batch
size $k$ and training for 5 epochs. We consider two alternatives to setting
the number of CCP iterations: (i) convergence to tolerance 0.001 on average
across examples in the batch (left), and (ii) a slowly increasing, uniform
number of iterations, with the number of iterations initialized at one and
increased by one after each epoch (right). As can be seen, increasing the
batch size greatly improves overall runtime, as well as the the relative
runtime of CCP.

We also report runtime on the real datasets used in Sec. 4.1. For equalized
comparison we set the number of epochs to 7. Batch sizes were set per dataset
as described in Sec. A.2 (as noted, these were not chosen to optimize for
speed). Figure 4 (two right-most plots) show total train times and relative
CCP times for a all datasets for both stopping criteria.

Figure 4: Runtime on synthetic data (varying CCP batch size) and real data
(fixed batch size).

##### Code.

Our code can be obtained at: https://github.com/SCMP-anonymous/SCMP.


11institutetext: University of Minnesota, Twin Cities, Minnesota,
USA22institutetext: Mayo Clinic, Rochester, Minnesota, USA 33institutetext:
Adler Planetarium, Chicago, Illinois, USA 44institutetext: The Francis Crick
Institute, London, UK

# TCuPGAN: A novel framework developed for optimizing human-machine
interactions in citizen science

Ramanakumar Sankar 11 Kameswara Mantha 11 Lucy Fortson 11 Helen Spiers Thomas
Pengo 4411 Douglas Mashek 11 Myat Mo 11 Mark Sanders 22 Trace Christensen 22
Jeffrey Salisbury 22 Laura Trouille 33

###### Abstract

In the era of big data in scientific research, there is a necessity to
leverage techniques which reduce human effort in labeling and categorizing
large datasets by involving sophisticated machine tools. To combat this
problem, we present a novel, general purpose model for 3D segmentation that
leverages patch-wise adversariality and Long Short-Term Memory to encode
sequential information. Using this model alongside citizen science projects
which use 3D datasets (image cubes) on the Zooniverse platforms, we propose an
iterative human-machine optimization framework where only a fraction of the 2D
slices from these cubes are seen by the volunteers. We leverage the patch-wise
discriminator in our model to provide an estimate of which slices within these
image cubes have poorly generalized feature representations, and
correspondingly poor machine performance. These images with corresponding
machine proposals would be presented to volunteers on Zooniverse for
correction, leading to a drastic reduction in the volunteer effort on citizen
science projects. We trained our model on $\sim 2300$ liver tissue 3D electron
micrographs. Lipid droplets were segmented within these images through human
annotation via the ‘Etch A Cell - Fat Checker’ citizen science project, hosted
on the Zooniverse platform. In this work, we demonstrate this framework and
the selection methodology which resulted in a measured reduction in volunteer
effort by more than $60\%$. We envision this type of joint human-machine
partnership will be of great use on future Zooniverse projects.

###### Keywords:

Generative model human-machine optimization volume segmentation.

##  1 Introduction

Improvements in data collection methodology such as robotic surveys in
astrophysics, or electron microscope advancements in bio-medicine, have led to
an unprecedented growth in data production rates [10, 8]. The analysis of much
of these data still requires human effort. Hence, to efficiently analyze these
large datasets, it is critical to consider leveraging human-machine
optimization frameworks, such as active learning strategies with human-in-the-
loop ideologies [4, 9]. One possible framework is to (1) use a machine model
to provide an initial analysis of the data; (2) identify poorly performing
data; (3) present this subset of data to humans for correction; and (4) use
the human-corrected data to refine the machine. Such a framework would enable
fast processing of large amounts of data, speeding the analytical pipeline and
ensuring more efficient application of human effort. However, one of the
greatest challenges in implementing such a framework is the accurate
identification of data with poor machine performance, particularly when ground
truth labels are unavailable. While uncertainty prediction has become a strong
component of new machine/deep-learning studies [5], most existing techniques
work well for classification tasks [3]. Generative models are much more
difficult due to their more complex architectures and training regiment and
would likely require more sophisticated training [2]. In this work, we focus
on using ad-hoc methods within the generative model (primarily the learnt
adversariality), as a proxy for machine uncertainty.

In this study, we use data from the Etch A Cell - Fat Checker
project111https://www.zooniverse.org/projects/dwright04/etch-a-cell-fat-
checker, which is a cell biology citizen science project hosted on
Zooniverse.org to identify lipid droplets in electron micrographs. Using this
project as a case study, we show how machine models can be used to predict
which data may benefit from human analysis. To satisfy the dual role of
improving the completion rate of the project by using machine models to
classify large fractions of the data and to determine poorly performing data
to present to volunteers, we present the Temporal Cubic Patch Generative
Adversarial Network (TCuPGAN), a generative model that works on image cubes
(3D images, like volume electron microscopy data) or video data to do 3D
segmentation. We apply our model to data from the Etch a Cell - Fat Checker
project and present our results from testing our framework on this dataset. In
this study, we use the discriminator component as a method for identifying
poorly performing data (i.e., those that generalize poorly between the input
image cube and the target segments). Our selection method can identify either
image cubes or individual slices which show poor machine performance; these
can be shown to the volunteers for refinement, thereby significantly reducing
both the project completion time and the volunteer effort.

##  2 Methods

We demonstrate our work on the TCuP-GAN, which is based on a generative Image-
to-Image translational model [PatchGAN; 6]. PatchGAN is 2D image segmentation
model, which uses the U-Net architecture, and features both a generative and
discriminative component. In our model generator, we replace the 2D
convolutional layers in the PatchGAN architecture with 2D convolutional Long
Short-Term Memory (LSTM) layers to simultaneously capture both the 2D spatial
information in each slice as well as the correlations along the third
dimension (depth axis in image cubes, or time axis for videos). The LSTM
layers extract both the feature vectors ($h_{t}$, which encodes the image
features as a function of depth/time) and the cell state ($c$, which captures
the cumulative spatial correlation of the features across the depth/time axis)
[7]. Subsequently, the learnt features encode both temporal (or depth-wise)
and spatial correlation information. We skip both the $h$ and the $c$ vectors
across the bottleneck from the encoder to the decoder as part of the U-Net
architecture.

The discriminator is a patch-wise binary classifier that takes a concatenation
of the input image and its corresponding ground truth or generated mask and
outputs a $8\times 8$ probability matrix per depth slice. The discriminator is
a series of 3D convolutions with kernel size $(1,3,3)$, followed by Layer
Normalization. We use the LeakyReLU activation with $\alpha=0.2$ for all
layers except the final convolutional layer, which has a Sigmoid output on a
single channel. Each unit of the output of the discriminator represents a
patch of the input image, and provides the probability that the patch is real.
For each slice, we take the mean and variance of its discriminator scores for
our test metrics.

###  2.1 Etch-a-Cell: FatChecker data

To train the model, we use data from Etch a Cell - Fat Checker where
volunteers are presented with individual 2D slices and asked to annotate the
lipid droplets. We aggregate the volunteer responses [8] and build the image
cube by stacking the 2D images and their corresponding masks. This Zooniverse
project presents $1200\times 1200$ pixel sized 2D image slices to the
volunteers, who annotate the outline of the lipid droplets. For each 2D slice,
a binary consensus mask is generated by aggregating the annotations of
multiple volunteers [8], where pixels corresponding to lipid regions are
indicated by $1$ and background is $0$. In this work, we stack these different
2D slices to generate their corresponding 3D image cubes with sizes
$1200\times 1200\times 10$. We then augment these cubes by resizing them to
$512\times 512\times 10$ and applying a TenCrop routine to generate $5$
overlapping crops of sizes $256\times 256\times 10$ (positioned at center,
top-left, bottom-left, top-right, bottom-right) and their respective vertical
flips. This yields a total of $2270$ image cubes with final dimensions of
$256\times 256\times 10$. We use the Focal Tversky Loss [FTL; 1]) to train the
model, which is a generalized version of the Tversky Loss (TL) defined in
terms of the Tversky Index (TI) as,

$TI={TP}/{(TP+\alpha FN+\beta FP)}\rightarrow TL=(1-TI)\rightarrow
FTL=(TL)^{\gamma}$ (1)

where $TP$, $FN$ and $FP$ are the true positive, false negative and false
positive pixels in each slice. The $\gamma$ parameter guides the model to
focus on harder ($\gamma<1$) vs. easier ($\gamma>1$) examples. We use
$\alpha=0.7$, $\beta=0.3$ and $\gamma=0.7$. For the discriminator
optimization, we use the Binary Cross-Entropy (BCE) loss.

##  3 Results

Figure 1: Results from our study. (a) Histogram of mean discriminator scores
per slice. (b) Distribution of mean and variance in discriminator score, per
slice, with the corresponding segmentation loss. We can use this distribution
to make cuts on which slices to show volunteers (region left of the black
line). (c, d) Comparison of slices with high discriminator score (more
realistic, c) vs low discriminator score (less real, d), with the rows in
order showing the input image slice, mask from aggregating volunteers’
annotations, the machine predicted segmentation and the patch discriminator
output. Blue regions correspond to high discriminator value (more real), while
red is low discriminator value (less real). Note how the poorly performing
subjects show large feature confusion within the image necessitating further
refinement by volunteers.

The model accuracy, precision and recall are 89.1%, 49.3% and 65.4%,
respectively. On Zooniverse, volunteers were asked not to annotate lipid
droplets that were not fully visible, but due to our augmentation methods
(i.e., cropping of the image cubes) there were cases where partially cropped
lipid droplets were shown to the model. As a result, the model learnt to pick
up lipid droplets on the edges where volunteers did not annotate any, leading
to the reduced precision.

Figure 1 presents the test of our proposed framework: panel (a) shows the
distribution of discriminator scores for the subjects in our model, panel (b)
shows the relation between the discriminator and segmentation loss, and panels
(c) and (d) show the comparison of image cubes with high (i.e., more realistic
segmentation) and low (i.e., more unrealistic/poorly generalized segmentation)
discriminator scores, respectively. It is clear that the discriminator has
learnt the features corresponding to the lipid droplets (dark circles in the
image), and is able to effectively identify where the generator fails to
predict these droplets. In fact, the discriminator is able to also show which
locations in the image correspond to poor generalization (blue is more real,
while red is more fake). The red regions correspond to features that the
generator needs to get better at identifying. Images with large red regions
can be passed to volunteers to refine the generator’s annotation and improve
the machine accuracy from re-training.

Figure 1a shows the histogram of discriminator scores for each slice in the
dataset (with 1 being very realistic and 0 being unrealistic). We found that
while the histogram shows that there are several slices with low discriminator
scores (i.e., more unrealistic), there is better separability between slices
when we also incorporate the 2D variation in the discriminator score per slice
(see Figure 1b). The selection cut described above can the be done by
investigating the relation between the mean and the variance in the
discriminator score and segmentation loss (Figure 1b). A high discriminator
mean corresponds to a more realistic image, while high discriminator variance
points to large variation in the generator’s performance for that cube. These
values are correlated with the segmentation loss $TL$ (i.e., high mean and low
variance generally correspond to low segmentation errors), and vice-versa. We
can use a selection cut on the discriminator score that would preferentially
pick poor performing images and pass it to the volunteers for refinement. For,
example, the selection cut proposed in Figure 1b is obtained by choosing a
sample of slices with $TL<0.3$, which produces 9362 slices out of the total of
22700 (a decrease of $64\%$ in the number of images shown to volunteers).

##  4 Conclusions

We have developed the TCuPGAN, a Convolutional LSTM-based image cube/video
segmentation model that simultaneously learns both the 2D spatial and temporal
(or depth) signatures of the data. We applied this model on a dataset of
microscopy images of the liver tissues from the Etch a Cell - Fat Checker
citizen science project on Zooniverse to identify lipid droplets. We find that
the adversarial component of the model is effective at identifying slices with
poor machine segmentation, and these slices can be provided to the volunteers
to correct the machine annotation. Future directions of this work will include
deploying a live test project on Zooniverse with this ‘correct-a-machine’
framework to test the increase in project completion rates; we anticipate that
this test will increase the applicability of this model to other use cases on
the Zooniverse platform and further reduce the number of images seen by
volunteers.

## References

  * [1] Abraham, N., Mefraz Khan, N.: A Novel Focal Tversky loss function with improved Attention U-Net for lesion segmentation. arXiv e-prints arXiv:1810.07842 (Oct 2018)
  * [2] Arikan, M., Sallo, F., Montesel, A., Ahmed, H., Hagag, A., Book, M., Faatz, H., Cicinelli, M., Meshkinfamfard, S., Ongun, S., et al.: Deep active learning for robust biomedical segmentation. bioRxiv pp. 2023–03 (2023)
  * [3] Chua, M., Kim, D., Choi, J., Lee, N.G., Deshpande, V., Schwab, J., Lev, M.H., Gonzalez, R.G., Gee, M.S., Do, S.: Tackling prediction uncertainty in machine learning for healthcare. Nature Biomedical Engineering 7(6), 711–718 (2023)
  * [4] Fortson, L., Wright, D., Lintott, C., Trouille, L.: Optimizing the human-machine partnership with Zooniverse. In: CI 2018: ACM Collective Intelligence. ACM, http://arxiv.org/abs/1809.09738 (2018), http://arxiv.org/abs/1809.09738
  * [5] Grote, T., Berens, P.: Uncertainty, evidence, and the integration of machine learning into medical practice. In: The Journal of Medicine and Philosophy: A Forum for Bioethics and Philosophy of Medicine. vol. 48, pp. 84–97. Oxford University Press US (2023)
  * [6] Isola, P., Zhu, J.Y., Zhou, T., Efros, A.A.: Image-to-image translation with conditional adversarial networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 1125–1134 (2017)
  * [7] Shi, X., Chen, Z., Wang, H., Yeung, D.Y., Wong, W.k., Woo, W.c.: Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting. arXiv e-prints arXiv:1506.04214 (Jun 2015)
  * [8] Spiers, H., Songhurst, H., Nightingale, L., de Folter, J., Community, Z.V., Hutchings, R., Peddie, C.J., Weston, A., Strange, A., Hindmarsh, S., et al.: Deep learning for automatic segmentation of the nuclear envelope in electron microscopy data, trained with volunteer segmentations. Traffic (Copenhagen, Denmark) 22(7), 240–253 (2021)
  * [9] Walmsley, M., Scaife, A.M.M., Lintott, C., Lochner, M., Etsebeth, V., Géron, T., Dickinson, H., Fortson, L., Kruk, S., Masters, K.L., Mantha, K.B., Simmons, B.D.: Practical galaxy morphology tools from deep supervised representation learning. MNRAS513(2), 1581–1599 (Jun 2022). https://doi.org/10.1093/mnras/stac525
  * [10] Wright, D.E., Fortson, L., Lintott, C., Laraia, M., Walmsley, M.: Help me to help you: Machine augmented citizen science. Trans. Soc. Comput. 2(3) (nov 2019). https://doi.org/10.1145/3362741, https://doi.org/10.1145/3362741