Yulai Zhao<EMAIL_ADDRESS>
Princeton University

# Optimizing the Performative Risk under
Weak Convexity Assumptions

###### Abstract

In performative prediction, a predictive model impacts the distribution that
generates future data, a phenomenon that is being ignored in classical
supervised learning. In this closed-loop setting, the natural measure of
performance named performative risk ($\mathrm{PR}$), captures the expected
loss incurred by a predictive model _after_ deployment. The core difficulty of
using the performative risk as an optimization objective is that the data
distribution itself depends on the model parameters. This dependence is
governed by the environment and not under the control of the learner. As a
consequence, even the choice of a convex loss function can result in a highly
non-convex $\mathrm{PR}$ minimization problem. Prior work has identified a
pair of general conditions on the loss and the mapping from model parameters
to distributions that implies the convexity of the performative risk. In this
paper, we relax these assumptions and focus on obtaining weaker notions of
convexity, without sacrificing the amenability of the $\mathrm{PR}$
minimization problem for iterative optimization methods.

##  1 Introduction

Predictions in the real world are often performative. This means predictions
because they are made public, or because they inform downstream actions, and
influence the distribution of the features or the target variable they aim to
predict. Thus, shifting the data distribution the model has been trained on.
Prominent examples include stock price prediction, credit scoring, and
predictive policing.

As a result, the performance of a model should not be measured with respect to
a fixed underlying distribution, as in classical supervised learning, but
instead on the very distribution, the model induces. This has been
conceptualized by [Perdomo et al. (2020)] through the framework of
_performative prediction_. As a dynamic setting gives rise to interesting and
new optimization challenges, the objective function in performative prediction
is the risk incurred by the learner on the distribution induced after
deploying the model:

$\displaystyle\mathrm{PR}(\theta)\coloneqq\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\ell(z;\theta),\theta\in\Theta$
(1)

where $\Theta$ is a closed and convex set in ${\mathbb{R}}^{d}$. And
$\mathrm{PR}$ is referred to as the performative risk and measures the loss of
a predictor $\theta$ on the distribution ${\mathcal{D}}(\theta)$ resulting
from its deployment. We focus on finding the minima of the performative risk
(1), known as performative optimal points. The main challenge of performative
risk minimization from an optimization perspective is that the dependence of
the performative risk on the model parameters is two-fold: it appears both in
the distribution ${\mathcal{D}}$ and the loss $\ell$. To decouple these two
dependencies, let us define the _decoupled performative risk_

$\displaystyle\mathrm{DPR}(\theta_{1},\theta_{2})\coloneqq\mathbb{E}_{z\sim{\mathcal{D}}(\theta_{1})}\ell(z;\theta_{2})$

to denote the loss of $\theta_{2}$ measured over the distribution
${\mathcal{D}}(\theta_{1})$. According to this definition we have
$\mathrm{PR}(\theta)=\mathrm{DPR}(\theta,\theta).$

Optimizing the performative risk directly is challenging because the structure
of the objective
$\mathrm{PR}(\theta)=\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\ell(z;\theta)$ is
not under the control of the learner and can be highly non-convex. Thus, for
tackling performative risk minimization by building on classical tools from
the optimization literature we need to better understand the structure of the
objective function, and how properties of the distribution map and the loss
interact.

As an important first step, Miller et al. (2021) identified a natural set of
properties of the loss function and model-induced distribution shift under
which the performative risk is convex. In particular, they showed that linear
dependence of the distribution map on the model parameters $\theta$, together
with strong convexity of the loss function $\ell$ implies global convexity of
$\mathrm{PR}$. In this work, we are interested in studying problems beyond
this specific setting and we intend to address the following question:

_How and under what conditions can we optimize the performative risk?_

In particular, we study how to optimize the performative risk through first-
order information and analyze the suboptimality gap of performative risks.
Noticing the fact that convexity can be relaxed to weaker conditions while the
same convergence guarantees are preserved by gradient-based optimizer, in
Section 3, we show weaker conditions on $\mathrm{DPR}$ still imply desirable
local properties of $\mathrm{PR}$. The properties enjoy generality since they
do not rely on global structural restrictions. In Section 4, we discuss what
information about ${\theta_{\mathrm{PO}}}$ we could have, if starting from a
stable point. The underlying idea is to make use of previous retraining
methods (Perdomo et al., 2020; Mendler-Dünner et al., 2020) converging to
${\theta_{\mathrm{PS}}}$ while the ultimate goal is still reaching
${\theta_{\mathrm{PO}}}$.

##  2 Background

Performativity is a phenomenon that is widely recognized in finance (Clarke,
2012), economics (Callon et al., 2007; Cochoy et al., 2010) and other social
sciences (Roberts, 2009). Following the seminal work by Perdomo et al. (2020)
performativity has increasingly gained attention from the machine learning
community. Performative distribution shifts constitute an instance of a more
general distribution shift problem, where the shift is endogenous to the
problem and entirely caused by the deployed predictive model. In other words,
the deployment of a predictive model represents an intervention to the
population (Mendler-Dünner et al., 2022). The resulting causal feedback
effects invalidate the standard assumption of supervised learning where there
is a static and model-independent data distribution describing the population,
surfacing as distribution shifts.

###  2.1 Key concepts

We first give an overview of two existing concepts characterizing whether
$\theta$ is a desirable solution of performative prediction.

#### Performative stability.

Performative prediction can be viewed as a game between the decision-maker and
the population that responds to the deployed model. The first concept of
optimality in this context is performative stability

${\theta_{\mathrm{PS}}}=\operatorname*{arg\,min}_{\theta}\mathrm{DPR}({\theta_{\mathrm{PS}}},\theta).$
(2)

The expected loss over ${\mathcal{D}}(\theta_{\mathrm{PS}})$ is minimized at
$\theta_{\mathrm{PS}}$. As such stable points constitute a fixed point of so-
called _retraining_ methods, which are heuristically adopted in dealing with
distribution shifts. More specifically, at the $t$-th iteration, these methods
find a set of parameters that minimizes the risk on the previously-generated
distribution ${\mathcal{D}}(\theta_{t})$. It can be formally described as
$\theta_{t+1}=\arg\min_{\theta\in\Theta}\mathrm{DPR}(\theta_{t},\theta).$
Several works have studied the convergence of population-based and stochastic
retraining methods to stable points in the standard framework (Perdomo et al.,
2020; Mendler-Dünner et al., 2020; Drusvyatskiy and Xiao, 2022) as well as
state-dependent extensions (Brown et al., 2022; Li and Wai, 2022; Harris et
al., 2021).

#### Performative optimality.

An alternative solution concept is performative optimality. Performative
optimal points describe models that achieve the minimal loss on the
distribution they induce. In this sense, they are globally optimal in the
following sense:

${\theta_{\mathrm{PO}}}=\operatorname*{arg\,min}_{\theta\in\Theta}\mathrm{DPR}(\theta,\theta).$

It follows from the definition that
$\mathrm{PR}({\theta_{\mathrm{PO}}})\leq\mathrm{PR}({\theta_{\mathrm{PS}}})$
while in general, stable points are not necessarily optimal and optimal points
are not necessarily stable. Furthermore, the two solutions
${\theta_{\mathrm{PS}}}$ and ${\theta_{\mathrm{PO}}}$ can be arbitrarily far
apart from each other, see (Perdomo et al., 2020; Miller et al., 2021). Thus,
retraining does not, in general, serve as a reliable heuristic for finding
optimal points. That being said, we focus on finding performative optima in
this work. There is only a handful of works that study approaches for finding
optimal points. The first to tackle performative optimality was Miller et al.
(2021). They proposed an iterative optimization method for minimizing the
performative risk directly by first learning a model of the distribution map
and then applying a gradient-based procedure to the resulting estimation of
the performative risk. To guarantee the global convergence of such an approach
they studied structural assumptions under which the performative risk is
convex. Around the same time, Izzo et al. (2021) studied _performative
gradient descent_ , an algorithm that directly estimates the gradient of the
performative risk. Technically, they assumed the existence of an estimator
$\hat{f}(\theta)$ so that one can use samples from the distribution
${\mathcal{D}}(\theta)$ to infer $\theta$, an assumption we will revisit later
in this manuscript. To prove convergence to optimal points they directly
assume convexity of the performative risk, an assumption that is hard to
verify.

A different approach has recently been taken by Jagadeesan et al. (2022) who
leveraged tools from the bandits’ literature for minimizing regret under
performativity without making structural assumptions on the performative risk
apart from weak regularity assumptions. Technically, they use data collected
from experiments to build performative confidence bounds to characterize the
regret of unexplored parameters. Their method achieves sublinear regret and is
the first to find optimal points for non-convex performative risk functions.
However, a significant drawback of such a bandit approach is the need for
global exploration, i.e., one needs to explore the entire parameter space to
find the minimizer, something that is often not feasible in practical
applications. Therefore, the focus of this work is on iterative descent
methods that gradually approach optimal points.

###  2.2 Assumptions on the loss function

The loss function in performative prediction takes the same role as the loss
in supervised learning. We discuss classical assumptions from the optimization
literature such as strong convexity and smoothness on the loss function.

######  Assumption 1 (Smoothness)

The loss $\ell(\cdot;\cdot)$ is $\beta$-smooth if for all
$z,z^{\prime},\theta$,

$\|\nabla_{\theta}\ell(z;\theta)-\nabla_{\theta}\ell(z^{\prime};\theta)\|_{2}\leq\beta\|z-z^{\prime}\|_{2}.$

######  Assumption 2 (Strong convexity)

The loss $\ell(\cdot;\cdot)$ is $\gamma$-strongly convex in $\theta$ if for
all $\theta,\theta^{\prime},z$,

$\ell(z;\theta^{\prime})-\ell(z;\theta)\geq\nabla_{\theta}\ell(z;\theta)^{\top}(\theta^{\prime}-\theta)+\frac{\gamma}{2}\|\theta-\theta^{\prime}\|_{2}^{2}.$

Note that this condition reduces to convexity when $\gamma=0$.

These two assumptions characterize the dependence of the loss function on the
model parameters $\theta$ and they are assumed to hold for any realization of
$z$. We will adopt the smoothness assumption in this work and we will discuss
the strong-convexity assumption as well as weaker notions of convexity.

In addition, we will need a regularity assumption for relating changes in the
data distribution to changes in the loss function. Therefore, we will adopt
the Lipschitzness condition w.r.t. $z$, which is common when dealing with
performative distribution shifts (Perdomo et al., 2020; Miller et al., 2021),
namely

######  Assumption 3 (Lipschitzness)

The loss $\ell(\cdot;\cdot)$ is $L$-Lipschitz in $z$ if for all
$z,z^{\prime},\theta$,

$\|\nabla_{z}\ell(z;\theta)-\nabla_{z}\ell(z^{\prime};\theta)\|_{2}\leq
L\|z-z^{\prime}\|_{2}.$

###  2.3 Characterizing the performative shift

Since performative effects are not under the control of the learner and are
typically unknown, we need assumptions on these distribution shifts for
studying the problem and establishing convergence guarantees of algorithmic
approaches. In contrast to classical supervised learning where optimization
techniques are commonly adopted under conditions on the loss function, we need
additional assumptions for performative optimization. This observation is at
the core of the main difficulty in performative prediction and the art is to
couple conditions on the loss function with conditions on the distribution
shift to obtain favorable properties of the resulting performative risk
minimization problem.

We shall first introduce the concept of Wasserstein distance, then we proceed
to the key sensitivity assumption that relates changes in the model parameters
to changes in the distribution.

######  Definition 2.1 (Wasserstein Distance).

The Wasserstein-1 distance, also called Earth-Mover (EM) distance, is defined
as

$W(P_{r},P_{g})=\inf_{\gamma\in\Pi(P_{r},P_{g})}\mathbb{E}_{(x,y)\sim\gamma}\big{[}\>\|x-y\|\>\big{]}~{},$
(3)

where $\Pi(P_{r},P_{g})$ denotes the set of all joint distributions
$\gamma(x,y)$ whose marginals are respectively $P_{r}$ and $P_{g}$.

Intuitively, $\gamma(x,y)$ indicates how much mass must be transported from
$x$ to $y$ in order to transform the distributions $P_{r}$ into the
distribution $P_{g}$. The EM distance then is the ”cost” of the optimal
transport plan. The infimum in Eq. 3 is highly intractable. On the other hand,
the Kantorovich-Rubinstein duality tells us that

$W(P_{r},P_{\theta})=\sup_{\|f\|_{L}\leq 1}\left[\int f(x)dP_{r}(x)-\int
f(x)dP_{\theta}(x)\right]$

This allows us to relate the distance of the expectation of a Lipschitz
function over two different distributions by their Wasserstein distance.

#### Sensitivity.

One commonly used assumption is a weak regularity condition that posits
Lipschitzness of the distribution shift relative to changes in the model
parameters. Intuitively, the idea is, if decisions are made according to
similar predictive models, then the resulting distributions should also be
close. More precisely, the _sensitivity condition_ introduced by Perdomo et
al. (2020) relates changes in the model parameter as measured in Euclidean
distance to changes in the distribution as measured in Wasserstein distance.

######  Assumption 4 (Sensitivity)

The distribution map ${\mathcal{D}}(\cdot)$ is $\epsilon$-sensitive if for all
$\theta,\theta^{\prime}$,

$W({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime}))\leq\epsilon\|\theta-\theta^{\prime}\|_{2}.$

A prominent example of a distribution shift that satisfies the sensitivity
assumption is strategic classification with quadratic costs (Perdomo et al.,
2020). Strategic classification microfounds performative prediction with the
best response model for individual actions (Jagadeesan et al., 2021).

#### Mixture dominance.

Below we present a stronger and more structural assumption on the distribution
shift introduced by Miller et al. (2021) which guarantees the convexity of
$\mathrm{DPR}(\theta^{\prime},\theta)$ w.r.t. the first argument
$\theta^{\prime}$.

######  Assumption 5 (Mixture dominance)

A set of losses and functions satisfy the mixture dominance condition if
$\mathrm{DPR}(\theta^{\prime},\theta)$ is convex w.r.t. $\theta^{\prime}$,
thus for all $\theta,\theta^{\prime}$,

$\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}[\ell(z;\theta)\nabla_{\theta}\log{(p_{\theta}(z))}]^{\top}(\theta^{\prime}-\theta)\leq\mathrm{DPR}(\theta^{\prime},\theta)-\mathrm{PR}(\theta).$

It has been demonstrated by Miller et al. (2021) that this assumption is
satisfied in performative environments by the well-known _location-scale_
distribution family, which is a family of distributions formed by translation
and re-scaling of a standard family member. For example, let the underlying
distribution be ${\mathcal{D}}_{\theta}$, data points
$z_{\theta}\sim{\mathcal{D}}_{\theta}$ satisfies $z_{\theta}=z_{0}+A\theta$,
where the matrix $A$ is an unknown parameter, and $z_{0}$ is is a zero-mean
random variable. Here the additive term $A\theta$ represents the effects of
performativity. Standard examples include Gaussian, Cauchy and uniform
distributions. There have been wide applications for these families in
economic (Wong and Ma, 2008) and statistics (Hazra et al., 2017). Examples of
location families can also be found in strategic classification (Hardt et al.,
2016).

##  3 Beyond convexity of the performative risk

In studying the convergence of gradient-based methods to performative optima,
previous works on performative prediction have focused on a setting where the
performative risk is convex. While some works such as Izzo et al. (2021)
directly start from apriori hard-to-verify assumptions, the notable work by
Miller et al. (2021) provides conditions on the loss function and the
distribution map under which global convexity of $\mathrm{PR}$ emerges. More
specifically they show that strong convexity of the loss function, together
with Assumptions 4-5 to control the performativity effects of distributions,
is sufficient to establish (strong) convexity of the performative risk. They
obtain a zeroth-order algorithm that provably converges towards globally
performative optimal points (${\theta_{\mathrm{PO}}}$) (Miller et al., 2021),
which could avoid generally difficult computing performative gradients.

In the following, we take a step further by demonstrating that the strong
convexity assumption on the loss function can be relaxed while preserving the
amenability of the performative risk minimization problem to gradient-based
optimization. We build on the existing literature on first-order optimization
that showed that convexity can be relaxed to weaker conditions while
maintaining the same convergence guarantees of gradient-based optimizers.

###  3.1 Weaker notions of strong convexity

In the optimization literature, strongly-convex optimization objectives are
playing an important role as they can be optimized using gradient-descent
methods at a linear rate. In the context of finding performatively stable
points, this linear rate can be maintained by retraining methods in the
presence of weak performative shifts (Perdomo et al., 2020).

There are various works in the optimization literature that aim to relax the
strong-convexity condition on the objective function while maintaining
favorable convergence properties. Examples include error bounds (EB) (Luo and
Tseng, 1993; Drusvyatskiy and Lewis, 2018), essential strong convexity (ESC)
(Strömberg, 2011; Liu et al., 2014), weak strong-convexity (WSC) (Ma et al.,
2016; Necoara et al., 2019), restricted secant inequality (RSI) (Zhang and
Yin, 2013; Zhang, 2017), restricted strong-convexity (RSC) (Negahban and
Wainwright, 2012; Zhang and Yin, 2013), Polyak-Lojasiewicz (PL) inequality
(Polyak, 1963; Loizou et al., 2021) and quadratic growth (QG) condition
(Anitescu, 2000; Drusvyatskiy and Lewis, 2018). The relations between these
conditions have been studied in (Liu and Wright, 2015; Karimi et al., 2016;
Bolte et al., 2017; Zhang, 2017). In particular, for a smooth function with
Lipschitz-continuous gradients, Karimi et al. (2016) showed the following
chain of implications:

$(SC)\xrightarrow[]{}(ESC)\xrightarrow[]{}(WSC)\xrightarrow[]{}(RSI)\xrightarrow{}(EB)\equiv(PL)\xrightarrow[]{}(QG).$
(4)

This implication chain is widely used in numerical optimization (Wang et al.,
2017; Nouiehed et al., 2019; Vaswani et al., 2019).

We build on this work to analyze performative prediction from an optimization
perspective. Previous works assumed the loss $\ell$ satisfies strong convexity
(SC) globally which is the strongest condition according to the implication
chain in Eq. 4. Our contribution is to show that weaker conditions on
$\mathrm{DPR}$ still imply desirable local properties of $\mathrm{PR}$.
Specifically, in this work, we prove that assuming WSC and RSI of
$\mathrm{DPR}$ is sufficient to establish WC and RSI of $\mathrm{PR}$,
respectively, following similar steps taken in Miller et al. (2021). These
local conditions only need to hold around the minimizer and do not posit
strong structural restrictions on the overall landscape such as SC, thus
making the assumptions more realistic in practice.

###  3.2 Establishing weak convexity of the performative risk

First, we introduce the _weak strong convexity_ (Karimi et al., 2016; Necoara
et al., 2019) in order to relax the strong convexity conditions. We will
follow the convention that $x_{p}$ denotes the projection of $x$ onto the
optimal solution set ${\mathcal{X}}^{*}$ throughout this paper.

######  Definition 3.1 (WSC).

A function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $\mu$-WSC if for all $x$ we
have

$f^{*}\geq f(x)+\langle\nabla
f(x),x_{p}-x\rangle+\frac{\mu}{2}\|x_{p}-x\|^{2}.$ (5)

where $x_{p}\in{\mathcal{X}}^{*}=\arg\min_{x}f(x)$ and $f^{*}=f(x_{p})$.

We translate this definition to the decoupled performative risk as follows:

###### Assumption 6

For performative optimum ${\theta_{\mathrm{PO}}}$ and its induced distribution
${\mathcal{D}}={\mathcal{D}}({\theta_{\mathrm{PO}}})$, suppose the optimal
solution for minimizing $\mathrm{DPR}({\theta_{\mathrm{PO}}},\cdot)$ is
$\theta^{*}$. We say $\mathrm{DPR}({\theta_{\mathrm{PO}}},\cdot)$ satisfies
$\mu-$WSC, if for any $\theta\in\Theta$ it holds that

$\displaystyle\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta^{*})\geq\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)+\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)^{\top}(\theta^{*}-\theta)+\frac{\mu}{2}\|\theta^{*}-\theta\|^{2}.$
(6)

This definition requires that the minimizer for the expected loss on the
distribution ${\mathcal{D}}$ is unique:
$\theta^{*}=\operatorname*{arg\,min}_{\theta\in\Theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta).$
This is a mild assumption used by previous work focusing on repeated
optimization in performative environments (Mendler-Dünner et al., 2020;
Drusvyatskiy and Xiao, 2022; Wood et al., 2021). Intuitively, we posit a local
property on the structure of $\mathrm{DPR}$ over the _specific_ distribution
${\mathcal{D}}$ induced by ${\theta_{\mathrm{PO}}}$. The quantity is measured
over the domain of model parameter $\theta$. We note that this condition is
already weaker than the strong convexity Assumption 2 which is assumed to be
true for _any data point $z$_ (Miller et al., 2021), thus depending heavily on
the structure of the loss function.

Equipped with Assumption 6, we are ready to state the following new theorem.

######  Theorem 3.2.

Under Assumptions 1, 4-6, suppose the performative optimum is also
performative stable, then the performative risk is guaranteed to be weakly
convex if $\frac{\mu}{2\beta}\geq\epsilon$.

We make justification on the assumption that ${\theta_{\mathrm{PO}}}$ is also
performative stable. As mentioned, optimal points and stable points do not
generally imply each other. Therefore, simply adopting retraining (e.g.,
(Perdomo et al., 2020)) does not return global optima. Nevertheless, the local
properties of $\mathrm{PR}(\theta)$ under this assumption would be really
helpful in determining the optimality of a performative stable point. In the
next section, we will extend to more results on what information about
${\theta_{\mathrm{PO}}}$ we could obtain at a specific stable point without
the assumption.

######  Proof 3.3 (Proof sketch).

Technically, our derivation starts from Eq. 6. After expanding the inequality
around the minimizer of ${\theta_{\mathrm{PO}}}$, we split $\nabla\mathrm{PR}$
into two terms: gradient of the loss function
$\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\nabla_{\theta}\ell(z;\theta)$, and
gradient on the variable distribution
$\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\ell(z;\theta)\nabla_{\theta}\log{p_{\theta}(z)}$,
where $p_{\theta}$ is the probability distribution function of
${\mathcal{D}}(\theta)$. We then use the sensitivity Assumption 4 to bound the
first term by the quadratic distance $\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
and use the mixture dominance Assumption 5 to control the second term.

The $\frac{\mu}{2\beta}$ term in the theorem is a sharp threshold for weak
convexity of the performative risk, which aligns with the observations in
(Perdomo et al., 2020; Miller et al., 2021). See details in Appendix A.

###  3.3 Establishing RSI of the performative risk

The second condition we consider is that _Restricted Secant Inequality_ (Zhang
and Yin, 2013). It is defined as follows:

######  Definition 3.4 (RSI).

A function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ satisfies Restricted Secant
Inequality (RSI) if for all $x$ we have

$\langle\nabla f(x),x-x_{p}\rangle\geq\mu\|x_{p}-x\|^{2}.$ (7)

Again, $x_{p}$ is the projection of $x$ onto the optimal solution set
${\mathcal{X}}^{*}$.

######  Remark 3.5.

A function satisfies restricted strongly convex (RSC) if it is convex and also
satisfies RSI.

###### Assumption 7

For performative optimum ${\theta_{\mathrm{PO}}}$ and its induced distribution
${\mathcal{D}}$, suppose the optimal solution for minimizing
$\mathrm{DPR}({\theta_{\mathrm{PO}}},\cdot)$ is unique and is denoted as
$\theta^{*}$. We say $\mathrm{DPR}({\theta_{\mathrm{PO}}},\cdot)$ satisfies
$\mu-$RSI, if for any $\theta$ it holds

$\displaystyle\langle\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),\theta-\theta^{*}\rangle\geq\mu\|\theta^{*}-\theta\|^{2}$
(8)

######  Theorem 3.6.

Under Assumptions 3-5, and 7, suppose the performative optima is also
performative stable, then $\mathrm{PR}(\theta)$ satisfies RSI.

Note that compared to WSC, the RSI condition is weaker and thus generalizes
more easily in first-order optimization. See details in Appendix A. We
conjecture that specific implementations discussed by Negahban and Wainwright
(2012); Zhang and Yin (2013); Zhang (2017) could be extended to optimize the
$\mathrm{PR}$ in this setting.

##  4 When are local properties sufficient for stability and optimality?

As aforementioned, existing methods in the literature that seek stable points
do not have global optimality guarantees. Meanwhile, current methods aiming at
optimizing $\mathrm{PR}$ _directly_ require local structural assumptions
around the performative optima that may not hold in real settings.

In this section, we investigate relations between stable points and optimal
points. We relate to previous work focusing on the convergence of retraining
methods to stable points (Mendler-Dünner et al., 2020; Drusvyatskiy and Xiao,
2022; Perdomo et al., 2020; Wood et al., 2021; Bianchin et al., 2021) and
argue that if stable points offer a good approximation for optimal points,
then they can serve as a good starting point to ensure convergence to optimal
points with only local assumption on the performative risk.

Suppose the Lipschitzness condition for loss (c.f. Assumption 3) holds
throughout this section, which is standard and mild in learning theory or
optimization theory literature. For any $\theta,\theta^{\prime}$ in the
parameter domain, we could quantify the gap between $\mathrm{PR}(\theta)$ and
$\mathrm{PR}(\theta^{\prime})$ as

$\displaystyle\mathrm{PR}(\theta^{\prime})$
$\displaystyle=\mathrm{DPR}(\theta^{\prime},\theta^{\prime})$
$\displaystyle\geq\mathrm{DPR}(\theta,\theta^{\prime})-LW({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime}))$
$\displaystyle=\mathrm{PR}(\theta)+[\mathrm{DPR}(\theta,\theta^{\prime})-\mathrm{DPR}(\theta,\theta)]-LW({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime})).$

The second term on the RHS measures the distance in the function value between
$\theta$ and $\theta^{\prime}$ over the distribution ${\mathcal{D}}(\theta)$.

In the remainder of this section, we pick $\theta$ to be a stable point (i.e.,
$\theta=\arg\min_{x}\mathrm{DPR}(\theta,x)$) so we can work with the
suboptimality gap of the function. First rewrite the above equation as

$\displaystyle\mathrm{PR}(\theta^{\prime})$
$\displaystyle\geq\mathrm{PR}(\theta)+\Delta_{\theta}(\theta^{\prime})-LW({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime})).$
(9)

where
$\Delta_{\theta}(\theta^{\prime}):=\mathrm{DPR}(\theta,\theta^{\prime})-\mathrm{PR}(\theta)\geq
0$ is the suboptimality of $\theta^{\prime}$ measured over
${\mathcal{D}}(\theta)$

######  Proposition 4.1.

Under Assumption 3, if

$\Delta_{\theta}(\theta^{\prime})\geq
LW({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime})),$ (10)

it holds that

$\mathrm{PR}(\theta)\leq\mathrm{PR}(\theta^{\prime}).$

The proof is straightforward by noticing that, when Eq. 10 holds, we have
$\mathrm{PR}(\theta)\leq\mathrm{PR}(\theta^{\prime})$ for all
$\theta^{\prime}\in\Theta$. Thus $\theta$ is performative optimal according to
definition. Intuitively, Eq. 10 relates changes in the loss to changes in the
distribution.

#### Starting from $\theta$.

Suppose we have reached $\theta$ which is a performative stable point. To
achieve ${\theta_{\mathrm{PO}}}$, we may consider two directions. (1) How is
the performance of $\mathrm{PR}(\theta)$? What is the gap between
$\mathrm{PR}(\theta)$ and the optimal performative risk (denoted as
$\mathrm{PR}^{*}$)? (2) What geometric information about
${\theta_{\mathrm{PO}}}$ could we obtain at $\theta$? As we may believe that
$\theta$ will serve as a good approximation for ${\theta_{\mathrm{PO}}}$ when
the Euclidean distance is close. We believe investigating along the two
directions is promising since it makes use of the large amount of work
focusing on reaching ${\theta_{\mathrm{PS}}}$.

Below, we give three preliminary examples on how some general structural
conditions on the loss function and distribution maps could lead to useful
results related to the two directions.

We show the suboptimality of $\theta$ under Lipschitzness and a type of
boundedness.

######  Example 4.2.

Assume performative shifts are bounded by an absolute value, i.e.,

$W({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime}))\leq B.$

We have the following bound characterizing the suboptimality of $\theta$

$\displaystyle\mathrm{PR}(\theta)-\mathrm{PR}^{*}$ $\displaystyle\leq LB.$
(11)

######  Proof 4.3.

The proof is straightforward by noticing $\Delta_{\theta}(\theta^{\prime})\geq
0$ when $\theta$ being stable. From Eq. 9 we have
$\mathrm{PR}(\theta^{\prime})\geq\mathrm{PR}(\theta)-LB$.

The next two examples will show that ${\theta_{\mathrm{PO}}}$ could not be far
from $\theta$.

######  Example 4.4.

Assume (1) performative shifts are bounded by an absolute value $B$ and (2)
$\Delta_{\theta}(\theta^{\prime})$ satisfies quadratic growth, i.e.,
$\Delta_{\theta}(\theta^{\prime})\geq\gamma\|\theta-\theta^{\prime}\|^{2}$, we
have that performative optimal point ${\theta_{\mathrm{PO}}}$ satisfies

$\|{\theta_{\mathrm{PO}}}-\theta\|\leq\sqrt{\frac{LB}{\gamma}}.$

######  Proof 4.5.

We proof by contradiction. Suppose there exists a performative optimal point
${\theta_{\mathrm{PO}}}$ which is $\sqrt{\nicefrac{{LB}}{{\gamma}}}-$close to
$\theta$. The quadratic growth shows

$\Delta_{\theta}({\theta_{\mathrm{PO}}})\geq LB\geq
LW({\mathcal{D}}(\theta),{\mathcal{D}}({\theta_{\mathrm{PO}}})).$

From Eq. 9 we have
$\mathrm{PR}({\theta_{\mathrm{PO}}})\geq\mathrm{PR}(\theta)$ which contradicts
with the optimality of ${\theta_{\mathrm{PO}}}$.

######  Example 4.6.

Under Assumption 4, suppose $\Delta_{\theta}(\theta^{\prime})$ satisfies
quadratic growth, the performative optimal point ${\theta_{\mathrm{PO}}}$
satisfies

$\|{\theta_{\mathrm{PO}}}-\theta\|\leq\frac{L\epsilon}{\gamma}.$

######  Proof 4.7.

We proof by contradiction. Suppose there exists a performative optimal point
${\theta_{\mathrm{PO}}}$ which is $\nicefrac{{L\epsilon}}{{\gamma}}-$close to
$\theta$. The quadratic growth shows
$\Delta_{\theta}({\theta_{\mathrm{PO}}})\geq\frac{L^{2}\epsilon^{2}}{\gamma}$.
At the meantime, senstitivity assumption 4 shows

$W({\mathcal{D}}(\theta),{\mathcal{D}}({\theta_{\mathrm{PO}}}))\leq\epsilon\|\theta-{\theta_{\mathrm{PO}}}\|\leq\frac{L\epsilon^{2}}{\gamma}.$

Therefore we have $\Delta_{\theta}({\theta_{\mathrm{PO}}})\geq
LW({\mathcal{D}}(\theta),{\mathcal{D}}({\theta_{\mathrm{PO}}}))$. Substituting
the relation into Eq. 9 shows
$\mathrm{PR}({\theta_{\mathrm{PO}}})\geq\mathrm{PR}(\theta)$ which contradicts
with the optimality of ${\theta_{\mathrm{PO}}}$.

To conclude, in this section we attempt to make use of stable points in
finding optima points. Though ${\theta_{\mathrm{PS}}}$ and
${\theta_{\mathrm{PO}}}$ do not imply each other as discussed aforementioned,
we aim at revealing when and how stable points could be served as starting
points for finding optima points. In such scenario, previous work focusing on
convergence of retraining methods to stable points would still be worthy.

Concretely, we have shown several conditions under which stable points offer a
good approximation for optimal points. Then, with only local assumption on
$\mathrm{PR}$, we show that one could start from stable points in an
optimization procedure, and finally, converge to optimal points.

######  Remark 4.8.

An interesting special case where stable points are optimal without requiring
some sort of global optimality is when the Bayesian error of every
distribution is the same. This means all minima are on one level-set. Hence,
no other point can have a smaller loss.

##  5 Conclusion

This paper studies optimization aspects of the performative risk minimization
problem.

First, we relax the standard strong convexity assumption on the loss function
required in prior work to show convergence of iterative optimization methods
in performative prediction. In particular, we study two weaker conditions on
$\mathrm{DPR}$: WSC and RSI – both are sufficient to establish weak convexity
of the performative risk under suitable assumptions on the distribution map.
Our work takes a first step towards importing advanced assumptions from the
classical optimization literature into performative prediction.

Second, we make a contribution by raising interesting questions about the
meaning of local regularity assumptions in the context of performative
prediction. If stable points can be found heuristically and serve as a good
approximation for global optima, the local regularity of $\mathrm{PR}$ can be
sufficient to find optimal points. We provide some bounds on the distance
between optimal and stable points but it remains to better understand how they
relate in practical settings.

As of future work, we note that a very interesting and important topic to
study is the PL condition which is among the weakest assumptions according to
the implication chain and is ubiquitous in over-parameterized neural networks
(Zhou et al., 2021).

Suppose the following $\mu$-PL condition holds

$\frac{1}{2}\left\|\nabla_{\theta^{\prime}}\mathrm{DPR}(\theta,\theta^{\prime})\right\|^{2}\geq\mu(\mathrm{DPR}(\theta,\theta^{\prime})-\mathrm{PR}(\theta))=\mu\Delta_{\theta}(\theta^{\prime}).$

Naturally, we expand the RHS through Eq. 9

$\displaystyle\frac{\left\|\nabla_{\theta^{\prime}}\mathrm{DPR}(\theta,\theta^{\prime})\right\|^{2}}{2\mu}$
$\displaystyle\geq\mathrm{PR}(\theta^{\prime})-\mathrm{PR}(\theta)-LW({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime}));.$

Intuitively, we raise several interesting questions related to finding
performative optima.

  1. 1.

Understanding when and how (e.g., some structural properties of loss function
or a natural set of distributions), it holds that
$W({\mathcal{D}}(\theta),{\mathcal{D}}(\theta^{\prime}))\leq
C\|\nabla_{\theta^{\prime}}\mathrm{DPR}(\theta,\theta^{\prime})\|^{2}$ where
$C$ is a certain constant. Since the condition characterizes local properties
of $\mathrm{DPR}$ near performative stable points, it could be more common in
practice. Notice that current performative prediction literature heavily rely
on sensitivity relation (c.f. Assumption 4).

  2. 2.

What is the impact of data pre-processing steps on the implications of
performative shifts? Can they influence performativity effects? For example,
can data whitening, result in distribution with favorable properties, such as
location-scale family?

## Acknowledgements

The author gratefully acknowledges Aurelien Lucchi and Celestine Mendler-
Dünner for numerous helpful discussions and advice during the internship at
ETH Zürich.

## References

  * Anitescu (2000) Mihai Anitescu.  Degenerate nonlinear programming with a quadratic growth condition.  _SIAM Journal on Optimization_ , 10(4):1116–1135, 2000.
  * Bianchin et al. (2021) Gianluca Bianchin, Miguel Vaquero, Jorge Cortes, and Emiliano Dall’Anese.  Online stochastic optimization for unknown linear systems: Data-driven synthesis and controller analysis.  _arXiv preprint arXiv:2108.13040_ , 2021.
  * Bolte et al. (2017) Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter.  From error bounds to the complexity of first-order descent methods for convex functions.  _Mathematical Programming_ , 165(2):471–507, 2017\.
  * Brown et al. (2022) Gavin Brown, Shlomi Hod, and Iden Kalemaj.  Performative Prediction in a Stateful World.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151, pages 6045–6061. PMLR, 2022\.
  * Callon et al. (2007) Michel Callon et al.  What does it mean to say that economics is performative.  _Do economists make markets_ , pages 311–357, 2007.
  * Clarke (2012) Chris Clarke.  Financial engineering, not economic photography: Popular discourses of finance and the layered performances of the sub-prime crisis.  _Journal of Cultural Economy_ , 5(3):261–278, 2012.
  * Cochoy et al. (2010) Franck Cochoy, Martin Giraudeau, and Liz McFall.  Performativity, economics and politics: An overview.  _Journal of Cultural Economy_ , 3(2):139–146, 2010.
  * Drusvyatskiy and Lewis (2018) Dmitriy Drusvyatskiy and Adrian S Lewis.  Error bounds, quadratic growth, and linear convergence of proximal methods.  _Mathematics of Operations Research_ , 43(3):919–948, 2018.
  * Drusvyatskiy and Xiao (2022) Dmitriy Drusvyatskiy and Lin Xiao.  Stochastic optimization with decision-dependent distributions.  _Mathematics of Operations Research_ , 2022.
  * Hardt et al. (2016) Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic classification.  In _Proceedings of the 2016 ACM conference on innovations in theoretical computer science_ , pages 111–122, 2016.
  * Harris et al. (2021) Keegan Harris, Hoda Heidari, and Steven Z Wu.  Stateful strategic regression.  _Advances in Neural Information Processing Systems_ , 34:28728–28741, 2021.
  * Hazra et al. (2017) Nil Kamal Hazra, Mithu Rani Kuiti, Maxim Finkelstein, and Asok K Nanda.  On stochastic comparisons of maximum order statistics from the location-scale family of distributions.  _Journal of Multivariate Analysis_ , 160:31–41, 2017.
  * Izzo et al. (2021) Zachary Izzo, Lexing Ying, and James Zou.  How to learn when data reacts to your model: performative gradient descent.  In _International Conference on Machine Learning_ , pages 4641–4650. PMLR, 2021.
  * Jagadeesan et al. (2021) Meena Jagadeesan, Celestine Mendler-Dünner, and Moritz Hardt.  Alternative microfoundations for strategic classification.  In _International Conference on Machine Learning_ , pages 4687–4697. PMLR, 2021.
  * Jagadeesan et al. (2022) Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner.  Regret Minimization with Performative Feedback.  In _International Conference on Machine Learning_ , pages 9760–9785. PMLR, 2022.
  * Karimi et al. (2016) Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 795–811. Springer, 2016.
  * Li and Wai (2022) Qiang Li and Hoi-To Wai.  State dependent performative prediction with stochastic approximation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3164–3186. PMLR, 2022.
  * Liu and Wright (2015) Ji Liu and Stephen J Wright.  Asynchronous stochastic coordinate descent: Parallelism and convergence properties.  _SIAM Journal on Optimization_ , 25(1):351–376, 2015.
  * Liu et al. (2014) Ji Liu, Steve Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar.  An asynchronous parallel stochastic coordinate descent algorithm.  In _International Conference on Machine Learning_ , pages 469–477. PMLR, 2014.
  * Loizou et al. (2021) Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien.  Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1306–1314. PMLR, 2021.
  * Luo and Tseng (1993) Zhi-Quan Luo and Paul Tseng.  Error bounds and convergence analysis of feasible descent methods: a general approach.  _Annals of Operations Research_ , 46(1):157–178, 1993.
  * Ma et al. (2016) Chenxin Ma, Rachael Tappenden, and Martin Takáč.  Linear convergence of randomized feasible descent methods under the weak strong convexity assumption.  _The Journal of Machine Learning Research_ , 17(1):8138–8161, 2016.
  * Mendler-Dünner et al. (2020) Celestine Mendler-Dünner, Juan C. Perdomo, Tijana Zrnic, and Moritz Hardt.  Stochastic Optimization for Performative Prediction.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, 2020.
  * Mendler-Dünner et al. (2022) Celestine Mendler-Dünner, Frances Ding, and Yixin Wang.  Predicting from Predictions.  _arXiv preprint arXiv:2208.07331_ , 2022.
  * Miller et al. (2021) John P Miller, Juan C Perdomo, and Tijana Zrnic.  Outside the Echo Chamber: Optimizing the Performative Risk.  In _International Conference on Machine Learning_ , pages 7710–7720. PMLR, 2021.
  * Necoara et al. (2019) Ion Necoara, Yu Nesterov, and Francois Glineur.  Linear convergence of first order methods for non-strongly convex optimization.  _Mathematical Programming_ , 175(1):69–107, 2019\.
  * Negahban and Wainwright (2012) Sahand Negahban and Martin J Wainwright.  Restricted strong convexity and weighted matrix completion: Optimal bounds with noise.  _The Journal of Machine Learning Research_ , 13(1):1665–1697, 2012.
  * Nouiehed et al. (2019) Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn.  Solving a class of non-convex min-max games using iterative first order methods.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Perdomo et al. (2020) Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.  Performative prediction.  In _International Conference on Machine Learning_ , pages 7599–7609. PMLR, 2020.
  * Polyak (1963) Boris Teodorovich Polyak.  Gradient methods for minimizing functionals.  _Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki_ , 3(4):643–653, 1963.
  * Roberts (2009) Brian Roberts.  Performative social science: A consideration of skills, purpose and context.  _Historical Social Research/Historische Sozialforschung_ , pages 307–353, 2009.
  * Strömberg (2011) Thomas Strömberg.  Duality between Fréchet differentiability and strong convexity.  _Positivity_ , 15(3):527–536, 2011.
  * Vaswani et al. (2019) Sharan Vaswani, Francis Bach, and Mark Schmidt.  Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1195–1204. PMLR, 2019.
  * Wang et al. (2017) Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more general.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Wong and Ma (2008) Wing-Keung Wong and Chenghu Ma.  Preferences over location-scale family.  _Economic Theory_ , 37(1):119–146, 2008.
  * Wood et al. (2021) Killian Wood, Gianluca Bianchin, and Emiliano Dall’Anese.  Online projected gradient descent for stochastic optimization with decision-dependent distributions.  _IEEE Control Systems Letters_ , 6:1646–1651, 2021.
  * Zhang (2017) Hui Zhang.  The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth.  _Optimization Letters_ , 11(4):817–833, 2017\.
  * Zhang and Yin (2013) Hui Zhang and Wotao Yin.  Gradient methods for convex minimization: better rates under weaker conditions.  _arXiv preprint arXiv:1303.4645_ , 2013.
  * Zhou et al. (2021) Mo Zhou, Rong Ge, and Chi Jin.  A local convergence theory for mildly over-parameterized two-layer neural network.  In _Conference on Learning Theory_ , pages 4577–4632. PMLR, 2021\.

##  Appendix A Proofs for Section 3

[Proofs for Theorem 3.2]

######  Proof A.1.

At ${\theta_{\mathrm{PO}}}$, since performative optimum is also performative
stable, it is known $\theta^{*}={\theta_{\mathrm{PO}}}$.

Using WSC property we have

$\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}\ell(z;{\theta_{\mathrm{PO}}})\geq\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}\ell(z;\theta)+\langle\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\frac{\mu}{2}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}.$
(12)

Our goal is to characterize the function class of
$\mathrm{PR}(\theta)=\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}[l(z;\theta)]$

Potentially, we expect it to be weak convex w.r.t. $\theta$, i.e.

$\mathrm{PR}({\theta_{\mathrm{PO}}})\geq\mathrm{PR}(\theta)+\langle\nabla\mathrm{PR}(\theta),{\theta_{\mathrm{PO}}}-\theta\rangle,$
(13)

or using the definition of $\mathrm{PR}(\theta)$:

$\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}[l(z;{\theta_{\mathrm{PO}}})]\geq\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}[l(z;\theta)]+\langle\nabla\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}[l(z;\theta)],{\theta_{\mathrm{PO}}}-\theta\rangle.$
(14)

First, we separate the gradient of $\mathrm{PR}$ into

$\displaystyle\nabla_{\theta}\mathrm{PR}(\theta)=\overbrace{\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\nabla_{\theta}\ell(z;\theta)}^{\nabla_{1}}+\overbrace{\mathbb{E}_{z\sim{\mathcal{D}}(\theta)}\ell(z;\theta)\nabla_{\theta}\log{p_{\theta}(z)}}^{\nabla_{2}}.$
(15)

We have

$\displaystyle\qquad\mathrm{PR}({\theta_{\mathrm{PO}}})\geq\mathrm{PR}(\theta)+\langle\nabla\mathrm{PR}(\theta),{\theta_{\mathrm{PO}}}-\theta\rangle$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\Leftarrow}}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)\geq\mathrm{PR}(\theta)+\nabla^{\top}({\theta_{\mathrm{PO}}}-\theta)-\langle\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}\nabla\ell(z;\theta),{\theta_{\mathrm{PO}}}-\theta\rangle-\frac{\mu}{2}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
$\displaystyle\Leftrightarrow\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)\geq\mathrm{PR}(\theta)+\nabla_{2}^{\top}({\theta_{\mathrm{PO}}}-\theta)+\langle\nabla_{1}-\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}\nabla\ell(z;\theta),{\theta_{\mathrm{PO}}}-\theta\rangle-\frac{\mu}{2}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\Leftarrow}}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)\geq\mathrm{PR}(\theta)+\nabla_{2}^{\top}({\theta_{\mathrm{PO}}}-\theta)+(\beta\epsilon-\frac{\mu}{2})\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\Leftarrow}}\frac{\mu}{2}\geq\beta\epsilon$

  1. (i).

Here we use:
$\mathrm{PR}({\theta_{\mathrm{PO}}})\geq\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)+\langle\mathbb{E}_{z\sim{\mathcal{D}}({\theta_{\mathrm{PO}}})}\nabla\ell(z;\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\frac{\mu}{2}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$.

  2. (ii).

This is because $\epsilon$-sensitive of distribution map ${\mathcal{D}}$.

  3. (iii).

Mixture dominance implies:
$\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)\geq\mathrm{PR}(\theta)+\nabla_{2}^{\top}({\theta_{\mathrm{PO}}}-\theta)$.

We conclude that we only need weak strong convexity of $\mathrm{DPR}$, local
mixture dominance and local distribution sensitivity to guarantee that
$\mathrm{PR}$ is weakly-convex to ${\theta_{\mathrm{PO}}}$, instead of
strongly convex everywhere.

[Proofs for Theorem 3.6]

######  Proof A.2.

At ${\theta_{\mathrm{PO}}}$, because performative optimum is also performative
stable, it is known $\theta^{*}={\theta_{\mathrm{PO}}}$.

Using RSI property we have

$\langle\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),\theta-{\theta_{\mathrm{PO}}}\rangle\geq\mu\|{\theta_{\mathrm{PO}}}-\theta\|^{2}.$

We derive back as following, we want to show $\mathrm{PR}$ is $RSI$, i.e.,

$\displaystyle\qquad\langle\nabla_{\theta}\mathrm{PR}(\theta),\theta-{\theta_{\mathrm{PO}}}\rangle\geq\mu^{\prime}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
$\displaystyle\Leftrightarrow
0\geq\mu^{\prime}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}+\langle\nabla_{1},{\theta_{\mathrm{PO}}}-\theta\rangle+\langle\nabla_{2},{\theta_{\mathrm{PO}}}-\theta\rangle$
$\displaystyle\Leftrightarrow
0\geq\mu^{\prime}\|{\theta_{\mathrm{PO}}}-\theta\|^{2}+\langle\nabla_{1}-\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\langle\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\langle\nabla_{2},{\theta_{\mathrm{PO}}}-\theta\rangle$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\xLeftarrow{}}}0\geq(\mu^{\prime}+\beta\epsilon)\|{\theta_{\mathrm{PO}}}-\theta\|^{2}+\langle\nabla_{\theta}\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\langle\nabla_{2},{\theta_{\mathrm{PO}}}-\theta\rangle$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\xLeftarrow{}}}0\geq(\mu^{\prime}+\beta\epsilon)\|{\theta_{\mathrm{PO}}}-\theta\|^{2}+\langle\nabla\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle+\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)-\mathrm{PR}(\theta)$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\xLeftarrow{}}}0\geq(\mu^{\prime}+\beta\epsilon+L\epsilon)\max(\|{\theta_{\mathrm{PO}}}-\theta\|,\|{\theta_{\mathrm{PO}}}-\theta\|^{2})+\langle\nabla\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),{\theta_{\mathrm{PO}}}-\theta\rangle$

because

  1. (i).

Because we have $\epsilon$-sensitiveness of distribution map ${\mathcal{D}}$.

  2. (ii).

From mixture dominance we know
$\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta)\geq\mathrm{PR}(\theta)+\langle\nabla_{2},{\theta_{\mathrm{PO}}}-\theta\rangle$.

  3. (iii).

This is because of $L$-Lipschitzness of loss function w.r.t. $z$.

We have 1) If
$\|{\theta_{\mathrm{PO}}}-\theta\|^{2}\leq\|{\theta_{\mathrm{PO}}}-\theta\|$
(close to optimum), then

$\displaystyle\underbrace{\langle\nabla\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),\theta-{\theta_{\mathrm{PO}}}\rangle}_{\geq\mu\|{\theta_{\mathrm{PO}}}-\theta\|^{2}}\geq(\mu^{\prime}+\beta\epsilon+L\epsilon)\|{\theta_{\mathrm{PO}}}-\theta\|$
(16)

The retrodiction shows when assuming $\mathrm{DPR}$ is $\mu$-RSI, then our
goal is achieved if

$\displaystyle\mu^{\prime}=\mu\|{\theta_{\mathrm{PO}}}-\theta\|-(\beta+L)\epsilon\geq
0$ (17)

2) If
$\|{\theta_{\mathrm{PO}}}-\theta\|\leq\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
then

$\displaystyle\langle\nabla\mathrm{DPR}({\theta_{\mathrm{PO}}},\theta),\theta-{\theta_{\mathrm{PO}}}\rangle\geq\mu\|{\theta_{\mathrm{PO}}}-\theta\|^{2}\geq(\mu^{\prime}+\beta\epsilon+L\epsilon)\|{\theta_{\mathrm{PO}}}-\theta\|^{2}$
(18)

The retrodiction shows: when assuming $\mathrm{DPR}$ is $\mu$-RSI, then our
goal is achieved if

$\displaystyle\mu^{\prime}=\mu-(\beta+L)\epsilon\geq 0$ (19)

Proof is completed.