# Generalized Strategic Classification and the Case of Aligned Incentives

Sagi Levanon  Nir Rosenfeld

###### Abstract

Strategic classification studies learning in settings where self-interested
users can strategically modify their features to obtain favorable predictive
outcomes. A key working assumption, however, is that “favorable” always means
“positive”; this may be appropriate in some applications (e.g., loan
approval), but reduces to a fairly narrow view of what user interests can be.
In this work we argue for a broader perspective on what accounts for strategic
user behavior, and propose and study a flexible model of _generalized
strategic classification_. Our generalized model subsumes most current models,
but includes other novel settings; among these, we identify and target one
intriguing sub-class of problems in which the interests of users and the
system are _aligned_. This setting reveals a surprising fact: that standard
max-margin losses are ill-suited for strategic inputs. Returning to our fully
generalized model, we propose a novel max-margin framework for _strategic_
learning that is practical and effective, and which we analyze theoretically.
We conclude with a set of experiments that empirically demonstrate the utility
of our approach.

Machine Learning, ICML

##  1 Introduction

Machine learning is increasingly being used in domains where human users are
the subject of prediction. But when users stand to gain from certain
predictive outcomes, they may be prone to act in ways that promote the
outcomes they desire. A growing recognition of this idea has led to much
recent interest in methods that are able to account for how humans respond to
learned models. One such line of research considers the problem of _strategic
classification_ (Brückner & Scheffer, 2011; Hardt et al., 2016), in which
users can modify their features (at some cost) to obtain favorable
predictions, and the goal in learning is to be robust to such behavior. Common
tasks include loan approval, university admissions, and hiring—all examples in
which users have incentive to be classified positively, and in which systems
must anticipate user behavior in order to predict well. Strategic
classification is appealing as a learning problem in that it is simple yet
succinctly captures a natural form of tension that can arise between systems
and their users. This has made it the focus of many recent works (Sundaram et
al., 2021; Zhang & Conitzer, 2021; Levanon & Rosenfeld, 2021; Ghalme et al.,
2021; Jagadeesan et al., 2021; Zrnic et al., 2021; Estornell et al., 2021;
Lechner & Urner, 2021).

But despite the elegant way in which it extends standard binary
classification, strategic classification remains narrow in the scope of
strategic behavior it permits. A key working assumption is that while the
system is interested in correct predictions, users are interested in
_positive_ predictions. One artifact of this is that learning is essentially
restricted to settings in which one outcome is globally “good” for users
(e.g., loan approved), while the other is “bad” (e.g., loan denied); another
is that users are grimly framed as always acting to “game” the system. But not
all outcomes are “good” or “bad”, and not all strategic behavior is gaming.
Here we argue for a broader perspective on what constitutes strategic behavior
in classification.

Towards this goal, we propose and study the novel problem of _generalized
strategic classification_ (GSC), which includes standard strategic
classification (SC) as a special case, as well as other rich problem sub-
classes. Our formulation relies on the simple observation that strategic
behavior depends on three key elements: (i) what users _know_ , (ii) what
users _want_ , and (iii) how users _use_ their knowledge to promote their
goals. For example, in standard strategic classification, users know their
true features (whereas the system does not); want positive predictions (rather
than correct predictions); and are willing to invest effort or resources to
obtain them (by applying costly feature modifications). But other forms of
knowledge, aims, and means lead to other types of strategic interactions
between a system and its users. The power of our framework lies in providing a
simple handle for reasoning about the effects of general forms of interaction
on learning.

Within the space of GSC problems, of particular interest to us is a sub-class
of problems we refer to as _incentive-aligned strategic classification_
(IASC). Aligned incentives naturally arise in settings where predictions are
intended to assist users; in particular, they are _for_ users, rather than
_about_ users (as in loans, hiring, etc.). Applications in which incentives
align are widespread—recommendation systems, search engines, and online
marketplaces are all examples in which prediction is provided by the system as
a service to its users, and both parties are interested in accurate
predictions.

From a modeling perspective, the key difference between SC and IASC is simply
that instead of wanting positive predictions, users now want correct
predictions—just as the system does. But from a learning perspective, this
mild change transforms the learning problem from one of robustness (to gaming)
to one of cooperation, and the key challenge in learning now lies in how to
best utilize individual strategic behavior to promote collective improvement.
Note this has concrete implications for transparency: to successfully promote
its own goals, it should be in the best interest of the system to clearly
communicate its predictive model to users, so that strategic updates are
maximally effective (c.f. SC, where the implications of transparency can be
ambiguous (Ghalme et al., 2021)).

How should learning be done in incentive-aligned settings? A natural approach
would be to simply take the conventional ERM rule and replace the original
features, $x$, with their strategically-modified counterparts, $x^{\prime}$.
Indeed, this approach is sensible when applied to the _true error_ , i.e., the
0/1-loss. However, our first key result shows that the argument breaks once
this naïve approach is applied to a _proxy loss_ , such as the hinge loss.
This has concrete practical implications; as we show, this naïve approach is
prone to adverse generalization issues, and is unnecessarily computationally
complex. As a solution, and with initial focus on a special instance of IASC,
we propose a new _strategic hinge loss_ , which builds on an adaptation of the
notion of margin to strategic settings. The strategic hinge has a simple and
differentiable form, and so can be optimized end-to-end. For generalization,
we give Rademacher-based bounds showing that the strategic hinge loss enjoys
favorable guarantees.

Building on these results, we return to the most general class of GSC
problems, and show that the principles underlying our analysis for IASC hold
more broadly; i.e., that naively applying the hinge loss to strategic inputs
is not only suboptimal, but can nullify the concept of ‘margins’ entirely. We
extend both of our modeling and theoretical contributions to the general case.
First, we give a formula for constructing an appropriate strategic hinge proxy
for any instance of GSC, this relying on a careful reinterpretation of the
definition of margin. We show that, like for IASC, the strategic proxies for
several notable sub-classes are simple and differentiable, and have intuitive
interpretations. Second, we extend our generalization bounds to hold for GSC
in its broadest form; we also give specialized bounds for several sub-classes,
and study their relations. Our bounds have a tight connection to, and closely
match, standard non-strategic bounds.

We conclude with an empirical section that includes two sets of experiments.
The first set of experiments target generalization, and in this way,
complement our theoretical findings. Here we evaluate performance on synthetic
data and for several types of strategic environments. The second set of
experiments consider an elaborate incentive-aligned environment, designed to
mimic a recommendation setting in which users act on the basis of private,
personalized past experiences. For this setting, we use data based on a real
fashion-related dataset (with simulated user responses). The strategic hinge
in this setting does _not_ have a simple form; nonetheless, we propose a
tractable approach for its optimization. Our results demonstrate that our
approach is efficient and effective. Code is publically available at
https://github.com/SagiLevanon1/GSC.

Taken together, our practical and theoretical results suggest that GSC is an
appropriate, well-balanced generalization: it is flexible in the strategic
behavior it permits and the learning problems that follow, but at the same
time, is precise enough to preserve general statistical properties and
empirical phenomena of conventional classification tasks.

###  1.1 Related work

The literature on strategic classification is growing rapidly. 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). Some studies focus on
theoretical aspects; for example, Zhang & Conitzer (2021) and Sundaram et al.
(2021) extend VC theory to account for strategic behavior. Other works focus
on practical aspects, such as Levanon & Rosenfeld (2021) who propose a
differentiable learning framework, and Eilat et al. (2022) who study
strategically-robust learning for graph-based classifiers. Our work includes a
blend of both theory and practice.

There have also been efforts to extend strategic classification beyond its
original formulation. For example, Ghalme et al. (2021) study a setting where
users respond based on individually-estimated classifiers, and Jagadeesan et
al. (2021) consider users having noisy estimates of model parameters. Sundaram
et al. (2021) make the connection to adversarial learning, and propose a
unified model allowing for more general forms of user response. Our framework
subsumes these earlier settings, and generalizes beyond.

Several works in the adversarial literature have suggested margin maximization
as a means to achieve robustness (Ding et al., 2020; Zhou et al., 2012). Our
work extends beyond this idea and studies the general role margins play under
strategic behavior, theoretically and methodologically.

Finally, we note there are many works within the broader area of strategic-
aware learning, focusing on dynamics and online learning (Dong et al., 2018;
Chen et al., 2020; Zrnic et al., 2021), causal effects (Miller et al., 2020;
Shavit et al., 2020; Rosenfeld et al., 2020; Harris et al., 2021b; Bechavod et
al., 2021a), strategic regression (Tang et al., 2021; Harris et al., 2021a;
Bechavod et al., 2021b), strategic ranking (Liu et al., 2021), and strategic
representation (Nair et al., 2022). These remain outside the scope of our
generalized framework for strategic classification.

##  2 Generalized Strategic Classification

We begin by reviewing the learning setup for SC, and then proceed to present
GSC and IASC.

###  2.1 Strategic classification

Denote by $x\in{\cal{X}}\subseteq{\mathbb{R}}^{d}$ features representing user
attributes, and by $y\in{\cal{Y}}=\\{-1,1\\}$ their corresponding labels. Let
$D$ be some unknown joint distribution over ${\cal{X}}\times{\cal{Y}}$. As in
standard classification, at _train time_ the system is given access to a
sample set of $m$ labeled pairs $S=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ sampled iid
from $D$, on which it aims to learn a classifier
$h:{\cal{X}}\rightarrow{\cal{Y}}$ from some function class $H$. What differs
in strategic classification is that at _test time_ , once $h$ has been learned
$h$ (and deployed), users can _modify_ their features $x\mapsto x^{\prime}$,
in a way we explain shortly. The objective of the system is to correctly
classify _modified_ inputs, and so its goal in learning is to minimize the
expected 0/1 loss, ${\texttt{err}}(h)=\mathbb{E}_{D}{[{\mathds{1}{\\{{y\neq
h(x^{\prime})}\\}}}]}$. Learning is therefore successful if it produces a
classifier that is robust to strategic modifications.

The way in which users modify their features derives from the utility they can
gain from predictive outcomes. In SC, users are willing to modify features if
this will help them be classified positively, denoted ${\hat{y}}=1$. But
modifications are costly, and the cost of applying $x\mapsto x^{\prime}$ is
given by a _cost function_ $c(x,x^{\prime})$, which is assumed to be known to
all. Users are modeled as rational utility-maximizers that update their
features via the following _best-response mapping_ :

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

Learning then aims to minimize the expected _strategic error_ :

$\operatorname*{argmin}_{h\in
H}\mathbb{E}_{D}{[{\mathds{1}{\\{{h({\Delta}^{\mathtt{SC}}_{h}(x))\neq
y}\\}}}]}$ (2)

###  2.2 Generalizing strategic classification

The update in Eq. (1) includes three important ingredients: what users know
(i.e., $x$), what they want (i.e., $h(x^{\prime})=1$), and how these two
concepts are integrated into action (i.e., maximizing utility minus cost). But
the update is _effective_ only when the original features $x$ remain _private
user information_.111Indeed, had the system known $x$ at test time, any
modification would have been futile (and costly). Privacy of information is a
crucial aspect of strategic classification, and is essentially what makes it
distinct from standard classification. Building on this simple observation, we
propose a generalized framework permitting users to make use of additional and
richer forms of private information, in more varied ways, and towards broader
goals.

Concretely, our GSC framework extends SC in two ways. First, we allow users to
hold, in addition to $x$, private _side information_ , denoted $z\in{\cal{Z}}$
(and redefine $D$ to be a joint distribution over triples $(x,z,y)$). Objects
$z$ can be of any type, and the main distinction between $z$-objects and
$x$-objects (which are also private) is that while $x$ are used by the system
as input to the classifier (and so are subject to modification by users), $z$
are used only by the user, and only for the purpose of computing ${\Delta}$
(and so remain unmodified). One interpretation of $z$ is that it defines a
user’s ‘type’ (in the game-theroretic sense), which affects her actions.

Second, we allow for broader user objectives by replacing $h(x^{\prime})$ in
Eq. (1) with a more general function of _perceived utility_ , denoted
${\tilde{{u}}}_{h}(x^{\prime},z)$, which encodes the utility users _believe_
they obtain from $x^{\prime}$ under the classifier $h$, and as a function of
$z$. This gives the _generalized response mapping_ :

${\Delta}^{\mathtt{GSC}}_{h}(x)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}{\tilde{{u}}}_{h}(x^{\prime},z)-c(x,x^{\prime})$
(3)

To see how $u$ and $z$ work together, observe that Eq. (3) provides a formula
for how users _act_ , meaning that $u$ reflects how utility is _perceived_ by
users. This perceived utility may, or may not, align with users’ _true_
utility (which must be independently defined);222In SC, they are the same.
note this means ${\Delta}^{\mathtt{GSC}}$ is no longer necessarily a best-
response. What controls the degree to which true and perceived utility align
is how useful $z$ is as side information when integrated into $u$ to form user
beliefs regarding value. Side information can be helpful—but also misleading;
a simple example is when $z\in{\mathbb{R}}$ and acts as additive noise, i.e.,
${\tilde{{u}}}_{h}(x^{\prime},z)={u}_{h}(x^{\prime})+z$ for true utility
${u}_{h}$, as in Random Utility Theory (Cascetta, 2009). But Eq. (3) is more
general, and can in principle allow for more elaborate forms of user modeling,
such as bounded-rational, Bayesian, or behavioral decision models. We next
survey some special instances of Eq. (3) which exemplify this idea.

#### Notable special cases.

Standard SC (Eq. (1)) is obtained from Eq. (3) by setting $z=\emptyset$ (i.e.,
no additional side information) and $u_{h}(x^{\prime},z)=h(x^{\prime})$.
Notice Eq. (1) can be rewritten as:

${\Delta}^{\mathtt{SC}}_{h}(x)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\mathds{1}{\\{{h(x^{\prime})=1}\\}}-\frac{1}{2}c(x,x^{\prime})$
(4)

where now
${\tilde{{u}}}_{h}(x,z)=\mathds{1}{\\{{h(x^{\prime})=1}\\}}=\frac{h(x^{\prime})+1}{2}$.
This simply emphasizes that users want positive predictions, but makes it easy
to consider other forms of user interests. For example, for _adversarial_
users, we plug in $y$ and obtain:

${\Delta}^{\mathtt{adv}}_{h}(x,y)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\mathds{1}{\\{{h(x^{\prime})\neq
y}\\}}-\frac{1}{2}c(x,x^{\prime})$ (5)

which is made possible once we set $z=y$ as private information. More
generally, if we let $z\in\\{-1,1\\}$ hold arbitrary values, then we recover
the general-preference (GP) model studied in (Sundaram et al., 2021):

${\Delta}^{\mathtt{GP}}_{h}(x,z)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\mathds{1}{\\{{h(x^{\prime})=z}\\}}-\frac{1}{2}c(x,x^{\prime})$
(6)

here, knowing $z$ is essential for users to effectively respond.

Returning to SC, the recent work of (Jagadeesan et al., 2021) on alternative
microfoundations proposes a noisy response model. This can be recovered by
setting $z\in{\mathbb{R}}^{d}$ as the random noise term, which gives:

${\Delta}^{\mathtt{noise}}_{h}(x,z)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}h_{\theta+z}(x^{\prime})-c(x,x^{\prime})$
(7)

where $\theta\in{\mathbb{R}}^{d}$ are the parameters of the classifier. A more
elaborate form of side information can be found in (Ghalme et al., 2021),
where users are ‘in the dark’ and respond based on an approximate classifier,
$\tilde{h}$, estimated from data:

${\Delta}^{\mathtt{dark}}_{h}(x,z)\triangleq\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\tilde{h}(x^{\prime};z,h)-c(x,x^{\prime})$
(8)

Here, $\tilde{h}(\cdotp;z,h)$ is estimated by users from a sample set
$\\{(x_{j},{\hat{y}}_{j})\\}_{j=1}^{n}$ consisting of additional examples
$z=\\{x_{j}\\}_{j=1}^{n}$ labeled by the true classifier,
${\hat{y}}_{j}=h(x_{j})$. In both of the above, users seek positive
predictions, but act based on how they _perceive_ utility, as determined by
$u$ and $z$.

###  2.3 Learning in GSC

In its most general form, the GSC learning objective is:

$\operatorname*{argmin}_{h\in
H}\mathbb{E}_{D}{[{\mathds{1}{\\{{h({\Delta}^{\mathtt{GSC}}_{h}(x,z))\neq
y}\\}}}]}$ (9)

where for each sub-class of problems, ${\Delta}^{\mathtt{GSC}}$ is replaced
with its appropriate counterpart. One key difference between Eq. (9) and Eq.
(2) is that the former now includes side information $z$. This requires us to
be precise about its role. Clearly, at test time, neither $x$ nor $z$ are
observed by the system. However, at train time, it remains a question whether
$z$ should be observed or not. For example, in the GP setting of (Sundaram et
al., 2021), $z$ is assumed to be _known_ ; in the noisy-parameter setting of
(Jagadeesan et al., 2021), when $z$ models users’ misperceptions of $\theta$,
it is reasonable to consider it as _unknown_ ; while for the ‘in-the-dark’
setting of (Ghalme et al., 2021), it is shown that for known $z$, learning
reduces to standard strategic classification, whereas for unknown $z$, errors
in estimating user responses can blow up in a way that can cause learning to
fail completely. Hence, the decision regarding observing $z$ remains task-
specific.

In this paper, we focus on the setting where $z$ is known—this places emphasis
on the introduction of $z$ into the response mapping ${\Delta}$, and abstracts
away other aspects (such as what system knows or does not). Note also that
when $z$ is unknown, from the system’s perspective, the user’s response
mapping ${\Delta}$ (Eq. (3)) is not well-defined, and so requires additional
assumptions on how the system compensates for this lack of knowledge in
learning, which we aim to avoid. We can therefore think of $z$ as obtained at
train time in the same manner that ground-truth labels $y$ (which are also
unobserved at test time) are typically gathered, e.g., by investing effort to
collect them from users.

##  3 Incentive-Aligned Strategic Classification

Next, we introduce and study a particular sub-class of problems in GSC which
we refer to as _incentive-aligned strategic classification_ (IASC). Our
results here will serve as a basis for our more general results for GSC in
Sec. 4, but are of independent interest (full proofs in the Appendix).

Intuitively, incentive alignment occurs when the utility of users is similar
enough to that of the system so that strategic behavior improves both. This
can happen when users also seek correct predictions, and the system provides
such predictions as a service (recommendation systems are one such example).
When incentives align, strategic behavior can improve outcomes for both the
system and its users.

We begin by formally defining _incentive alignment_ (IA).

######  Definition 1 (Incentive-alignment).

Let $D$ be a joint distribution over
${\cal{X}}\times{\cal{Z}}\times{\cal{Y}}$, $H$ be a function class, and
${\Delta}$ a response mapping. We say the learning task is _incentive-aligned_
if $\exists\,h\in H$ such that $\forall\,h^{\prime}\in H$, it holds that:

$\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}_{h}(x;z))\neq
y}\\}}]\leq\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$ (10)

If such an $h$ exists, we say it _aligns incentives_.

Incentive alignment holds when there is some classifier whose performance on
strategically modified inputs is better than the optimal classifier on
unmodified inputs. We next describe two novel settings in which users seek to
accurate predictions, and so incentive alignment is likely.

Noisy labels (NL). In this simple model, side information $z$ consists of a
noisy estimate of a user’s true label, denoted ${\tilde{y}}\in\\{\pm 1\\}$.
Users seek accurate predictions (i.e., want ${\hat{y}}=y$), but act as if
${\tilde{y}}$ (which may be $\neq y$) is their true label:

${\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})=\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\mathds{1}{\\{{h(x^{\prime})={\tilde{y}}}\\}}-\frac{1}{2}c(x,x^{\prime})$
(11)

When ${\tilde{y}}$ and $y$ are sufficiently correlated, and if the system is
able to ‘correct’ erroneous user updates, then incentive alignment should
hold. Note ${\Delta}^{\mathtt{NL}}$ is a special case of
${\Delta}^{\mathtt{GP}}$.

Personalized previous experiences (PPE). Here we mimic a recommendation
setting in which the system provides users $x$ with personalized (binary)
relevance predictions $y\in\\{\pm 1\\}$ for various items
$a\in{\mathbb{R}}^{\ell}$. Instances are tuples $(x,z,a,y)$ ($D$ is extended
accordingly), and the system aims to predict relevance for user-item pairs,
${\hat{y}}=h(x^{\prime},a)$. For modifying features, users have as side
information previously experienced items, in the form of a sample set
$z=\\{(a_{j},y_{j})\\}_{j=1}^{n}$, where typically $n\ll m$. Here,
${\Delta}^{\mathtt{PPE}}_{h}(x,z)$ is:

$\displaystyle\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\frac{1}{n}\sum\nolimits_{j=1}^{n}\mathds{1}{\\{{h(x^{\prime},a_{j})=y_{j}}\\}}-\frac{1}{2}c(x,x^{\prime})$
(12)

Hence, users modify their features to maximize the accuracy of the proposed
$h$ on their past preferences.

In the settings above, the system and its users cooperate (indirectly) to
achieve better accuracy, and are complementary in their strength: the system
has large data but on the collective of past users, whereas new users have
small or noisy data, but personalized for their own preferences. Learning is
successful if the system can harness user efforts to improve accuracy for all.
In the remainder of this section we focus on the noisy labels model to
establish our main results for IASC, which we then extend to generic GSC cases
in Sec. 4. We return to PPE (and define it more precisely) in Sec. 5.

###  3.1 Learning with noisy labels as side information

In this section we study an instance of the noisy-label side-information
setting in which noise is uniform and independent: ${\tilde{y}}=y$ w.p.
$1-\epsilon$ and ${\tilde{y}}=1-y$ w.p. $\epsilon$ for all $y$. The noise
parameter $\epsilon$ controls how informative ${\tilde{y}}$ are of $y$; this
has direct connections to incentive alignment. Figure 1 shows on synthetic
data that incentives align for most values of $\epsilon$ (Def. 1), and hence
strategic behavior is preferable (details in Appendix B.1). In Appendix A.1,
we theoretically characterize the conditions under which incentive alignment
holds, and under which predictions are informatively useful.

Throught this section we focus on linear classifiers
$h_{w}(x)=\operatorname{sign}(f_{w}(x))$ where $f_{w}(x)=w^{\top}x+b$, and on
2-norm costs $c(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|_{2}$. We use
${\Delta}_{h}$ to mean ${\Delta}_{h_{w}}$, and omit the intercept term $b$
throughout for clarity.

#### Learning via loss minimization.

A natural approach to minimizing the expected strategic loss (Eq. (9) with
${\Delta}^{\mathtt{NL}}$) is to instead aim at minimizing the empirical risk:

$\operatorname*{argmin}_{w\in{\mathbb{R}}^{d}}\frac{1}{m}\sum_{i=1}^{m}\mathds{1}{\\{{h_{w}({\Delta}^{\mathtt{NL}}_{h}(x_{i},z_{i}))\neq
y_{i}}\\}}$ (13)

While this approach is well-motivated _in principle_ , in practice, since the
0/1 loss is intractable; just as for non-strategic data, a proxy loss is
needed, and to control for overfitting, regularization is added. Using the
hinge loss as a proxy and $L_{2}$ regularization (as in SVM), naïvely adapting
the standard objective to the strategic case gives:

$\operatorname*{argmin}_{w\in{\mathbb{R}}^{d}}\frac{1}{m}\sum_{i=1}^{m}\max\\{0,1-y_{i}w^{\top}{\Delta}^{\mathtt{NL}}_{h}(x_{i},z_{i}))\\}+\lambda\left\|{w}\right\|_{2}^{2}$
(14)

Figure 1: Regions of incentive alignment in NL, for synthetic data (see right
plot) and varying noise $\epsilon$. For a wide range of $\epsilon$, learning
is incentive-aligned (IA), meaning that the strategic behavior of users is
beneficial for both the system and its users. The leftmost region is also IA,
but ${\tilde{y}}$ is better for users than ${\hat{y}}$.

Eq. (14) seems appealing and straightforward: in the same way as for the 0/1
loss, it simply replaces $x$ with ${\Delta}^{\mathtt{NL}}_{h}(x,z)$. However,
as we show in the next section, this naïve approach has two significant
drawbacks: it is difficult to optimize, and may fail to generalize well.
Hence, while minimizing the strategic empirical 0/1 loss is a sound approach,
a naïve adaptation of conventional proxy approaches may not be.

#### The problem with margins.

Consider first a non-strategic setting. If data is linearly separable, then
multiple classifiers can exist having zero empirical error. But some solutions
are better than others, and so to guarantee good generalization, additional
criteria (beyond loss minimization) must be considered. One popular approach
is _max-margin learning_ (Cortes & Vapnik, 1995), which aims to learn the
classifier having the largest _margin_ :

${\gamma}_{w}\triangleq\min_{i\in[m]}y_{i}{\widebar{w}}^{\top}x_{i},\quad\qquad{\widebar{w}}=w/\left\|{w}\right\|\frac{w}{\left\|{w}\right\|}$
(15)

The main motivation for max-margin learnin is that large-margin classifiers
can be shown to generalize well, and the canonical max-margin approach (for
linearly-separable data) is Hard-SVM. A naïve adaptation of Hard-SVM to our
strategic setting would be to replace each $x_{i}$ with
${\Delta}_{h}(x_{i},{\tilde{y}}_{i})$, this giving:

$\displaystyle\operatorname*{argmax}_{w\,:\,\left\|{w}\right\|=1}\,$
$\displaystyle\min_{i\in[m]}\left|w^{\top}{\Delta}_{h}(x_{i},{\tilde{y}}_{i})\right|$
$\displaystyle\text{
s.t.}\,\,\,y_{i}w^{\top}{\Delta}_{h}(x_{i},{\tilde{y}}_{i})>0\quad\forall
i\in[m]$ (16)

Figure 2:  (Left) In non-strategic settings, maximzing the (soft) margin is a
useful criterion for learning models that generalize well. (Right) In
strategic settings, this logic breaks; even for strategically separable data,
once any point moves, the margin becomes zero. One implication is that
mulitple models are likely to attain the max margin (which is zero). The
illustration portrays one such model, but _all_ models (passing at the origin)
are equally ‘good’.

Note that since points now ‘move’, data that was originally separable may no
longer satisfy the constraints in Eq. (3.1). Conversely, non-separable data
might _become_ separable if points move in a way that ‘corrects’
classification mistakes (e.g., consider the extreme case of ${\tilde{y}}=y$).
This calls for a notion of _strategic_ separability.

######  Definition 2.

A sample set is _strategically linearly separable_ if there exists a $w$ that
separates the data _after_ it has been modified, i.e.,
$y_{i}w^{\top}{\Delta}_{h}(x_{i};z_{i})>0$ $\forall i\in[m]$.

Intuitively, a model $w$ that (strategically) separates the data and has a
large margin should be appealing. However, a key observation is that for any
$w$ that permits _some_ movement—the maximal margin is _zero_ ; this is since
users minimize costs, and so land directly on the decision boundary. This has
concrete implications on learning. Consider, for example, data that is
strategically linearly separable, but is not (non-strategically) linearly
separable333This is sufficient; strategic linear separability is necessary..
In this case, _multiple optimal solutions are likely to exist_ —all of which
have a margin of zero—and to which the learning algorithm is oblivious (see
Figure 2). Thus, the naïve approach resurfaces the very same issues that the
max-margin approach aims to _avoid_. This deficiency is easiest to imagine for
${\tilde{y}}=y$, but holds for GSC settings beyond NL (Sec. 5.1).

#### Strategic margins and hinge.

Our next result shows that to recover the generalization properties of the
max-margin approach, we must rethink the notion of ‘margin’. We begin by
reinterpreting the strategic constraints in Eq. (3.1).

######  Lemma 1.

For any linear classifier $w$, it holds that:

$y_{i}w^{\top}{\Delta}^{\mathtt{NL}}_{h}(x_{i},{\tilde{y}}_{i})>0\,\,\Leftrightarrow\,\,y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\|w\|)>0$

Proof in Appendix E.5. The constraints can therefore be rewritten in a simple
form that does not rely on ${\Delta}$. This suggests that margins should be
measured accordingly.

######  Definition 3.

The _strategic margin_ (or _s-margin_) of $w$ is:

${{{\gamma}}_{\mathrm{\mathnormal{w}}}^{\mathtt{NL}}}\triangleq\min_{i\in[m]}y_{i}({\widebar{w}}^{\top}x_{i}+2{\tilde{y}}_{i}),\quad\qquad{\widebar{w}}=w/\left\|{w}\right\|$
(17)

Figure 3: An illustration of the s-hinge for NL with ${\tilde{y}}=y$.
Strategic movement creates a flat ‘kink’ in naïve hinge at
$[-2\left\|{w}\right\|,0]$, since all points in this range move to the
decision boundary. The s-hinge corrects for this by properly anticipating
strategic behavior.

Note that Eq. (17) differs from the standard margin in the corrective term
$+2{\tilde{y}}$, which captures the maximal admissible cost, and the direction
of change. This new margin has an intuitive interpretation: the distance of
each $x_{i}$ is measured w.r.t. an ‘individualized‘ classifier, $w^{(i)}$,
which is simply $w$ shifted parallelly by 2 units in the direction of
anticipated movement, ${\tilde{y}}_{i}$ (see Fig. 7 in Appx. C). This new
margin is _not_ equivalent to the naïve objective in Eq. (3.1).

For strategically-separable data, our approach will be to optimize the
s-margin using the appropriate constraints. For non-separable problems, this
can easily be extended to the ‘soft’ case using slack variables, akin to
standard soft SVM (see Appendix D.2). From this, we can derive an appropriate
proxy loss—the _strategic hinge_ , or _s-hinge_.

######  Definition 4.

For noisy labels, the _strategic hinge_ is:

${{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(x,{\tilde{y}},y;w)\triangleq\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}$

Hence, the s-hinge is simply the standard ‘vanilla’ hinge, but with an
additional additive term of $-2y{\tilde{y}}\left\|{w}\right\|$, which can be
interpreted as aiming to correctly classify _unmodified_ inputs $x_{i}$, but
w.r.t. an instance-dependent reference point, $1-2{\tilde{y}}\|w\|$, from
which the margin is measured. To see where this comes from, note that the
s-hinge can be rewritten as:

$\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})-(2-c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})))y{\tilde{y}}\left\|{w}\right\|\\}$

(proof in Appendix E.8). This is exactly the _naïve_ hinge,
$\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})\\}$, but with a
term that accounts for both the _actual_ and _maximal_ cost. Figure 3
illustrates the crux of the naïve hinge, and how the s-hinge corrects it.

Finally, adding regularization gives our learning objective:

$\operatorname*{argmin}_{w\in{\mathbb{R}}^{d}}\frac{1}{m}\sum_{i=1}^{m}{{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(x_{i},{\tilde{y}}_{i},y_{i};w)+\lambda\left\|{w}\right\|_{2}^{2}$
(18)

Our approach has two key benefits: it can be efficiently optimized, and it
enjoys favorable generalization guarantees (Sec. 4.2); fortunately, and as we
show next, our approach (and its benefits) extend to broader instances of GSC.

Figure 4: Results for the generalization experiment. The three leftmost plots
are on ‘easy’ environments that reflect differences in generalization
behavior. The rightmost plot is on a ‘hard’ environment in which the naïve
approach also suffers from optimization issues.

##  4 GSC: Proxy Losses and Bounds

In this section, we generalize our approach and results to GSC, this using the
principles underlying our results for NL in Sec. 3. Our focus remains on
linear classifiers, but we will now allow for general side information $z$,
utilities ${\tilde{{u}}}$, and costs $c$. In particular, our results here
cover the personalized previous experiences model (PPE) proposed in Sec. 3.

###  4.1 Generalized s-hinge

Returning to the standard hinge, note it can be rewritten as:

$\max\\{0,1-\operatorname{sign}(yw^{\top}x)|w^{\top}x|\\}$ (19)

which decouples the original penalty term $yw^{\top}x$ into a ‘correctness’
term, $\operatorname{sign}(yw^{\top}x)=\mathds{1}{\\{{y=h(x)}\\}}$, and an un-
normalized ‘distance’ term,

$d(x;w)\triangleq|w^{\top}x|=|{\widebar{w}}^{\top}x|\left\|{w}\right\|$ (20)

Now, consider again the naïve hinge. Under this perspective:

$\displaystyle\max\\{0,1-yw^{\top}{\Delta}_{h}(x,z)\\}$ $\displaystyle=$
$\displaystyle\max\\{0,1-\operatorname{sign}(yw^{\top}{\Delta}_{h}(x,z))|w^{\top}{\Delta}_{h}(x,z)|\\}$
(21)

This reveals its fault: while it is appropriate to consider _correctness_ on
modified inputs, measuring _distances_ in this way lacks to account for the
fact that ${\Delta}_{h}(x,z)$ is a _response_ to $w$; in other words, it
treats ${\Delta}_{h}(x,z)$ as some predetermined fixed point $x^{\prime}$,
discarding any information on the original point $x$ and how it changes as a
function of $w$.

To appropriately adapt the hinge to strategic settings, we must rethink the
definition of margin. Notice that the standard distance in Eq. (20) can be
reinterpreted as follows:

Observation: $d(x;w)$ is the distance from $x$ to the closest point
$x^{\prime}$ that is classified differently, i.e.,

$d(x;w)=\min_{x^{\prime}}\|x-x^{\prime}\|\,\,\text{s.t.}\,\,h(x)\neq
h(x^{\prime})$ (22)

This definition considers distances between _points_ , rather than between a
point and a hyperplane, as in Eq. (20); here, the role of the hyperplane is
expressed in terms of classification outcomes (as a constraint).

We can now adapt Eq. (22) to a strategic setting by replacing $x$ with
${\Delta}_{h}(x,z)$ only where it affects predictions.

######  Definition 5.

The _strategic distance_ of a point $x$ (and w.r.t. $z$) from the decision
boundary of $h_{w}$ is:

$\displaystyle d_{\Delta}(x,z;w)=$
$\displaystyle\min_{x^{\prime}}\left\|{x-x^{\prime}}\right\|$ (23)
$\displaystyle\text{ s.t. }\,\,h({\Delta}_{h}(x,z))\neq
h({\Delta}_{h}(x^{\prime},z))$

Here, unlike the naïve approach, distance are correctly measured on _un_
-modified inputs, and modified inputs are used to anticipate changes in
classification outcomes. These can then be used to define a _generalized
strategic margin_.

Consequently, strategic distances also suggest the appropriate form for the
_generalized strategic hinge_ , or _gs-hinge_ :

######  Definition 6.

The _generalized strategic hinge_ is defined as:

$\displaystyle{{{L}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(x,z,y;w)\triangleq$
(24)
$\displaystyle\quad\,\,\max\\{0,1-y\operatorname{sign}(w^{\top}{\Delta}_{h}(x,z))d_{\Delta}(x,z;w)\left\|{w}\right\|\\}$

which applies to any subclass of GSC. Note that for the non-strategic setting,
plugging ${\Delta}_{h}(x,z)=x$ into Eq. (24) recovers the standard margin. The
rationale behind the gs-hinge for generic instances of GSC is illustrated in
Fig. 8 (see Appendix C).

#### Optimization.

In its most general form, and with no particular structure, optimizing the gs-
hinge is likely to be hard. However, for several subclasses of interest, it
turns out to have a tractable form. For the special case of GP (which includes
NL, SC, and ADV) and for norm costs, the strategic distance can be simplified
to
${{d}_{\mathrm{\mathnormal{{\Delta}}}}^{\mathtt{GP}}}(x,z;w)=|{\widebar{w}}^{\top}x+2z|$
since points move at most distance 2 in the direction of $z$ (proof in
Appendix E.9). For this case, Eq. (24) becomes:

${{{L}}_{\mathrm{s-hinge}}^{\mathtt{GP}}}(x,z,y;w)\triangleq\max\\{0,1-yw^{\top}x-2zy\left\|{w}\right\|\\}$
(25)

For NL, $z={\tilde{y}}$, which recovers
${{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}$ (Def. 4). For SC and ADV, $z=1$ and
$z=-y$, respectively.

For all cases above, the gs-hinge in Eq. (25) accounts for strategic movement
_but does not explicitly include ${\Delta}_{h}(x,z)$ as a term_. This removes
the main computational difficulty which strategic behavior introduces—coping
with an argmax. In addition, Eq. (25), is differentiable, and so can be
optimized end-to-end using standard gradient methods. We view this as a
substantial advantage of our approach.

###  4.2 Generalization bounds

Our next result provides a data-dependent bound on the expected 0/1 error when
minimizing the gs-hinge objective.

######  Theorem 1.

Let $D$ be a joint distribution over triples $(x,z,y)$, and let
$r=\max_{x\in{\cal{X}}}\left\|{x}\right\|$. Denote by ${\hat{w}}$ the
minimizer of the empirical generalized strategic hinge loss with $L_{2}$
regularization. Then for every $\delta\in[0,1]$, if the training set
${\mathcal{S}}$ includes $m$ samples, then w.p. $\geq 1-\delta$ it holds that:

${{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{}}}\leq{{{\hat{{\mathcal{L}}}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}+\frac{8r\left\|{{\hat{w}}}\right\|}{\sqrt{m}}+(1+2{{\rho}_{\mathrm{}}^{\mathtt{GSC}}}\left\|{w}\right\|)\sqrt{\frac{2\ln(\frac{4\left\|{{\hat{w}}}\right\|}{\delta})}{m}}$

where ${{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{}}}$ is the expected 0/1 loss,
${{{\hat{{\mathcal{L}}}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}$ is the empirical
s-hinge loss on ${\mathcal{S}}$, and ${{\rho}_{\mathrm{}}^{\mathtt{GSC}}}=2r$.

The proof (Appendix E.10) relies on Rademacher bounds, and carefully adapts
the approach in (Fetaya, 2016) to account for strategic updates. The bound in
Thm. 1 closely matches the original bound for non-strategic settings, with the
only differences being that in the original bound the constant in the middle
summand is 4 (vs. 8), and $\rho=r$. We view this as suggesting that, in some
sense, the gs-hinge is an appropriate strategic generalization of the standard
hinge.

For notable subclasses of GSC, the bound in Thm. 1 can be tightened: the
middle constant is reduced to the original 4, and each case has its own $\rho$
term (Appendix E.11). For GP, we get
${{\rho}_{\mathrm{}}^{\mathtt{GP}}}=(r+2)\leq{{\rho}_{\mathrm{}}^{\mathtt{GSC}}}$,
and also
${{\rho}_{\mathrm{}}^{\mathtt{SC}}}={{\rho}_{\mathrm{}}^{\mathtt{adv}}}={{\rho}_{\mathrm{}}^{\mathtt{GP}}}$
in the worst case. For NL, we get
${{\rho}_{\mathrm{\mathnormal{\epsilon}}}^{\mathtt{NL}}}=r-2+4\epsilon$;
hence, for $\epsilon=1/2$, the standard bound is recovered, and for smaller
$\underline{\epsilon}\leq\nicefrac{{1}}{{2}}$, sample complexity in NL is
_better_ since
${{\rho}_{\mathrm{\mathnormal{\underline{\epsilon}}}}^{\mathtt{NL}}}<\rho$;444Since
points move within ${\cal{X}}$, and since movement is for distance of at most
2, we make the simplifying assumption that $r\geq 2$.555For larger
$\epsilon\in(1/2,1]$, where most labels are flipped, sample complexity is
worse. Note $\epsilon=1$ matches an adversarial setting. and when incentives
align, the empirical loss is also likely to be lower. Together, and for
$\overline{\epsilon}\geq\nicefrac{{1}}{{2}}$, we get:

${{\rho}_{\mathrm{\mathnormal{\underline{\epsilon}}}}^{\mathtt{NL}}}\leq\rho\leq{{\rho}_{\mathrm{\mathnormal{\overline{\epsilon}}}}^{\mathtt{NL}}}\leq{{\rho}_{\mathrm{}}^{\mathtt{SC}}}={{\rho}_{\mathrm{}}^{\mathtt{adv}}}={{\rho}_{\mathrm{}}^{\mathtt{GP}}}\leq{{\rho}_{\mathrm{}}^{\mathtt{GSC}}}$

##  5 Experiments

We now turn to our experimental evaluation. Our first experiment empirically
studies generalization behavior for the gs-hinge on synthetic data and in
various strategic settings. Our second experiment returns to the personalized
previous experiences (PPE) setting from Sec. 3 and uses real data.

###  5.1 Generalization

To complement our theoretical results, we study the generalization behavior of
learning with the gs-hinge, as it compares to the naïve hinge and standard
(non-strategic) hinge, across multiple settings: NL ($\epsilon=0$), SC, and
adversarial (ADV). We also add as a baseline the standard hinge applied to
non-strategic data (in SC and ADV it is an upper bound on strategic
performance; in NL, it is a lower bound). The challenge in empirically
analyzing generalization is that it is difficult to decouple statistical and
optimizational issues; this is particularly true in our case, since the gs-
hinge (for the settings we consider) has both a simpler functional form and
better theoretical guarantees than the naïve hinge. We therefore experiment in
two types of synthetic environments: ‘easy’ and ‘hard’, which vary in the
difficulty to optimize. Further details are in Appendix B.2.

#### Results.

Figure 4 presents our results. Each plot shows performance for an increasing
number of samples used for training. Results are averaged over $30$ random
splits, with bars showing (asymmetric) standard errors. For the easy
environment, the figure shows that across all settings, both our gs-hinge and
the naïve hinge achieve roughly optimal accuracy when training on 100% of the
data; however the gs-hinge strictly dominates the naïve hinge, and converges
significantly faster. This result suggests that the gs-hinge generalizes
better. For the hard environment, results show that the naïve approach does
not reach the optimum; train accuracy shows that this is not due to
overfitting. This shows that the simplicity of the gs-hinge is beneficial.

###  5.2 Personalized Previous Experiences

In PPE, the goal is to predict for a user-item pair $(x,a)$ whether user $x$
will like item $a$. Users can modify their inputs based on a (private) sample
set of previous experiences, $z=\\{(a_{j},y_{j})\\}_{j=1}^{n}$. We use
$c(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|_{2}^{2}$ and bi-linear
classifiers $h_{W}(x,a)=\operatorname{sign}(a^{\top}Wx)$, where $w_{x}=Wx$ is
a ‘personalized’ classifier.

The PPE setting is unique in that, in essence, users also aim to solve a
classification problem. To see this, note that for a given $W$, user responses
${\Delta}^{\mathtt{PPE}}_{h}(x,z)$ (Eq. 12) becomes:

$\operatorname*{argmin}_{x^{\prime}\in{\mathbb{R}}^{d}}\frac{1}{n}\sum\nolimits_{j=1}^{n}\mathds{1}{\\{{\operatorname{sign}(a_{j}^{\top}Wx^{\prime})\neq
y_{j}}\\}}-\frac{1}{2}\left\|{x-x^{\prime}}\right\|_{2}^{2}$

This is a linear classification problem: $x^{\prime}$ act as learned
classifier weights, $a_{j}^{{}_{(W)}}=a_{j}^{\top}W\in{\mathbb{R}}^{d}$ serve
as features, $y_{j}$ are target labels, and $x^{\prime}$ is regularized
towards $x$. In this sense, PPE becomes a problem of multiple agents solving
interwoven classification problems, and with similar goals.

#### Data.

We use the Coats Shopping dataset from Schnabel et al. (2016). The data
includes 290 users and 300 items (coats), with features for both (e.g.,
fashion preferences for users, type and color for coats). Labels include
relevance scores (here, binarized) given by each user to 40 coats.

#### Optimization.

In principle, both system and users aim to solve difficult 0/1-loss
objectives; as these are in general intractable, we model both entities as
solving proxy objectives instead. For the system we use the gs-hinge in (Eq.
(24)). In PPE, the general hinge is unlikely to have a closed-form solution.
This makes learning especially challenging, as it requires solving a triple-
nested optimization problem (the outer $\operatorname*{argmax}$ on $w$; the
interim $\min$ in $d_{\Delta}(x,z;w)$; and the inner $\operatorname*{argmax}$
in ${\Delta}_{h}$). Nonetheless, we show that if the system uses a squared-
loss proxy, the objective becomes tractable (for a full derivation see
Appendix Sec. B.3).

Figure 5:  Results for the PPE setting on the coats dataset. Learning with the
strategic gs-hinge is significantly better than the standard hinge, starting
at $n=4$ and improving as $n$ increases. Performance is optimal when user
respond with a proxy loss that match the system’s (squared). Results show
clear incentive alignment.

#### Results.

We consider three user types that differ by the proxy loss they employ to
solve ${\Delta}^{\mathtt{PPE}}$: square, hinge, and logistic. For each user
type, we compare the performance of our gs-hinge approach to the standard
hinge, and vary the number of previous experiences, $n=|z|$. Figure 5 shows
that for all user types, and with as little as $n=4$ examples in $z$, the gs-
hinge provides a clear improvement over the standard hinge. As $n$ grows, the
gain in accuracy becomes more pronounced. For the square-loss user, $n=24$
improves upon the standard hinge by $6.4$%. Improvement exhibits a clear
diminishing-returns trend, with most of the gain achieved by $n=12$ ($5.7$%).
For the hinge- and log-loss users, gains are less pronounced, but still
significant ($3.8\%$ at $n=12$, after which gains plateau). Note that both
parties are better off when users employ the squared loss, this matching the
proxy loss used by the system. Hence, it is in the best interest of the system
to be transparent about the loss it uses (here, squared), and in the best
interest of users follow suit. This is true since incentives align; results
show clear incentive-alignment from $n=4$. Interestingly, strategic behavior
under incentive alignment also helps the standard (non-strategic) hinge
classifier (vs. the baseline).

##  6 Conclusions

In a world where decisions about humans are increasingly being made by (or
with the support of) learned classifiers, it is only reasonable to expect that
humans will act to promote their own goals. Our main takeaway is that these
goals, and the means taken to pursue them, are varied. Our generalized
framework aims to capture this idea, and to provide what we feel is a much
needed flexibility in user modeling within this domain. Methodologically, our
paper shows that coping with strategic behavior cannot always be done by
simply plugging a human response model into exiting methods for non-strategic
learning, and that any adaptation of conventional approaches must be done with
care.

While our framework is general, it is intentionally restricted to the
fundamental setting of supervised binary classification. Our hopes are
twofold: that within the limits of our framework, its flexibility will aid in
developing new and interesting strategic learning problems; and that beyond
our framework’s boundaries, these new problems can extend to broader settings
including dynamics, causality, and others.

## References

  * Bechavod et al. (2021a) Bechavod, Y., Ligett, K., Wu, S., and Ziani, J.  Gaming helps! learning from strategic interactions in natural dynamics.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 1234–1242. PMLR, 2021a.
  * Bechavod et al. (2021b) Bechavod, Y., Podimata, C., Wu, Z. S., and Ziani, J.  Information discrepancy in strategic learning.  _arXiv preprint arXiv:2103.01028_ , 2021b.
  * 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.
  * Cascetta (2009) Cascetta, E.  _Random Utility Theory_ , pp. 89–167.  Springer US, Boston, MA, 2009.  ISBN 978-0-387-75857-2.  doi: 10.1007/978-0-387-75857-2˙3.
  * Chen et al. (2020) Chen, Y., Liu, Y., and Podimata, C.  Learning strategy-aware linear classifiers.  In _Thirty fourth Conference on Neural Information Processing Systems (NeurIPS), Advances in Neural Information Processing Systems_ , 2020.
  * Cortes & Vapnik (1995) Cortes, C. and Vapnik, V.  Support-vector networks.  _Machine learning_ , 20(3):273–297, 1995.
  * Ding et al. (2020) Ding, G. W., Sharma, Y., Lui, K. Y. C., and Huang, R.  MMA training: Direct input space margin maximization through adversarial training.  In _International Conference on Learning Representations_ , 2020.
  * 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.
  * Eilat et al. (2022) Eilat, I., Finkelshtein, B., Baskin, C., and Rosenfeld, N.  Strategic classification with graph neural networks.  _arXiv preprint arXiv:2205.15765_ , 2022.
  * Erdogdu (2022) Erdogdu, M. A.  Statistical learning theory, lecture 6.  https://erdogdu.github.io/csc2532/lectures/lecture06.pdf, 2022\.
  * Estornell et al. (2021) Estornell, A., Das, S., Liu, Y., and Vorobeychik, Y.  Unfairness despite awareness: Group-fair classification with strategic agents.  In _Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS), StratML workshop_ , 2021.
  * Fetaya (2016) Fetaya, E.  Introduction to statistical learning theory, lecture 7.  https://www.wisdom.weizmann.ac.il/~ethanf/teaching/ItSLT_16/lectures/lec7_no_anim.pdf, 2016\.
  * Ghalme et al. (2021) Ghalme, G., Nair, V., Eilat, I., Talgam-Cohen, I., and Rosenfeld, N.  Strategic classification in the dark.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , 2021.
  * 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\.
  * 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.
  * Harris et al. (2021a) Harris, K., Heidari, H., and Wu, Z. S.  Stateful strategic regression.  In _Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS)_ , 2021a.
  * Harris et al. (2021b) Harris, K., Ngo, D., Stapleton, L., Heidari, H., and Wu, Z. S.  Strategic instrumental variable regression: Recovering causal relationships from strategic responses.  In _Proceedings of the 38th International Conference on Machine Learning (ICML), Workshop on The Neglected Assumptions in Causal Inference_ , 2021b.
  * Jagadeesan et al. (2021) Jagadeesan, M., Mendler-Dünner, C., and Hardt, M.  Alternative microfoundations for strategic classification.  In _International Conference on Machine Learning_ , pp. 4687–4697. PMLR, 2021.
  * Kingma & Ba (2017) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization, 2017.
  * Lechner & Urner (2021) Lechner, T. and Urner, R.  Learning losses for strategic classification.  In _Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS), Workshop on Learning in Presence of Strategic Behavior_ , 2021\.
  * Levanon & Rosenfeld (2021) Levanon, S. and Rosenfeld, N.  Strategic classification made practical.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , 2021.
  * Liu et al. (2021) Liu, L. T., Garg, N., and Borgs, C.  Strategic ranking.  _arXiv preprint arXiv:2109.08240_ , 2021.
  * 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.
  * Nair et al. (2022) Nair, V., Ghalme, G., Talgam-Cohen, I., and Rosenfeld, N.  Strategic representation.  _arXiv preprint_ , 2022.
  * Rosenfeld et al. (2020) Rosenfeld, N., Hilgard, A., Ravindranath, S. S., and Parkes, D. C.  From predictions to decisions: Using lookahead regularization.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Schnabel et al. (2016) Schnabel, T., Swaminathan, A., Singh, A., Chandak, N., and Joachims, T.  Recommendations as treatments: Debiasing learning and evaluation.  In _international conference on machine learning_ , pp. 1670–1679. PMLR, 2016.
  * 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.
  * Sundaram et al. (2021) Sundaram, R., Vullikanti, A., Xu, H., and Yao, F.  PAC-learning for strategic classification.  In _International Conference on Machine Learning_ , pp. 9978–9988. PMLR, 2021.
  * Tang et al. (2021) Tang, W., Ho, C.-J., and Liu, Y.  Linear models are robust optimal under strategic behavior.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2584–2592. PMLR, 2021.
  * Zhang & Conitzer (2021) Zhang, H. and Conitzer, V.  Incentive-aware PAC learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021.
  * Zhou et al. (2012) Zhou, Y., Kantarcioglu, M., Thuraisingham, B., and Xi, B.  Adversarial support vector machine learning.  In _Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2012.
  * Zrnic et al. (2021) Zrnic, T., Mazumdar, E., Sastry, S., and Jordan, M.  Who leads and who follows in strategic classification?  _Advances in Neural Information Processing Systems_ , 34, 2021.

##  Appendix A Additional Results

###  A.1 Conditions for Incentive Alignment in NL

Our first results give a characterization of when a learning task is incentive
aligned (see Definition 1) in a simple instance of the noisy label model with
independent uniform noise: ${\tilde{y}}=y$ w.p. $1-\epsilon$ and
${\tilde{y}}=1-y$ w.p. $\epsilon$ for all $y$.

As the noise parameter $\epsilon$ controls how informative ${\tilde{y}}$ are
of $y$, we can ask: for what values of $\epsilon$ is strategic behavior
beneficial to all? As we show, the answer directly depends on whether
incentives can be aligned.

We begin with a definition of _flipping cost_.

######  Definition 7.

The flipping cost of a point $x$ with respect to a classifier $h$ and a cost
function $c$ is:

${\phi}_{h}(x)\triangleq\min_{x^{\prime}\in{\cal{X}}}c(x,x^{\prime})\quad\text{s.t.}\quad
h(x^{\prime})\neq h(x)$ (26)

Hence, ${\phi}_{h}(x)$ is the minimal cost required for modifying $x$ to
‘flip’ its label (we will return to label flipping in Sec. 4). Next, under the
common case of $c(x,x)=0$, observe that:

######  Lemma 2.

  * •

If $h(x)={\tilde{y}}$, then
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=h(x)$

  * •

If $h(x)\neq{\tilde{y}}$, then
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\neq h(x)$ iff ${\phi}_{h}(x)\leq
2$

Proof in Appendix E.1. Given this, we will define:

$\displaystyle{\Phi}_{h}=\\{x\,:\,{\phi}_{h}(x)\leq 2\\}$ (27)

to include all points that _can_ flip their label.

We can now state our first result.

######  Theorem 2.

Let $D$ be a joint distribution over ${\cal{X}}\times{\cal{Y}}$. Assume
$z={\tilde{y}}=y$ with probability $1-\epsilon$, and $-y$ otherwise, and
assume features are modified via ${\Delta}^{\mathtt{NL}}$ in Eq. (11). Then it
is better for the system to encourage strategic behavior iff it learns a
classifier $h$ for which it holds that:

$\displaystyle\mathbb{P}{\left[{x\not\in{\Phi}_{h}\,\wedge\,h(x)\neq
y}\right]}$
$\displaystyle+\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}\cdot\epsilon$ (28)
$\displaystyle\leq\min_{h^{\prime}\in H}P(h^{\prime}(x)\neq y)$

The proof (Appendix E.2) relies on the coupling of a technical lemma with the
careful accounting of different error types. The theorem states that strategic
behavior is helpful if the system can learn a classifier whose error on points
that cannot flip their label (first summand) plus an $\epsilon$-proportion of
the points that can flip their label (second summand) is at most the optimal
error with no strategic behavior (RHS). This relates to incentive alignment:

######  Corollary 1.

If such an $h$ exists, then the learning task is incentive-aligned.

Proof in Appendix E.3. Thm. 2 states when it is preferable for users to modify
features via ${\Delta}^{\mathtt{NL}}$, rather than simply reporting their
original $x$. For completeness, we also state when predictions ${\hat{y}}$ on
modified inputs are better than ${\tilde{y}}$.

######  Lemma 3.

In the same setting as above, it is better for users to use system-provided
predictions ${\hat{y}}$ than their own side-information ${\tilde{y}}$ iff the
system uses a classifier $h$ for which:

$\frac{\mathbb{P}{\left[{x\not\in{\Phi}_{h}\,\wedge\,h(x)\neq
y}\right]}}{\mathbb{P}{\left[{x\not\in{\Phi}_{h}}\right]}}\leq\epsilon$ (29)

Proof in Appendix E.4. Lemma 3 states that predictions are helpful as long as
errors on points who cannot flip their label (and so cannot in principle
“correct” system errors) is no more than the noise inherent in side
information, $\epsilon$. Proofs for both results rely on the coupling of a
technical lemma with the careful accounting of different error types. Figure 1
shows on synthetic data that for most values of $\epsilon$, strategic behavior
is preferable (details in Appendix B.1).

###  A.2 NL as an Extreme Subclass

Recall that our discussion regarding the need for a specialize hinge loss for
strategic settings began with the observation that, under a naïve approach,
multiple classifiers can obtain a margin of zero. Our next result shows that,
in this sense, NL is a ‘extreme’ class within problems in GP.

######  Lemma 4.

Let $S=\\{(x_{i},y_{i})\\}_{i=1}^{m}$. Then of all possible assignments to
corresponding side information $\\{z_{i}\\}_{i=1}^{m}$, the assignment
$z_{i}=y_{i}$ for all $i\in[m]$ has the largest set of feasible solutions
having zero margin (when such exist).666Note that the set of feasible
solutions may also be large; the ratio of zero-margin feasible solutions is
data-dependent.

###### Proof.

Let $S=\\{(x_{i},z_{i},y_{i})\\}_{i=1}^{m}$ such that $\exists
i\in[m],z_{i}\neq y_{i}$. Denote by $H_{S}^{\prime}\subseteq H$ the set of all
feasible solutions to the naive S-SVM optimization problem (Eq. 3.1) for the
GP setting. Denote by $H_{S}^{\prime\prime}\subseteq H^{\prime}$ the set of
all feasible solutions which induce zero margin
$(\min_{i\in[m]}\left|w^{\top}{\Delta}_{h}(x_{i},z_{i})\right|=0)$.

Fix some $i\in[m]$ for which $z_{i}\neq y_{i}$. Consider the sample set
$S^{\prime}=S\setminus\\{(x_{i},z_{i},y_{i})\\}\cup\\{(x_{i},y_{i},y_{i})\\}$.
The $i_{th}$ constraint for $S^{\prime}$ is strictly weaker in comparison to
$S$ (Lemma 1). The rest of the constraints remain unchanged. Therefore
$\forall h\in H^{\prime}_{S},h\in H_{S^{\prime}}^{\prime}$.

If $h\in H_{S}^{\prime\prime}$ than
$\min_{i\in[m]}\left|w^{\top}{\Delta}_{h}(x_{i},z_{i})\right|=0$. This means
that $\exists j\in[m],w^{\top}{\Delta}_{h}(x_{j},z_{j})=0$. Notice that $j\neq
i$. Proof:
If $h\in H_{S^{\prime}}^{\prime\prime}$ than all constraints must hold. In
particular $y_{i}w^{\top}x_{i}<-2$ (Lemma 1). If
$w^{\top}{\Delta}_{h}(x_{i},z_{i})=0$ than $h({\Delta}_{h}(x_{i},z_{i}))\neq
h(x_{i})$ which means that $x_{i}$ modified it’s features to be classified as
$z_{i}$. Since $z_{i}\neq y_{i}$, the $i_{th}$ constraint does not hold - a
contradiction.

Notice that
$w^{\top}{\Delta}_{h}(x_{j},z_{j})=0\Rightarrow\min_{i\in[m]}\left|w^{\top}{\Delta}_{h}(x_{i},z_{i})\right|=0\Rightarrow
h\in H_{S^{\prime}}^{\prime\prime}$. We get that $\forall h\in
H^{\prime\prime}_{S},h\in H_{S^{\prime}}^{\prime\prime}$. Therefore
$H^{\prime\prime}_{S}\subseteq H_{S^{\prime}}^{\prime\prime}$. Finally,
applying such modifications to $S$ recursively we get that
$H^{\prime\prime}_{S^{*}}$ is maximal for
$S^{*}=\\{(x_{i},y_{i},y_{i})\\}_{i=1}^{m}$. ∎

##  Appendix B Additional Experimental Details

#### Technical details.

All experiment results were averaged over $30$ randomized experiments (data
generation/shuffles and train/test splits). In our experiments we used the
soft S-SVM for the naive and non-strategic models and used our proposed soft
formulation for the strategically aware models. These methods require a hyper-
parameter $(\lambda)$ controlling the tradeoff between maximization and amount
of constraint violations. We tuned this hyper-parameter using cross-validation
of $3$ splits for $\lambda\in\\{0.01,0.1,1\\}$. For the optimization we used
the standard Adam optimizer (Kingma & Ba, 2017) and a learning rate of $0.05$.
Each model trained for $200/200/50$ epochs with a batch size of $5/16/24$ for
the generalization experiment, the varying preference noise experiment and the
PPE experiment respectively.

###  B.1 Experiment: Varying $\epsilon$ in NL (Sec. 3.1)

In this experiment our goal was to emphasize that there are simple and common
environments which are incentive-aligned, for both low and high values of
$\epsilon$. For this we generated a 2D dataset with clusters sampled from a
normal distribution as depicted in Figure 1. Then generated user preferences
according to the Noisy labels setting for various $\epsilon$ values between
$0$ and $0.5$. For the learning process we used our proposed approach (Eq. 18)
and compared its accuracy to the baseline accuracy (non-strategic model) and
the pure user-information accuracy $(1-\epsilon)$. Results can be viewed in
Figure 1.

#### Data.

For this experiment we considered $2$D user features, and the distribution we
used is composed out of $4$ sub-distributions:

  * •

$(x,y)\sim N\left(\binom{-5}{0},\binom{0.5,\,0}{0,\,20}\right)\times\\{1\text{
w.p. }0.95,-1\text{ w.p. }0.05\\}$

  * •

$(x,y)\sim
N\left(\binom{0.3}{0},\binom{0.5,\,0}{0,\,20}\right)\times\\{1\text{ w.p.
}0,-1\text{ w.p. }1\\}$

  * •

$(x,y)\sim
N\left(\binom{-0.3}{0},\binom{0.5,\,0}{0,\,20}\right)\times\\{1\text{ w.p.
}1,-1\text{ w.p. }0\\}$

  * •

$(x,y)\sim N\left(\binom{5}{0},\binom{0.5,\,0}{0,\,20}\right)\times\\{1\text{
w.p. }0.05,-1\text{ w.p. }0.95\\}$

From each distribution we sampled $50$ samples for the train set and $1250$
samples for the test set.

###  B.2 Experiment: Generalization (Sec. 5.1)

#### Optimization.

Here we describe how we calculated ${\Delta}^{\mathtt{GP}}$ (for the naive
approach) in a differential way - allowing GD-based optimization methods.
Notice that for norm-based cost function, the GP response mapping argmax
problem has a closed-form solution:

${\Delta}^{\mathtt{GP}}_{h}(x,z)=\left\\{\begin{matrix}x-\frac{zw^{\top}xw}{\left\|{w}\right\|^{2}}&-2\leq\frac{zw^{\top}x}{\left\|{w}\right\|}\leq
0\\\ x&otherwise\end{matrix}\right.$

This closed form solution is unfortunately non-differentiable; instead, we
apply the following differentiable approximation:

${\Delta}^{\mathtt{GP}}_{h}(x,z)=x-\frac{zw^{\top}xw}{\left\|{w}\right\|^{2}}\cdot\sigma(cond),\qquad\quad
cond=(-\frac{zw^{\top}x}{\left\|{w}\right\|})\cdot(\frac{zw^{\top}x}{\left\|{w}\right\|}+2)$

Where $\sigma$ is the sigmoid function.

#### Data.

Here we consider 2D user features, and the distributions we used are composed
out of two sub-distributions:

  * NL:

  * •

$(x,z,y)\sim
N\left(\binom{10}{0},\binom{5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{1\text{ w.p. }1\\}$

  * •

$(x,z,y)\sim
N\left(\binom{-10}{0},\binom{5,\,0}{0,\,0.2}\right)\times\\{-1\text{ w.p.
}1\\}\times\\{-1\text{ w.p. }1\\}$

  * ADV:

  * •

$(x,z,y)\sim
N\left(\binom{15.5}{0},\binom{1.5,\,0}{0,\,0.2}\right)\times\\{-1\text{ w.p.
}1\\}\times\\{1\text{ w.p. }1\\}$

  * •

$(x,z,y)\sim
N\left(\binom{4.5}{0},\binom{1.5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{-1\text{ w.p. }1\\}$

  * SC:

  * •

$(x,z,y)\sim
N\left(\binom{15}{0},\binom{1.5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{1\text{ w.p. }1\\}$

  * •

$(x,z,y)\sim
N\left(\binom{4}{0},\binom{1.5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{-1\text{ w.p. }1\\}$

  * SC (hard):

  * •

$(x,z,y)\sim
N\left(\binom{2.25}{0},\binom{0.5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{1\text{ w.p. }1\\}$

  * •

$(x,z,y)\sim
N\left(\binom{-2.25}{0},\binom{0.5,\,0}{0,\,0.2}\right)\times\\{1\text{ w.p.
}1\\}\times\\{-1\text{ w.p. }1\\}$

From each distribution we sampled $25$ samples for the train set and $1250$
samples for the test set.

###  B.3 Experiment: Private Personalized Experiences (PPE) (Sec. 5.2)

Notice that in this setting, ${\Delta}$ does not have a closed-form solution
and can only be approximated by both users and the system. This means that
even at test time, users will modify their features according to an
approximation of ${\Delta}^{\mathtt{PPE}}$. To test the effectiveness and
robustness of our proposed algorithm, we fix the approximation of the system
and vary the approximation of users. We trained the system with the MSE loss,
and tested $3$ different user approximation losses: MSE loss, classic hinge
loss and logistic loss. For each experiment, we varied the amount of items
users were exposed to in advanced (size of $z$). The more items in $z$, the
more accurate their ”model” will be, and therefore we expect higher accuracy.

$\displaystyle\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)=\operatorname*{argmin}_{x^{\prime}\in{\cal{X}}}\frac{1}{|z|}\sum_{(a,y)\in
z}L(x^{\prime},a,y;W)+\frac{1}{2}\left\|{x^{\prime}-x}\right\|^{2}$ (30)
$\displaystyle
L^{\mathtt{squared}}(x,a,y;W)=\left\|{a^{\top}Wx-y}\right\|^{2}$
$\displaystyle L^{\mathtt{hinge}}(x,a,y;W)=\max\\{0,1-y\cdot(a^{\top}Wx)\\}$
$\displaystyle L^{\mathtt{logistic}}(x,a,y;W)=e^{-y\cdot(a^{\top}Wx)}$

#### System training procedure.

In PPE the recommender takes $2$ arguments (Eq. 12) so we used an adaptation
of the GSC s-hinge loss (Eq.24) for this experiment.

$\displaystyle{{{L}}_{\mathrm{s-hinge}}^{\mathtt{PPE}}}(x,z,a,y;W)\triangleq$
(31)
$\displaystyle\quad\,\,\max\\{0,1-y\operatorname{sign}(a^{\top}W{\Delta}_{h}(x,z))d_{\Delta}(x,z;W)\left\|{a^{\top}W}\right\|\\}$

We begin by replacing the $sign$ function with a a sigmoid function - an
approximated smooth and differential version of $sign$. We continue by
describing how we calculate $\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)$. Recall
the system uses the $MSE$ approximation and therefore
$\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)$ can be rewritten as:

$\displaystyle\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)=\operatorname*{argmin}_{x^{\prime}\in{\cal{X}}}\left\|{AWx^{\prime}-Y}\right\|^{2}+\frac{|z|}{2}\left\|{x^{\prime}-x}\right\|^{2}$
(32) $\displaystyle A=(a_{1},...,a_{|z|}),Y=(y_{1},...,y_{|z|})$

This is a standard LS with regularization optimization problem and has a
closed form solution:

$\displaystyle\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)=(2(AW)^{\top}AW+|z|\mathbb{I})^{-1}(2(AW)^{\top}Y+|z|x)$
(33)

Next, we describe how we find $d_{\Delta}(x,z;W)$. Notice that according to
the MSE approximation, users’ strategic modifications are linear
transformations:

$\displaystyle\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)=\alpha_{W,z}x+\beta_{W,z}$
(34) $\displaystyle\alpha_{W,z}=|z|(2(AW)^{\top}AW+|z|\mathbb{I})^{-1}$
$\displaystyle\beta_{W,z}=(2(AW)^{\top}AW+|z|\mathbb{I})^{-1}(2(AW)^{\top}Y)$

Being a linear transformation, it is also continuous. This implies that for
any $x$, the closest $x^{\prime}$ to it for which $h({\Delta}_{h}(x,z))\neq
h({\Delta}_{h}(x^{\prime},z))$ (Eq. 23), has to hold
$\frac{|aW{\Delta}_{h}(x^{\prime},z)|}{\left\|{aW}\right\|}=0$. Meaning it’s
distance to the hyperplane after applying modifications is $0$.

Now, we plug in Eq. 34 to this constraint and get:

$\displaystyle aW\alpha_{W,z}x-aW\beta_{W,z}=0$ (35)

All that remains is to solve a convex optimization problem with linear
equality constraints to find $d_{\Delta}(x,z;W)$. To do this in a differential
way, we apply another approximation and solve the following optimization
problem instead:

$\displaystyle\tilde{{\Delta}}^{\mathtt{PPE}}_{h}(x,z)=\operatorname*{argmin}_{x^{\prime}\in{\cal{X}}}\left\|{aW\alpha_{W,z}x-aW\beta_{W,z}}\right\|^{2}+\lambda\left\|{x^{\prime}-x}\right\|^{2}$
(36)

For fairly small values of $\lambda$ (In our experiments we used
$\lambda=0.01$). This optimization problem too has a closed form solution
which concludes the training procedure calculations.

##  Appendix C Additional Illustrations

Figure 6: A depiction of the generalized strategic classification world and
various sub-classes within it. Figure 7: An illustration of the GP/NL s-margin
minimization objective for different samples. The hyperplane classifies points
to its left as $-1$ (orange side) and points to its right as $+1$ (blue side).
The red and blue lines represent $d_{\Delta}$ \- which in this setting is the
distances of users to the shifted hyperplane 2 units into their ”undesired
side”. Red lines mean that the user is in a ”red” region
$(\operatorname{sign}(yw^{\top}{\Delta}_{h}(x;z)<0)$ and similarly for blue
lines $(\operatorname{sign}(yw^{\top}{\Delta}_{h}(x;z)>0)$. Figure 8: Let
$h,{\Delta},z,y$ be a classifier, a response mapping, user latent information
and a label. Notice that these elements induce regions in ${\cal{X}}$ for
which $h({\Delta}(x;z))=y$ (blue) and $h({\Delta}(x;z))\neq y$ (red). The
objective of the gs-hinge (Eq. 24) is to maximize $d_{\Delta}(x,z;h)$ (Eq. 23)
for $x$ values in blue regions, and minimize it for $x$ values in red regions.
The reason is that
$\operatorname{sign}(yw^{\top}{\Delta}_{h}(x_{1};z))d_{{\Delta}_{h}}(x_{1},z;h)>0$
and
$\operatorname{sign}(yw^{\top}{\Delta}_{h}(x_{2};z))d_{{\Delta}_{h}}(x_{2},z;h)<0$.

##  Appendix D Additional Definitions

###  D.1 NL Hard formulation equivalent optimization problem

According to Lemma 1, the Hard formulation from Eq. 3.1 for the NL setting can
be rewritten as:

$\displaystyle\operatorname*{argmax}_{w\,:\,\left\|{w}\right\|=1}\,$
$\displaystyle\min_{i\in[m]}\left|y_{i}(w^{\top}x+2{\tilde{y}}_{i})\right|$
$\displaystyle\text{
s.t.}\,\,\,y_{i}(w^{\top}x+2{\tilde{y}}_{i})>0\quad\forall i\in[m]$ (37)

This optimization problem can be reformulated as follows:

Algorithm 1 NL Hard formulation

Input: $\\{(x_{i},{\tilde{y}}_{i},y)\\}^{m}$

Solve:

$w_{0}=\operatorname*{argmin}_{w}\left\|{w}\right\|^{2}$

s.t. $\forall i\in[m],y_{i}(w^{\top}x+2{\tilde{y}}_{i}\left\|{w}\right\|)\geq
1$

Output: $\hat{w}=\frac{w_{0}}{\left\|{w_{0}}\right\|}$

Algorithm 1 and Eq. D.1 output the same classifier $w$. Proof in Appendix E.6.

###  D.2 NL/GP Soft formulation

The hard constraints of the algorithm 1 optimization problem can be soften by
introducing slack variables, similarly to the classic soft SVM algorithm.

Algorithm 2 NL/GP Soft formulation

Input: $\\{(x_{i},{\tilde{y}}_{i},y)\\}^{m}$

Parameter: $\lambda>0$

Solve:

$w,\xi_{i}=\operatorname*{argmin}_{w,\xi_{i}}\lambda\left\|{w}\right\|^{2}+\frac{1}{m}\sum_{i=1}^{m}\xi_{i}$

s.t. $\forall i\in[m],y_{i}(w^{\top}x+2{\tilde{y}}_{i}\left\|{w}\right\|)\geq
1-\xi_{i}$ and $\xi_{i}\geq 0$

Output: $w$

We can rewrite the optimization problem of Algorithm 2 as a regularized loss-
minimization problem:

$\displaystyle
w,\xi_{i}=\operatorname*{argmin}_{w,\xi_{i}}\lambda\left\|{w}\right\|^{2}+\frac{1}{m}{{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(x_{i},{\tilde{y}}_{i},y_{i};w)$
$\displaystyle{{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(x,{\tilde{y}},y;w)\triangleq\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}$

Proof in Appendix E.7.

##  Appendix E Proofs

###  E.1 Lemma 2

###### Proof.

Assume $c(x,x)=0$.

  * •

If $h(x)={\tilde{y}}$: Assume, for sake of contradiction, that
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\neq h(x)$. This implies
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=-{\tilde{y}}$.

  * •

Recall the definition:

${\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})=\operatorname*{argmax}_{x^{\prime}\in{\cal{X}}}\mathds{1}{\\{{h(x^{\prime})={\tilde{y}}}\\}}-\frac{1}{2}c(x,x^{\prime})$

This means that
$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)\leq\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$.
But $\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)=1$; hence, since:

$\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=\mathds{1}{\\{{-{\tilde{y}}={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\leq
0<1$

we get that:

$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)>\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$

Therefore the assumption must be false.

  * •

If $h(x)\neq{\tilde{y}}$: $h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\neq
h(x)$ iff ${\phi}_{h}(x)\leq 2$

    * –

If $h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\neq h(x)$:
So $h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}$.
Assume, for sake of contradiction, that ${\phi}_{h}(x)>2$.
Therefore $c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))>2$.
Again,
$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)\leq\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$.
But
$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)=0$.
$\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=\mathds{1}{\\{{{\tilde{y}}={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))<1-\frac{1}{2}\cdot
2=0$.
So
$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)>\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$.
Therefore the assumption must be false.

    * –

If ${\phi}_{h}(x)\leq 2$:
Let $x^{\prime}$ be the minimizer of the flipping cost optimization problem
(Definition 7).
Therefore $h(x)\neq h(x^{\prime})$ and $c(x,x^{\prime})\leq 2$. This means
that $h(x^{\prime})={\tilde{y}}$.
Assume, for sake of contradiction, that
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=h(x)$.
So $h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=-{\tilde{y}}$.
Again,
$\mathds{1}{\\{{h(x^{\prime})={\tilde{y}}}\\}}-\frac{1}{2}c(x,x^{\prime})\leq\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$.
But
$\mathds{1}{\\{{h(x^{\prime})={\tilde{y}}}\\}}-\frac{1}{2}c(x,x^{\prime})=\mathds{1}{\\{{{\tilde{y}}={\tilde{y}}}\\}}-\frac{1}{2}c(x,x^{\prime})\geq
1-\frac{1}{2}\cdot 2=0>-1$.
$\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=\mathds{1}{\\{{-{\tilde{y}}={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=-1-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))\leq
0$.
So
$\mathds{1}{\\{{h(x)={\tilde{y}}}\\}}-\frac{1}{2}c(x,x)>\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}}\\}}-\frac{1}{2}c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))$.
Therefore the assumption must be false.

∎

###  E.2 Theorem 2

###### Proof.

Let $D$ be a joint distribution over ${\cal{X}}\times{\cal{Y}}$. Assume
$z={\tilde{y}}=y$ with probability $1-\epsilon$, and $-y$ otherwise, and
assume features are modified via ${\Delta}^{\mathtt{NL}}$ in Eq. (11). It is
better for the system to encourage strategic behavior iff it learns a
classifier $h$ for which it holds that:

$\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\min_{h^{\prime}\in
H}\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$

  * •

RHS: We have $\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq
y}\\}}]=\mathbb{P}{\left[{h^{\prime}(x)\neq y}\right]}$

  * •

LHS: From Lemma 2 we derive two conclusions:

    * –

1\. $x\in{\Phi}_{h}\Rightarrow
h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))={\tilde{y}}$.

    * –

2\. $x\notin{\Phi}_{h}\Rightarrow
h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=h(x)$.

This gives us:

$\displaystyle\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]=\mathbb{P}{\left[{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\right]}=$
$\displaystyle\mathbb{P}{\left[{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y|x\in{\Phi}_{h}}\right]}\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y|x\notin{\Phi}_{h}}\right]}\cdot\mathbb{P}{\left[{x\notin{\Phi}_{h}}\right]}=_{1,2}$
$\displaystyle\mathbb{P}{\left[{{\tilde{y}}\neq
y|x\in{\Phi}_{h}}\right]}\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{h(x)\neq
y|x\notin{\Phi}_{h}}\right]}\cdot\mathbb{P}{\left[{x\notin{\Phi}_{h}}\right]}=_{{\tilde{y}}\text{
and }x\text{ are i.i.d}}$
$\displaystyle\epsilon\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{h(x)\neq
y\wedge x\notin{\Phi}_{h}}\right]}$

Finally, we get:

$\displaystyle\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\min_{h^{\prime}\in
H}\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$
$\displaystyle\Leftrightarrow\epsilon\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{h(x)\neq
y\wedge x\notin{\Phi}_{h}}\right]}\leq\min_{h^{\prime}\in
H}\mathbb{P}{\left[{h^{\prime}(x)\neq y}\right]}$

∎

###  E.3 Corollary 1

###### Proof.

if such an $h$ exists, then according to Theorem 2:

$\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\min_{h^{\prime}\in
H}\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$

Therefore $\exists h\in H$ such that $\forall h^{\prime}\in H$ it holds that:

$\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$

According to Definition 1, the environment is incentive-aligned. ∎

###  E.4 Lemma 3

###### Proof.

Let $D$ be a joint distribution over ${\cal{X}}\times{\cal{Y}}$. Assume
$z={\tilde{y}}=y$ with probability $1-\epsilon$, and $-y$ otherwise, and
assume features are modified via ${\Delta}^{\mathtt{NL}}$ in Eq. (11). It is
better for users to use system-provided predictions ${\hat{y}}$ than their own
side-information ${\tilde{y}}$ iff the system learns a classifier $h$ for
which it holds that:

$\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\mathbb{E}_{D}[\mathds{1}{\\{{{\tilde{y}}\neq y}\\}}]$

  * •

RHS: We have $\mathbb{E}_{D}[\mathds{1}{\\{{{\tilde{y}}\neq
y}\\}}]=\mathbb{P}{\left[{{\tilde{y}}\neq y}\right]}=\epsilon$.

  * •

LHS:

$\displaystyle\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]=\mathbb{P}{\left[{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\right]}=_{\text{Theorem \ref{thm:condition1} proof}}$
$\displaystyle\epsilon\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{h(x)\neq
y\wedge x\notin{\Phi}_{h}}\right]}$

Finally, we get:

$\displaystyle\mathbb{E}_{D}[\mathds{1}{\\{{h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
y}\\}}]\leq\min_{h^{\prime}\in
H}\mathbb{E}_{D}[\mathds{1}{\\{{h^{\prime}(x)\neq y}\\}}]$
$\displaystyle\Leftrightarrow\epsilon\cdot\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]}+\mathbb{P}{\left[{{\tilde{y}}\neq
y\wedge x\notin{\Phi}_{h}}\right]}\leq\epsilon$
$\displaystyle\Leftrightarrow\mathbb{P}{\left[{{\tilde{y}}\neq y\wedge
x\notin{\Phi}_{h}}\right]}\leq\epsilon(1-\mathbb{P}{\left[{x\in{\Phi}_{h}}\right]})$
$\displaystyle\Leftrightarrow\mathbb{P}{\left[{{\tilde{y}}\neq y\wedge
x\notin{\Phi}_{h}}\right]}\leq\epsilon\cdot\mathbb{P}{\left[{x\notin{\Phi}_{h}}\right]}$
$\displaystyle\Leftrightarrow\frac{\mathbb{P}{\left[{{\tilde{y}}\neq y\wedge
x\notin{\Phi}_{h}}\right]}}{\mathbb{P}{\left[{x\notin{\Phi}_{h}}\right]}}\leq\epsilon$

∎

###  E.5 Lemma 1

###### Proof.

Let $h=(w)$ be a linear classifier and $(x,{\tilde{y}},y)\in{\cal{X}}\times
Y\times Y$. We show that:

$yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})>0\,\,\Leftrightarrow\,\,y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)>0$

Or equivalently:

$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))=y\,\,\Leftrightarrow\,\,\frac{yw^{\top}x}{\left\|{w}\right\|}>-2{\tilde{y}}y$

Observation: In $NL$, the cost function is the euclidean distance between two
vectors $(c(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|)$. Therefore the
flipping cost (Definition 7) of a user $x$ is the euclidean distance to the
separating hyperplane
$({\phi}_{h}(x)=\frac{|w^{\top}x|}{\left\|{w}\right\|})$.

  * •

If $y={\tilde{y}}$:

    * –

If $h(x)={\tilde{y}}$: From Lemma 2, we have
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}=y$. Hence,

$yw^{\top}x={\tilde{y}}w^{\top}x>0\Leftrightarrow\frac{yw^{\top}x}{\left\|{w}\right\|}>0>-2=-2{\tilde{y}}y$

    * –

If $h(x)\neq{\tilde{y}}$: From Lemma 2, we have
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}=y\Leftrightarrow{\phi}_{h}(x)\leq
2$. Hence,

$\displaystyle{\phi}_{h}(x)\leq
2\Leftrightarrow\frac{|w^{\top}x|}{\left\|{w}\right\|}\leq
2\qquad\text{(observation)}$
$\displaystyle\frac{|w^{\top}x|}{\left\|{w}\right\|}\leq
2\Leftrightarrow\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}\geq-2\qquad({\tilde{y}}w^{\top}x<0)$
$\displaystyle\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}\geq-2\Leftrightarrow\frac{yw^{\top}x}{\left\|{w}\right\|}\geq-2{\tilde{y}}y$

  * •

If $y\neq{\tilde{y}}$:

    * –

If $h(x)={\tilde{y}}$: From Lemma 2, we have
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}=-y$. Hence,

$yw^{\top}x=-{\tilde{y}}w^{\top}x<0\Leftrightarrow\frac{yw^{\top}x}{\left\|{w}\right\|}<0<2=-2{\tilde{y}}y$

    * –

If $h(x)\neq{\tilde{y}}$: From Lemma 2, we have
$h({\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}}))={\tilde{y}}=-y\Leftrightarrow{\phi}_{h}(x)\leq
2$. Hence,

$\displaystyle{\phi}_{h}(x)\leq
2\Leftrightarrow\frac{|w^{\top}x|}{\left\|{w}\right\|}\leq
2\qquad\text{(observation)}$
$\displaystyle\frac{|w^{\top}x|}{\left\|{w}\right\|}\leq
2\Leftrightarrow\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}\geq-2\qquad({\tilde{y}}w^{\top}x<0)$
$\displaystyle\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}\geq-2\Leftrightarrow\frac{yw^{\top}x}{\left\|{w}\right\|}<-2{\tilde{y}}y$

∎

###  E.6 Hard formulation equivalent form (Appendix D.1)

###### Proof.

We begin by rewriting Eq. D.1:

$\operatorname*{argmax}_{w\,:\,\left\|{w}\right\|=1}\,\min_{i\in[m]}y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i})$
(38)

The two are equivalent whenever there is a solution to the preceding problem,
i.e. the data is strategically separable (Definition 2).

Let $w^{*}$ be a solution of Eq. 38. Define
$\gamma^{*}=\min_{i\in[m]}y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i})$. Therefore
$\forall i\in[m]$ we have:

$y_{i}((w^{*})^{\top}x_{i}+2{\tilde{y}}_{i})\geq\gamma^{*}$

Or equivalently (since $\gamma^{*}>0$ and $\left\|{w^{*}}\right\|=1$):

$y_{i}((\frac{w^{*}}{\gamma^{*}})^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{\frac{w^{*}}{\gamma^{*}}}\right\|)\geq
1$

Hence, $\frac{w^{*}}{\gamma^{*}}$ satisfies the conditions of the optimization
in Algorithm 1. Therefore,
$\left\|{w_{0}}\right\|\geq\left\|{\frac{w^{*}}{\gamma^{*}}}\right\|=\frac{1}{\gamma^{*}}$.

It follows that $\forall i\in[m]$:

$y_{i}(\hat{w}^{\top}x_{i}+2{\tilde{y}}_{i})=\frac{1}{\left\|{w_{0}}\right\|}y_{i}(w_{0}^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w_{0}}\right\|)\geq\frac{1}{\left\|{w_{0}}\right\|}\geq\gamma^{*}$

Since $\left\|{\hat{w}}\right\|=1$ we obtain that $\hat{w}$ is an optimal
solution of Eq. 38. ∎

###  E.7 Soft formulation equivalent form (Appendix D.2)

###### Proof.

Fix some $w,i$ and consider the minimization over $\xi_{i}$ in Algorithm 2.
Since $\xi_{i}$ must be nonnegative, the best assignment to $x_{i}$ would be
$0$ if $y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|)\geq 1$ and
would be $1-y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|)$
otherwise. Therefore

$\xi_{i}=\left\\{\begin{matrix}0,&y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|)\geq
1\\\
1-y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|),&y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|)<1\end{matrix}\right.=\max\\{0,1-y_{i}(w^{\top}x_{i}+2{\tilde{y}}_{i}\left\|{w}\right\|)\\}$

∎

###  E.8 Definition 4 equivalent form

###### Proof.

We will show that for the $NL$ setting:

${{{L}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(x,{\tilde{y}},y;w)\triangleq\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}=\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})-(2-c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})))y{\tilde{y}}\left\|{w}\right\|\\}$

Assumption:
Users do not change their features unless the change strictly increase their
utility, i.e.
$h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=h(x)\Rightarrow{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=x$.

Observation:
Assuming $c(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|$ as in NL, the closest
point $x^{\prime}$ to $x$ for which $h(x^{\prime})\neq h(x)$ is a point on the
hyperplane $w$ closest to $x$. The modification cost is the euclidean distance
between $x$ and the hyperplane
$(c(x,x^{\prime})=\frac{|w^{\top}x|}{\left\|{w}\right\|})$

Let $h=(w)$ be a linear classifier and $(x,{\tilde{y}},y)\in{\cal{X}}\times
Y\times Y$.

  * •

If $\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}>0$:
${\tilde{y}}w^{\top}x>0\Rightarrow$
$h(x)={\tilde{y}}\Rightarrow$ (Lemma 2).
$h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=h(x)={\tilde{y}}\Rightarrow$
(assumption).
${\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=x\Rightarrow$
$yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=yw^{\top}x\Rightarrow$
$(c(x,{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=c(x,x)=0)$
$\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}=\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})-(2-c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})))y{\tilde{y}}\left\|{w}\right\|\\}$

  * •

If $0\geq\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}\geq-2$:
${\tilde{y}}w^{\top}x<0\Rightarrow$
$h(x)\neq{\tilde{y}}\Rightarrow$ (Lemma 2).
$(h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
h(x)\Leftrightarrow{\phi}_{h}(x)\leq 2)\Rightarrow$
$({\phi}_{h}(x)=\frac{|w^{\top}x|}{\left\|{w}\right\|}\text{( see
observation). Therefore }{\phi}_{h}(x)\leq 2)$.
$h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq h(x)\Rightarrow$
(observation).
$yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=0\wedge
c(x,{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=\frac{|w^{\top}x|}{\left\|{w}\right\|}\Rightarrow$
$(\frac{|w^{\top}x|}{\left\|{w}\right\|}=\frac{-{\tilde{y}}w^{\top}x}{\left\|{w}\right\|})$.
$\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}=\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})-(2-c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})))y{\tilde{y}}\left\|{w}\right\|\\}$

  * •

If $\frac{{\tilde{y}}w^{\top}x}{\left\|{w}\right\|}<-2$:
${\tilde{y}}w^{\top}x<0\Rightarrow$
$h(x)\neq{\tilde{y}}\Rightarrow$ (Lemma 2).
$(h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))\neq
h(x)\Leftrightarrow{\phi}_{h}(x)\leq 2)\Rightarrow$
$({\phi}_{h}(x)=\frac{|w^{\top}x|}{\left\|{w}\right\|}\text{ (see Lemma
\ref{lem:s-margin} proof). Therefore }{\phi}_{h}(x)>2)$.
$h({\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=h(x)\Rightarrow$ (assumption).
${\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=x\Rightarrow$
$yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}})=yw^{\top}x\Rightarrow$
$(c(x,{\Delta}^{\mathtt{NL}}_{h}(x;{\tilde{y}}))=c(x,x)=0)$
$\max\\{0,1-y(w^{\top}x+2{\tilde{y}}\left\|{w}\right\|)\\}=\max\\{0,1-yw^{\top}{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})-(2-c(x,{\Delta}^{\mathtt{NL}}_{h}(x,{\tilde{y}})))y{\tilde{y}}\left\|{w}\right\|\\}$

∎

###  E.9 Strategic distance for GP

Claim:
${{d}_{\mathrm{\mathnormal{{\Delta}}}}^{\mathtt{GP}}}(x,z;w)=|{\widebar{w}}^{\top}x+2z|$

###### Proof.

Let $h=(w)$ be a linear classifier, $x,x^{\prime}\in{\cal{X}}$ and
$z\in{\cal{Z}}$. We show necessary and sufficient conditions for which
$h({\Delta}^{\mathtt{GP}}_{h}(x))\neq
h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))$.

  * •

If $h(x)=z$:
$h({\Delta}^{\mathtt{GP}}_{h}(x))\neq
h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$z\neq h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$h(x^{\prime})\neq z\wedge{\phi}_{h}(x^{\prime})>2\Leftrightarrow$
$zw^{\top}x^{\prime}<0\wedge\frac{|w^{\top}x^{\prime}|}{\left\|{w}\right\|}>2\Leftrightarrow$
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}<-2$.
Also, $zw^{\top}x>0$. Therefore $x$ and any $x^{\prime}$ for which
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}<-2$ are on different sides of
the hyperplane.
The minimal distance from $x$ to such $x^{\prime}$ is the distance from $x$ to
the hyperplane plus $2$:
${{d}_{\mathrm{\mathnormal{{\Delta}}}}^{\mathtt{GP}}}(x,z;w)=\frac{|w^{\top}x|}{\left\|{w}\right\|}+2=\frac{zw^{\top}x}{\left\|{w}\right\|}+2=|\frac{w^{\top}x}{\left\|{w}\right\|}+2z|=|{\widebar{w}}^{\top}x+2z|$

  * •

If $h(x)\neq z$:

    * –

If ${\phi}_{h}(x)\leq 2$:
$h({\Delta}^{\mathtt{GP}}_{h}(x))\neq
h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$z\neq h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$h(x^{\prime})\neq z\wedge{\phi}_{h}(x^{\prime})>2\Leftrightarrow$
$zw^{\top}x^{\prime}<0\wedge\frac{|w^{\top}x^{\prime}|}{\left\|{w}\right\|}>2\Leftrightarrow$
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}<-2$.
Also, $zw^{\top}x\leq 0$ and
$\frac{|w^{\top}x^{\prime}|}{\left\|{w}\right\|}\leq 2$.
This means that $-2\leq\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}\leq 0$.
Therefore $x$ and any $x^{\prime}$ for which
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}<-2$ are on the same side of
the hyperplane and $x$ is closer to the hyperplane than $x^{\prime}$.
The minimal distance from $x$ to such $x^{\prime}$ is $2$ minus the distance
from $x$ to the hyperplane:
${{d}_{\mathrm{\mathnormal{{\Delta}}}}^{\mathtt{GP}}}(x,z;w)=2-\frac{|w^{\top}x|}{\left\|{w}\right\|}=2+\frac{zw^{\top}x}{\left\|{w}\right\|}=|\frac{w^{\top}x}{\left\|{w}\right\|}+2z|=|{\widebar{w}}^{\top}x+2z|$

    * –

If ${\phi}_{h}(x)>2$:
$h({\Delta}^{\mathtt{GP}}_{h}(x))\neq
h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$z=h({\Delta}^{\mathtt{GP}}_{h}(x^{\prime}))\Leftrightarrow$ (Lemma 2).
$h(x^{\prime})=z\vee(h(x^{\prime})\neq z\wedge{\phi}_{h}(x^{\prime})\leq
2)\Leftrightarrow$
$zw^{\top}x^{\prime}>0\vee(zw^{\top}x^{\prime}\leq
0\wedge\frac{|w^{\top}x^{\prime}|}{\left\|{w}\right\|}\leq 2)\Leftrightarrow$
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}>0\vee(-2\leq\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}\leq
0)\Rightarrow$
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}\geq-2.$
Also, $zw^{\top}x\leq 0$ and
$\frac{|w^{\top}x^{\prime}|}{\left\|{w}\right\|}>2$.
This means that $\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}<-2$.
The minimal distance from $x$ to an $x^{\prime}$ for which
$\frac{zw^{\top}x^{\prime}}{\left\|{w}\right\|}\geq-2$ is the distance from
$x$ to the hyperplane minus $2$:
${{d}_{\mathrm{\mathnormal{{\Delta}}}}^{\mathtt{GP}}}(x,z;w)=\frac{|w^{\top}x|}{\left\|{w}\right\|}-2=-\frac{zw^{\top}x}{\left\|{w}\right\|}-2=|\frac{w^{\top}x}{\left\|{w}\right\|}+2z|=|{\widebar{w}}^{\top}x+2z|$.

∎

###  E.10 Theorem 1

###### Proof.

Denote by $s$ a sample $(x,z,y)\in{\cal{X}}\times{\cal{Z}}\times{\cal{Y}}$.
Recall:

$\displaystyle{{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{GSC}}}(s;w)\triangleq\mathds{1}{\\{{y\operatorname{sign}(w^{\top}{\Delta}_{h}(x;z))}\\}}$
$\displaystyle{{{L}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(s;w)\triangleq\max\\{0,1-y\operatorname{sign}(w^{\top}{\Delta}_{h}(x,z))d_{\Delta}(x,z;w)\left\|{w}\right\|\\}$

Since $d_{\Delta}(x,z;w)\geq 0$ it is clear that
${{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{GSC}}}(s;w)\leq{{{L}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(s;w)$.

We rewrite ${{{L}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(s;w)$:

$\displaystyle{{{L}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(s;w)\triangleq\max\\{0,1-y\operatorname{sign}(w^{\top}{\Delta}_{h}(x,z))\left\|{x-x^{d}}\right\|\left\|{w}\right\|\\}$
where $\displaystyle
x^{d}\triangleq\operatorname*{argmin}_{x^{\prime}}\left\|{x-x^{\prime}}\right\|$
$\displaystyle\qquad\text{ s.t. }\,\,h({\Delta}_{h}(x,z))\neq
h({\Delta}_{h}(x^{\prime},z))$

Define ${\cal{H}}_{k}=\\{s\rightarrow
y\operatorname{sign}(w^{\top}{\Delta}_{h}(x,z))\left\|{x-x_{d}}\right\|\left\|{w}\right\|:\left\|{w}\right\|\leq
k\\}$ and let $S=\\{s_{i}\\}^{m}$ be vectors in that space. Denote
$r=\max_{x\in{\cal{X}}}$.
We bound the Rademacher complexity of ${\cal{H}}_{k}\circ S$:

$\displaystyle mR({\cal{H}}_{k}\circ
S)=\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}y_{i}\operatorname{sign}(w^{\top}{\Delta}_{h}(x_{i},z_{i}))\left\|{x_{i}-x^{d}_{i}}\right\|\left\|{w}\right\|\right]=_{1}$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\left\|{w}\right\|\right]=\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\left\|{w}\right\|\sum_{i=1}^{m}\sigma_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\right]\leq$
$\displaystyle\mathbb{E}_{\sigma}\left[k\left|\sum_{i=1}^{m}\sigma_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\right|\right]=k\mathbb{E}_{\sigma}\left[\sqrt{\left(\sum_{i=1}^{m}\sigma_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\right)^{2}}\right]\leq_{2}$
$\displaystyle
k\sqrt{\mathbb{E}_{\sigma}\left[\left(\sum_{i=1}^{m}\sigma_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\right)^{2}\right]}=k\sqrt{\mathbb{E}_{\sigma}\left[\sum_{i,j}\sigma_{i}\sigma_{j}\left\|{x_{i}-x^{d}_{i}}\right\|\left\|{x_{j}-x^{d}_{j}}\right\|\right]}=_{3}$
$\displaystyle
k\sqrt{\sum_{i=1}^{m}\mathbb{E}_{\sigma}\left[\sigma_{i}^{2}\right]\left\|{x_{i}-x^{d}_{i}}\right\|^{2}}\leq
k\sqrt{m}\cdot\max_{i}\left\|{x_{i}-x^{d}_{i}}\right\|\leq
k\sqrt{m}\cdot\max_{i}\left\|{x_{i}}\right\|+\left\|{x^{d}_{i}}\right\|\leq
k\sqrt{m}\cdot 2r$

With steps following from:

  1. 1.

$\sigma_{i}y_{i}\operatorname{sign}(w^{\top}{\Delta}_{h}(x_{i},z_{i}))\equiv_{d}\sigma_{i}$
under the expectancy

  2. 2.

Jensen’s inequality

  3. 3.

Independence

Therefore. $R({\cal{H}}_{k}\circ S)\leq\frac{2kr}{\sqrt{m}}$.

Consider the hinge function $\phi(t)=\max\\{0,1-t\\}$ for scalar values
$t\in\mathbb{R}$. $\phi$ is 1-Lipschitz:

$\forall
t_{1},t_{2}\in\mathbb{R},\qquad\left|\phi(t_{1})-\phi(t_{2})\right|=\left|\max{0,1-t_{1}}-\max{0,1-t_{2}}\right|\leq\max{|0-0|,|1-t_{1}-1+t_{2}|}=|t_{1}-t_{2}|$

Then, according to Talagrand’s contraction principal,
$R(\phi\circ{\cal{H}}_{k})\leq R({\cal{H}}_{k})$.

Let $D$ be a distribution on ${\cal{X}}\times{\cal{Z}}\times{\cal{Y}}$ such
that there exists some $w^{*}$ with
$\mathbb{P}_{D}{\left[{y\operatorname{sign}((w^{*})^{\top}{\Delta}_{h}(x,z)\geq
1}\right]}=1$. Let $w_{S}$ be the output of the Hard formulation algorithm
without normalization:

$\displaystyle w=\operatorname*{argmin}_{w}\left\|{w}\right\|^{2}$
$\displaystyle s.t.\,\,\forall
i\in[m],y_{i}\operatorname{sign}(w^{\top}{\Delta}_{h}(x_{i},z_{i}))\left\|{x_{i}-x^{d}_{i}}\right\|\left\|{w}\right\|\geq
1$

Define ${\cal{H}}^{*}=\\{w:\left\|{w}\right\|\leq\left\|{w^{*}}\right\|\\}$.
We have $\left\|{w_{S}}\right\|\leq\left\|{w^{*}}\right\|$ and therefore
$w_{S}\in{\cal{H}}^{*}$. From the generalization theorem on Rademacher
complexity, with probability greater or equal to $1-\delta$, for all
$w\in{\cal{H}}^{*}$:

${{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;D)-{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;S)\leq
2R_{D}(\phi\circ{\cal{H}}_{\left\|{w^{*}}\right\|})+c\sqrt{\frac{2ln(\frac{2}{\delta})}{m}}$

where $c$ is the maximal loss, which in our case is
$(1+2r\left\|{w^{*}}\right\|)$.

Finally, we get:

${{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;D)\leq{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;S)+\frac{4r\left\|{w^{*}}\right\|}{\sqrt{m}}+(1+2r\left\|{w^{*}}\right\|)\sqrt{\frac{2ln(\frac{2}{\delta})}{m}}$

Notice that $w^{*}$ is unknown. Therefore we show a data-dependant bound.
Define ${\cal{H}}^{i}=\\{w:\left\|{w}\right\|\leq 2^{i}\\}$ and
$\delta_{i}=\frac{\delta}{2^{i}}$. Note that
$\sum_{i=1}^{\infty}\delta_{i}=\delta$. Similarly to the first part of the
proof, for all $i$, $\forall w\in{\cal{H}}_{i}$ with probability greater or
equal to $\delta$:

${{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;D)\leq{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;S)+\frac{4r\cdot
2^{i}}{\sqrt{m}}+(1+2\cdot 2^{i})\sqrt{\frac{2ln(\frac{2}{\delta_{i}})}{m}}$

From the union bound, we get that with probability greater or equal to
$1-\delta$ this holds for all ${\cal{H}}_{i}$. This means that for all
$w\in{\cal{H}}$ we have for
$i=\left\lceil\log(\left\|{w}\right\|)\right\rceil\leq\log(\left\|{w}\right\|)+1$:

${{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;D)\leq{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{GSC}}}(w;S)+\frac{8r\left\|{w}\right\|}{\sqrt{m}}+(1+4r\left\|{w}\right\|)\sqrt{\frac{2ln(\frac{4\left\|{w}\right\|}{\delta})}{m}}$

Plugging $w=w_{S}$ finishes the proof. This proof can be adjusted easily to
work for the soft formulation algorithm. ∎

###  E.11 Tightened generalization bounds for notable subclasses of GSC

Let $D$ be a joint distribution over triples $(x,z,y)$, and let
$r=\max_{x\in{\cal{X}}}\left\|{x}\right\|$. Denote by ${\hat{w}}$ the
minimizer of the empirical generalized strategic hinge loss with $L_{2}$
regularization. Then for every $\delta\in[0,1]$, if the training set
${\mathcal{S}}$ includes $m$ samples, then w.p. $\geq 1-\delta$ it holds that:

${{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{}}}\leq{{{\hat{{\mathcal{L}}}}}_{\mathrm{s-hinge}}^{\mathtt{GP}}}+\frac{4r\left\|{{\hat{w}}}\right\|}{\sqrt{m}}+(1+2{{\rho}_{\mathrm{}}^{\mathtt{GP}}}\left\|{w}\right\|)\sqrt{\frac{2\ln(\frac{4\left\|{{\hat{w}}}\right\|}{\delta})}{m}}$

where ${{{\mathcal{L}}}_{\mathrm{0/1}}^{\mathtt{}}}$ is the expected 0/1 loss,
${{{\hat{{\mathcal{L}}}}}_{\mathrm{s-hinge}}^{\mathtt{GP}}}$ is the empirical
s-hinge loss on ${\mathcal{S}}$, and ${{\rho}_{\mathrm{}}^{\mathtt{GP}}}=r+2$.

###### Proof.

This proof follows the proof of Theorem 1 with two slight differences:

Rademacher complexity of ${\cal{H}}_{k}\circ S$:

$\displaystyle mR({\cal{H}}_{k}\circ
S)=\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}y_{i}(w^{\top}x_{i}+2z_{i}\left\|{w}\right\|)\right]=_{1}$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}(w^{\top}x_{i}+2z_{i}\left\|{w}\right\|)\right]=\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}(w^{\top}x_{i}+2z_{i}\left\|{w}\right\|)\right]\leq$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}w^{\top}x_{i}\right]+\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}\sum_{i=1}^{m}\sigma_{i}\cdot
2z_{i}\left\|{w}\right\|\right]=_{2}$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}w^{\top}\sum_{i=1}^{m}\sigma_{i}x_{i}\right]+\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}2\left\|{w}\right\|\sum_{i=1}^{m}\sigma_{i}\right]=$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup_{w\in{\cal{H}}_{k}}w^{\top}\sum_{i=1}^{m}\sigma_{i}x_{i}\right]\leq_{3}\mathbb{E}_{\sigma}\left[k\left\|{\sum_{i=1}^{m}\sigma_{i}x_{i}}\right\|\right]=$
$\displaystyle
k\mathbb{E}_{\sigma}\left[\sqrt{\left\|{\sum_{i=1}^{m}\sigma_{i}x_{i}}\right\|^{2}}\right]\leq_{4}k\sqrt{\mathbb{E}_{\sigma}\left[\left\|{\sum_{i=1}^{m}\sigma_{i}x_{i}}\right\|^{2}\right]}=$
$\displaystyle
k\sqrt{\mathbb{E}_{\sigma}\left[\sum_{i,j}^{m}\sigma_{i}\sigma_{j}\left\langle
x_{i},x_{j}\right\rangle\right]}=_{5}k\sqrt{\sum_{i=1}^{m}\mathbb{E}_{\sigma}\left[\sigma_{i}^{2}\right]\left\|{x_{i}}\right\|^{2}}\leq$
$\displaystyle k\sqrt{m}\cdot\max_{i}\left\|{x_{i}}\right\|\leq
k\sqrt{m}\cdot\max_{i}\left\|{x_{i}}\right\|=k\sqrt{m}\cdot r$

where steps follow from:

  1. 1.

$\sigma_{i}y_{i}\equiv_{d}\sigma_{i}$ under the expectancy

  2. 2.

$\sigma_{i}z_{i}\equiv_{d}\sigma_{i}$ under the expectancy

  3. 3.

Cauchy-Schwartz inequality

  4. 4.

Jensen’s inequality

  5. 5.

Independence

Therefore, $R({\cal{H}}_{k}\circ S)\leq\frac{kr}{\sqrt{m}}$.

Derivation of
${{\rho}_{\mathrm{}}^{\mathtt{NL}}},{{\rho}_{\mathrm{}}^{\mathtt{GP}}},{{\rho}_{\mathrm{}}^{\mathtt{ADV}}},{{\rho}_{\mathrm{}}^{\mathtt{SC}}}$:
The Rademacher complexity generalization theorem states that $c$ is equal to
the maximal loss for any sample in $S$. Therefore for GP, ADV and SC:

$\displaystyle\max_{s\in
S}{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{}}}(s)=\max_{s\in
S}\max\\{0,1-yw^{\top}x+2yz\left\|{w}\right\|\\}=1+(r+2)\left\|{w}\right\|\Rightarrow$
$\displaystyle\Rightarrow{{\rho}_{\mathrm{}}^{\mathtt{GP}}},{{\rho}_{\mathrm{}}^{\mathtt{ADV}}},{{\rho}_{\mathrm{}}^{\mathtt{SC}}}=r+2$

However, a close examination of the theorem proof (Erdogdu, 2022) allows for
the partition of the sample-set $S$ into several subsets
$S_{1},S_{2},...S_{k}$. Then
$c=\sum_{i=1}^{k}\frac{\mathbb{E}_{D}[|S_{i}|]}{|S|}\max_{s\in S_{i}}loss(s)$.

In NL, the sample set can be partitioned into $2$ subsets:
$S_{1}=\\{s=(x,{\tilde{y}},y)\in
S:{\tilde{y}}=y\\},S_{2}=\\{s=(x,{\tilde{y}},y)\in S:{\tilde{y}}\neq y\\}$.
$\mathbb{E}_{D}[|S_{1}|]=1-\epsilon,\mathbb{E}_{D}[|S_{2}|]=\epsilon$.
$\max_{s\in
S_{1}}{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(s)=\max_{s\in
S_{1}}\max\\{0,1-yw^{\top}x-2\left\|{w}\right\|\\}=1+(r-2)\left\|{w}\right\|$.
$\max_{s\in
S_{2}}{{{\mathcal{L}}}_{\mathrm{s-hinge}}^{\mathtt{NL}}}(s)=\max_{s\in
S_{2}}\max\\{0,1-yw^{\top}x+2\left\|{w}\right\|\\}=1+(r+2)\left\|{w}\right\|$.

In conclusion,
$c=\epsilon(1+(r+2)\left\|{w}\right\|)+(1-\epsilon)(1+(r-2)\left\|{w}\right\|)=1+(r+2-4\epsilon)\left\|{w}\right\|$.

∎