# Performative Prediction with Bandit Feedback: Learning through
Reparameterization

Yatong Chen
Computer Science and Engineering
University of California, Santa Cruz
Santa Cruz, CA, 95064 Wei Tang
Data Science Institute
Columbia University
New York, NY, 10027 Chien-Ju Ho
Computer Science and Engineering
Washington University in St. Louis
St. Louis, MO, 63130 Yang Liu
Computer Science and Engineering
University of California, Santa Cruz
Santa Cruz, CA, 95064 ychen592 (at) ucsc.eduwt2359 (at) columbia.educhienju.ho
(at) wustl.eduyangliu (at) ucsc.edu

###### Abstract

Performative prediction, as introduced by [26], is a framework for studying
social prediction in which the data distribution itself changes in response to
the deployment of a model. Existing work in this field usually hinges on three
assumptions that are easily violated in practice: that the performative risk
is convex over the deployed model, that the mapping from the model to the data
distribution is known to the model designer in advance, and the first-order
information of the performative risk is available. In this paper, we initiate
the study of performative prediction problems that do not require these
assumptions. Specifically, we develop a reparameterization framework that
reparametrizes the performative prediction objective as a function of the
induced data distribution. We also develop a two-level zeroth-order
optimization procedure, where the first level performs iterative optimization
on the distribution parameter space, and the second level learns the model
that induced a particular target distribution parameter at each iteration.
Under mild conditions, this reparameterization allows us to transform the non-
convex objective into a convex one and achieve provable regret guarantees. In
particular, we provide a regret bound that is sublinear in the total number of
performative samples taken and is only polynomial in the dimension of the
model parameter. On the application side, we believe our method is useful for
large online recommendation systems like YouTube or TikTok, where the
recommendation update frequency is high and might potentially reshape future
preferences.

##  1 Introduction

_Performative prediction_ , as introduced by [26], provides a framework for
studying prediction and risk minimization when the data distribution itself
changes in response to the deployment of a model. Such phenomena, usually
addressed as “performativity”, are prevalent in various social prediction
contexts, including education, recommendation systems, and criminal
prediction, among others [26, 3, 12, 6, 16, 4]. For instance, consider a
college admissions process that places significant importance on standardized
test scores; this can incentivize students to invest more effort in test
preparation, ultimately leading to a pool of applicants with much higher test
scores overall than expected.

This phenomenon is also prevalent in web applications, where the update
frequency for the recommendation algorithm is high and might potentially
reshape users’ future behavior. Below, we provide a few examples of when
performativity can potentially occur in web settings: Large-Scale
Recommendation Systems. Consider video platforms (e.g., TikTok, Netflix, and
YouTube) that provide personalized recommendations. These recommendations can
influence users’ future preferences and lead to a shift in the user-advertiser
interaction patterns, creating a dynamic and evolving data distribution.

Online Advertising Imagine an online advertising platform that uses machine
learning models to target users with ads. These models analyze user behavior
and characteristics to display personalized advertisements. Performativity in
this context occurs when the deployment of these models changes the behavior
of both users and advertisers, creating a feedback loop.

Real-Time Suggestions In online proofreading tools such as Grammarly or Google
Docs, features like auto-correction and predictive text suggestions could
alter forthcoming content. Mathematically, consider the standard empirical
risk minimization (ERM) problem defined by a loss function $\ell$, model
parameter space $\Theta\subset\mathbb{R}^{d_{\Theta}}$, instance space
$Z=X\times Y$, and a _fixed_ data distribution $\mathcal{D}$ over $Z$. The
task is to find a model that minimizes the empirical risk defined as:

$\mathsf{ER}(\theta,\mathcal{D}):=\mathbb{E}_{z\sim\mathcal{D}}[\ell(z;\theta)]~{}.$

Performative prediction extends this learning task by positing that
$\mathcal{D}$ is _not_ fixed but is, instead, a function over the model
parameter $\theta\in\Theta$. Here, we call $\mathcal{D}(\cdot)$ a
_distribution map_ , and $\mathcal{D}(\theta)$ the data distribution _induced_
by the model $\theta$. The objective is then to minimize the _performative
risk_ , defined as

$\displaystyle\mathsf{PR}(\theta,\mathcal{D}(\theta)):=\mathbb{E}_{z\sim\mathcal{D}(\theta)}[\ell(z;\theta)]~{}.$

Intuitively, the performative prediction risk evaluates the model $\theta$’s
performance on the resulting distribution $\mathcal{D}(\theta)$ via the loss
function $\ell$. When it is clear from the content, we also use
$\mathsf{PR}(\theta)$ to shorthand the performative risk.

Optimizing the performative risk is challenging in general. In standard ERM, a
convex loss function $\ell$ implies a convex empirical risk. But as [26]
observed, the performative risk $\mathsf{PR}(\cdot)$ may be non-convex even
when the loss $\ell$ itself is convex. For this reason, earlier studies [26,
22, 8, 2] focused on computing a _performative stable_ solution instead, which
is easier to achieve using standard optimization tools like repeated risk
minimization. A performative stable model is loss-minimizing _on the data
distribution it induces_ , though other models may incur smaller losses on
their respective induced distributions. However, as recent works [23, 14]
point out, such stable solutions may be highly suboptimal and, worse yet, may
not exist in certain settings.

One major challenge in performative risk minimization is the unknown
distribution map between the model parameter $\theta$ and the distribution
$\mathcal{D}(\theta)$ without making any structural assumption. For example,
one can hardly anticipate the click-through rate of an ad without putting out
the ad first. In the language of performative prediction, only by deploying a
model $\theta$ can the learner observe data samples that are i.i.d realized
from the induced data distribution $\mathcal{D}(\theta)$. Due to this inherent
uncertainty about $\mathcal{D}(\theta)$, it is impossible to compute the
gradient of $\mathsf{PR}(\theta)$ w.r.t $\theta$, not to mention finding a
model with the lowest performative risk offline. Instead, the learner must
interact with the environment and deploy models $\theta$ to explore the
induced distributions $\mathcal{D}(\theta)$, which involves deploying
“imperfect” models on decision subjects.

In this paper, we propose to measure the loss incurred by deploying a sequence
of models $\theta_{1},\ldots,\theta_{T_{\textsf{total}}}$ by evaluating the
following regret measured with respect to the total number of samples deployed
during the process:

$\displaystyle\mathcal{R}_{N}(\mathcal{A},\mathsf{PR})=\sum_{\tau=1}^{T_{\textsf{total}}}\sum_{i=1}^{n_{\tau}}\ell(z_{\tau}^{(i)};\theta_{\tau})-N\cdot\mathsf{PR}(\theta_{\texttt{OPT}})$
(1)

where $N:=\sum_{\tau=1}^{T_{\textsf{total}}}n_{\tau}$ denotes the total number
of observed data samples throughout the process, $\mathcal{A}$ corresponds to
the particular algorithm, and $\mathsf{PR}$ represents the objective function.
This regret measures the suboptimality of the deployed sequence of models
relative to a performative optimum
$\theta_{\texttt{OPT}}\in\operatorname{argmin}_{\theta}\mathrm{PR}(\theta)$ in
terms of how much loss they incur on the population with $N$ decision
subjects.

In contrast to earlier studies that primarily assess the final model’s
performance based on optimality rather than the cumulative loss incurred
throughout the process, we argue that this constitutes a more practical
evaluation metric in predictive scenarios involving multiple rounds of human
feedback. In particular, since the process of finding the optimal performative
model involves deploying sub-optimal models on human agents in the process, it
is more appropriate to define regret on the total number of agents that are
subjected to the “imperfect” algorithmic system rather than only caring about
whether the final model is optimal. We believe this provides a unique
evaluation metric suitable for performative prediction.

Later in Section 6, we compare our proposed regret definition with the
standard regret measured in $T_{\textsf{total}}$ in more detail and show that
our algorithm is, in fact, also sublinear in the total deployment steps
$T_{\textsf{total}}$. This, combined with the fact that sublinear regret
implies model convergence (Proposition 1), also means that our algorithm can
guarantee to output a model arbitrarily close to the performative optimal
model $\theta_{\texttt{OPT}}$.

###  1.1 Our Contributions

We study the problem of performative regret minimization based on performative
feedback through reparametrization. Our main contributions are a two-level
zeroth order optimization algorithm that achieves a sublinear regret bound
measured using the total number of samples, as well as a novel
reparametrization framework that attempts to tackle a particular kind of non-
convex performative prediction problem.

#### Reparametrization Framework.

Departing from previous work, we allow $\mathsf{PR}(\theta)$ to be non-convex
in the model parameter $\theta$, but suppose it is convex in the _data
distribution_ parameter $\phi\equiv\varphi(\theta)$. Informally, under mild
conditions, we show that non-convex $\mathsf{PR}(\theta)$ can be
reparameterized as a new (convex) function $\mathsf{PR}^{\dagger}(\phi)$ over
the induced data distribution parameter $\phi$. We discuss detailed
parametrization procedure in Section 3.

#### Zeroth-Order Optimization Algorithm with Performativity.

Given the parametrization framework proposed above, we propose a two-level
zeroth-order optimization procedure, which, to our knowledge, is novel in
performative prediction. The outer loop optimizes the objective function
$\mathsf{PR}$ in the distribution parameter space $\phi\in\Phi$ iteratively
and tries to find the optimal data parameter
$\phi_{\texttt{OPT}}=\varphi(\theta_{\texttt{OPT}})$, while the inner loop
($\operatorname{\mathsf{LearnModel}}$) tries to find a model parameter to
induce the particular data parameter that the outer loop is currently
iterating on. This approach allows for various levels of noise tolerance
coming from function estimations and the use of oracles.

We summarize the regret guarantee as follows:

######  Theorem 1 (Informal).

There exists an algorithm that, under appropriate conditions, incurs regret
$\widetilde{O}((d_{\Theta}+d_{\Phi})\cdot N_{\mathsf{KL}}^{1/6}\cdot
N^{5/6})$111$\widetilde{O}(\cdot)$ suppresses polylogarithmic factors in $N$
and the failure probability $1/p$. after $N$ performative samples222Samples
that the learner deploys along the way of finding the performative optimal
model. with probability at least $1-p$, where $N_{\mathsf{KL}}$ depends on the
sample efficiency of an off-the-shelf estimator for KL divergence, and
$d_{\Theta}$ and $d_{\Phi}$ denote the dimension of the model and distribution
parameter space, respectively.

$N_{\mathsf{KL}}$ term in our regret depends on the sample efficiency of the
estimator for KL divergence. The discussion is detailed in Section 5.

Compared to a closely related recent work [15] that proposes using the
Lipschitz bandit approach to find the performative optimal model without
explicitly making the convexity assumption, our regret has a polynomial
dependency on the model parameter and distribution parameter dimension rather
than exponential dependency.

Overall, we believe our method (i.e., zeroth-order optimization with the
presence of performativity) enjoys the following benefits: Flexibility and
Applicability to Real-World Problems Since our method is zeroth-order
optimization based, it is particularly useful for decision-making in scenarios
where the underlying processes are complex, uncertain, or difficult to model
accurately, such as in financial portfolio optimization, engineering design,
and hyperparameter tuning for ML models. In particular, unlike the traditional
gradient-based optimization procedure, our method does not require the
explicit calculation of gradients that may be complex or unavailable.

Black-Box Models When dealing with models or systems that are treated as black
boxes, where the internal mechanisms are not well understood (such as
complicated economic system), our method can still be effective since it
doesn’t require knowledge of the underlying model structure.

Robustness to Noise In many real-world applications, objective function
evaluations may be noisy or subject to uncertainty, such as modeling consumer
behavior or market behavior and dynamics. Our method can handle noisy
evaluations and make decisions that are robust to noise.

###  1.2 Related work

Our work most closely relates to performative prediction and zeroth-order
optimization. Due to page limit, we include additional related work in
Appendix G, including detailed comparisons of our work to three closely
related jobs ([15, 23, 20]), and more recent developments of performative
prediction.

#### Performative Prediction.

Performative Prediction, first explored in [26], has recently received much
follow-up work [23, 14, 8, 22, 2, 15, 7, 5, 27]. The original work and the
follow-ups both study the performative stability and the performative
optimality, including proposing an algorithmic procedure that converges to
performatively stable or optimal points. Like other works [7, 15, 14, 23], our
paper focuses on performative optimality. Another recent work by [15] proposes
using the Lipschitz bandit approach to solve the performative prediction
problem.

#### Zeroth-Order Optimization.

Our algorithms and techniques are based on the line of work on zeroth-order
optimization (also known as bandit optimization) initiated by [9], who has
shown how to optimize an unknown convex function $f$, using only function
value query access to $f$. [1, 31] later extend the technique that allows
multiple points query and showed that two points suffice to guarantee that the
regret bounds closely resemble bounds for the full information case. To deal
with non-convex performative risk, we use a reparameterization approach to
transform the performative risk as a function over the induced data
distribution parameter. The reparameterization approach mirrors the intuition
behind the algorithms proposed for learning from revealed feedback or
preferences (see, e.g., [29, 34, 6]), which consider a _Stackerlberg game_
involving a utility-maximizing learner and strategic agent. Our work differs
from theirs as we consider a different problem – performative prediction, and
the environment responding to the learner’s model deployment is exogenously
characterized by a distribution map $\mathcal{D}(\cdot)$.

###  1.3 Notations

In this paper, $\|\cdot\|$ always denotes the $\ell_{2}$ norm, and Lipschitz
condition is with respect to $\ell_{2}$. Let $d\in\mathbb{Z}_{>0}$ denote the
dimension of the data,
$\mathbb{S}^{d}:=\\{z\in\mathbb{R}^{d}~{}|~{}\|z\|=1\\}$ and
$\mathbb{B}:=\\{z\in\mathbb{R}^{d}~{}|~{}\|z\|\leq 1\\}$ refer to the unit
sphere and ball, respectively. Given a function $f$, a constant $\delta>0$,
and $v$ that is uniformly sampled from $\mathbb{B}^{d}$, let
$\hat{f}(x):=\mathbb{E}_{v\sim\mathbb{B}^{d}}[f(x+\delta v)]$ refer to the
value of $f$ at $x$ _smoothed over the $\delta$-ball_, and
$x_{\delta}:=\Pi_{(1-\delta)X}(x)$ is the $\ell_{2}$-projection of $x$ onto
the subset $(1-\delta)X:=\\{(1-\delta)x~{}|~{}x\in X\\}$.

Let $d_{\Theta}\in\mathbb{Z}_{>0}$ denote the dimension of the model parameter
$\theta$, and let
$D_{\Theta}:=\sup\\{\|\theta-\theta^{\prime}\|,\forall\theta,\theta^{\prime}\in\Theta\\}$
denote the diameter of the model parameter space $\Theta$. The data
distribution $\mathcal{D}(\theta)$ has a parametric continuously
differentiable density $p(z;\varphi(\theta))$ where $\varphi(\theta)$ denote
the distribution parameter for $\mathcal{D}(\theta)$. We use $\varphi(\cdot)$
to denote the distribution parameter mapping while $\phi$ to denote a given
distribution parameter. Let $d_{\Phi}\in\mathbb{Z}_{>0}$ denote the dimension
of the model parameter $\phi$, and let
$D_{\Phi}:=\sup\\{\|\phi-\phi^{\prime}\|~{}|,\forall\phi,\phi^{\prime}\in\Phi\\}$
denote the diameter of the model parameter space $\Phi$. When it is clear from
the content, we use $\varphi(\theta)$ to represent $\mathcal{D}(\theta)$ the
distribution $\theta$ induces. Let $\vartheta^{*}(\phi)$ denote the _optimal_
model parameter that induces a specific target distribution parameter $\phi$ –
in case of having multiple model parameters that potentially induce the same
distribution parameter $\phi$, $\vartheta^{*}(\phi)$ is the one that achieves
the minimum performative prediction risk.

###  1.4 Structure of the Paper

The rest of the paper is organized as follows: In Section 2, we introduce the
problem formulation and provide a warm-up setting when $\mathsf{PR}(\theta)$
is convex over the model parameter $\theta$. Using this simple setting, we
introduce the zeroth-order optimization technique we use, which will serve as
the building block to solve for a more complicated setting (i.e., when
$\mathsf{PR}(\theta)$ is not convex over $\theta$). We also present a
fundamental fact in convex optimization that sublinear regret implies model
convergence (Proposition 1), which unifies the goal of regret minimization and
model optimality in our setting. In Section 3, we provide an overview of our
proposed solution – we first describe the _reparameterization_ procedure that
transforms $\mathsf{PR}(\theta)$ into an indirectly convex function over the
distribution parameter $\phi$, and then describe a two-level bandit
optimization framework that operates on the distribution parameter space. In
Section 4, we describe the outer algorithm, and Section 5 describes the inner
algorithm called $\operatorname{\mathsf{LearnModel}}$, which is used to solve
a subroutine problem using black-box oracle. Section 6 contains the overall
regret analysis. Lastly, in Section 7, we discuss the limitations and
potential future work.

All omitted proofs can be found in the Appendix.

##  2 Preliminaries

We begin by formally defining our problem.

###  2.1 Problem Formulation

Restating from the introduction, we largely extend from the traditional
empirical risk minimization (ERM) problem defined by a loss function $\ell$,
model parameter space $\Theta\subset\mathbb{R}^{d_{\Theta}}$, instance space
$Z=X\times Y$, and a fixed data distribution $\mathcal{D}$ over $Z$. Our
setting, or rather _performative prediction_ in general, extends this learning
task by positing that the real risk $\mathsf{PR}(\theta)$ encounters is over
an induced distribution $\mathcal{D}(\theta)$ by a machine learning model
$\theta\in\Theta$, where the distribution $\mathcal{D}(\theta)$ is
parametrized by a distribution parameter $\varphi(\theta)$. In other words,
the underlying data distribution is no longer fixed but is instead a function
of the model parameter $\theta$. Here, we call $\mathcal{D}(\cdot)$ a
_distribution map_.

The objective of performative prediction is then to minimize the _performative
risk_ defined as
$\mathsf{PR}(\theta):=\mathbb{E}_{z\sim\mathcal{D}(\theta)}[\ell(z;\theta)]~{}.$
A model $\theta_{\texttt{OPT}}\in\Theta$ is said to be _performatively
optimal_ if
$\mathsf{PR}(\theta_{\texttt{OPT}})=\min_{\theta\in\Theta}\mathsf{PR}(\theta)$.
To find the performatively optimal model, one usually needs to have the full
knowledge of the underlying distribution map
$\mathcal{D}:\Theta\rightarrow\Phi$. In this work, we consider a more
practical scenario where the distribution map $\mathcal{D}(\cdot)$ is not
known in advance, and to learn the performatively optimal model, the learner
has to adaptively deploy models with gradually learning the underlying
distribution map.

Formally, we consider the following repeated interaction between the learner
and the environment consisting of decision subjects where we can only query
through samples. The interaction proceeds for $T_{\textsf{total}}$ steps, at
each time step $\tau=1,\ldots,T_{\textsf{total}}$: (1) the learner deploys a
model $\theta_{\tau}\in\Theta$; (2) the learner observes $n_{t}$ data samples
$z_{\tau}^{(i)}\overset{\text{iid}}{\sim}\mathcal{D}(\theta_{\tau})$; (3) the
learner incurs empirical loss $\ell(z_{\tau}^{(i)};\theta_{\tau})$ for each
sample.

The goal of the learner is to design an online model deployment policy
$\mathcal{A}$ such that it minimizes her cumulative empirical risk over all
observed data samples:

$\displaystyle\mathcal{R}_{N}(\mathcal{A},\mathsf{PR})=\sum_{\tau=1}^{T_{\textsf{total}}}\sum_{i=1}^{n_{\tau}}\ell(z_{\tau}^{(i)};\theta_{\tau})-N\cdot\mathsf{PR}(\theta_{\texttt{OPT}})$
(2)

where $N:=\sum_{\tau=1}^{T_{\textsf{total}}}n_{\tau}$ denotes the total number
of observed data samples throughout the process. The reason we introduce
$T_{\textsf{total}}$ instead of $N$ directly is because each step ($\tau$) of
our algorithm performs different tasks, where we would impose different
requirements of samples to be collected. This shall become clear later when we
present our algorithm in the following sections.

###  2.2 Warmup Setting: When $\mathsf{PR}(\theta)$ is Convex in $\theta$

In this section, we analyze a simple scenario when we assume that the
performative risk $\mathsf{PR}(\theta)$ is convex over the model parameter
$\theta$. The technique we use to solve this simple case will be the building
block to solve the later more challenging problem where $\mathsf{PR}(\theta)$
is not convex over the model parameter $\theta$.

Recall that when the learner deploys a model $\theta$, she observes a set of
data samples which are i.i.d drawn from the underlying data distribution
$\mathcal{D}(\theta)$. This enables us to compute an unbiased estimate
$\widetilde{\mathsf{PR}}(\theta)$ for the performative risk
$\mathsf{PR}(\theta)$ of the deployed model $\theta$:

$\displaystyle\widetilde{\mathsf{PR}}(\theta)=\frac{1}{n_{t}}\sum_{i=1}^{n_{t}}\ell(z_{t}^{(i)};\theta),\quad\text{and}\quad\mathbb{E}[\widetilde{\mathsf{PR}}(\theta)]=\mathsf{PR}(\theta),\qquad\forall\theta\in\Theta$

where the expectation is over the randomness of the observed samples. Since
$\mathsf{PR}(\theta)$ is convex over the model parameter $\theta$, one can use
an off-the-shelf zeroth-order convex optimization technique [1] to solve this
problem and get the following regret guarantee:

######  Lemma 1.

When $\mathsf{PR}(\theta)$ is convex, $L$-Lipschitz w.r.t. the deployed model
parameter $\theta$, there exists an algorithm (Algorithm 3) achieving
$\mathcal{R}_{N}(\mathcal{A}_{\ref{algorithm:minimize-convex-
function}},\mathsf{PR})=O(\sqrt{d_{\Theta}N\log\frac{1}{p}})$ with probability
at least $1-p$, where $N$ is the total number of samples deployed during the
process.

We defer the proof and the details of Algorithm 3 to Appendix B. In
particular, Algorithm 3 deploys two models at each time step, in doing so, one
can show that the regret bounds closely resemble bounds for the full
information case where the learner knows the distribution map
$\mathcal{D}(\cdot)$. The proof of the above result builds on the main result
of [1], and also incorporates an improved analysis of the gradient estimate
due to [31].

###  2.3 Useful Fact: Sublinear Regret Implies Convergence in Model Optimality

A well-known fact in online and zeroth order optimization is that if a
function $f$ is convex and we wish to converge to an approximately optimal
point, it suffices to show a query algorithm that achieves $o(n)$ regret after
$n$ queries. In particular, we have the following proposition:

######  Proposition 1 (Sublinear Regret Implies Convergence).

Let $f:X\to\mathbb{R}$ be convex, and let $\mathcal{A}$ be an algorithm for
minimizing $f$ whose regret after $n$ queries is sublinear in $n$, i.e.
$\mathcal{R}_{n}(\mathcal{A},f)=o(n)$. Then we can compute an
$\epsilon$-suboptimal point for $f$ in
$\mathcal{R}_{n}(\mathcal{A},f)/\epsilon$ queries of $f$.

###### Proof.

Let $x_{1},\ldots,x_{n}$ be the first $n$ points queried by $\mathcal{A}$. By
the convexity of $f$, the average of these points
$\bar{x}=\frac{1}{n}\sum_{i}x_{i}$ satisfies

$\displaystyle
f(\bar{x})-f(x^{*})\leq\frac{1}{n}\sum_{i=1}^{n}\left[f(x_{i})-f(x^{*})\right]=\frac{\mathcal{R}_{n}(\mathcal{A},f)}{n}$

Thus if $\mathcal{R}_{n}(\mathcal{A},f)=o(n)$, then after
$n=\mathcal{R}_{n}(\mathcal{A},f)/\epsilon$ queries, $\bar{x}$ satisfies
$f(\bar{x})-f(x^{*})\leq\epsilon$ as required. ∎

This proposition holds great significance for us, as it establishes a strong
link between achieving sublinear regret and the convergence towards an optimal
model. It implies that if our proposed algorithm attains a sublinear regret as
defined in Equation 1, this automatically suggests that we can obtain an
almost optimal model, which is exceptionally close to the truly optimal model,
denoted as $\theta_{\texttt{OPT}}$. This closeness is achieved simply by
averaging the models $\theta_{1},\ldots,\theta_{T_{\textsf{total}}}$
throughout the deployment process. This helps us unify the goal of regret
minimization and find the optimal model.

##  3 Optimizing $\mathsf{PR}$ via Reparameterization: An Overview of Our
Solutions

When $\mathsf{PR}(\theta)$ is not convex over the model parameter $\theta$,
the zeroth-order convex optimization technique used in Section 2.2 is not
directly applicable. Instead, we leverage the structure of
$\mathsf{PR}(\theta)$ and reparameterize it as a function of the _induced_
data distribution $\mathcal{D}(\theta)$. In particular, we consider the
setting where the data distribution $\mathcal{D}(\theta)$ has a parametric
continuously differentiable density $p(z;\varphi(\theta))$, and the functional
form $p(z;\phi)$ is known to the learner but the the distribution parameter
$\phi$ remains unknown. Under mild conditions, we show that the performative
risk $\mathsf{PR}(\theta)$ can be expressed as a function of the _induced_
distribution distribution parameter $\phi\equiv\varphi(\theta)$, namely,

$\displaystyle\mathsf{PR}(\theta)=\mathsf{PR}^{\dagger}(\varphi(\theta))\equiv\mathsf{PR}(\vartheta^{*}(\phi))~{},$
(3)

and $\mathsf{PR}^{\dagger}(\phi)$ is convex over the distribution parameter
$\phi$ (See more details in Section 4).

With this reparameterization, one can operate on the space of distribution
parameters and hopefully apply the zeroth-order convex optimization technique.
However, one notable challenge is in zeroth-order convex optimization, the
learner is usually assumed to have an direct query access to an unknown convex
function $f$. Namely, when querying point $x$, the learner immediately knows
the (noisy) value of $f(x)$. In our setting, such direct access is not
available since the mapping $\varphi(\cdot)$ is not known to the learner.
Indeed, the learner can only deploy a model $\theta$ to observe the empirical
performative risk $\widetilde{\mathsf{PR}}(\theta)$ which is evaluated over
the observed data samples that are drawn from the induced data distribution
$\mathcal{D}(\theta)$. Hence, to evaluate the value
$\mathsf{PR}^{\dagger}(\phi)$ on a target data distribution with the parameter
$\phi$, we develop another algorithm called
$\operatorname{\mathsf{LearnModel}}$ to find a model $\bar{\theta}$ such that
$\varphi(\bar{\theta})\approx\phi$ (See Section 5).

#### Summary of our proposed procedure.

Intuitively, the outer loop optimizes the objective function $\mathsf{PR}$ in
the distribution parameter space $\phi\in\Phi$ iteratively and tries to find
the optimal data parameter $\phi*$, while the inner loop
($\operatorname{\mathsf{LearnModel}}$) tries to find a model parameter to
induce the particular data parameter that the outer loop is currently
iterating on 333 One might wonder how to find the optimal
$\vartheta^{*}(\phi)$ when there are two model parameters $\theta$ and
$\theta^{\prime}$ that realize the same $\phi$ (i.e.,
$\varphi(\theta)=\varphi\left(\theta^{\prime}\right)$ and
$\mathsf{PR}\left(\theta^{\prime}\right)\geq\mathsf{PR}(\theta))$. Recall that
the objective function for $\operatorname{\mathsf{LearnModel}}$ is to find
_any_ model $\theta$ that leads to the particular target data parameter $\phi$
such that $\varphi(\theta)=\phi$. It is quite possible that multiple models
can induce the same target data parameter; however, since the goal is to find
any one of them, having multiple model parameters won’t be an issue – in fact,
it can only help speed up the process. We summarize the procedure in our
algorithm in the Figure 1.

Figure 1: Illustration of our procedure (Algorithm 1). Each big block
represents one iteration of the outer algorithm, which consists of three sub-
steps: Step 1, the learner first computes the two target distribution
$\phi^{+}_{t}$ and $\phi^{-}_{t}$ (corresponds to the white section), Step 2,
the learner uses $\operatorname{\mathsf{LearnModel}}$ to learn the
corresponding model $\hat{\theta}^{+}_{t}$ and $\hat{\theta}^{-}_{t}$ that can
best approximately induce $\phi^{+}_{t}$ and $\phi^{-}_{t}$(corresponds to the
grey section) correspondingly. Step 3, the learner deploys
$\hat{\theta}^{+}_{t}$ and $\hat{\theta}^{-}_{t}$ and perform a gradient
update and get $\phi_{t+1}$. Each deployment of
$\operatorname{\mathsf{LearnModel}}$ requires a total number of $S$ steps.
Thus, the total number of steps involved in the whole procedure is
$T_{\textsf{total}}=T\times S$.

###  3.1 Examples of $\mathsf{PR}$ Being Convex in $\phi$ not in $\theta$

We first provide an example in which our condition ($\mathsf{PR}$ loss is
convex in the induced distribution parameter $\varphi_{\theta}:=\phi(\theta)$,
but non-convex in the model parameter $\theta$) holds. Consider the following
one-dimensional example:

######  Example 1.

Consider following one-dimension linear model with the squared loss
$\ell(\theta;(x,y))=-(\theta x-y)^{2}$. Assuming a model
$\theta\in\Theta=[0,1]$ induces a Bernoulli distribution over the labels with
the distribution parameter $\varphi(\theta):=\theta^{2}$, i.e.,
$y\sim\mathsf{Bern}(\varphi(\theta))$.

Since $\varphi$ is strictly increasing in $[0,1]$, the inverse mapping
$\varphi^{-1}$ is well-defined, and we can reformulate the performative risk
$\mathsf{PR}(\theta)$ as a function of $\varphi_{\theta}$, denoted
$\mathsf{PR}^{\dagger}(\varphi_{\theta})$, as follows:

$\displaystyle\mathsf{PR}(\theta;x)$
$\displaystyle=\mathbb{E}_{y\sim\mathsf{Bern}(\varphi_{\theta})}[\ell(\theta;x,y)]$
$\displaystyle=\varphi_{\theta}\ell(\theta;x,1)+(1-\varphi_{\theta})\ell(\theta;x,0)$
$\displaystyle=\varphi_{\theta}\ell\left(\phi^{-1}(\varphi_{\theta});x,1\right)+(1-\varphi_{\theta})\ell\left(\phi^{-1}(\varphi_{\theta});x,0\right)$
$\displaystyle=:\mathsf{PR}^{\dagger}(\varphi_{\theta};x)$

Plugging in $\ell$, we have

$\displaystyle\mathsf{PR}^{\dagger}(\varphi_{\theta};x)$
$\displaystyle=-\varphi_{\theta}\cdot\left(\phi^{-1}(\varphi_{\theta})x-1\right)^{2}-(1-\varphi_{\theta})\cdot\left(\phi^{-1}(\varphi_{\theta})x\right)^{2}$
$\displaystyle=-\varphi_{\theta}\cdot\left(\sqrt{\varphi_{\theta}}x-1\right)^{2}-(1-\varphi_{\theta})\varphi_{\theta}x^{2}$
($\phi^{-1}(\varphi_{\theta})=\sqrt{\varphi_{\theta}}$)

Note that for all $x\in[0,1]$,
$\mathsf{PR}^{\dagger}(\varphi_{\theta};x)=\mathsf{PR}(\theta;x)$ is convex in
$\varphi_{\theta}$ over $[0,1]$. In contrast,

$\displaystyle\mathsf{PR}(\theta;x)$
$\displaystyle=\theta^{2}\cdot\ell(\theta;x,1)+(1-\theta^{2})\cdot\ell(\theta;x,0)$
$\displaystyle=-\theta^{2}\cdot(\theta x-1)^{2}-(1-\theta^{2})\cdot(\theta
x)^{2}$

which is non-convex in $\theta$ over $[0,1]$ for all $x\in[0,1]$.

Figure 2: An example showing that our condition of $\mathsf{PR}$ being convex
in $\phi$ but not in $\theta$ exists. The blue curve represents the function
$\mathsf{PR}^{\dagger}(\varphi_{\theta})$, which is convex w.r.t the data
distribution parameter $\varphi_{\theta}$, while the red curve represents the
function $\mathsf{PR}(\theta)$, which is not a convex function w.r.t $\theta$.

In Appendix F, we provide a sufficient condition for our condition to hold
when the distribution follows an exponential family such that the data
distribution of the form: $p_{\phi}(z)=\exp(\phi\cdot
T(z)-A(\phi)+B(z))$444where $T(z)$, $h(z)$ and $A(\phi)$ are known functions.

######  Remark 1.

Earlier work [23] posits the “mixture dominance assumption”, under which the
performative prediction risk turns out to be convex in the model parameter
$\theta$. In particular, the assumption requires that for any triple
$\theta,\theta^{\prime},\theta_{0}\in\Theta$, the following condition holds:
$\mathbb{E}_{z\sim\mathcal{D}(\alpha\theta+(1-\alpha)\theta^{\prime})}[\ell(\theta_{0};z)]\leq\mathbb{E}_{z\sim\alpha\mathcal{D}(\theta)+(1-\alpha)\mathcal{D}(\theta^{\prime})}[\ell(\theta_{0};z)]$.
The primary distinction between our condition and theirs is that our condition
only needs to be valid for each individual data parameter. This is in contrast
to [23]’s condition, which must be met for any combination of
$\theta,\theta^{\prime}$, and $\theta_{0}\in\Theta$. We believe our approach
has greater versatility and is more likely to be fulfilled in various
scenarios.

##  4 The Outer Algorithm: A Reparameterization Approach

As we mentioned, in this work, we study the scenario where
$\mathsf{PR}(\theta)$ is not convex over the model parameter. The high-level
idea is that we can reparameterize the performative risk $\mathsf{PR}(\theta)$
as a function $\mathsf{PR}^{\dagger}(\phi)$ over the data distribution
parameter $\phi$. In particular, we first reformulate the learner’s loss
function so that it can be expressed as a function _only_ in the induced data
distribution. For each data distribution $\phi\in\Phi$, assume the set of
learner’s actions (deployed model parameters) that induce $\phi$ is

$\displaystyle\Theta^{*}(\phi)=\\{\theta\in\Theta|\varphi(\theta)=\phi\\}$

Among all of the learner’s actions that induce $\phi$, the optimal one which
achieve the minimal $\mathsf{PR}$ loss across the whole population is:

$\displaystyle\vartheta^{*}(\phi)=\operatorname*{\arg\\!\min}_{\theta\in\Theta^{*}(\phi)}\mathsf{PR}(\theta)$

where ties are broken arbitrarily. Now we can rewrite learner’s objective
function as a function of $\phi$

$\displaystyle\mathsf{PR}^{\dagger}(\phi)=\mathsf{PR}(\vartheta^{*}(\phi))$
(4)

To make the problem tractable, we consider following generic class of
$\mathsf{PR}^{\dagger}(\cdot)$ that is convex and Lipchitz continuous.

######  Assumption 1.

$\mathsf{PR}^{\dagger}(\phi)$ is convex and $L^{\dagger}$-Lipschitz over the
data distribution parameter $\phi\in\Phi$.

With reparameterizing $\mathsf{PR}(\theta)$ as a function
$\mathsf{PR}^{\dagger}(\phi)$ over the induced data distribution parameter
$\phi$, we now wish to minimize a bounded, $L^{\dagger}$-Lipschitz function
$\mathsf{PR}^{\dagger}(\cdot):\Phi\to\mathbb{R}$, where
$\Phi\subset\mathbb{R}^{d_{\Phi}}$ has bounded diameter $D_{\Phi}$, by
operating on the distribution parameter space $\Phi$.

Instead of having an immediate query access in zeroth-order convex
optimization algorithm, in our setting, we cannot directly evaluate the
(noisy) value $\mathsf{PR}^{\dagger}(\phi)$ for a particular data distribution
parameter, but may query the following oracles: A noisy _function oracle_
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$, which takes $\theta\in\Theta$
as input and returns an unbiased estimate $\widetilde{\mathsf{PR}}$ such that
$\mathbb{E}[\widetilde{\mathsf{PR}}(\theta)]=\mathsf{PR}(\theta)$. This noisy
oracle can be implemented by simply making a prediction and observing the loss
as defined in Section 2.2 555The sample required for each round of estimate
EstimatePR is $\mathcal{O}(1)$; this is because EstimatePR itself is an
unbiased estimator, so even with one sample, in expectation, the estimation
will be unbiased..

A noisy _reparameterization oracle_
$\operatorname{\mathsf{LearnModel}}(\phi,\epsilon_{\mathsf{LM}},p_{\mathsf{LM}})$,
which takes $\phi\in\Phi$, $\epsilon_{\mathsf{LM}}>0$, and $p_{\mathsf{LM}}>0$
as input and returns $\theta\in\Theta$ such that
$\Pr(\|\varphi(\theta)-\phi\|\geq\epsilon_{\mathsf{LM}})\leq p_{\mathsf{LM}}$.
We will specify $\operatorname{\mathsf{LearnModel}}$ in Section 5.

The following algorithm performs this task; specifically, it returns both
$\bar{\theta}\in\Theta$ and $\bar{\phi}\in\Phi$ such that with probability at
least $1-p$,
$|\mathsf{PR}(\bar{\theta})-\mathsf{PR}(\theta_{\texttt{OPT}})|\leq\epsilon$
and
$|\mathsf{PR}^{\dagger}(\bar{\phi})-PR^{\dagger}(\varphi(\theta_{\texttt{OPT}}))|\leq\epsilon$.

function $\operatorname{\mathsf{Estimate}\mathsf{PR}}$($\theta$)
$\triangleright$ Unbiased estimate of $\mathsf{PR}(\theta)$

Deploy $\theta$, observe sample $z\sim\mathcal{D}(\theta)$

return $\ell(z;\theta)$

function
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$($\operatorname{\mathsf{LearnModel}}:\Phi\to\Theta$;
$\epsilon,p,\epsilon_{\mathsf{LM}},p_{\mathsf{LM}}>0$)

$T\leftarrow\frac{d_{\Phi}}{(\epsilon-\sqrt{\epsilon_{\mathsf{LM}}d_{\Phi}})^{2}}$

$\delta\leftarrow\sqrt{\epsilon_{\mathsf{LM}}d_{\Phi}}$

$\eta\leftarrow 1/\sqrt{d_{\Phi}T}$

$y_{1}\leftarrow\mathbf{0}$

for $t\leftarrow 1,\ldots,T$ do

$u_{t}\leftarrow$ sample from $\mathrm{Unif}(\mathbb{S})$

$\phi_{t}^{+}\leftarrow\phi_{t}+\delta u_{t}$,
$\phi_{t}^{-}\leftarrow\phi_{t}-\delta u_{t}$

$\hat{\theta}_{t}^{+}\leftarrow\operatorname{\mathsf{LearnModel}}(\phi_{t}^{+},\epsilon_{\mathsf{LM}},p_{\mathsf{LM}})$

$\hat{\theta}_{t}^{-}\leftarrow\operatorname{\mathsf{LearnModel}}(\phi_{t}^{-},\epsilon_{\mathsf{LM}},p_{\mathsf{LM}})$
$\triangleright$ $\hat{\theta}_{t}^{+}$ such that
$\mathsf{PR}(\hat{\theta}_{t}^{+})\approx\mathsf{PR}^{\dagger}(\phi_{t}^{+})$,
similarly, $\hat{\theta}_{t}^{-}$ such that
$\mathsf{PR}(\hat{\theta}_{t}^{-})\approx\mathsf{PR}^{\dagger}(\phi_{t}^{-})$

$\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})\leftarrow\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{+})$

$\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{-})\leftarrow\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{-})$
$\triangleright$ Approximations of $\mathsf{PR}(\hat{\theta}_{t}^{+})$,
$\mathsf{PR}(\hat{\theta}_{t}^{-})$

$\tilde{g}_{t}\leftarrow\frac{d_{\Phi}}{2\delta}\left(\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})-\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{-})\right)\cdot
u_{t}$ $\triangleright$ Approximation of
$\nabla_{\phi}\mathsf{PR}^{\dagger}(\phi_{t})$

$\phi_{t+1}\leftarrow\Pi_{(1-\delta)\Phi}(\phi_{t}-\eta\tilde{g}_{t})$
$\triangleright$ Take gradient step and project

$\bar{\phi}\leftarrow\frac{1}{T}\sum_{t=1}^{T}\phi_{t}$

$\bar{\theta}\leftarrow\operatorname{\mathsf{LearnModel}}(\bar{\phi},\epsilon_{\mathsf{LM}},p_{\mathsf{LM}})$

return $\bar{\theta}$, $\bar{\phi}$

Algorithm 1 Bandit algorithm for minimizing an indirectly convex function with
noisy oracles

For analysis purpose, we also define regret in $T$, the total number of steps
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ has to go through in order to
get an $\epsilon$-suboptimal model parameter w.r.t the $\mathsf{PR}$ objective
function:

$\displaystyle\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left[\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{+})+\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta_{\texttt{OPT}})\right]$

We demonstrate the following regret bound for this algorithm:

######  Theorem 2 (High-probability regret bound for Algorithm 1 in $T$).

When Algorithm 1 is called with arguments $\epsilon_{\mathsf{LM}}$ and
$p_{\mathsf{LM}}$, we have for every $p>0$ that

$\displaystyle\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})=O\left(\sqrt{d_{\Phi}T}+\sqrt{\epsilon_{\mathsf{LM}}d_{\Phi}}\cdot
T+\sqrt{T\log\frac{1}{p}}\right)$

with probability at least $1-p-2Tp_{\mathsf{LM}}$.

The above 2 requires that the output of $\operatorname{\mathsf{LearnModel}}$
is $\epsilon_{\mathsf{LM}}$-close to the target distribution parameter $\phi$
with probability at least $1-p_{\mathsf{LM}}$. Later in Section 5, we show
that how we achieve this by developing an zeroth-order convex optimization
algorithm with the objective of minimizing the $\mathsf{KL}$ divergence of two
distributions.

##  5 Inner Algorithm: Inducing a Target Distribution Using
$\operatorname{\mathsf{LearnModel}}$

In this section, we show how to solve the sub-problem
$\operatorname{\mathsf{LearnModel}}$ mentioned in Algorithm 1: given a target
distribution with the parameter $\phi\in\Phi$, find a model $\theta\in\Theta$
whose corresponding distribution parameter $\varphi(\theta)$ is close to
$\phi$.

###  5.1 Objective Function for $\operatorname{\mathsf{LearnModel}}$ and
Technique Assumptions

To this end, we consider minimizing the $\mathsf{KL}$ divergence between
$\phi$ and $\varphi(\theta)$: 666For notation simplicity, here, we use
$\mathsf{KL}(\phi_{1}||\phi_{2})$ to represent
$\mathsf{KL}(\mathcal{D}_{1}||\mathcal{D}_{2})$ where the data distribution
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ has the parameter $\phi_{1}$ and
$\phi_{2}$, respectively.

$\displaystyle\mathsf{KL}(\phi||\varphi(\theta)):=\int_{z}p(z;\phi)\log\frac{p(z;\phi)}{p(z;\varphi(\theta))}dz$
(5)

where $p(z;\phi)$ denotes the pdf for the target distribution $\phi$, and
$p(z;\varphi(\theta))$ denotes the pdf for the distribution induced by
deploying $\theta$.

In general, ${\mathsf{KL}}(\phi||\varphi(\theta))$ measures how much a
distribution with the parameter $\varphi(\theta)$ is away from the target
distribution with the parameter $\phi$: if the two distributions
$\phi_{1},\phi_{2}\in\Phi$ satisfy $\phi_{1}=\phi_{2}$, then
${\mathsf{KL}}(\phi_{1}||\phi_{2})=0$, otherwise
${\mathsf{KL}}(\phi_{1}||\phi_{2})>0$. Intuitively, the lower the value
${\mathsf{KL}}(\phi_{1}||\phi_{2})$ is, the better we have matched the target
distribution with our approximate distribution induced by the chosen model.
However, the $\mathsf{KL}(\phi||\cdot)$ is generally not convex and not
Lipschitz. Hence, to make the problem tractable, we will make several
assumptions. We view these assumptions as comparatively mild, and provide
examples shortly after stating the assumptions we need.

######  Assumption 2.

The function $\mathsf{KL}(\phi||\varphi(\cdot))$, the data distribution
$\mathcal{D}(\theta)$, and its parameter mapping $\varphi(\cdot)$ satisfies
the following properties.

  1. 2a.

$\mathsf{KL}(\phi||\varphi(\cdot))$ is convex in the model parameter
$\theta\in\Theta$;

  2. 2b.

The data distribution $\mathcal{D}(\theta)$ with the parameter
$\varphi(\theta)$ is $(\ell_{2},K)$-Lipschitz continuous in the model
parameter $\theta\in\Theta$ with constant $K(z),\forall z\in Z$ 777A
distribution $\mathcal{D}(\theta)$ with the density function
$p(\cdot|\varphi(\theta))$ parameterized by $\theta\in\Theta$ is called
$(\ell_{2},K)$-Lipschitz continuous [13] if for all $z$ in the sample space,
the log-likelihood $f(\theta)=\log p(z|\varphi(\theta))$ is Lipschitz
continuous with respect to the $\ell_{2}$ norm of $\theta$ with constant
$K(z)$. ;

  3. 2c.

Let $\mathcal{D}_{1},\mathcal{D}_{2}$ be two data distributions with the
parameter $\phi_{1},\phi_{2}\in\Phi$, and
$d_{\mathsf{TV}}(\mathcal{D}_{1},\mathcal{D}_{2})$ be the total variation
distance. Then $\|\phi_{1}-\phi_{2}\|\leq L_{\mathsf{TV}}\cdot
d_{\mathsf{TV}}(\mathcal{D}_{1},\mathcal{D}_{2})$ for some constant
$L_{\mathsf{TV}}>0$.

Here, we provide examples to demonstrate that the above assumptions are
comparatively mild. The following is an example showing the convexity of
$\mathsf{KL}(\phi||\varphi(\cdot))$.

######  Example 2.

Consider the density function $p(z;\varphi(\theta))$ of the data distribution
$\mathcal{D}(\theta)$ satisfying
$p(z;\varphi(\theta))=\mathrm{Unif}(\exp(c\varphi(\theta)))$ for some constant
$c>0$ and for any convex function $\varphi(\theta)$, then
$\mathsf{KL}(\phi||\varphi(\cdot))$ is convex over $\theta$.

In the above Assumption 2b, we assume a family of distribution called the
$(\ell_{2},K)$-Lipschitz continuous. This Lipschitz continuity over the
parametrization of probability distributions allows us to have the following
Lipschitz condition of the function $\mathsf{KL}(\phi||\varphi(\cdot))$ over
the model parameter $\theta$:

######  Lemma 2 (Lipschitzness of $\mathsf{KL}(\phi||\varphi(\theta))$ in
$\theta$).

Given two $\left(\ell_{2},K\right)$-Lipschitz continuous distributions
$\mathcal{D}_{1}=p\left(\cdot\mid\varphi(\theta_{1})\right)$ and
$\mathcal{D}_{2}=p\left(\cdot\mid\varphi(\theta_{2})\right)$, and a target
distribution parameter $\phi\in\Phi$, we have
$\left|\mathsf{KL}\left(\phi||\varphi(\theta_{1})\right)-\mathsf{KL}\left(\phi||\varphi(\theta_{2})\right)\right|\leq{L_{\mathsf{KL}}}\left\|\theta_{1}-{\theta}_{2}\right\|$
with a constant $L_{\mathsf{KL}}>0$.

The above Assumption 2c is about the continuity on the distribution parameter
$\phi\in\Phi$. Intuitively, this assumption ensures that if the parameters of
two distribution are close, then their total variation distance is close as
well. With this assumption, we can show that the distance between two
distribution parameters $\|\phi_{1}-\phi_{2}\|$ can be bounded by the KL
divergence between the corresponding data distributions.

######  Lemma 3.

With Assumption 2c, we have $\|\phi_{1}-\phi_{2}\|\leq
L_{\phi}\sqrt{\mathsf{KL}(\phi_{1}||\phi_{2})}$ for some constant
$L_{\phi}>0$.

Intuitively, the above result ensures that given a target distribution
parameter $\phi$, as long as a model $\theta$ whose corresponding data
distribution is close (i.e., $\mathsf{KL}(\phi||\varphi(\theta))$ is small) to
the distribution with the parameter $\phi$, then $\varphi(\theta)$ is close to
$\phi$. We will use 3 in the proof of our main theorem in Section 6.

###  5.2 Algorithm for $\operatorname{\mathsf{LearnModel}}$

When $\mathsf{KL}(\phi||\varphi(\cdot))$ is convex and Lipschitz over the
model $\theta$, its minimizer can be computed using algorithms similar to
Algorithm 1. In our problem, given a target data distribution with the
parameter $\phi$, we can use the observed data samples to approximately
compute the $\mathsf{KL}(\phi||\varphi(\theta))$ when deploying a model
$\theta$. Indeed, we assume an existence of an oracle
$\operatorname{\mathsf{EstimateKL}}(\phi,(z_{t}^{(i)})_{i\in[n_{t}]})$ which
takes the observed samples $(z_{t}^{(i)})_{i\in[n_{t}]}$ realized from the
induced data distribution $\mathcal{D}(\theta)$ and the target data
distribution parameter $\phi$ as input to approximate the value
$\mathsf{KL}(\phi||\varphi(\theta))$. We remark that such oracle has been
widely used in the literature on KL divergence estimation [30].

######  Definition 1 (Oracle $\operatorname{\mathsf{EstimateKL}}$).

There exists an oracle $\operatorname{\mathsf{EstimateKL}}$ that given any
target parameter $\phi\in\Phi$, error tolerance $\epsilon_{\mathsf{KL}}>0$ and
error probability $p_{\mathsf{KL}}>0$, and
$N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$ samples
$z_{1},\ldots,z_{N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})}$
from a distribution with parameter $\phi^{\prime}$, returns an estimated
$\mathsf{KL}$ divergence $\widetilde{\mathsf{KL}}(\phi||\phi^{\prime})$
satisfying
$\big{\|}\widetilde{\mathsf{KL}}(\phi||\phi^{\prime})-\mathsf{KL}(\phi||\phi^{\prime})\big{\|}\leq\epsilon_{\mathsf{KL}}$
with probability at least $1-p_{\mathsf{KL}}$.

With the above defined oracle $\operatorname{\mathsf{EstimateKL}}$ to
approximately compute the KL divergence, we are now ready to present our inner
algorithm, which we term it as $\operatorname{\mathsf{LearnModel}}$:

function $\operatorname{\mathsf{LearnModel}}$($\phi\in\Phi$;
$\epsilon_{\mathsf{LM}},p_{\mathsf{LM}}>0$,
$\epsilon_{\mathsf{KL}},p_{\mathsf{KL}}>0$)

$S\leftarrow\frac{d_{\Theta}}{(\epsilon_{\mathsf{LM}}-\sqrt{\epsilon_{\mathsf{KL}}d_{\Theta}})^{2}}$

$\delta_{\mathsf{LM}}\leftarrow\sqrt{\epsilon_{\mathsf{KL}}d_{\Theta}}$

$\eta_{\mathsf{LM}}\leftarrow\frac{1}{\sqrt{d_{\Theta}S}}$

$N_{\mathsf{KL}}\leftarrow
N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$

$\theta_{1}\leftarrow\mathbf{0}$

for $s\leftarrow 1,\ldots,S$ do

$u_{s}\leftarrow$ sample from $\mathrm{Unif}(\mathbb{S}^{d_{\Theta}})$

$\theta_{s}^{+}\leftarrow\theta_{s}+\delta_{\mathsf{LM}}u_{s}$,
$\theta_{s}^{-}\leftarrow\theta_{s}-\delta_{\mathsf{LM}}u_{s}$

$z_{s,1}^{+},\ldots,z^{+}_{s,N}\sim\varphi(\theta_{s}^{+})$,
$z_{s,1}^{-},\ldots,z^{-}_{s,N}\sim\varphi(\theta_{s}^{-})$ $\triangleright$
Deploy $\theta_{s}^{+}$, $\theta_{s}^{-}$; observe $N_{\mathsf{KL}}$ samples

$\widetilde{\mathsf{KL}}\left(\phi||\varphi(\theta_{s}^{+})\right)\leftarrow\operatorname{\mathsf{EstimateKL}}(\phi,z_{s,1}^{+},\cdots
z^{+}_{s,N_{\mathsf{KL}}},\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$

$\widetilde{\mathsf{KL}}\left(\phi||\varphi(\theta_{s}^{-})\right)\leftarrow\operatorname{\mathsf{EstimateKL}}(\phi,z_{s,1}^{-},\cdots
z^{-}_{s,N_{\mathsf{KL}}},\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$
$\triangleright$ Approximations of $\mathsf{KL}$

$\tilde{g}_{s}\leftarrow\frac{d_{\Theta}}{2\delta_{\mathsf{LM}}}\left(\widetilde{\mathsf{KL}}(\phi||\varphi({\theta}_{s}^{+}))-\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{-})\right)\cdot
u_{s}$ $\triangleright$ Approximation of
$\nabla_{\theta}\mathsf{KL}(\phi||\varphi(\theta_{s}))$

$\theta_{s+1}\leftarrow\Pi_{(1-\delta_{\mathsf{LM}})\Theta}(\theta_{s}-\eta_{\mathsf{LM}}\tilde{g}_{s})$
$\triangleright$ Take gradient step and project

$\bar{\theta}\leftarrow\frac{1}{S}\sum_{s=1}^{S}\theta_{s}$

return $\bar{\theta}$

Algorithm 2 Learn a model that approximately induces a given distribution
parameter $\phi$

Similar as before, for analysis purpose, we also define regret of
$\operatorname{\mathsf{LearnModel}}$ in $S$, the total number of rounds
$\operatorname{\mathsf{LearnModel}}$ has to go through in order to output a
$\epsilon_{\mathsf{LM}}$-suboptimal model parameter w.r.t the $\mathsf{KL}$
objective function:

$\displaystyle\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{S}\left[\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{+}))+\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{-}))-2\mathsf{KL}(\phi||\vartheta^{*}(\phi))\right]$

where $\vartheta^{*}(\phi)$ is the model that can induce the target
distribution $\phi$. Using the similar arguments in 2, we first show the
following regret guarantee for $\operatorname{\mathsf{LearnModel}}$:

######  Theorem 3 (High-probability regret bound for Algorithm 2 with $S$
rounds).

When $\operatorname{\mathsf{LearnModel}}$ is run for $S$ steps and invokes
$\operatorname{\mathsf{EstimateKL}}$ with arguments $\epsilon_{\mathsf{KL}}>0$
and $p_{\mathsf{KL}}>0$, we have $\forall p>0$

$\displaystyle\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})=O\left(\sqrt{d_{\Phi}S}+\sqrt{\epsilon_{\mathsf{KL}}d_{\Phi}}\cdot
S+\sqrt{S\log\frac{1}{p}}\right)$

with probability at least $1-p-2Sp_{\mathsf{KL}}>0$.

3 provides us the regret formulation of $\operatorname{\mathsf{LearnModel}}$
as a function of the total number of deployments of the procedure $S$. We can
plug this expression into the regret expression for the outer algorithm in 2
and get the final regret expression.

##  6 Putting Things Together

As shown in the previous section, both the outer algorithm
($\operatorname{\mathsf{Minimize}\mathsf{PR}}$ – in Section 4) and inner
algorithm ($\operatorname{\mathsf{LearnModel}}$ – in Section 5) achieve a
sublinear regret w.r.t the total number of steps ($T$ and $S$) when outputting
an $\epsilon$-optimal solutions. In this section, we combine the results in
Section 4 and Section 5 to conclude the analysis for
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ (Algorithm 1) for convex
$\mathsf{PR}^{\dagger}(\phi)$. The main result of this section is summarized
as follows:

######  Theorem 4 (Regret of $\operatorname{\mathsf{Minimize}\mathsf{PR}}$ in
$N$).

Under Assumption 2, and given access an oracle
$\operatorname{\mathsf{EstimateKL}}$, there exists a choice of
$\epsilon_{\mathsf{KL}},p_{\mathsf{KL}}>0$ in Algorithm 2 such that for every
$p>0$,

$\displaystyle\mathcal{R}_{N}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})=\widetilde{O}\left((d_{\Theta}+d_{\Phi})N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})^{1/6}N^{5/6}\sqrt{\log\frac{1}{p}}\right)$

with probability at least $1-p$.

###### Proof Sketch of 4.

Let $T$ be the number of steps executed by the outer algorithm
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$, and $S$ the number of steps in
$\operatorname{\mathsf{LearnModel}}$. Let
$N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$ (or
$N_{\mathsf{KL}}$ for short) denote the number of samples used by
$\operatorname{\mathsf{EstimateKL}}$. Since
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ calls
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ and
$\operatorname{\mathsf{LearnModel}}$ $2T$ times, and
$\operatorname{\mathsf{LearnModel}}$ calls
$\operatorname{\mathsf{EstimateKL}}$ $2S$ times, the overall number of samples
involved in the whole process is $N=2(2N_{\mathsf{KL}}S+1)T$. Following the
regret definition, we can break down the regret into the regret from calling
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ in the outer algorithm and the
regret from calling $\operatorname{\mathsf{EstimateKL}}$ in
$\operatorname{\mathsf{LearnModel}}$. Using the fact that
$\mathsf{PR}^{\dagger}$ is lipschitnez in the distribution parameter $\phi$
and the distance between any two distribution parameters can be bounded by the
KL divergence between the corresponding data distributions (3), we show that
the total regret in $N$ can be expressed as:

$\displaystyle\mathcal{R}_{N}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=O\left(\sqrt{N}+N_{\mathsf{KL}}T\cdot\sqrt{S\cdot\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}\right.$
$\displaystyle\quad\quad\left.+(N_{\mathsf{KL}}S+1)\cdot\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})\right)$

where
$\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$ and
$\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})$ are obtained
from 2 and 3 as functions of
$\epsilon_{\mathsf{LM}},\epsilon_{\mathsf{KL}},S,T$ and $D_{\Theta}$ and
$D_{\Phi}$. Then by balancing the terms and set $\epsilon_{\mathsf{LM}}$ and
$\epsilon_{\mathsf{KL}}$ according to the convergence analysis for both
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ and
$\operatorname{\mathsf{LearnModel}}$ (Claim 9 and Claim 10), we can get an
express of the total regret. The complete proof can be found in Appendix E. ∎

4 show that our two-level zeroth-order optimization procedure is sublinear in
the $N$, the total number of samples we deploy during the process. Notice that
this also implies that our method is sublinear w.r.t. the total number of
deployments $T_{\textsf{total}}=S\times T$. To see this, recall that the total
number of samples $N$ required throughout the process is $N=2(2N_{{kl}}\times
S+1)\times T$; if we measure the regret w.r.t. the total number of
deployments, $N_{{kl}}$ will be constant, and thus the regret will still be
sublinear w.r.t. $T_{\textsf{total}}$. In addition, recall from Proposition 1
in Section 2, the lowest regret optimal classifier implies the optimal
classifier up to some addictive error, which means that by having a sublinear
regret in $N$ (and $T_{\textsf{total}}$), we also get a model that is
arbitrarily close to the performative optimal model.

##  7 Practical Consideration and Future Works

Since our method uses a double-loop zeroth order optimization method, the
convergence is likely to be slow in practice. Thus, our work requires extra
consideration regarding the convergence rate, and efficiency can vary based on
particular settings. In particular, the success of our method depends on the
fast deployment of the frequently updated models. There are real-life settings
and scenarios where the deployment update frequency is high, the data
collection is relatively straightforward not that costly. For example, in
large-scale recommendation systems, such as short video platforms (e.g.,
TikTok) that provide personalized recommendations. Those platforms require
immediate model updates using user’s feedback and personalized. And in online
proofreading systems, such as Grammarly, with functionalities like auto-
correction and next-word typing suggestions. One potential way to speed up the
deployment process may be performing _parallelization_ : many zeroth-order
optimization algorithms are amenable to parallel computation, which can
accelerate the optimization process and reduce the time required to find a
suitable solution (see, e.g., [19] for a detailed reference). In our
algorithm, parallelization can be applied to several places, for example,
since our algorithm involves performing zeroth-order optimization with two-
point feedback, and the two-point estimations can be computed in parallel and
potentially speed up the process.

## References

  * [1] Alekh Agarwal, Ofer Dekel and Lin Xiao  “Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback”  In _Annual Conference on Learning Theory_ , 2010, pp. 28–40
  * [2] Gavin Brown, Shlomi Hod and Iden Kalemaj  “Performative Prediction in a Stateful World”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 6045–6061
  * [3] Yatong Chen, Zeyu Tang, Kun Zhang and Yang Liu  “Model transferability with responsive decision subjects”  In _International Conference on Machine Learning_ , 2023, pp. 4921–4952  PMLR
  * [4] Yatong Chen, Jialu Wang and Yang Liu  “Linear classifiers that encourage constructive adaptation”  In _arXiv preprint arXiv:2011.00355_ , 2020
  * [5] Joshua Cutler, Dmitriy Drusvyatskiy and Zaid Harchaoui  “Stochastic Optimization under Distributional Drift”  arXiv, 2021
  * [6] Jinshuo Dong et al.  “Strategic classification from revealed preferences”  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , 2018, pp. 55–70
  * [7] Roy Dong and Lillian J. Ratliff  “Approximate Regions of Attraction in Learning with Decision-Dependent Distributions”  arXiv, 2021
  * [8] Dmitriy Drusvyatskiy and Lin Xiao  “Stochastic Optimization with Decision-Dependent Distributions”  In _arXiv preprint arXiv:2011.11173_ , 2020
  * [9] Abraham D Flaxman, Adam Tauman Kalai and H Brendan McMahan  “Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient”  In _The Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2005, pp. 385–394
  * [10] Dylan J Foster, Dean P Foster, Noah Golowich and Alexander Rakhlin  “On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring”  In _arXiv preprint arXiv:2305.00684_ , 2023
  * [11] Moritz Hardt, Meena Jagadeesan and Celestine Mendler-Dünner  “Performative power”  In _arXiv preprint arXiv:2203.17232_ , 2022
  * [12] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou and Mary Wootters  “Strategic Classification”  In _Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science_ , 2016, pp. 111–122
  * [13] Jean Honorio  “Lipschitz Parametrization of Probabilistic Graphical Models”  In _Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence_ , 2011
  * [14] 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_ , 2021, pp. 4641–4650
  * [15] Meena Jagadeesan, Tijana Zrnic and Celestine Mendler-Dünner  “Regret Minimization with Performative Feedback”  In _Proceedings of the 39th International Conference on Machine Learning_ 162, Proceedings of Machine Learning Research  PMLR, 2022
  * [16] Jon Kleinberg and Manish Raghavan  “How Do Classifiers Induce Agents to Invest Effort Strategically?”  In _ACM Trans. Econ. Comput._ 8.4 New York, NY, USA: Association for Computing Machinery, 2020
  * [17] Qiang Li and Hoi-To Wai  “State dependent performative prediction with stochastic approximation”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 3164–3186  PMLR
  * [18] Qiang Li, Chung-Yiu Yau and Hoi-To Wai  “Multi-agent Performative Prediction with Greedy Deployment and Consensus Seeking Agents”  In _arXiv preprint arXiv:2209.03811_ , 2022
  * [19] Sijia Liu et al.  “A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning”, 2020  arXiv:2006.06224 [cs.LG]
  * [20] Chinmay Maheshwari et al.  “Zeroth-order methods for convex-concave min-max problems: Applications to decision-dependent risk minimization”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 6702–6734  PMLR
  * [21] Celestine Mendler-Dünner, Frances Ding and Yixin Wang  “Anticipating Performativity by Predicting from Predictions”  In _Advances in Neural Information Processing Systems_
  * [22] Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic and Moritz Hardt  “Stochastic Optimization for Performative Prediction”  In _Advances in Neural Information Processing Systems_ 33, 2020
  * [23] John P Miller, Juan C Perdomo and Tijana Zrnic  “Outside the Echo Chamber: Optimizing the Performative Risk”  In _International Conference on Machine Learning_ , 2021, pp. 7710–7720
  * [24] Mehrnaz Mofakhami, Ioannis Mitliagkas and Gauthier Gidel  “Performative Prediction with Neural Networks”  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , Proceedings of Machine Learning Research  PMLR, 2023
  * [25] Adhyyan Narang et al.  “Multiplayer performative prediction: Learning in decision-dependent games”  In _arXiv preprint arXiv:2201.03398_ , 2022
  * [26] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner and Moritz Hardt  “Performative Prediction”  In _International Conference on Machine Learning_ , 2020, pp. 7599–7609
  * [27] Georgios Piliouras and Fang-Yi Yu  “Multi-agent performative prediction: From global stability and optimality to chaos”  In _arXiv preprint arXiv:2201.10483_ , 2022
  * [28] Mitas Ray, Lillian J Ratliff, Dmitriy Drusvyatskiy and Maryam Fazel  “Decision-dependent risk minimization in geometrically decaying dynamic environments”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 36.7, 2022, pp. 8081–8088
  * [29] Aaron Roth, Jonathan Ullman and Zhiwei Steven Wu  “Watch and Learn: Optimizing from Revealed Preferences Feedback”  In _Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing_ , 2016, pp. 949–962
  * [30] Paul Rubenstein et al.  “Practical and Consistent Estimation of f-Divergences”  In _Advances in Neural Information Processing Systems_ , 2019
  * [31] Ohad Shamir  “An Optimal Algorithm for Bandit and Zero-order Convex Optimization with Two-point Feedback”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 1703–1713
  * [32] Killian Wood and Emiliano Dall’Anese  “Online Saddle Point Tracking with Decision-Dependent Data”  In _arXiv preprint arXiv:2212.02693_ , 2022
  * [33] Man-Jie Yuan and Wei Gao  “Learning with Interactive Models over Decision-Dependent Distributions”  In _Proceedings of The 14th Asian Conference on Machine Learning_ , Proceedings of Machine Learning Research  PMLR, 2023
  * [34] Morteza Zadimoghaddam and Aaron Roth  “Efficiently learning from revealed preference”  In _International Workshop on Internet and Network Economics_ , 2012, pp. 114–127  Springer

## Appendix

##  Appendix A Appendix Arrangement

We arrange the appendix as follows: Appendix B provides omitted algorithm and
proofs for Section 2.

* [1] Appendix C provides omitted proofs for Section 4.
* [2] Appendix D provides omitted proofs for Section 5.
* [3] Appendix E provides omitted proof for Section 6.
* [4] Appendix G provides an additional literature review on performative prediction and related literature.

##  Appendix B Omitted Algorithm and Proof for Section 2

Algorithm 3 is a straightforward generalization of the algorithm introduced by
[1], while we generalize their setting where the function can be evaluated
exactly to the setting where noisy evaluation is allowed.

function $\operatorname{\mathsf{Estimate}\mathsf{PR}}$($\theta$)
$\triangleright$ Unbiased estimate of $\mathsf{PR}(\theta)$

Deploy $\theta$, observe sample $z\sim\mathcal{D}(\theta)$

return $\ell(z;\theta)$

function MinimizePR($T$)

$\delta\leftarrow\sqrt{d_{\theta}/T}$

$\eta\leftarrow 1/\sqrt{d_{\Theta}T}$

$\theta_{1}\leftarrow\mathbf{0}$

for $t\leftarrow 1,\ldots,T$ do

$u_{t}\leftarrow$ sample from $\mathrm{Unif}(\mathbb{S}^{d_{\Theta}})$

$\theta_{t}^{+}\leftarrow\theta_{t}+\delta u_{t}$,
$\theta_{t}^{-}\leftarrow\theta_{t}-\delta u_{t}$

$\widetilde{\mathsf{PR}}(\theta_{t}^{+})\leftarrow\operatorname{\mathsf{Estimate}\mathsf{PR}}(\theta_{t}^{+})$
$\triangleright$ Approximations of $\mathsf{PR}(\theta_{t}^{+})$,
$\mathsf{PR}(\theta_{t}^{-})$

$\widetilde{\mathsf{PR}}(\theta_{t}^{-})\leftarrow\operatorname{\mathsf{Estimate}\mathsf{PR}}(\theta_{t}^{-})$

$g_{t}\leftarrow\frac{d_{\Theta}}{2\delta}\left(\widetilde{\mathsf{PR}}(\theta_{t}^{+})-\widetilde{\mathsf{PR}}(\theta_{t}^{-})\right)\cdot
u_{t}$ $\triangleright$ Approximation of
$\nabla_{\theta}\widehat{\mathsf{PR}}(\theta_{t})$

$\theta_{t+1}\leftarrow\Pi_{(1-\delta)\Theta}(\theta_{t}-\eta g_{t})$
$\triangleright$ Take gradient step and project

return $\frac{1}{T}\sum_{t=1}^{T}\theta_{t}$

Algorithm 3 Bandit algorithm for minimizing convex and lipschitz
$\mathsf{PR}(\theta)$

To prove 1, we first provide a series of lemmas and claims that will be useful
later.

######  Claim 1 (Regret from estimating $\mathsf{PR}$).

For any $p>0$, with probability at least $1-p$,

$\displaystyle\sum_{t=1}^{T}\left[\widetilde{\mathsf{PR}}(\theta_{t}^{+})-f(\theta_{t}^{+})\right]\leq
F\sqrt{T\log\frac{1}{p}}\quad\mathrm{and}\quad\sum_{t=1}^{T}\left[\widetilde{\mathsf{PR}}(\theta_{t}^{-})-f(\theta_{t}^{-})\right]\leq
F\sqrt{T\log\frac{1}{p}}$

###### Proof.

The claim follows from Hoeffding’s inequality, since
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ is unbiased and bounded by
$[0,F]$. ∎

######  Claim 2 (Regret from smoothing over the sphere or ball).

For any $\theta\in\Theta$, $u\in\mathbb{S}$, and $\delta>0$, all of the
following are at most $\delta L$:

$\displaystyle|\mathsf{PR}(\theta+\delta
u)-\mathsf{PR}(\theta)|,\quad|\mathsf{PR}(\theta-\delta
u)-\mathsf{PR}(\theta)|,\quad$
$\displaystyle\left|\frac{1}{2}[\mathsf{PR}(\theta+\delta
u)+\mathsf{PR}(\theta-\delta
u)]-\mathsf{PR}(\theta)\right|,\quad\text{and}\quad|\widehat{\mathsf{PR}}(\theta)-\mathsf{PR}(\theta)|.$

###### Proof sketch.

Lipschitzness of $\mathsf{PR}$. ∎

######  Claim 3 (Deviation of smoothed function).

For any $p>0$, with probability at least $1-p$,

$\displaystyle\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta_{t})-\mathbb{E}_{T}\left[\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta_{t})\right]\leq
F\sqrt{T\log\frac{1}{p}}$

###### Proof sketch.

The left-hand side is the sum of a martingale difference sequence. The Azuma-
Hoeffding inequality yields the result. ∎

######  Claim 4 (Gradient estimate is unbiased and bounded).

There exists a constant $c>0$ such that for all $t\in[T]$,
$\mathbb{E}_{t}[g_{t}]=\nabla\widehat{\mathsf{PR}}(\theta_{t})$ and
$\|g_{t}\|_{2}^{2}\leq cd_{\theta}L^{2}$.

###### Proof.

Proved in [31] (see Lemma 10, noting that the $\ell_{2}$ norm is its own
dual). ∎

######  Lemma 4 (Expected suboptimality under smoothing when $\mathsf{PR}$ is
convex).

Let $\theta\in\Theta$, and let $\theta_{1},\ldots,\theta_{t}\in\Theta$ be a
sequence of iterates given by the update rule
$\theta_{t+1}=\Pi_{(1-\delta)\theta}(\theta_{t}-\eta g_{t})-\theta$ for some
sequence of gradient estimates $g_{t}\in\mathbb{R}^{d_{\Theta}}$. Then

$\displaystyle\mathbb{E}_{T}\left[\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta_{t})\right]-\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta)\leq\frac{D_{\Theta}^{2}}{\eta}+\eta
cd_{\theta}L^{2}T$

###### Proof of 4.

Observe that

$\displaystyle\mathbb{E}_{T}\left[\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta_{t})\right]-\sum_{t=1}^{T}\widehat{\mathsf{PR}}(\theta)$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{t}\left[\widehat{\mathsf{PR}}(\theta_{t})-\widehat{\mathsf{PR}}(\theta)\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{t}\left[\nabla\widehat{\mathsf{PR}}(\theta_{t})^{\top}(\theta_{t}-\theta)\right]$
(convexity of $\widehat{\mathsf{PR}}$)
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{t}\left[g_{t}^{\top}(\theta_{t}-\theta)\right]$
(Claim 4)

To decompose $g_{t}^{\top}(\theta_{t}-\theta)$, note that

$\displaystyle\|\theta_{t+1}-\theta\|^{2}$
$\displaystyle=\|\Pi_{(1-\delta)\theta}(\theta_{t}-\eta g_{t})-x\|^{2}$
$\displaystyle\leq\|\theta_{t}-\eta g_{t}-\theta\|^{2}$
$\displaystyle=\|\theta_{t}-\theta\|^{2}+\eta^{2}\|g_{t}\|^{2}-2\eta\cdot
g_{t}^{\top}(\theta_{t}-\theta)$

Therefore

$\displaystyle g_{t}^{\top}(\theta_{t}-x)$
$\displaystyle\leq\frac{\|\theta_{t}-\theta\|^{2}-\|\theta_{t+1}-\theta\|^{2}+\eta^{2}\|g_{t}\|^{2}}{2\eta}$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{t}\left[g_{t}^{\top}(\theta_{t}-\theta)\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{t}\left[\frac{\|\theta_{t}-\theta\|^{2}-\|\theta_{t+1}-\theta\|^{2}+\eta^{2}\|g_{t}\|^{2}}{2\eta}\right]$
$\displaystyle\leq\frac{1}{2\eta}\mathbb{E}_{t}\left[\|\theta_{1}-\theta\|^{2}+\eta^{2}cd_{\Theta}L^{2}T\right]$
(Claim 4) $\displaystyle\leq\frac{D_{\Theta}^{2}}{2\eta}+\frac{\eta
cd_{\Theta}L^{2}T}{2}$ (diameter of $\Theta$)

as required. ∎

######  Claim 5 (Regret from projection).

For any $\theta\in\Theta$,
$\mathsf{PR}(\theta_{\delta})-\mathsf{PR}(\theta)\leq\delta D_{\Theta}L$.

###### Proof.

Since $\mathsf{PR}$ is $L$-Lipschitz and $\Pi_{(1-\delta)\Theta}$ projects
from a set of diameter $D_{\Theta}$ to a set of diameter
$(1-\delta)D_{\Theta}$, we have
$\mathsf{PR}(\theta_{\delta})-\mathsf{PR}(\theta)\leq
L\|\theta_{\delta}-\theta\|\leq\delta D_{\Theta}L$. ∎

######  Claim 6 (Optimality of projected parameters).

Since $\mathsf{PR}$ is convex in $\theta$,
$\mathsf{PR}\left(\Pi_{(1-\delta)\Theta}(\theta_{\texttt{OPT}})\right)=\operatorname*{\arg\\!\min}_{\theta\in(1-\delta)\Theta}\mathsf{PR}(\theta)$.

#### Overall Regret Analysis for 1

We can now complete our regret bound for 1. Recall the lemma statement:

See 1

###### Proof of 1.

We have

$\displaystyle\mathcal{R}_{T}(\mathcal{A}_{\ref{algorithm:minimize-convex-
function}},f)$
$\displaystyle=\sum_{t=1}^{T}\left[\operatorname{\mathsf{Estimate}\mathsf{PR}}(\theta_{t}^{+})+\operatorname{\mathsf{Estimate}\mathsf{PR}}(\theta_{t}^{-})-2\mathsf{PR}(\theta_{\texttt{OPT}})\right]$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\left[\widetilde{\mathsf{PR}}(\theta_{t}^{+})+\widetilde{\mathsf{PR}}(\theta_{t}^{-})-\mathsf{PR}(\theta_{t}^{+})-\mathsf{PR}(\theta_{t}^{-})\right]}_{\text{(I)}}+\underbrace{\sum_{t=1}^{T}\left[\mathsf{PR}(\theta_{t}^{+})+\mathsf{PR}(\theta_{t}^{-})-2\widehat{\mathsf{PR}}(\theta_{t})\right]}_{\text{(II)}}$
$\displaystyle\qquad+\underbrace{2\sum_{t=1}^{T}\left[\widehat{\mathsf{PR}}(\theta_{t})-\mathbb{E}_{t}[\widehat{\mathsf{PR}}(\theta_{t})]\right]}_{\text{(III)}}+\underbrace{2\sum_{t=1}^{T}\left[\mathbb{E}_{t}[\widehat{\mathsf{PR}}(\theta_{t})]-\hat{f}(\theta^{*}_{\delta})\right]}_{\text{(IV)}}$
$\displaystyle\qquad+\underbrace{2\sum_{t=1}^{T}\left[\widehat{\mathsf{PR}}(\theta^{*}_{\delta})-f(\theta^{*}_{\delta})\right]}_{\text{(V)}}+\underbrace{2\sum_{t=1}^{T}\left[\mathsf{PR}(\theta^{*}_{\delta})-\mathsf{PR}(\theta_{\texttt{OPT}})\right]}_{\text{(VI)}}$
$\displaystyle\leq\underbrace{2F\sqrt{T\log\frac{1}{p_{1}}}}_{\begin{subarray}{c}\text{(I),
w.p. $1-2p_{1}$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:regret-from-
estimating-f})}\end{subarray}}+\underbrace{4\delta
LT}_{\begin{subarray}{c}\text{(II), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-over-sphere-
or-
ball})}\end{subarray}}+\underbrace{2F\sqrt{T\log\frac{1}{p_{2}}}}_{\begin{subarray}{c}\text{(III),
w.p. $1-2p_{2}$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:deviation-of-
smoothed-
function})}\end{subarray}}+\underbrace{\frac{2D_{\Theta}^{2}}{\eta}+2\eta
cd_{\theta}L^{2}T}_{\begin{subarray}{c}\text{(IV), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{lemma:expected-suboptimality-under-
smoothing})}\end{subarray}}+\underbrace{2\delta
LT}_{\begin{subarray}{c}\text{(V), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-over-sphere-
or-ball})}\end{subarray}}+\underbrace{2\delta
D_{\Theta}LT}_{\begin{subarray}{c}\text{(V), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-
projection})}\end{subarray}}$

Thus for any $p>0$, a choice of $p_{1}=p_{2}=p/4$, along with
$\eta=1/\sqrt{d_{\theta}T}$ and any $\delta\leq\sqrt{d_{\theta}/T}$, yields
$\mathcal{R}_{T}(\mathcal{A}_{\ref{algorithm:minimize-convex-
function}},\mathsf{PR})=O(\sqrt{d_{\theta}T\log\frac{1}{p}})$ with probability
at least $1-p$. Finally, since $\operatorname{\mathsf{Estimate}\mathsf{PR}}$
is queried twice per step, $n=2T$, which gives us
$\mathcal{R}_{n}(\mathcal{A}_{\ref{algorithm:minimize-convex-
function}},\mathsf{PR})=\mathcal{R}_{T}(\mathcal{A}_{\ref{algorithm:minimize-
convex-function}},\mathsf{PR})=O(\sqrt{d_{\theta}n\log\frac{1}{p}})$,
completing the proof. ∎

##  Appendix C Omitted Proof for Section 4

We present a series of lemmas and claims that are helpful for proving 2.

######  Claim 7 (Deviation of $\mathsf{PR}^{\dagger}$ due to error of
$\operatorname{\mathsf{LearnModel}}$).

If $\mathsf{PR}^{\dagger}$ is $L^{\dagger}$-Lipschitz, then for any
$\phi\in\Phi$, the value $\hat{\theta}\in\Theta$ returned by
$\operatorname{\mathsf{LearnModel}}(\phi,\epsilon_{\mathsf{LM}},p_{\mathsf{LM}})$
satisfies $|\mathsf{PR}^{\dagger}(\phi)-\mathsf{PR}(\hat{\theta})|\leq
L^{\dagger}\epsilon_{\mathsf{LM}}$ with probability at least
$1-p_{\mathsf{LM}}$.

###### Proof.

We have

$\displaystyle\left|\mathsf{PR}^{\dagger}(\phi)-\mathsf{PR}(\hat{\theta})\right|$
$\displaystyle=\left|\mathsf{PR}^{\dagger}(\phi)-\mathsf{PR}^{\dagger}(\varphi(\hat{\theta}))\right|$
$\displaystyle\leq L^{\dagger}\left\|\phi-\varphi(\hat{\theta})\right\|$
(Lipschitzness of $\mathsf{PR}^{\dagger}$) $\displaystyle\leq
L^{\dagger}\epsilon_{\mathsf{LM}}$ (guarantee of
$\operatorname{\mathsf{LearnModel}}$)

where the last inequality holds with probability at least $1-p_{\mathsf{LM}}$.
∎

######  Claim 8 (Deviation of gradient estimate due to error of
$\operatorname{\mathsf{LearnModel}}$ and
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$).

Define

$\displaystyle\tilde{g}_{t}:=\frac{d_{\Phi}}{\delta}\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})u_{t}\qquad\text{and}\qquad
g_{t}:=\frac{d_{\Phi}}{\delta}\mathsf{PR}^{\dagger}(\phi_{t}^{+})u_{t}$ (6)

For any $t\in[T]$,

$\displaystyle
g_{t}-\tilde{g}_{t}\leq\frac{d_{\Phi}}{\delta}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})-\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})+\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]u_{t}.$

###### Proof.

We have

$\displaystyle g_{t}$
$\displaystyle=\frac{d_{\Phi}}{\delta}\mathsf{PR}^{\dagger}(\phi_{t}^{+})u_{t}$
$\displaystyle=\frac{d_{\Phi}}{\delta}\left[\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})-\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}^{\dagger}(\phi_{t}^{+})\right]u_{t}$
$\displaystyle=\tilde{g}_{t}+\frac{d_{\Phi}}{\delta}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})-\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})+\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]u_{t}$
(definition of $\tilde{g}_{t}$)

∎

######  Lemma 5 (Expected suboptimality under smoothing for
$\mathsf{PR}^{\dagger}$).

For any $\phi\in\Phi$, with probability at least $1-Tp_{\mathsf{LM}}$ over the
calls to $\operatorname{\mathsf{LearnModel}}$,

$\displaystyle\mathbb{E}_{T}\left[\sum_{t=1}^{T}\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})\right]-\sum_{t=1}^{T}\widehat{\mathsf{PR}}^{\dagger}(\phi)\leq\frac{D_{\Phi}^{2}}{\eta}+\eta
cd_{\Phi}L^{2}T+\frac{D_{\Phi}L^{\dagger}\epsilon_{\mathsf{LM}}d_{\Phi}T}{\delta}$

###### Proof of 5.

For any $\phi\in\Phi$, we have

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})\right]-\sum_{t=1}^{T}\widehat{\mathsf{PR}}^{\dagger}(\phi)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})-\widehat{\mathsf{PR}}^{\dagger}(\phi)\right]$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\nabla\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})^{\top}(\phi_{t}-\phi)\right]$
(convexity of $\widehat{\mathsf{PR}}^{\dagger}$) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[g_{t}^{\top}(\phi_{t}-\phi)\right]$
(Claim 4) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\left(\tilde{g}_{t}+\frac{d_{Y}}{\delta}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})-\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})+\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]\cdot
u_{t}\right)^{\top}(\phi_{t}-\phi)\right]$ (Claim 8) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\left(\tilde{g}_{t}+\frac{d_{Y}}{\delta}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]\cdot
u_{t}\right)^{\top}(\phi_{t}-\phi)\right]$
($\mathbb{E}[\widetilde{\mathsf{PR}}(\cdot)]=\mathsf{PR}(\cdot)$ since
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ is unbiased) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\tilde{g}_{t}^{\top}(\phi_{t}-\phi)\right]+\frac{d_{Y}}{\delta}\sum_{t=1}^{T}\mathbb{E}\left[\left(\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right)u_{t}^{\top}(\phi_{t}-\phi)\right]$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\tilde{g}_{t}^{\top}(\phi_{t}-\phi)\right]+\frac{d_{Y}}{\delta}\sum_{t=1}^{T}\mathbb{E}\left[\left|\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right|\cdot\|u_{t}\|\cdot\|\phi_{t}-\phi\|\right]$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\tilde{g}_{t}^{\top}(\phi_{t}-\phi)\right]+\frac{d_{Y}}{\delta}\sum_{t=1}^{T}\mathbb{E}\left[L^{\dagger}\epsilon_{h}\cdot
D_{Y}\right]$ (Claim 7, w.p. $1-Tp_{h}$) $\displaystyle\leq$
$\displaystyle\frac{D_{Y}^{2}}{\eta}+\eta
cd_{Y}L^{2}T+\frac{d_{Y}}{\delta}L^{\dagger}\epsilon_{h}D_{Y}T$ (same argument
as in 4)

∎

#### Regret analysis for the outer algorithm in total number of step $T$

We can now complete our regret bound for
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ (Algorithm 1). We recall the
theorem statement for 2:

See 2

###### Proof of 2.

We have

$\displaystyle\
\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=\sum_{t=1}^{T}\left[\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{+})+\operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta_{\texttt{OPT}})\right]$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\left[\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{+})+\widetilde{\mathsf{PR}}(\hat{\theta}_{t}^{-})-\mathsf{PR}(\hat{\theta}_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{-})\right]}_{\text{(I)}}+\underbrace{\sum_{t=1}^{T}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-})-\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}^{\dagger}(\phi_{t}^{-})\right]}_{\text{(II)}}$
$\displaystyle\qquad+\underbrace{\sum_{t=1}^{T}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{+})+\mathsf{PR}^{\dagger}(\phi_{t}^{-})-2\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})\right]}_{\text{(III)}}+\underbrace{2\sum_{t=1}^{T}\left[\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})-\mathbb{E}_{t}[\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})]\right]}_{\text{(IV)}}$
$\displaystyle\qquad+\underbrace{2\sum_{t=1}^{T}\left[\mathbb{E}_{t}[\widehat{\mathsf{PR}}^{\dagger}(\phi_{t})]-\widehat{\mathsf{PR}}^{\dagger}(\phi^{*}_{\delta})\right]}_{\text{(V)}}+\underbrace{2\sum_{t=1}^{T}\left[\widehat{\mathsf{PR}}^{\dagger}(\phi^{*}_{\delta})-\mathsf{PR}^{\dagger}(\phi^{*}_{\delta})\right]}_{\text{(VI)}}+\underbrace{2\sum_{t=1}^{T}\left[\mathsf{PR}^{\dagger}(\phi^{*}_{\delta})-\mathsf{PR}^{\dagger}(\phi_{\texttt{OPT}})\right]}_{\text{(VII)}}$
$\displaystyle\leq\underbrace{2F\sqrt{T\log\frac{1}{p_{1}}}}_{\begin{subarray}{c}\text{(I),
w.p. $1-2p_{1}$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:regret-from-
estimating-f})}\end{subarray}}\qquad+\underbrace{2L^{\dagger}\epsilon_{\mathsf{LM}}T}_{\begin{subarray}{c}\text{(II),
w.p. $1-2Tp_{\mathsf{LM}}$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:deviation-of-PRdagger-due-to-error-
of-learnmodel})}\end{subarray}}\qquad+\underbrace{4\delta
LT}_{\begin{subarray}{c}\text{(III), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-over-sphere-
or-
ball})}\end{subarray}}\qquad+\underbrace{2F\sqrt{T\log\frac{1}{p_{2}}}}_{\begin{subarray}{c}\text{(IV),
w.p. $1-2p_{2}$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:deviation-of-
smoothed-function})}\end{subarray}}$
$\displaystyle\qquad\qquad\qquad+\underbrace{\frac{2D_{\Phi}^{2}}{\eta}+2\eta
cD_{\Phi}L^{2}T+\frac{2D_{\Phi}L^{\dagger}\epsilon_{\mathsf{LM}}D_{\Phi}T}{\delta}}_{\begin{subarray}{c}\text{(V),
w.p. $1-2Tp_{\mathsf{LM}}$}\\\ \text{(\lx@cref{creftypecap~refnum}{lemma:high-
probability-expected-suboptimality-under-
smoothing})}\end{subarray}}\qquad+\underbrace{2\delta
L^{\dagger}T}_{\begin{subarray}{c}\text{(VI), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-over-sphere-
or-ball})}\end{subarray}}\qquad+\underbrace{2\delta
D_{\Phi}L^{\dagger}T}_{\begin{subarray}{c}\text{(VII), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-
projection})}\end{subarray}}$

Recall that in Algorithm 1, we set
$\delta=\sqrt{\epsilon_{\mathsf{LM}}D_{\Phi}}$ and $\eta=1/\sqrt{D_{\Phi}T}$.
Thus for any $p^{\prime}>0$, a choice of $p_{1}=p_{2}=p^{\prime}/4$ yields

$\displaystyle\mathcal{R}_{T}(\mathcal{A}_{\ref{algorithm:minimize-indirectly-
convex-
function}},\mathsf{PR})=O\left(\sqrt{D_{\Phi}T}+\sqrt{\epsilon_{\mathsf{LM}}D_{\Phi}}\cdot
T+\sqrt{T\log\frac{1}{p^{\prime}}}\right)$

with probability at least $1-p^{\prime}-2Tp_{\mathsf{LM}}$ as required. ∎

##  Appendix D Omitted Proof for Section 5

We first provide a proof for 2. Recall the lemma statement:

See 2

###### Proof of 2.

$\displaystyle\left|\mathsf{KL}(\phi||\varphi(\theta_{1}))-\mathsf{KL}(\phi||\varphi(\theta_{2}))\right|$
$\displaystyle=$
$\displaystyle\left|\int_{z}p(z|\phi)\log\frac{p(z|\phi)}{p(z|\varphi(\theta_{1}))}dz-\int_{z}p(z|\phi)\log\frac{p(z|\phi)}{p(z|\varphi(\theta_{2}))}dz\right|$
$\displaystyle=$ $\displaystyle\left|\int_{z}p(z|\phi)(\log
p(z|\varphi(\theta_{1}))-\log p(z|\varphi(\theta_{2})))dz\right|$
$\displaystyle\leq$ $\displaystyle\int_{z}p(z|\phi)\left|\log
p(z|\varphi(\theta_{1}))-\log p(z|\varphi(\theta_{2}))\right|dz$
$\displaystyle\leq$
$\displaystyle\int_{z}p(z|\phi)L_{\mathsf{KL}}\|\theta_{1}-\theta_{2}\|dz$
($\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ are lipschitzness continuous, Theorem
3 of [13]) $\displaystyle=$ $\displaystyle
L_{\mathsf{KL}}\|\theta_{1}-\theta_{2}\|\underbrace{\int_{z}p(z|\phi)dz}_{=1}$
$\displaystyle=$ $\displaystyle L_{\mathsf{KL}}\|\theta_{1}-\theta_{2}\|$

∎

Next, we provide the proof for 3. Recall the lemma statement: See 3

###### Proof of 3.

$\displaystyle\|\phi_{1}-\phi_{2}\|_{2}\leq
L_{\mathsf{TV}}d_{\mathsf{TV}}(\phi_{1},\phi_{2})\leq
L_{\mathsf{TV}}\sqrt{\frac{1}{2}\mathsf{KL}(\phi_{1},\phi_{2})}\triangleq
L_{\phi}\sqrt{\mathsf{KL}(\phi_{1},\phi_{2})}$

The second inequality is due to Pinsker’s inequality. ∎

We then show the example provide by 2 is convex in $\theta$. Recall the
example: See 2

Below we provide proof for it being convex in $\theta$:

###### Proof for 2 being convex in $\theta$.

Under condition 1, we have $p(z;\phi)=\frac{1}{\exp(c\varphi(\theta))}$. We
can rewrite the $\mathsf{KL}(\phi||\varphi(\theta))$ divergence as:

$\displaystyle\mathsf{KL}(\phi||\varphi(\theta))=$
$\displaystyle\int_{z}p(z;\phi)\log\frac{p(z;\phi)}{p(z;\varphi(\theta))}dz$
$\displaystyle=$
$\displaystyle\int_{z}\frac{1}{\exp(c\phi)}\log\frac{\exp(c\varphi(\theta))}{\exp(c\phi)}dz$
$\displaystyle=$
$\displaystyle\frac{\exp(c\varphi(\theta))}{\exp(c\phi)}\log\frac{\exp(c\varphi(\theta)}{\exp(c\phi)}$
$\displaystyle=$
$\displaystyle\exp(c(\varphi(\theta)-\phi))c(\varphi(\theta)-\phi)$

Denote $\mathsf{KL}(\phi||\varphi(\theta))=f(g(\theta))$ where
$f(x)=cx\exp(cx)$ and $g(\theta)=\varphi(\theta)-\phi$.

To show Equation 5 is convex in $\theta$, it suffices to show f(x) is convex
non-decreasing in x, and $g(\theta)$ is convex in $\theta$. First, $g(\theta)$
is convex in $\theta$ due to condition 2.
For $f(x)$, take the first and second derivative and find conditions to make
them both non negative:

$\displaystyle\frac{\partial f(x)}{\partial x}$
$\displaystyle=c\exp(cx)+cx^{2}\exp(cx)$ $\displaystyle=c\exp(cx)(1+cx)\geq 0$
$\displaystyle\frac{\partial^{2}f(x)}{\partial x^{2}}$
$\displaystyle=c^{2}\exp(cx)(2+cx)\geq 0$

It suffices to set $(2+cx)\geq 0$ and $c(1+cx)\geq 0$ which suffices to set
$c\geq\frac{2}{\max|\varphi(\theta)-\phi|}$.

∎

#### Regret Analysis and convergence guarantee of
$\operatorname{\mathsf{LearnModel}}$ in total number of steps $S$

We can now complete our regret bound for $\operatorname{\mathsf{LearnModel}}$
(Algorithm 2). Recall the theorem statement: See 3

###### Proof of 3.

$\displaystyle\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{S}\left[\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{+}))+\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{-}))-2\underbrace{\mathsf{KL}(\phi||\varphi(\vartheta^{*}(\phi)))}_{=0,\varphi(\vartheta^{*}(\phi)))=\phi}\right]$
$\displaystyle=$
$\displaystyle\underbrace{\sum_{s=1}^{S}\left[\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{+}))-{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{+}))+\widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^{+}))-\mathsf{KL}(\phi||\varphi(\theta_{s}^{-}))\right]}_{\text{(I)}}$
$\displaystyle\qquad+\underbrace{\sum_{s=1}^{S}\left[\mathsf{KL}(\phi||\varphi(\theta_{s}^{+}))+\mathsf{KL}(\phi||\varphi(\theta_{s}^{-}))-2\widehat{\mathsf{KL}}(\phi||\varphi(\theta_{s}))\right]}_{\text{(II)}}$
$\displaystyle\qquad+\underbrace{2\sum_{s=1}^{S}\left[\widehat{\mathsf{KL}}(\phi||\varphi(\theta_{s}))-\mathbb{E}_{s}[\widehat{\mathsf{KL}}(\phi||\varphi(\theta_{s}))]\right]}_{\text{(III)}}+\underbrace{2\sum_{s=1}^{S}\left[\mathbb{E}_{s}[\widehat{\mathsf{KL}}(\phi||\varphi(\theta_{s}))]-\widehat{\mathsf{KL}}(\phi||\varphi(\theta^{*}_{\delta}))\right]}_{\text{(IV)}}$
$\displaystyle\qquad+\underbrace{2\sum_{s=1}^{S}\left[\widehat{\mathsf{KL}}(\phi||\varphi(\theta^{*}_{\delta}))-{\mathsf{KL}}(\phi||\varphi(\theta^{*}_{\delta}))\right]}_{\text{(V)}}+\underbrace{2\sum_{s=1}^{S}\left[{\mathsf{KL}}(\phi||\varphi(\theta^{*}_{\delta}))-{\mathsf{KL}}(\phi||\varphi(\theta^{*}))\right]}_{\text{(VI)}}$
$\displaystyle\leq\underbrace{2\epsilon_{\mathsf{KL}}S}_{\begin{subarray}{c}\text{(I),
w.p. $1-2Sp_{\mathsf{KL}}$}\\\ \text{(Assumption \ref{ass:kl-
oracle})}\end{subarray}}\qquad+\underbrace{4\delta
L_{\mathsf{KL}}S}_{\begin{subarray}{c}\text{(II), w.p. $1$}\\\
\text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-over-sphere-
or-
ball})}\end{subarray}}\qquad+\underbrace{2F_{\mathsf{KL}}\sqrt{S\log\frac{1}{p_{2}}}}_{\begin{subarray}{c}\text{(III),
w.p. $1-2p_{2}$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:deviation-of-
smoothed-function})}\end{subarray}}$
$\displaystyle\qquad+\underbrace{\frac{2D_{\Theta}^{2}}{\eta_{\mathsf{LM}}}+2\eta_{\mathsf{LM}}d_{\Theta}L_{\mathsf{KL}}^{2}S+\frac{2D_{\Theta}L_{\mathsf{KL}}\epsilon_{\mathsf{KL}}d_{\Theta}S}{\delta_{\mathsf{LM}}}}_{\begin{subarray}{c}\text{(IV),
w.p. $1-2Sp_{\mathsf{KL}}$}\\\ \text{(Similar argument as
\lx@cref{creftypecap~refnum}{lemma:high-probability-expected-suboptimality-
under-
smoothing})}\end{subarray}}\qquad+\underbrace{2\delta_{\mathsf{LM}}L_{\mathsf{KL}}S}_{\begin{subarray}{c}\text{(V),
w.p. $1$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:regret-from-smoothing-
over-sphere-or-
ball})}\end{subarray}}\qquad+\underbrace{2\delta_{\mathsf{LM}}D_{\Theta}L_{\mathsf{KL}}S}_{\begin{subarray}{c}\text{(VI),
w.p. $1$}\\\ \text{(\lx@cref{creftypecap~refnum}{claim:regret-from-
projection})}\end{subarray}}$

Similar to Algorithm 1, we set
$\delta_{\mathsf{LM}}=\sqrt{\epsilon_{\mathsf{KL}}d_{\Theta}}$,
$\eta_{\mathsf{LM}}=1/\sqrt{d_{\Theta}S}$. For any $p_{2}=p^{\prime}/2>0$, it
yields

$\displaystyle
R_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})=O\left(\sqrt{d_{\Theta}S}+\sqrt{\epsilon_{\mathsf{KL}}d_{\theta}}S+\sqrt{S\log\frac{1}{p}}\right)$

with probability $1-p^{\prime}-2Sp_{\mathsf{KL}}$ > 0.

∎

##  Appendix E Omitted Proof for Section 6

We start with leveraging 2 to show the following convergence guarantee for
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ (Algorithm 1).

######  Claim 9 (Convergence of
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$).

Given any $\epsilon,p>0$, $\operatorname{\mathsf{Minimize}\mathsf{PR}}$
outputs an $\epsilon$-suboptimal solution for $\mathsf{PR}(\theta)$ with
probability at least $1-p$. Moreover,
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$ runs for
$T=O(d_{\Phi}/\epsilon^{2})$ steps and performs $O(d_{\Phi}/\epsilon^{2})$
queries to $\operatorname{\mathsf{Estimate}\mathsf{PR}}$, as well as
$O(d_{\Phi}/\epsilon^{2})$ queries to $\operatorname{\mathsf{LearnModel}}$
with $\epsilon_{\mathsf{LM}}=O(\epsilon^{2})$ and
$p_{\mathsf{LM}}=O(\epsilon^{2}p/d_{\Phi})$.

###### Proof of Claim 9.

Choosing $\epsilon_{\mathsf{LM}}=1/T$, $p_{\mathsf{LM}}=p/2T$, and
$p^{\prime}=p/2$, 2 shows that $\operatorname{\mathsf{Minimize}\mathsf{PR}}$
satisfies

$\displaystyle\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})=O\left(\sqrt{d_{\Phi}T}\right)$

with probability $1-p$, using $2T$ queries to
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ and $2T$ queries to
$\operatorname{\mathsf{LearnModel}}$. By Proposition 1,
$T=O(d_{\Phi}/\epsilon^{2})$ steps suffice to output a model that is
$\epsilon$-suboptimal with respect to $\mathsf{PR}$. Plugging in this bound on
$T$ into the expressions for $\epsilon_{\mathsf{LM}}$ and $p_{\mathsf{LM}}$
above yields the result. ∎

Similarly, we have the convergence guarantee for
$\operatorname{\mathsf{LearnModel}}$ as well:

######  Claim 10 (Convergence of $\operatorname{\mathsf{LearnModel}}$).

Given any $\phi\in\Phi$ and $\epsilon_{\mathsf{LM}},p_{\mathsf{LM}}>0$,
$\operatorname{\mathsf{LearnModel}}$ outputs an
$\epsilon_{\mathsf{LM}}$-suboptimal model for Equation 5 with probability at
least $1-p_{\mathsf{LM}}$. Moreover, $\operatorname{\mathsf{LearnModel}}$ runs
for $S=O(d_{\Theta}/\epsilon_{\mathsf{LM}}^{2})$ steps and performs two
queries to $\operatorname{\mathsf{EstimateKL}}$ per step with
$N_{\mathsf{KL}}(\frac{\epsilon^{2}_{\mathsf{LM}}}{d_{\theta}},\frac{\epsilon^{2}_{\mathsf{LM}}p_{\mathsf{LM}}}{4d_{\theta}})$
samples per query.

###### Proof of Claim 10.

Choosing $\epsilon_{\mathsf{KL}}=1/S$, $p_{\mathsf{KL}}=p_{\mathsf{LM}}/4S$
and $p^{\prime}=p_{\mathsf{LM}}/2$, 3 shows that
$\operatorname{\mathsf{LearnModel}}$ satisfies

$\displaystyle\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})=O\left(\sqrt{d_{\Phi}S}\right)$

By Proposition 1, $S=O(d_{\Theta}/\epsilon_{\mathsf{LM}}^{2})$ steps suffice
to output a model that is $\epsilon_{\mathsf{LM}}$-suboptimal with respect to
$\mathsf{KL}$; thus we have
$\epsilon_{\mathsf{KL}}=\frac{\epsilon_{\mathsf{LM}}^{2}}{d_{\Theta}}$,
$p_{\mathsf{KL}}=\frac{1}{4Sp_{\mathsf{LM}}}$. In total,
$\operatorname{\mathsf{LearnModel}}$ makes $2S$ queries to
$\operatorname{\mathsf{EstimateKL}}$ with
$N_{\mathsf{KL}}(\frac{\epsilon_{\mathsf{LM}}^{2}}{d_{\Theta}},\frac{\epsilon^{2}_{\mathsf{LM}}p_{\mathsf{LM}}}{4d_{\theta}})$
samples per query. ∎

Now are are ready to prove 4. Recall the theorem statement:

See 4

###### Proof of 4.

Let $T$ be the number of steps executed by
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$, and $S$ the number of steps in
$\operatorname{\mathsf{LearnModel}}$. Let
$N_{\mathsf{KL}}(\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$ (or
$N_{\mathsf{KL}}$ for short) denote the number of samples used by
$\operatorname{\mathsf{EstimateKL}}(\cdot,\cdots,\epsilon_{\mathsf{KL}},p_{\mathsf{KL}})$.
Since $\operatorname{\mathsf{Minimize}\mathsf{PR}}$ calls
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ and
$\operatorname{\mathsf{LearnModel}}$ $2T$ times, and
$\operatorname{\mathsf{LearnModel}}$ calls
$\operatorname{\mathsf{EstimateKL}}$ $2S$ times, the overall number of samples
is $N=2(2N_{\mathsf{KL}}S+1)T$.

Let $\theta_{t,s}^{+},\theta_{t,s}^{-}$ denote the models deployed by
$\operatorname{\mathsf{EstimateKL}}$ in the $s$-th step of
$\operatorname{\mathsf{LearnModel}}$ within the $t$-th step of
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$, obtaining samples
$z_{t,s,1}^{+},\ldots,z_{t,s,N_{\mathsf{KL}}}^{+}$ and
$z_{t,s,1}^{-},\ldots,z_{t,s,N_{\mathsf{KL}}}^{-}$, respectively. Similarly,
let $\hat{\theta}_{t}^{+},\hat{\theta}_{t}^{-}$ denote the models deployed by
$\operatorname{\mathsf{Estimate}\mathsf{PR}}$ in the $t$-th step of
$\operatorname{\mathsf{Minimize}\mathsf{PR}}$, obtaining samples
$\hat{z}_{t}^{+},\hat{z}_{t}^{-}$.

The total regret can be written as

$\displaystyle\quad\mathcal{R}_{N}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=\sum_{t=1}^{T}\left(\ell(\hat{z}_{t}^{+};\hat{\theta}_{t}^{+})+\ell(\hat{z}_{t}^{-};\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta^{*})+\sum_{s=1}^{S}\sum_{i=1}^{N_{\mathsf{KL}}}\left[\ell(z_{t,s,i}^{+};\theta_{t,s}^{+})+\ell(z_{t,s,i}^{-};\theta_{t,s}^{-})-2\mathsf{PR}(\theta^{*})\right]\right)$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\left(\ell(\hat{z}_{t}^{+};\hat{\theta}_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})+\ell(\hat{z}_{t}^{-};\hat{\theta}_{t}^{-})-\mathsf{PR}(\hat{\theta}_{t}^{-})+\sum_{s=1}^{S}\sum_{i=1}^{N_{\mathsf{KL}}}\left[\ell(z_{t,s,i}^{+};\theta_{t,s}^{+})-\mathsf{PR}(\theta_{t,s}^{+})+\ell(z_{t,s,i}^{-};\theta_{t,s}^{-})-\mathsf{PR}(\theta_{t,s}^{-})\right]\right)}_{n\text{
difference terms with expectation zero}}$
$\displaystyle\qquad\qquad+\sum_{t=1}^{T}\left(\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta^{*})+\sum_{s=1}^{S}\sum_{i=1}^{N_{\mathsf{KL}}}\left[\mathsf{PR}(\theta_{t,s}^{+})+\mathsf{PR}(\theta_{t,s}^{-})-2\mathsf{PR}(\theta^{*})\right]\right)$
$\displaystyle=O\left(\sqrt{N}\right)+\sum_{t=1}^{T}\left(\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta^{*})+\sum_{s=1}^{S}\sum_{i=1}^{N_{\mathsf{KL}}}\left[\mathsf{PR}(\theta_{t,s}^{+})+\mathsf{PR}(\theta_{t,s}^{-})-2\mathsf{PR}(\theta^{*})\right]\right)$
(by Hoeffding’s inequality, w.p. $1-p^{\prime}$)
$\displaystyle=O\left(\sqrt{N}\right)+\sum_{t=1}^{T}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta^{*})\right]$
$\displaystyle\qquad\qquad+N_{\mathsf{KL}}\cdot\sum_{t=1}^{T}\sum_{s=1}^{S}\left[(\mathsf{PR}(\theta_{t,s}^{+})+\mathsf{PR}(\theta_{t,s}^{-}))-(\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-}))+(\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-}))-2\mathsf{PR}(\theta^{*})\right]$
$\displaystyle=O\left(\sqrt{N}\right)+(N_{\mathsf{KL}}S+1)\sum_{t=1}^{T}\left[\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\hat{\theta}_{t}^{-})-2\mathsf{PR}(\theta^{*})\right]$
$\displaystyle\qquad\qquad+N_{\mathsf{KL}}\cdot\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}(\theta_{t,s}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\theta_{t,s}^{-})-\mathsf{PR}(\hat{\theta}_{t}^{-})\right]$
$\displaystyle=O\left(\sqrt{N}\right)+(N_{\mathsf{KL}}S+1)\cdot\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})+N_{\mathsf{KL}}\cdot\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}(\theta_{t,s}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}(\theta_{t,s}^{-})-\mathsf{PR}(\hat{\theta}_{t}^{-})\right]$
$\displaystyle=O\left(\sqrt{N}\right)+(N_{\mathsf{KL}}S+1)\cdot\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})+N_{\mathsf{KL}}\cdot\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\varphi(\theta_{t,s}^{+}))-\mathsf{PR}(\hat{\theta}_{t}^{+})+\mathsf{PR}^{\dagger}(\varphi(\theta_{t,s}^{-}))-\mathsf{PR}(\hat{\theta}_{t}^{-})\right]$
$\displaystyle=O\left(\sqrt{N}\right)+(N_{\mathsf{KL}}S+1)\cdot\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle\qquad\qquad+N_{\mathsf{KL}}\cdot\underbrace{\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\varphi(\theta_{t,s}^{+}))-\mathsf{PR}^{\dagger}(\phi_{t}^{+})\right]}_{\text{(I)}}+N_{\mathsf{KL}}\cdot\underbrace{\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]}_{\text{(II)}}$
$\displaystyle\qquad\qquad+N_{\mathsf{KL}}\cdot\underbrace{\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\varphi(\theta_{t,s}^{-}))-\mathsf{PR}^{\dagger}(\phi_{t}^{-})\right]}_{\text{(III)}}+N_{\mathsf{KL}}\cdot\underbrace{\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{-})-\mathsf{PR}(\hat{\theta}_{t}^{-})\right]}_{\text{(IV)}}$

Term (I) is:

$\displaystyle\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\varphi(\theta_{t,s}^{+}))-\mathsf{PR}^{\dagger}(\phi_{t}^{+})\right]$
$\displaystyle\leq
L^{\dagger}\cdot\sum_{t=1}^{T}\sum_{s=1}^{S}\left\|\varphi(\theta_{t,s}^{+})-\phi_{t}^{+}\right\|$
(Lipschitzness of $\mathsf{PR}^{\dagger}$) $\displaystyle\leq
L^{\dagger}\cdot\sum_{t=1}^{T}\sqrt{S\sum_{s=1}^{S}\left(\left\|\varphi(\theta_{t,s}^{+})-\phi_{t}^{+}\right\|^{2}\right)}$
(Cauchy-Schwarz)
$\displaystyle=L^{\dagger}T\sqrt{S\sum_{s=1}^{S}L_{\theta}^{2}{\mathsf{KL}(\phi_{t}^{+}||\varphi(\theta_{t,s}^{+}))}}$
(2) $\displaystyle\leq
L^{\dagger}L_{\theta}T\cdot\sqrt{S\cdot\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}$

and term (III) is analogous. Term (II) is

$\displaystyle\sum_{t=1}^{T}\sum_{s=1}^{S}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}(\hat{\theta}_{t}^{+})\right]$
$\displaystyle=S\cdot\sum_{t=1}^{T}\left[\mathsf{PR}^{\dagger}(\phi_{t}^{+})-\mathsf{PR}^{\dagger}(\varphi(\hat{\theta}_{t}^{+}))\right]$
$\displaystyle\leq
L^{\dagger}S\cdot\sum_{t=1}^{T}\left\|\phi_{t}^{+}-\varphi(\hat{\theta}_{t}^{+})\right\|$
(Lipschitzness of $\mathsf{PR}^{\dagger}$) $\displaystyle\leq
L^{\dagger}S\cdot\sum_{t=1}^{T}L_{\theta}\sqrt{\mathsf{KL}(\phi_{t}^{+}||\varphi(\hat{\theta}_{t}^{+}))}$
(2) $\displaystyle\leq L^{\dagger}L_{\theta}\cdot
S\cdot\sum_{t=1}^{T}\sqrt{\frac{1}{S}\sum_{s=1}^{S}\mathsf{KL}(\phi_{t}^{+}||\varphi(\theta_{t,s}^{+}))}$
($\hat{\theta}_{t}^{+}:=\frac{1}{S}\sum_{s=1}^{S}\theta_{t,s}^{+}$, convexity
of $\mathsf{KL}(\phi^{+}_{t}||\varphi(\theta))$) $\displaystyle\leq
L^{\dagger}L_{\phi}TS\sqrt{\frac{1}{S}\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}$
$\displaystyle=L^{\dagger}L_{\phi}T\sqrt{S\cdot\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}$

and term (IV) is analogous. In total we have

$\displaystyle\mathcal{R}_{N}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=O\left(\sqrt{N}+N_{\mathsf{KL}}T\cdot\sqrt{S\cdot\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}+(N_{\mathsf{KL}}S+1)\cdot\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})\right)$
$\displaystyle=N\cdot
O\left(\frac{1}{\sqrt{N}}+\sqrt{\frac{\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})}{S}}+\frac{\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})}{T}\right)$
($n=2(N_{\mathsf{KL}}2S+1)T$) $\displaystyle=N\cdot
O\left(\frac{1}{\sqrt{N}}+\sqrt{\sqrt{\frac{d_{\Theta}\log\frac{1}{p^{\prime}}}{S}}+\sqrt{\epsilon_{\mathsf{KL}}d_{\Theta}}}+\sqrt{\frac{d_{\Phi}\log\frac{1}{p^{\prime\prime}}}{T}}+\sqrt{\epsilon_{\mathsf{LM}}d_{\Phi}}\right)$
(by 2,3, w.p. to be analyzed later) $\displaystyle=N\cdot
O\left(\left(\frac{d_{\Theta}}{S}\log\frac{1}{p^{\prime}}\right)^{1/4}+(\epsilon_{\mathsf{KL}}d_{\Theta})^{1/4}+\left(\frac{d_{\Phi}}{T}\log\frac{1}{p^{\prime\prime}}\right)^{1/2}+(\epsilon_{\mathsf{LM}}d_{\Phi})^{1/2}\right)$
(for $a,b\geq 0$, $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$;
$\frac{1}{\sqrt{n}}\leq\sqrt{\frac{d_{\Phi}}{T}}$) $\displaystyle\leq
N\cdot\left(1+\left(\log\frac{1}{p^{\prime}}\right)^{1/4}+\left(\log\frac{1}{p^{\prime\prime}}\right)^{1/2}\right)\cdot
O\left(\left(\frac{d_{\Theta}}{S}\right)^{1/4}+(\epsilon_{\mathsf{KL}}d_{\Theta})^{1/4}+\left(\frac{d_{\Phi}}{T}\right)^{1/2}+(\epsilon_{\mathsf{LM}}d_{\Phi})^{1/2}\right)$
$\displaystyle=N\cdot\left(1+\left(\log\frac{1}{p^{\prime}}\right)^{1/4}+\left(\log\frac{1}{p^{\prime\prime}}\right)^{1/2}\right)\cdot
O\left(\left(\frac{d_{\Theta}}{S}\right)^{1/4}+(\epsilon_{\mathsf{KL}}d_{\Theta})^{1/4}+\left(\frac{d_{\Phi}N_{\mathsf{KL}}S}{N}\right)^{1/2}+(\epsilon_{\mathsf{LM}}d_{\Phi})^{1/2}\right)$
($T=\frac{N}{N_{\mathsf{KL}}S+1}$)

Choose $\epsilon_{\mathsf{LM}}=\left(\frac{N_{\mathsf{KL}}}{N}\right)^{1/3}$
and
$\epsilon_{\mathsf{KL}}=\frac{1}{4d_{\Theta}}\left(\frac{N_{\mathsf{KL}}}{N}\right)^{2/3}$.

To balance the terms, set the number of steps for the outer algorithm to be
$T=\frac{d_{\Phi}}{(\epsilon-\sqrt{\epsilon_{\mathsf{LM}}d_{\Phi}})^{2}}$, and
the number of steps in $\operatorname{\mathsf{LearnModel}}$ to be

$\displaystyle
S=\frac{d_{\Theta}}{\left(\epsilon_{\mathsf{LM}}-\sqrt{\epsilon_{\mathsf{KL}}d_{\Theta}}\right)^{2}}=4d_{\Theta}\left(\frac{N}{N_{\mathsf{KL}}}\right)^{2/3}$

Plugging these expressions for $\epsilon_{\mathsf{KL}}$,
$\epsilon_{\mathsf{LM}}$, and $S$ in above, we have

$\displaystyle\mathcal{R}_{n}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=N\cdot\left(1+\left(\log\frac{1}{p^{\prime}}\right)^{1/4}+\left(\log\frac{1}{p^{\prime\prime}}\right)^{1/2}\right)\cdot
O\left((d_{\Theta}d_{\Phi})^{1/2}\left(\frac{N_{\mathsf{KL}}}{N}\right)^{1/6}\right)$
$\displaystyle=O\left(\left(1+\left(\log\frac{1}{p^{\prime}}\right)^{1/4}+\left(\log\frac{1}{p^{\prime\prime}}\right)^{1/2}\right)(d_{\Theta}+d_{\Phi})N_{\mathsf{KL}}^{1/6}N^{5/6}\right)$

We would like to ensure that this bound holds with probability $p>0$. To that
end, observe that the probabilistic terms are the high-probability bounds on
$\mathcal{R}_{S}(\operatorname{\mathsf{LearnModel}},\mathsf{KL})$ and
$\mathcal{R}_{T}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$. By
recalling 2 and 3, the probability that any of these bounds fails is at most

$\displaystyle
p^{\prime}+Tp_{\mathsf{LM}}=p^{\prime}+T(p^{\prime\prime}+Sp_{\mathsf{KL}})=p^{\prime}+Tp^{\prime\prime}+STp_{\mathsf{KL}}$

for any $p^{\prime},p^{\prime\prime}>0$. For a choice of $p^{\prime}=p/3$,
$p^{\prime\prime}=p/3T$, and $p_{\mathsf{KL}}=\frac{pN_{\mathsf{KL}}}{3n}$,
this is at most $p$ as required. Finally, plugging these choices into the
above regret bound yields

$\displaystyle\mathcal{R}_{n}(\operatorname{\mathsf{Minimize}\mathsf{PR}},\mathsf{PR})$
$\displaystyle=O\left(\left(1+\left(\log\frac{1}{p^{\prime}}\right)^{1/4}+\left(\log\frac{1}{p^{\prime\prime}}\right)^{1/2}\right)(d_{\Theta}+d_{\Phi})N_{\mathsf{KL}}^{1/6}N^{5/6}\right)$
$\displaystyle=O\left(\left(1+\left(\log\frac{1}{p}\right)^{1/4}+\left(\log\frac{T}{p}\right)^{1/2}\right)(d_{\Theta}+d_{\Phi})N_{\mathsf{KL}}^{1/6}N^{5/6}\right)$
$\displaystyle=O\left(\left(1+\sqrt{\log\frac{1}{p}}\right)(d_{\Theta}+d_{\Phi})N_{\mathsf{KL}}^{1/6}N^{5/6}\sqrt{\log
N}\right)$ ($T\leq N$)

with probability at most $p$ as required. ∎

##  Appendix F Convex condition for exponential family

Consider an exponential family where:

$\displaystyle p_{\phi}(z)=\exp(\phi\cdot T(z)-A(\phi)+B(z))$

thus:

$\displaystyle\log\left(p_{\phi}(z)\right)=\phi\cdot T(z)-A(\phi)+B(z)$

Recall that in performative prediction, the data parameter $\phi$ is a
function of the model parameter $\theta$, namely $\phi=\varphi(\theta)$.

We begin by writing out the gradient of the performative risk w.r.t. to the
data parameter $\phi$:

$\displaystyle\nabla_{\phi}\operatorname{PR}(\theta,\phi)=\nabla_{\phi}\left(\int\ell(z;\theta)p_{\phi}(z)dz\right)$
$\displaystyle=\int\nabla_{\phi}\ell(z;\theta)p_{\phi}(z)dz+\int\ell(z;\theta)\nabla_{\phi}p_{\phi}(z)dz$
$\displaystyle=\int\frac{\partial\ell(z;\theta)}{\partial\theta}\frac{\partial\theta}{\partial\phi}p_{\phi}(z)dz+\int\ell(z;\theta)\nabla_{\phi}\log\left(p_{\phi}(z)\right)p_{\phi}(z)dz$
$\displaystyle=\frac{\partial\theta}{\partial\phi}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\right]+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\nabla_{\phi}\log\left(p_{\phi}(z)\right)\right]$
$\displaystyle=\frac{1}{\nabla_{\theta}\varphi(\theta)}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right].$

Now consider the second derivative of the performative risk w.r.t to the data
parameter $\phi$:

$\displaystyle\nabla^{2}_{\phi}\operatorname{PR}(\theta,\phi)$
$\displaystyle=\nabla_{\phi}\left(\frac{1}{\nabla_{\theta}\varphi(\theta)}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\right]+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)$
$\displaystyle=\underbrace{\frac{1}{\nabla_{\theta}\varphi(\theta)}\nabla_{\phi}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\right]\right)}_{\text{Part
(I)}}$
$\displaystyle+\underbrace{\nabla_{\phi}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)}_{\text{Part (II)}}$

where

$\displaystyle\text{Part
(I)}=\frac{1}{\nabla_{\theta}\varphi(\theta)}(\frac{1}{\nabla_{\theta}\varphi(\theta)}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla^{2}_{\theta}\ell(z;\theta)\right]$
$\displaystyle+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right])$

and

Part (II)
$\displaystyle=\nabla_{\phi}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)$
$\displaystyle=\int\nabla_{\phi}\left(\ell(z;\theta)\left(T(z)-\frac{A(\phi)}{\phi}\right)\right)p_{\phi}(z)dz$
$\displaystyle\qquad+\int\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\nabla_{\phi}p_{\phi}(z)dz$
$\displaystyle=\int[\nabla_{\phi}\ell(z;\theta)\left(T(z)-\frac{A(\phi)}{\phi}\right)$
$\displaystyle\qquad+\ell(z;\theta)\left(-\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\right)]p_{\phi}(z)dz$
$\displaystyle\qquad+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)^{2}\right]$
$\displaystyle=\int[\frac{\partial\ell(z;\theta)}{\partial\theta}\frac{\partial\theta}{\partial\phi}\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)$
$\displaystyle\qquad-\ell(z;\theta)\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}]p_{\phi}(z)dz$
$\displaystyle\qquad+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)^{2}\right]$
$\displaystyle=\frac{1}{\nabla_{\theta}\varphi(\theta)}\int\left[\nabla_{\theta}\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]p_{\phi}(z)dz-\int\left[\ell(z;\theta)\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\right]p_{\phi}(z)dz$
$\displaystyle\qquad+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)^{2}\right]$
$\displaystyle=\frac{1}{\nabla_{\theta}\varphi(\theta)}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}[\nabla_{\theta}\ell(z;\theta)\left(T(Z)-\frac{\partial
A(\phi)}{\partial\phi}\right)]$
$\displaystyle\qquad-\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\right]$
$\displaystyle\qquad+\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)^{2}\right]$

Thus combining part (I) and part (II), we get:

$\displaystyle\nabla^{2}_{\phi}\operatorname{PR}(\theta,\phi)$
$\displaystyle=\underbrace{\left(\frac{1}{\nabla_{\theta}\varphi(\theta)}\right)^{2}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla^{2}_{\theta}\ell(z;\theta)\right]}_{\text{always}~{}\geq
0\text{if $\ell$ is strongly convex}}\\}$
$\displaystyle~{}~{}~{}~{}+\frac{2}{\nabla_{\theta}\varphi(\theta)}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)$
$\displaystyle~{}~{}~{}~{}-\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\right]$
$\displaystyle~{}~{}~{}~{}+\underbrace{\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)^{2}\right]}_{\text{always}~{}\geq 0}$

Thus a sufficient condition we need is:

$\displaystyle-$
$\displaystyle\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\right]$
$\displaystyle\qquad\qquad+\frac{2}{\nabla_{\theta}\varphi(\theta)}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)\geq 0$

$\displaystyle\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\ell(z;\theta)\right]$
$\displaystyle\leq$
$\displaystyle\frac{2}{\nabla_{\theta}\varphi(\theta)}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)\left(T(z)-\frac{\partial
A(\phi)}{\partial\phi}\right)\right]\right)$

Consider several different example distributions:

  * •

Poisson distribution:

$\displaystyle\phi$ $\displaystyle=\log\lambda$ $\displaystyle T(z)$
$\displaystyle=z$ $\displaystyle A(\phi)$ $\displaystyle=\lambda=e^{\phi}$

Thus we have

$\displaystyle\frac{\partial^{2}A(\phi)}{\partial\phi^{2}}=\lambda,T(z)-\frac{\partial
A(\phi)}{\partial\phi}=z-\lambda$

The above expression becomes:

$\displaystyle\lambda\operatorname{PR}(\theta)\leq\frac{2}{\varphi^{\prime}(\theta)}\left(\underset{z\sim\mathcal{D}(\varphi(\theta))}{\mathbb{E}}\left[\nabla_{\theta}\ell(z;\theta)(z-\lambda)\right]\right)$

##  Appendix G Additional Related Work

In this section, we provide additional related work in performative prediction
and a detailed comparison of our work and some closely related work.

#### Overview

Performative prediction is a new type of supervised learning problem in which
the underlying data distribution shifts in response to the deployed model [26,
2, 8, 14, 17, 20, 28, 24]. It is also called the _decision-dependent risk
minimization_ problem [20, 18, 33]. In particular, [26] first propose the
notion of the _performative risk_ defined as
$\mathsf{PR}(\theta):=\mathbb{E}_{z\sim\mathcal{D}(\theta)}[\ell(\theta;z)]$
where $\theta$ is the model parameter, and $\mathcal{D}(\theta)$ is the
induced distribution due to the deployment of $\theta$.

One of the major focuses of performative prediction is to find the optimal
model $\theta_{\textsf{OPT}}$ which achieves the minimum performative
prediction risk:
$\theta_{\textsf{OPT}}:=\operatorname*{\arg\\!\min}_{\theta\in\Theta}\mathsf{PR}(\theta)$,
or performative stable model $\theta_{\textsf{ST}}$, which is optimal under
its own induced distribution:
$\theta_{\textsf{ST}}:=\operatorname*{\arg\\!\min}_{\theta\in\Theta}\mathbb{E}_{z\sim\mathcal{D}(\theta_{\textsf{ST}})}[\ell(\theta;z)]$
. In particular, one way to find a performative stable model
$\theta_{\textsf{ST}}$ is to perform repeated retraining [26].

In order to get meaningful theoretical guarantees on any proposed algorithms,
works in this field generally require particular assumptions on the mapping
between the model parameter and its induced distribution (e.g., the smoothness
of the mapping), or requires multiple rounds of deployments and observing the
corresponding induced distributions, which can be costly in practice [15, 22].
A few recent works are on finding performative optimal solutions without
explicitly making the convexity assumption. For example, [7] does not
explicitly convexity assumption, but they focus on optimization heuristics
that are not guaranteed to minimize performative regret. below, we will
provide the discussions for three of them.

#### Comparison with [23]

[23] identifies _mixture dominance condition_ for any particular model
parameter pairs under which the performative risk is convexity. In particular,
they posit a simple distribution map in which
$\varphi(\theta)=\phi_{0}+M\theta$, where $M\in\mathbb{R}^{d_{\Phi}\times
d_{\Theta}}$ and $\phi_{0}\in\Phi$ is some “base” distribution parameter; in
other words, they assume that the data population reacts to a model by
shifting each of their features according to some linear transformation of the
model parameter. Their algorithm for this special case works in two stages:
first estimating $\varphi_{0}$ and $M$ by deploying random models; then, once
this distribution map has been accurately estimated, the performative loss is
convex in $\theta$, and can be optimized offline. The distribution map
estimation takes $O(d_{\Theta}/\epsilon)$ samples to obtain an
$\epsilon$-suboptimal model.

#### Comparison with [15]

For example, closely related is a recent paper that proposes using the
Lipschitz bandit approach to solve the performative prediction problem [15].
The major differences between this work and their work are: first, we define
the regret w.r.t $N$ rather than w.r.t $T$, which is a more realistic measure
in the performative prediction setting; second, their regret has exponential
dependency on the “zooming dimension” $d$ (which is roughly the model
parameter $d_{\Theta}$), while our dependency on the model and distribution
dimensions are both linear.

#### Comparison with [20]

Another closely related work is [20] uses zeroth-order methods for the convex-
concave minimax problem. Specifically, they proposed to formulate the
performative prediction problem as the _Wasserstein distributionally robust
learning with decision-dependent data_ problem, and further reduce it to a
constrained finite-dimensional smooth convex-concave min-max problem, and
propose a zeroth-order random reshuffling-based algorithm to solve the problem
without assuming any other structure on the curvature of the min-max loss.
Similar to ours, they also use the zeroth-order method to perform their
optimization procedure; different from ours, they approach the performative
prediction problem through the angle of robustness, which accounts for model
misspecification in their analysis.

#### Other Aspects of performative prediction

Also related are the recently developed lines of work on the _multiplayer_
version of the performative prediction problem [27, 25, 18, 10]. While
existing strategic classification and performative prediction problems focus
primarily on the interplay between a single learner and the population that
reacts to the learner’s actions, this line of work takes into account
competition from multi-learners, and develop performatively stable equilibria
and Nash equilibria of the game. Similarly, [33] confront multiple interactive
models in some dynamic environments. Another line of work is the economic
aspects of performative prediction [11, 21]. From the optimization aspect,
[32] focuses on the optimization aspect of finding the performative optimal
point and offers an online stochastic primal-dual algorithm for tracking
equilibrium trajectories. Also related is the recent development of the
concept called induced domain adaptation [3], whose primary focus is to study
the _transferability_ of a particular model trained primarily on the source
distribution and provide theoretical bounds on its performance on its induced
distribution, which is helpful in estimating the effect of a given classifier
when repeated retraining is unavailable.