# Stochastic optimization with decision-dependent distributions

Dmitriy Drusvyatskiy Department of Mathematics, University of Washington,
Seattle, WA 98195; www.math.washington.edu/$\scriptstyle\sim$ddrusv. Research
of Drusvyatskiy was supported by the NSF DMS 1651851 and CCF 1740551 awards.
Lin Xiao ††Part of this work was done when both authors were affiliated with
Microsoft Research. Facebook AI Research, Seattle, WA 98109. Email:
<EMAIL_ADDRESS>
###### Abstract

Stochastic optimization problems often involve data distributions that change
in reaction to the decision variables. This is the case for example when
members of the population respond to a deployed classifier by manipulating
their features so as to improve the likelihood of being positively labeled.
Recent works on performative prediction have identified an intriguing solution
concept for such problems: find the decision that is optimal with respect to
the static distribution that the decision induces. Continuing this line of
work, we show that typical stochastic algorithms—originally designed for
static problems—can be applied directly for finding such equilibria with
little loss in efficiency. The reason is simple to explain: the main
consequence of the distributional shift is that it corrupts the algorithms
with a bias that decays linearly with the distance to the solution. Using this
perspective, we obtain sharp convergence guarantees for popular algorithms,
such as stochastic gradient, clipped gradient, proximal point, and dual
averaging methods, along with their accelerated and proximal variants. In
realistic applications, deployment of a decision rule is often much more
expensive than sampling. We show how to modify the aforementioned algorithms
so as to maintain their sample efficiency while performing only
logarithmically many deployments.

##### Keywords:

stochastic optimization, distributional shift, Wasserstein distance,
performative prediction, stochastic gradient, proximal point method.

##  1 Introduction

Stochastic optimization plays a central role in statistical sciences and
large-scale data-driven computing. The goal of stochastic optimization in
these settings is to learn a decision rule (e.g. classifier) from a limited
data sample that generalizes well to the entire population. In simplest
circumstances, this task amounts to the optimization problem

$\mathtt{St}({\mathcal{P}}):\qquad\qquad\min_{x}~{}\operatorname*{\mathbb{E}}_{z\sim{\mathcal{P}}}\ell(x,z)+r(x).$
(1.1)

Here, $z$ encodes the population data, which is assumed to follow some fixed
probability distribution ${\mathcal{P}}$ that is accessible only through
sampling. The functions $\ell$ and $r$ play qualitatively different roles.
Typically, $\ell(x,z)$ evaluates the loss of the decision rule parametrized by
$x$ on a data point $z$. In contrast, the function $r\colon{\bf R}^{d}\to{\bf
R}\cup\\{\infty\\}$ models constraints or promotes some low-dimensional
structure in $x$, such as sparsity or low-rank. We refer to the problem (1.1)
as $\mathtt{St}({\mathcal{P}})$ to emphasize its dependence on the
distribution ${\mathcal{P}}$, while “$\mathtt{St}$” abbreviates “static”—a
term whose significance will become clear shortly.

Stochastic approximation algorithms are often the methods of choice for
$\mathtt{St}({\mathcal{P}})$. In every iteration $t=1,2,\ldots$, such methods
draw a fresh sample $z_{t}\in{\mathcal{P}}$ and update the iterate $x_{t}$
using the randomly selected function $\ell(\cdot,z_{t})$. Among such
algorithms, the stochastic proximal gradient method is the most popular; in
each iteration, the method simply takes a step from $x_{t}$ in the direction
opposite to the gradient $\nabla\ell(x_{t},z_{t})$, followed by a proximal
operation of $r$. Other common stochastic algorithms include proximal point,
clipped gradient, and dual averaging methods, along with their inertial
variants.

Convergence guarantees of stochastic optimization algorithms crucially rely on
the sampling distribution ${\mathcal{P}}$ being fixed throughout the run of an
algorithm. This assumption, however, is violated in applications where the
distribution evolves along the iterations. There are two main sources of such
distributional shifts. The first is temporal, where the distribution varies
slowly in time due to reasons that are independent of the iterates $x_{t}$.
This setting has been extensively studied in the machine learning literature;
see e.g.[25, 5, 4, 19, 10, 11]. The second common source is due to a feedback
mechanism, wherein the distribution generating the data in iteration $t$ may
depend on, or react to, the current “state” $x_{t}$. For example, deployment
of a classifier by a learning system, when made public, often causes the
population to adapt their attributes in order to increase the likelihood of
being positively labeled—a process called “gaming”. Even when the population
is agnostic to the classifier, the decisions made by the learning system (e.g.
loan approval) may inadvertently alter the profile of the population (e.g.
credit score). The goal of the learning system therefore is to find a
classifier that generalizes well under the response distribution. Recent
research in strategic classification [22, 12, 6, 14] and performative
prediction [36, 30] has highlighted the prevalence of this phenomenon.

Algorithms | Iterate update with $z_{t}\sim\mathcal{D}(x_{t})$
---|---
Proximal point | $\displaystyle x_{t+1}=\operatornamewithlimits{arg\,min}_{x}~{}\ell(x,z_{t})+r(x)+\frac{1}{2\eta_{t}}\|x-x_{t}\|^{2}$
Prox-gradient | $\displaystyle x_{t+1}={\rm prox}_{\eta_{t}r}\bigl{(}x_{t}-\eta_{t}\nabla\ell(x_{t},z_{t})\bigr{)}$
Accel. prox-grad. | $\left\\{\begin{aligned} x_{t}&={\rm prox}_{\eta_{t}r}\left(y_{t-1}-\eta_{t}\nabla\ell(y_{t-1},z_{t}^{\prime})\right)\\\ y_{t}&=x_{t}+\beta_{t}(x_{t}-x_{t-1})\end{aligned}\right\\}\quad\textrm{with }z_{t}^{\prime}\sim\mathcal{D}(y_{t-1})$
Clipped gradient | $\displaystyle x_{t+1}=\operatornamewithlimits{arg\,min}_{x}\,\bigl{(}\ell(x_{t},z_{t})+\langle\nabla\ell(x_{t},z_{t}),x-x_{t}\rangle\bigr{)}^{+}+r(x)+\frac{1}{2\eta_{t}}\|x-x_{t}\|^{2}$
Dual averaging | $\displaystyle x_{t+1}=\operatornamewithlimits{arg\,min}_{x}\Big{\langle}\frac{1}{t}\sum_{i=1}^{t}\nabla\ell(x_{t},z_{t}),x\Big{\rangle}+r(x)+\frac{1}{2\eta_{t}}\|x-x_{0}\|^{2}$
Table 1: Stochastic algorithms with state-dependent distributions.

###  1.1 Problem setting

The focus of this work is stochastic optimization under decision-dependent
distributions. Our approach to such problems builds on the framework of
“performative prediction” proposed in [36, 30]. Namely, we consider
optimization problems of the form

$\min_{x}~{}\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(x)}\ell(x,z)+r(x),$
(1.2)

where $\mathcal{D}(x)$ is a distribution indexed by the decision variable
$x\in{\bf R}^{d}$. In contrast to $\mathtt{St}({\mathcal{P}})$ in (1.1), the
data distribution is now decision-dependent. Thus, the quality of a decision
rule $x$ is judged by its performance according to the induced distribution
$\mathcal{D}(x)$. A direct solution of (1.2) is out of reach in general, even
for convex loss functions. Nonetheless, an appealing and widely used heuristic
for such problems is to apply standard stochastic optimization algorithms to
the static problem $\mathtt{St}(\mathcal{D}(x_{t}))$ for one or more
iterations, then update the distribution $\mathcal{D}(x_{t+1})$ based on the
generated iterates, and repeat. Motivated by the recent works [36, 30], we ask
the following question:

> What can one expect from standard stochastic algorithms (Table 1) when the
> sampling distribution $\mathcal{D}(x_{t})$ used in iteration $t$ depends on
> the iterate $x_{t}$?

The answer we present relies on a certain distinguished point $\bar{x}$,
highlighted in [36, 30]. A point $\bar{x}$ is at equilibrium for the family of
distributions $\mathcal{D}(x)$ if $\bar{x}$ solves the static problem
$\mathtt{St}({\mathcal{P}})$ with ${\mathcal{P}}=\mathcal{D}(\bar{x})$. Thus
$\bar{x}$ is at equilibrium if it solves the static problem that the
distribution $\mathcal{D}(\bar{x})$ induces. Equilibrium points are sure to
exist under mild continuity and convexity assumptions [36]. Our main
contribution can be summarized as follows:

> Under mild conditions, stochastic optimization algorithms that sample
> according to a state-dependent distribution $\mathcal{D}(x_{t})$ can be
> viewed as inexact analogues of the same algorithms applied to the static
> problem $\mathtt{St}(\mathcal{D}(\bar{x}))$. The inexactness manifests in a
> bias/error that decays linearly as one approaches $\bar{x}$.

Thus, stochastic optimization algorithms under decision-dependent
distributions automatically search for the equilibrium point $\bar{x}$ by
implicitly solving the problem $\mathtt{St}(\mathcal{D}(\bar{x}))$. The
strength of the distribution’s dependence on the state—measured by the
Lipschitz constant of the map $\mathcal{D}(\cdot)$—directly impacts the decay
rate in the bias/error. We show therefore that if the state dependence is
sufficiently weak, standard stochastic algorithms (Table 1) exhibit the same
efficiency estimates as if they were directly applied to the static problem
$\mathtt{St}(\mathcal{D}(\bar{x}))$—an a priori impossible task, since the
distribution $\mathcal{D}(\bar{x})$ is unknown and inaccessible.

###  1.2 Illustrative application: strategic classification

An important application arena for the developed techniques is the framework
of _strategic classification_ [22, 31]. This problem class can model a variety
of settings with state-dependent distributions, such as fraud detection,
traffic prediction, spam filtering, and service recommendations. See [43] and
[36, Appendix B] for detailed applications.

Strategic classification is a two player game between an “institution” that
deploys a classifier and a population of “agents” who can adapt their features
in response in order to increase their likelihood of being positively
classified. The game proceeds as an iterative process where the institution
and the population take turns to adjust the classifier and features
respectively. Specifically, let $z=(a,b)$ denote the features-label pairs of
the population that follow a base distribution $z\sim{\mathcal{P}}$. The
institution begins the game by deploying a classifier $h_{x}$, parametrized by
$x\in{\bf R}^{d}$, and learned from data sampled from ${\mathcal{P}}$. Each
agent responds to the classifier $h_{x}$ by greedily modifying their features
$a$ to increase their chance of being favorably labeled:

$\Delta(h_{x},a):=\operatornamewithlimits{arg\,max}_{a^{\prime}}\bigl{\\{}u(h_{x},a^{\prime})-c(a,a^{\prime})\bigr{\\}}.$
(1.3)

Here $u(\cdot,\cdot)$ is some utility function and $c(\cdot,\cdot)$ is the
cost of altering the features. Thus the samples available to the institution
$(\Delta(h_{x},a),b)$ in the next stage of the game follow a distribution that
depends on $x$, and which we denote by $(\Delta,b)\sim\mathcal{D}(x)$. The
goal of the institution is to find the decision variable $x$ that minimizes
the classification error with respect to the response distribution:

$\operatorname*{\text{{Pr}}}_{(\Delta,b)\sim\mathcal{D}(x)}[h_{x}(\Delta)\neq
b]~{}=~{}\operatorname*{\mathbb{E}}_{(\Delta,b)\sim\mathcal{D}(x)}[\mathbf{1}(h_{x}(\Delta)\neq
b].$

In practice, one often replaces the $0/1$ loss $\mathbf{1}(\cdot)$ with a
convex surrogate $\ell(x,z)$, such as the logistic loss, to facilitate large-
scale optimization. Thus the problem of strategic classification is an
instance of (1.2) under a specific family of distributions $\mathcal{D}(x)$.

In practice, the agents are unlikely to actually play the best-response
solutions when modifying their features or that the utility and cost functions
are common to all agents. Moreover, in some cases, the dependence of the
distribution on the state can be passive; for example, when a bank uses a
classifier to approve loan applications, the credit scores of the population
are automatically impacted for downstream tasks, even in absence of feature
manipulation. In line with the recent works [36, 30], we do not restrict to
the model of strategic classification, and instead only require the
distribution map $\mathcal{D}(\cdot)$ to have a relatively small Lipschitz
constant.

###  1.3 Related work

Our work is closely related to a number of research themes in optimization,
statistics, and machine learning. We now highlight these relationships.

Performative prediction and distributional shift. The two seminal papers on
performative prediction [36, 30] motivate and guide much of our work. In
particular, the problem setting and assumptions we use (Section 3) are
identical to that of [36, 30]. “Performative prediction” is an evocative name
for the problem class in machine learning settings since it nicely contrasts
the problem class with supervised learning. To stay consistent with the
stochastic optimization literature, however, we do not use this terminology
here and instead refer to the qualifier “decision-dependent distributions”
when needed.

The earlier paper [36] introduces the notion of an equilibrium point (therein
called “performatively stable”) and identified regimes in which retraining and
gradient descent algorithms converge linearly. The follow up paper [30], in
turn, analyzes two variants of the projected stochastic gradient method
(called greedy and lazy). Our current work complements [36, 30], aiming to
provide a systematic and transparent treatment. The convergence guarantees we
develop apply for a wide class of stochastic algorithms, including stochastic
gradient, clipped gradient, proximal point, and dual averaging methods, along
with their accelerated and proximal variants. Comments and comparisons with
[36, 30] appear throughout the text. Aside from performative prediction, there
is a long history of problems with distributional shift in machine learning,
whether due to time drift (e.g. [25, 5, 4, 19, 10, 11]) or deployment of
classifiers (e.g. [22, 12, 6, 14]. We believe that the techniques developed
here may be useful in these contexts as well.

Convex stochastic optimization. Many of the techniques used here are rooted in
convex optimization; recent monographs on the subject include [8, 13, 35]. The
arguments we present are most closely related to the literature on
(accelerated) stochastic gradient methods [26, 20], dual averaging [34, 41],
and model-based minimization [2, 15].

Online convex optimization. Online convex optimization is a more general
framework than stochastic convex optimization in the sense that the loss
function at each iteration need not follow any probability distribution and
can even be adversarial. On the other hand, online convex optimization
requires stronger assumptions such as bounded domain and gradients; see, e.g.,
[42, 39, 23]. Under these conditions, any online convex optimization algorithm
can be applied to static stochastic optimization problems. Similarly, we show
by a simple reduction that any online algorithm can be applied to stochastic
optimization problems with state-dependent distributions.

Error and bias in gradient oracles. Biased stochastic gradients play a central
role in this work. There is a vast literature on errors/bias in gradient
computations. For example, [16, 18, 40] analyze first-order methods under
inexact oracles and discuss convergence rates. The bias that appears in the
current work is fundamentally different, however, in that it decays linearly
with the distance to the solution. The closest error model we are aware of is
based on relative errors in the gradient (e.g. [9, Section 1.2.1] and [1]).
The bias we encounter is more restrictive still and therefore facilitates
stronger guarantees.

###  1.4 Outline of the paper

The outline of the rest of the paper is as follows. Section 2 presents two
fundamental lemmas that characterize the sensitivity of the expected loss
function and its gradient to arbitrary distributional shift. Section 3
formalizes the assumptions that we will use throughout the paper, in
particular emphasizing Lipschitz continuity of the distributions relative to
variations in the decision variables. Section 4 outlines the main results and
previews technical contributions—formally developed in Sections 5-9,

The main technical content appears in Sections 5-9. Section 5 analyzes several
conceptual algorithms (that require evaluation of the full expectation during
each iteration) through two key properties: calmness with respect to
distributional shift and contraction under a fixed distribution. Section 6
reduces stochastic optimization problems under state-dependent distributions
to the framework of online convex optimization and derives convergence rates
for the projected stochastic gradient and the regularized dual averaging
methods. Section 7 presents convergence analysis for the stochastic proximal
gradient method and an accelerated variant under state-dependent
distributions. Section 8 presents convergence analysis of stochastic model-
based algorithms, including the proximal point and clipped gradient variants.
In Section 9, we consider settings where deployment of a decision rule is much
more expensive than sampling. We show how to modify the aforementioned
algorithms so as to maintain their sample efficiency while performing only
logarithmically many deployments.

##### Notation.

Throughout, we consider a Euclidean space, denoted for simplicity as ${\bf
R}^{d}$. The symbol $\langle\cdot,\cdot\rangle$ will denote the inner product
in ${\bf R}^{d}$, while $\|x\|=\sqrt{\langle x,x\rangle}$ will denote the
induced norm. The proximal map of any function $f\colon{\bf R}^{d}\to{\bf
R}\cup\\{\infty\\}$ is defined as

${\rm prox}_{\eta
f}(x)=\operatornamewithlimits{arg\,min}_{y}\,\Bigl{\\{}f(y)+\tfrac{1}{2\eta}\|y-x\|^{2}\Bigr{\\}},$

where $\eta>0$ is an arbitrary constant.

We will be interested in random variables taking values in a metric space.
Therefore, throughout the paper, we fix a metric space ${Z}$ with metric
$d(\cdot,\cdot)$ and equip ${Z}$ with the Borel $\sigma$-algebra. The symbol
$\mathbb{P}$ will denote the set of Radon probability measures on ${Z}$ with a
finite first moment
$\operatorname*{\mathbb{E}}_{z\sim{\mathcal{P}}}[d(z,z_{0})]<\infty$ for some
$z_{0}\in Z$. We measure the deviation between two measures
$\mu,\nu\in\mathbb{P}$ using the Wasserstein-1 distance:

$W_{1}(\mu,\nu)=\sup_{g\in{\rm
Lip}_{1}}\,\bigl{\\{}{\mathbb{E}}_{X\sim\mu}[g(X)]-{\mathbb{E}}_{Y\sim\nu}[g(Y)]\bigr{\\}},$

where ${\rm Lip}_{1}$ denotes the set of $1$-Lipschitz continuous functions
$g\colon{Z}\to{\bf R}$. The equivalence of this definition with the
description of $W_{1}(\mu,\nu)$ using couplings is the Kantorovich-Rubinstein
duality theorem [24].

Throughout the paper, we fix an arbitrary function $r\colon{\bf R}^{d}\to{\bf
R}\cup\\{\infty\\}$ and a loss function $\ell\colon{\bf R}^{d}\times Z\to{\bf
R}$. The symbol $\nabla\ell(x,z)$ will always refer to the gradient of
$\ell(x,z)$ in the variable $x$. Throughout the paper, we impose the following
assumption.

######  Assumption 1 (Smoothness).

The loss $\ell(x,z)$ is $C^{1}$-smooth in $x$ for all $z\in Z$, and the map
$z\mapsto\nabla\ell(x,z)$ is $\beta$-Lipschitz continuous for any $x\in{\bf
R}^{d}$.

An important consequence (following from the dominated convergence theorem) is
that for any measure $\mu\in\mathbb{P}$, the expected loss
$\operatorname*{\mathbb{E}}_{z\sim\mu}\ell(x,z)$ is differentiable in $x$ with
gradient $\operatorname*{\mathbb{E}}_{z\sim\mu}[\nabla\ell(x,z)]$.

##  2 Sensitivity to distributional shift

Optimization algorithms that rely on state-dependent sampling, in essence,
perform updates on a sequence of static problems that slowly vary along the
iterations. An appealing strategy for analyzing such algorithms—and the one we
follow here—leverages the stability of the problem
$\mathtt{St}({\mathcal{P}})$ to perturbations in ${\mathcal{P}}$. Formalizing
this viewpoint, define the expected loss

$f_{\mu}(x):=\operatorname*{\mathbb{E}}_{z\sim\mu}\ell(x,z),$

for any measure $\mu\in\mathbb{P}$. The main question we aim to answer in this
section is how variations in $\mu\in\mathbb{P}$ impact the function $f_{\mu}$
and its gradient $\nabla f_{\mu}$. The two Lemmas 2.1 and 2.2 provide the
answer that guides much of our development.

We begin with Lemma 2.1, which shows that the distance $W_{1}(\mu,\nu)$
between two measures $\mu,\nu\in\mathbb{P}$ uniformly bounds the deviation
$\nabla f_{\mu}(x)-\nabla f_{\nu}(x)$. This result is well-known and widely
used; we provide a short proof for completeness.

######  Lemma 2.1 (Gradient deviation).

Under Assumption 1, all measures $\mu,\nu\in\mathbb{P}$ satisfy:

$\sup_{x\in{\bf R}^{d}}\|\nabla f_{\mu}(x)-\nabla f_{\nu}(x)\|\leq\beta\cdot
W_{1}(\mu,\nu).$ (2.1)

###### Proof.

Fix a unit vector $v\in{\bf R}^{d}$ and define the function
$g(z):=v^{T}\nabla\ell(x,z)$. Clearly by Assumption 1, $g$ is
$\beta$-Lipschitz continuous in $z$ and therefore we deduce

$v^{T}(\nabla f_{\mu}(x)-\nabla
f_{\nu}(x))={\mathbb{E}}_{z\sim\mu}g(z)-{\mathbb{E}}_{z\sim\nu}g(z)\leq\beta\cdot
W_{1}(\mu,\nu).$

Taking the supremum over unit vectors $v$ yields the result. ∎

Similarly, it is tempting to use the distance $W_{1}(\mu,\nu)$ to linearly
bound the functional error $|f_{\mu}(x)-f_{\nu}(x)|$; such an estimate,
however, is far too crude for analyzing algorithms. Instead, the key insight
is that convergence analysis of algorithms does not rely on function values in
absolute terms, but rather on their differences. The following lemma provides
a multiplicative bound on the error in the function gaps
$\Delta_{\mu}(x,y):=f_{\mu}(x)-f_{\mu}(y)$.

######  Lemma 2.2 (Function gap deviation).

Under Assumption 1, all points $x,y\in{\bf R}^{d}$ and measures
$\mu,\nu\in\mathbb{P}$ satisfy:

$\Delta_{\mu}(x,y)-\Delta_{\nu}(x,y)\leq\beta\cdot\|y-x\|\cdot
W_{1}(\mu,\nu).$ (2.2)

###### Proof.

Fix two points $x,y\in{\bf R}^{d}$. For any $s\in[0,1]$, set
$x_{s}:=x+s(y-x)$. The fundamental theorem of calculus allows to write

$\displaystyle f_{\mu}(y)-f_{\mu}(x)=\int_{0}^{1}\langle\nabla
f_{\mu}(x_{s}),y-x\rangle~{}ds\quad\textrm{and}\quad
f_{\nu}(y)-f_{\nu}(x)=\int_{0}^{1}\langle\nabla
f_{\nu}(x_{s}),y-x\rangle~{}ds.$

Subtracting the two estimates yields

$\displaystyle|[f_{\mu}(y)-f_{\mu}(x)]-[f_{\nu}(y)-f_{\nu}(x)]|$
$\displaystyle=\left|\int_{0}^{1}\langle\nabla f_{\mu}(x_{s})-\nabla
f_{\nu}(x_{s}),y-x\rangle~{}ds\right|$
$\displaystyle\leq\|y-x\|\cdot\int_{0}^{1}\|\nabla f_{\mu}(x_{s})-\nabla
f_{\nu}(x_{s})\|~{}ds$ (2.3) $\displaystyle\leq\beta\cdot\|y-x\|\cdot
W_{1}(\mu,\nu),$ (2.4)

where (2.3) follows from Cauchy–Schwarz and (2.4) follows from Lemma 2.1. ∎

Importantly, the right side of (2.2) is proportional to the product
$\|y-x\|\cdot W_{1}(\mu,\nu)$. In particular, if the distance $W_{1}(\mu,\nu)$
is on the order of $\|y-x\|$—the setting we will pass to shortly—then the
right-side is proportional to the quadratic error $\|y-x\|^{2}$. Both Lemmas
2.1 and 2.2 will play a central role in the later sections.

##  3 Assumptions under state-dependent sampling

We next record the assumptions that we will use to analyze stochastic
optimization under state-dependent distributions—the main content of the work.
The imposed conditions are identical to those used in the seminal work [36].

Consider a family of probability measures $\mathcal{D}(x)\in\mathbb{P}$
indexed by $x\in{\bf R}^{d}$. It is instructive throughout the discussion to
keep in mind the corresponding problem (1.2). The first assumption asserts
Lipschitz control on the assignment $x\mapsto\mathcal{D}(x)$.

######  Assumption 2 (Lipschitz distributions).

There exists $\gamma>0$ satisfying

$W_{1}(\mathcal{D}(x),\mathcal{D}(y))\leq\gamma\cdot\|x-y\|\qquad\textrm{ for
all }x,y\in{\bf R}^{d}.$

As an example, consider the framework of strategic classification in Section
1.2. If the agents employ a linear utility function $u(x,a)=\langle
x,a\rangle$ and a quadratic cost for modifying the features
$c(a,a^{\prime})=\frac{1}{2\gamma}\|a-a^{\prime}\|^{2}$, then
$W_{1}(\mathcal{D}(x),\mathcal{D}(y))\leq\gamma\|x-y\|$; see [36, Appendix G].

The Lipschitz condition on the distribution map $\mathcal{D}(\cdot)$, recorded
in Assumption 2, quantifies how far the map is away from being constant—the
strength of the state-dependence. The guarantees of Lemmas 2.1 and 2.2 become
especially potent under Assumption 2. We record them in Corollary 3.1, and
will use it often. To simplify the exposition, we introduce the notation

$f_{x}(y):=\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(x)}\ell(y,z)\qquad\textrm{and}\qquad\nabla
f_{x}(y):=\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(x)}\nabla\ell(y,z).$

Note that in light of Section 2, we may equivalently write
$f_{x}(y)=f_{\mathcal{D}(x)}(y)$. Observe also that $\nabla f_{x}(x)$ is the
gradient of the function $y\mapsto f_{x}(y)$ evaluated at $y=x$.

######  Corollary 3.1 (Gradient and function gap deviations).

Suppose Assumptions 1 and 2 hold. Then for all points $x,y,u,v\in{\bf R}^{d}$
the estimates hold:

$\displaystyle\sup_{w\in{\bf R}^{d}}~{}\|\nabla f_{x}(w)-\nabla f_{y}(w)\|$
$\displaystyle\leq\gamma\beta\cdot\|x-y\|,$ (3.1)
$\displaystyle|\left(f_{x}(u)-f_{x}(v)\right)-\left(f_{y}(u)-f_{y}(v)\right)|$
$\displaystyle\leq\gamma\beta\cdot\|x-y\|\cdot\|u-v\|.$ (3.2)

We will see that a variety of algorithms with state-dependent sampling are
implicitly solving a certain static problem that is at “equilibrium”. A formal
description of this phenomenon relies on the notion of an equilibrium point
from [36].

######  Definition 3.2 (Equilibrium point).

A point $\bar{x}\in{\bf R}^{d}$ is at equilibrium with respect to
$\mathcal{D}(\cdot)$ if $\bar{x}$ solves the static problem
$\mathtt{St}(\mathcal{D}(\bar{x}))$, or equivalently

$\bar{x}\in\operatornamewithlimits{arg\,min}_{x}\,\bigl{\\{}f_{\bar{x}}(x)+r(x)\bigr{\\}}.$

Thus a point $\bar{x}$ is at equilibrium with respect to $\mathcal{D}(\cdot)$
if $\bar{x}$ solves the static problem that it entails. In the context of
strategic classification, the decision variable $\bar{x}$ is at equilibrium if
the institution has no incentive to deploy another classifier based purely on
the population’s response to $\bar{x}$. Equilibrium points are distinct from
minimizers of (1.2) in general, though the distance between the two can be
bounded under strong convexity assumptions [36, Theorem 4.3].

Observe that equilibrium points are precisely the fixed points of the repeated
minimization procedure

$x_{t+1}=\operatornamewithlimits{arg\,min}_{x}\,\bigl{\\{}f_{x_{t}}(x)+r(x)\bigr{\\}}.$
(3.3)

This algorithm is largely conceptual since it requires access to the entire
data set (to evaluate the expectation) in every iteration. Nonetheless, such
“retraining heuristics” are ubiquitous in practice for recovering from
distributional shifts, regardless of their origin. Repeated minimization will
play an important role in later sections.

Equilibrium points are sure to exist under fairly weak assumptions. The
following two sufficient conditions were proved in Theorem 3.5 and Proposition
4.1 of [36], respectively.

######  Proposition 3.3 (Existence of equilibrium points).

The family of distributions $\mathcal{D}(\cdot)$ is sure to admit an
equilibrium point under either of the two conditions:

  1. (a)

Assumptions 1 and 2 hold and the functions $f_{x}$ are $\alpha$-strongly
convex for all $x\in{\bf R}^{d}$ with $\frac{\gamma\beta}{\alpha}<1$.
Moreover, in this case, the equilibrium point is unique.

  2. (b)

The loss $\ell(x,z)$ is jointly continuous in $(x,z)$ and convex in $x$, the
distribution map $\mathcal{D}(\cdot)$ is continuous, and the domain of $r$ is
compact.

In light of Proposition 3.3, we make the blanket assumption throughout:

> _The family of distributions $\mathcal{D}(\cdot)$ admits an equilibrium
> point, denoted by $\bar{x}$._

The final two ingredients are assumptions on strong convexity and smoothness:
we will use three variants of the former and two variants of the latter
depending on context.

######  Assumption 3 (Strong convexity).

The regularizer $r$ is convex and there exists $\alpha>0$ satisfying one of
the following three properties:

  1. (a)

$f_{\bar{x}}$ is $\alpha$-strongly convex,

  2. (b)

$f_{x}$ is $\alpha$-strongly convex for all $x\in{\bf R}^{d}$,

  3. (c)

the loss function $\ell(\cdot,z)$ is $\alpha$-strongly convex for all $z\in
Z$.

In this case, define the ratio $\rho:=\frac{\gamma\beta}{\alpha}$.

Clearly, the implications
$\ref{it:str_conv_loss}\Rightarrow\ref{it:str_conv_uniform}\Rightarrow\ref{it:str_conv1}$
hold in Assumption 3. We will see that the constant
$\rho=\frac{\gamma\beta}{\alpha}$ sharply characterizes the regime of
convergence of basic stochastic algorithms with state-dependent sampling.

######  Assumption 4 (Smoothness).

There exists $L>0$ satisfying one of the following:

  1. (a)

$\nabla f_{\bar{x}}$ is $L$-Lipschitz continuous,

  2. (b)

$\nabla f_{x}$ is $L$-Lipschitz continuous for all $x\in{\bf R}^{d}$.

If in addition either of Assumptions 3(a)-(c) hold, define the condition
number $\kappa:=\frac{L}{\alpha}$.

###  3.1 The interesting parameter regime $\rho<1$

The proof of Proposition 3.3(a), presented in [36, Theorem 3.5], is
particularly instructive algorithmically. Namely, observe that repeated
minimization (3.3) is a fixed point iteration of the map
$S(x):=\operatornamewithlimits{arg\,min}_{y}\\{f_{x}(y)+r(y)\\}$. The authors
of [36] show that $S$ is Lipschitz continuous with parameter $\rho$.
Consequently, in the regime $\rho<1$, the map $S$ is a contraction and has a
fixed point, which by definition is at equilibrium relative to
$\mathcal{D}(\cdot)$. Conversely, they show in the same paper that repeated
minimization can easily diverge if $\rho\geq 1$. In this sense, the parameter
regime $\rho<1$ is the natural setting for analyzing algorithms under state-
dependent distributions. In this work, we aim to show that in the setting
$\rho<1$, typical stochastic algorithms (Table 1) implicitly solve the static
problem $\mathtt{St}(\mathcal{D}(\bar{x}))$, where $\bar{x}$ is an equilibrium
point. We end the section with an illuminating informal argument supporting
this claim for the stochastic gradient method. The precise argument appears in
Section 7.

Suppose that Assumptions 1, 2, 3(a), 4(a) hold. In each iteration, the
stochastic gradient method draws a sample $z_{t}\sim\mathcal{D}(x_{t})$ and
uses $\nabla\ell(x_{t},z_{t})$ to advance. Clearly $\nabla\ell(x_{t},z_{t})$
is an unbiased estimator of $\nabla f_{x_{t}}(x_{t})$ but is biased with
respect to the true gradient $\nabla f_{\bar{x}}(x_{t})$. The estimate (3.1)
directly bounds the bias $\|\nabla f_{x}(x)-\nabla f_{\bar{x}}(x)\|$, which
combined with strong convexity, yields the relative error guarantee:

$\|\nabla f_{x}(x)-\nabla f_{\bar{x}}(x)\|\leq\rho\cdot\|\nabla
f_{\bar{x}}(x)\|.$ (3.4)

A simple consequence is that in the regime $\rho<1$, the two vectors $\nabla
f_{x}(x)$ and $\nabla f_{\bar{x}}(x)$ are well-aligned in the sense that they
span an angle with cosine $\sqrt{1-\rho}$. Therefore, in this parameter
regime, numerical methods that use unbiased estimators of $\nabla f_{x}(x)$
are effectively solving the static problem $\mathtt{St}(\mathcal{D}(\bar{x}))$
using biased gradients. This intuition is indeed correct in the setting $r=0$.
When regularization and/or constraints are present, the estimate (3.4) is not
useful because the right-hand side might be uniformly bounded away from zero.
Instead, our arguments in Section 7 will use (3.1) directly.

##  4 Outline of the main results

This section outlines the main results of this work. Throughout, the reader
should keep in mind the running theme of the paper: a variety of stochastic
algorithms under state-dependent distributions are implicitly solving the
static problem $\texttt{St}(\mathcal{D}(\bar{x}))$, where $\bar{x}$ is the
equilibrium point. We impose Assumptions 1, 2, 3(c), 4(b) throughout the
section. Define the objective function of the static problems
$\texttt{St}(\mathcal{D}(x))$ as

$\min_{y}~{}\varphi_{x}(y):=f_{x}(y)+r(y).$

To shorten the notation, we drop the subscript $\bar{x}$ from
$\varphi_{\bar{x}}$ and set $\varphi:=\varphi_{\bar{x}}$.

###  4.1 Calm and contractive algorithms (Section 5)

We begin the algorithmic development by analyzing a number of conceptual
algorithms under state-dependent distributions, the most important of which is
repeated minimization (3.3). More generally, the classical proximal point and
gradient methods extend to the state-dependent setting as follows:

(Proximal point) |  $\displaystyle x_{t+1}=\operatornamewithlimits{arg\,min}_{x}\,\Bigl{\\{}f_{x_{t}}(x)+r(x)+\frac{1}{2\eta}\|x-x_{t}\|^{2}\Bigr{\\}}$,
---|---
(Proximal gradient) |  $\displaystyle x_{t+1}={\rm prox}_{\eta r}(x_{t}-\eta\nabla f_{x_{t}}(x_{t}))$,

where $\eta>0$ is a user-specified step size. Thus in each iteration $t$, the
two algorithms simply take a proximal point step and a proximal gradient step,
respectively, on the static problem $\texttt{St}(\mathcal{D}(x_{t}))$. The
proximal point method in the extreme case $\eta=\infty$ coincides with
repeated minimization (3.3). Setting notation, let us denote either of these
updates as $x_{t+1}=S_{x_{t}}(x_{t})$; more generally, the symbol $S_{y}(x)$
will denote the update of a point $x$ by an algorithm acting on the static
problem $\mathtt{St}(\mathcal{D}(y))$.

The paper [36] showed that when $r$ is the indicator function of a closed
convex set and $\rho<1$, repeated minimization and the projected gradient
method converge linearly to the equilibrium point $\bar{x}$. Section 5
provides an alternative and transparent explanation based on stability to
distributional shifts. Namely, linear convergence is a direct consequence of
the two independent phenomenon:

  1. 1.

(Calmness to distribution) The updates $S_{y}(x)$ are $\tau$-calm relative to
$\mathcal{D}(\bar{x})$, meaning there exists $\tau>0$ satisfying
$\displaystyle\sup_{x}\|S_{y}(x)-S_{\bar{x}}(x)\|\leq\tau\cdot
W_{1}(\mathcal{D}(y),\mathcal{D}(\bar{x}))$ for all $y\in{\bf R}^{d}$.

  2. 2.

(Contraction at equilibrium) The updates $S_{\bar{x}}(\cdot)$ are
$q$-contractive on the static problem $\mathtt{St}(\mathcal{D}(\bar{x}))$,
meaning $\|S_{\bar{x}}(x)-S_{\bar{x}}(y)\|\leq q\cdot\|x-y\|$ for all
$x,y\in{\bf R}^{d}$.

The first property asserts control on how the algorithm $S_{y}(x)$ varies with
respect to the distribution $\mathcal{D}(y)$, while the contraction property
asserts that the algorithm is contractive when applied to the static problem
induced by $\mathcal{D}(\bar{x})$. It is elementary to see that these two
conditions imply that the update $x\mapsto S_{x}(x)$ contracts towards
$\bar{x}$ with ratio $q+\gamma\tau$. By computing the calmness and contraction
parameters for different algorithms (in terms of $\rho>0$), we obtain the
following theorem.

######  Theorem 4.1 (Informal).

Repeated minimization and proximal point methods converge linearly to
$\bar{x}$ in the regime $\rho<1$, while the proximal gradient method converges
linearly to $\bar{x}$ in the regime $\rho<\frac{1}{2}$. (A more careful
argument in Section 7 shows that the proximal gradient method converges
linearly in the optimal regime $\rho<1$.)

The three algorithms described so far are largely conceptual since they
require access to the entire data set in every iteration. Implementable
algorithms under state-dependent distributions fall into two categories—those
that update the sampling distribution in every step and those that run
multiple iterations of stochastic methods on the current static problem before
updating the sampling distribution. The former algorithms are called “greedy”
and the latter are called “lazy” in [30]. Clearly, lazy algorithms can be
interpreted as performing inexact repeated minimization. Such algorithms can
be advantageous in applications where the action of updating the distribution
is much costlier than sampling from the currently available distribution. For
example, this is the case in applications where it takes significant amount of
time for the population to adjust to a newly unveiled learning rule.

We analyze both types of algorithms in this work. Most of the paper, however,
focuses on greedy algorithms while inexact repeated minimization is deferred
to Section 9. Though the two types of methods generate entirely different
trajectories, the convergence arguments we present are small modifications of
each other—thereby underscoring the utility of the developed techniques.

###  4.2 Reduction to online convex optimization (Section 6)

We begin by showing that virtually any algorithm developed for “online convex
optimization” can be used to find the equilibrium point $\bar{x}$ in the
stochastic setting under state-dependent distributions. The framework of
online convex optimization can be interpreted as a repeated game (e.g., [42,
39, 23]). At each round $t$, the player chooses a point
$x_{t}\in\operatorname*{dom\,}r$, then a convex cost function $\ell_{t}$ is
revealed and the player incurs the cost $\ell_{t}(x_{t})$. The goal of the
player is to minimize the regret

$R_{t}:=\sum_{i=1}^{t}\bigl{(}\ell_{i}(x_{i})+r(x_{i})\bigr{)}-\min_{x}\sum_{i=1}^{t}\bigl{(}\ell_{i}(x)+r(x)\bigr{)},$

which is simply the difference between the total regularized cost incurred up
to round $t$ and the minimum regularized cost in hindsight. Typical algorithms
for online convex optimization are the proximal gradient [17], dual averaging
[41], and variants of FTRL (Follow-The-Regularized-Leader) methods [29].
Importantly, under various Lipschitz and strong convexity assumptions, the
regret $R_{t}$ scales as $\mathcal{O}(\log{t})$. We establish the following
reduction by leveraging the gap deviation inequality (3.2).

######  Theorem 4.2 (Informal).

Suppose that we are in the regime $\rho<\frac{1}{2}$. Then any online
algorithm with regret $R_{t}=\mathcal{O}(\log t)$ can be used under state-
dependent distributions by declaring $\ell_{i}(x_{i})=\ell(x_{i},z_{i})$ with
$z_{i}\sim\mathcal{D}(x_{i})$ in each iteration. Then the average iterate
$\hat{x}_{t}:=\frac{1}{t}\sum_{i=1}^{t}x_{i}$ satisfies

${\mathbb{E}}[\varphi(\hat{x}_{t})-\varphi(\bar{x})]~{}\leq~{}\mathcal{O}\left(\frac{\log
t}{(1-2\rho)\,t}\right),\qquad\textrm{for all }t\geq 0.$

In particular, known regret bounds for the proximal gradient, regularized dual
averaging, and FTRL algorithms directly yield a converge rate
$\mathcal{O}(\log(t)/(1-2\rho)t)$ under state-dependent sampling. Though the
theorem is attractive in its generality, it is far from satisfactory. Indeed,
the framework of online convex optimization is far more general than
stochastic optimization, since the loss function $\ell_{t}$ at each iteration
may not follow any probability distribution and can even be adversarial. As a
consequence, online convex optimization requires stringent assumptions in
order to have meaningful regret analysis, most notably boundedness of the
encountered gradients of the loss functions and bounded of
$\operatorname*{dom\,}r$. Moreover smoothness of the loss function does not
play a significant role.

We will see that much finer convergence guarantees hold for stochastic
optimization under state-dependent distributions. In particular, bounds on the
gradient of the loss will be replaced by the finite variance assumption.

######  Assumption 5 (Finite variance).

There is a constant $\sigma>0$ satisfying

${\mathbb{E}}_{z\sim\mathcal{D}(x)}\|\nabla\ell(x,z)-\nabla
f_{x}(x)\|^{2}\leq\sigma^{2}\qquad\forall x\in\operatorname*{dom\,}r.$

###  4.3 Stochastic gradient methods (Section 7)

The simplest and most widely used stochastic algorithm is the stochastic
gradient method. We begin by investigating its extension under state-dependent
distributions:

$\mathrm{SG:}\qquad\left\\{\quad\begin{aligned}
&\textrm{Sample~{}}z_{t}\sim\mathcal{D}(x_{t})\textrm{ and set
}g_{t}=\nabla\ell(x_{t},z_{t}),\\\ &\textrm{Set~{}}x_{t+1}={\rm
prox}_{\eta_{t}r}(x_{t}-\eta_{t}g_{t}).\end{aligned}\quad\right\\}$ (4.1)

Rather than reducing the method SG to online convex optimization, as mentioned
previously, we will analyze it directly. Observe that contrary to the static
setting, the vector $g_{t}$ is a biased estimator for the true gradient
$\nabla f_{\bar{x}}(x_{t})$, where the bias is proportional to
$\|x_{t}-\bar{x}\|$; recall the gradient deviation inequality (3.1). We will
prove the following.

######  Lemma 4.3 (Key recursion).

Suppose that the step-size sequence satisfies $\eta_{t}<\frac{1}{2L}$. Then
the iterates $\\{x_{t}\\}$ generated by the SG Algorithm in (4.1) satisfy

$\displaystyle 2\eta_{t}{\mathbb{E}}[\varphi(x_{t+1})-\varphi(\bar{x})]$
$\displaystyle\leq\left(1-\alpha(1-2\rho)\eta_{t}+2\gamma^{2}\beta^{2}\eta_{t}^{2}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}-{\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}+2\eta_{t}^{2}\sigma^{2}.$

Observe that the contraction factor multiplying
${\mathbb{E}}\|x_{t}-\bar{x}\|^{2}$ for small $\eta$ scales as
$1-\alpha(1-2\rho)\eta$. It follows that in the regime $\rho<\frac{1}{2}$, one
can drive the gap ${\mathbb{E}}[\varphi(x_{t+1})-\varphi(\bar{x})]$ to zero at
a controlled rate, with an appropriate choice of $\eta_{t}$. Moreover, a quick
argument shows that the parameter regime of convergence becomes larger if we
focus on the rate at which the distance $\|x_{t+1}-\bar{x}\|^{2}$ decays.
Indeed, lower-bounding the left side in Lemma 4.3 using strong convexity and
rearranging yields the one-step progress guarantee

$\displaystyle{\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}$
$\displaystyle\leq\left(1-\alpha(1-\rho)\eta_{t}+\tfrac{1}{2}\eta_{t}^{2}\gamma^{2}\beta^{2}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}+\eta_{t}^{2}\sigma^{2}.$

For small $\eta_{t}$, the contraction factor multiplying
$\|x_{t}-\bar{x}\|^{2}$ roughly scales as $1-\alpha(1-\rho)\eta$. Therefore in
the regime $\rho<1$, one can drive the square distance
${\mathbb{E}}[\|x_{t+1}-\bar{x}\|^{2}]$ to zero at a controlled rate, with an
appropriate choice of $\eta_{t}$.

With Lemma 4.3 at hand, obtaining formal guarantees with various choices of
parameters $\eta_{t}$ is standard. The following theorem presents one such
guarantee.

######  Theorem 4.4 (Informal).

In the regime $\rho<1$, the proximal stochastic gradient method with
appropriate parameters $\eta_{t}$ will generate a point $x$ satisfying
$\|x-\bar{x}\|^{2}\leq\varepsilon$ using

$\mathcal{O}\left(\left(\left(\frac{\rho}{1-\rho}\right)^{2}+\frac{\kappa}{1-\rho}\right)\cdot\log\left(\frac{\|x_{0}-\bar{x}\|^{2}}{\varepsilon}\right)+\frac{\sigma^{2}}{(1-\rho)^{2}\alpha^{2}\varepsilon}\right)\qquad\textrm{samples}.$

Moreover, in the regime $\rho<\frac{1}{2}$, the method will generate a point
$x$ satisfying ${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$
using

$\mathcal{O}\left(\left(\left(\frac{\rho}{1-2\rho}\right)^{2}+\frac{\kappa}{1-2\rho}\right)\cdot\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\frac{\sigma^{2}}{(1-2\rho)\alpha\varepsilon}\right)\qquad\textrm{samples}.$

In the static setting $\gamma=0$ (and hence $\rho=0$), Theorem 4.4 recovers
the classical guarantees for the proximal stochastic gradient method [20, 21].
A closely related result for the projected stochastic gradient method was
proved in [30]. Their guarantee is weaker in that it $(i)$ assumes that $r$ is
the indicator function of a closed convex set and $(ii)$ it provides estimates
only on the distance of the last iterate to $\bar{x}$.

Accelerated gradient methods, famously introduced by Nesterov [33] and
extended to the proximal setting by Beck and Teboulle [7], play a central role
in convex optimization. Such methods are best in class for smooth convex
optimization. Ghadimi and Lan [28, 21] proposed an accelerated method for the
stochastic setting, which is best in class for smooth convex stochastic
problems. Continuing with the theme of the paper, we ask whether acceleration
is possible with state-dependent distributions. We show an affirmative answer
in the slightly suboptimal regime $\rho\lesssim\kappa^{-1/4}$.

Rather than analyzing the original method of Ghadimi and Lan [21], we focus on
the more recent variant of Kulunchakov and Mairal [26]. With decision-
dependent distributions, the method reads as:

$\mathrm{ASG:}\qquad\left\\{\quad\begin{aligned}
&\textrm{Sample~{}}z_{t}\sim\mathcal{D}(y_{t-1})\textrm{ and set
}g_{t}=\nabla\ell(y_{t-1},z_{t}),\\\ &\textrm{Set~{}}x_{t}={\rm
prox}_{\eta_{t}r}(y_{t-1}-\eta g_{t}),\\\
&\textrm{Set~{}}y_{t}=x_{t}+\tfrac{1-\sqrt{\eta\alpha(1-2\rho)}}{1+\sqrt{\eta\alpha(1-2\rho)}}(x_{t}-x_{t-1}).\end{aligned}\quad\right\\}.$
(4.2)

In the deterministic and unregularized ($r\equiv 0$) setting, the method
reduces to the classical procedure in [32], derived through estimate
sequences. The following theorem summarizes the convergence guarantees of the
ASG algorithm under state dependent sampling.

######  Theorem 4.5 (Informal).

In the regime $\rho\lesssim\kappa^{-1/4}$, the stochastic accelerated proximal
gradient method (4.2) with appropriate parameter choices will generate a point
$x$ satisfying ${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$
using

$\mathcal{O}\left(\sqrt{\kappa}\cdot\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\frac{\sigma^{2}}{\alpha\varepsilon}\right)\qquad\textrm{samples}.$

Notice that the regime when the accelerated method is guaranteed to work
$\rho\lesssim\kappa^{-1/4}$ is “suboptimal” by the small factor
$\kappa^{-1/4}$. On the other hand, it is surprising that there is any regime
$\gamma>0$ where the accelerated method works at all, since it is well known
that accelerated methods suffer from error accumulation [16]. The reason there
is no contradiction here is that the gradient bias that we encounter tends to
zero linearly as one approaches the solution (2.1). It would be interesting to
know whether the extra factor $\kappa^{-1/4}$ is really necessary or is an
artifact of the proof.

##### Proof technique: gradient deviation as a measure of bias.

The results in this section follow from the following transparent geometric
reasoning. Recall that the gradient deviation inequality (3.1) shows that
contrary to the static setting, the vector $\nabla\ell(x,z)$ with
$z\sim\mathcal{D}(x)$ is a biased estimator of the gradient $\nabla
f_{\bar{x}}(x)$, with bias scaling as $\|x-\bar{x}\|$. Nonetheless, a quick
computation shows that the mean of the estimator $\nabla
f_{x}(x)=\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(x)}[\nabla\ell(x,z)]$
furnishes a strong convexity inequality between $x$ and $\bar{x}$ given by

$f_{\bar{x}}(\bar{x})\geq f_{\bar{x}}(x)+\langle\nabla
f_{x}(x),\bar{x}-x\rangle+\frac{\alpha(1-2\rho)}{2}\|x-\bar{x}\|^{2}.$

This inequality suffices to establish convergence guarantees for the proximal
stochastic gradient method; the reason is simply that strong convexity is used
in the classical argument only to compare the function values along the
iterates with the minimal value. Perhaps more surprisingly, the accelerated
variant of the method can also be understood from this viewpoint. Section 7
analyzes the proximal stochastic gradient method and its accelerated variant
under a biased stochastic oracle model. This oracle model is broader than the
setting of state-dependent sampling and may be of independent interest.

###  4.4 Model-based minimization: stochastic proximal point and clipped
gradient methods (Section 8)

Though the stochastic gradient method is popular in practice, it has well-
documented deficiencies. Notably, the method is highly sensitive to
algorithmic parameters, with small misspecifications often drastically
degrading performance. Recent works [2, 38] have suggested that algorithms
based on tighter models than linear may lead to more robust algorithms.
Following [2, 15], we consider a class of stochastic algorithms that proceed
as follows. In each iteration $t$, the methods draw a sample
$z_{t}\in\mathcal{D}(x_{t})$ and approximate the loss function
$\ell(\cdot,z_{t})$ by a simpler model $\ell_{x_{t}}(\cdot,z_{t})$ formed at
the basepoint $x_{t}$. The next iterate $x_{t+1}$ is then the minimizer of the
function $\ell_{x_{t}}(\cdot,z_{t})+r+\frac{1}{2\eta_{t}}\|\cdot-x_{t}\|^{2}$.
Thus, the model-based algorithm repeats the steps

$\left\\{\quad\begin{aligned}
&\textrm{Sample~{}}z_{t}\sim\mathcal{D}(x_{t})\\\
&\textrm{Set~{}}x_{t+1}=\operatornamewithlimits{arg\,min}_{y}\,\Bigl{\\{}\ell_{x_{t}}(y,z_{t})+r(y)+\frac{1}{2\eta_{t}}\|y-x_{t}\|^{2}\Bigr{\\}}\end{aligned}\quad\right\\}$
(MBA)

For example, the stochastic proximal gradient method (4.1) uses the linear
model $\ell_{x}(y,z)=\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle$, while the
stochastic proximal point method uses the loss function itself
$\ell_{x}(y,z)=\ell(y,z)$. Often, the proximal point subproblem can be solved
in closed form since it depends only on a single data point. Yet another
interesting algorithm is the clipped gradient method, which uses the truncated
models $\ell_{x}(y,z)=\max\\{\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle,0\\}$
under the assumption that the losses are nonnegative. See Fig. 1 for an
illustration. Tighter models often lead to better performing algorithms.

$1$

$1$

$1$

Figure 1: Illustration of the three models for the function
$\ell(y)=\ln(1+e^{y})$; black curve depicts the graph of $\ell$, the red
curves depict the models $\ell_{1}(y)=\ell(y)$ (proximal point),
$\ell_{1}(y)=\ell(1)+\ell^{\prime}(1)(y-1)$ (gradient),
$\ell_{1}(y)=\max\\{\ell(1)+\ell^{\prime}(1)(y-1),0\\}$ (clipped gradient).

Section 8 presents convergence guarantees for the entire class of model-based
algorithms. It will be important for the clipped stochastic gradient method to
assume that $r$ is $\mu$-strongly convex for some $\mu\geq 0$. The efficiency
guarantees specialized for the stochastic proximal gradient, proximal point,
and clipped gradient methods read as follows.

######  Theorem 4.6 (Informal).

Define $\tilde{\alpha}:=\alpha+\mu$ for stochastic proximal gradient and
proximal point methods and set $\tilde{\alpha}:=\mu$ for the clipped gradient
method; in addition, set $\tilde{\rho}=\frac{\gamma\beta}{\tilde{\alpha}}$. In
the regime $\tilde{\rho}<1$, the three methods with appropriate parameters
$\eta_{t}$ will generate a point $x$ satisfying
$\|x-\bar{x}\|^{2}\leq\varepsilon$ using

$\mathcal{O}\left(\frac{L+\tilde{\alpha}}{\tilde{\alpha}(1-\tilde{\rho})}\cdot\log\left(\frac{\|x_{0}-\bar{x}\|^{2}}{\varepsilon}\right)+\frac{\sigma^{2}}{\tilde{\alpha}^{2}(1-\tilde{\rho})^{2}\varepsilon}\right)\qquad\textrm{samples}.$

Moreover, in the regime $\tilde{\rho}<\frac{1}{2}$, the methods will generate
a point $x$ satisfying
${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$ using

$\mathcal{O}\left(\frac{L+\tilde{\alpha}}{\tilde{\alpha}(1-2\tilde{\rho})}\cdot\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\frac{\sigma^{2}}{\tilde{\alpha}(1-2\tilde{\rho})\varepsilon}\right)\qquad\textrm{samples}.$

##### Proof technique: function gap deviation (3.2) & Lyapunov analysis.

The proofs of the outlined results rely on the interplay between the function
gap inequality (3.2) and typical Lyapunov arguments used in stochastic
optimization. Namely, classical convergence arguments for stochastic methods
on a static problem $\min_{x}\psi(x)$ rely on one-step improvement bounds of
the form:

$\eta_{t}{\mathbb{E}}_{t}[\psi(x_{t+1})-\psi(x)]\leq\frac{1-c_{1}\eta_{t}}{2}\|x_{t}-x\|^{2}-\frac{1+c_{2}\eta_{t}}{2}\|x_{t+1}-x\|^{2}+c_{3}\eta_{t}^{2}\qquad\forall
x.$ (4.3)

Here, $c_{1},c_{2},c_{3}\in{\bf R}$ are some constants and $\eta_{t}>0$ is a
user-specified sequence. As long as the sum $c_{1}+c_{2}$ is positive, one may
drive the gap ${\mathbb{E}}[\psi(x_{t+1})-\psi(x)]$ below any fixed tolerance
by choosing $\eta_{t}>0$ appropriately. The condition $c_{1}+c_{2}>0$
typically holds under strong convexity assumptions. Standard efficiency
estimates follow by setting $x$ to be the minimizer of $\psi$; for our
purposes, however, it is important that $x$ can be arbitrary.

Returning to stochastic optimization with state-dependent distributions,
recall that the losses themselves are assumed to be smooth and strongly
convex. Therefore, stochastic methods on the static problem $\min\varphi_{x}$
(for any $x$) likely enjoys the estimate (4.3) with $c_{1}+c_{2}>0$. Imagine
now that given a current iterate $x_{t}$ we take a single step of such an
algorithm on the problem $\texttt{St}(\mathcal{D}(x_{t}))$. Setting
$x=\bar{x}$ (with $\psi\equiv\varphi_{x_{t}}$) and applying the function gap
inequality implies the one-step improvement:

$\eta_{t}{\mathbb{E}}_{t}[\varphi(x_{t+1})-\varphi(\bar{x})]\leq\frac{1-(c_{1}-\gamma\beta)\eta_{t}}{2}\|x_{t}-\bar{x}\|^{2}-\frac{1+(c_{2}-\gamma\beta)\eta_{t}}{2}\|x_{t+1}-\bar{x}\|^{2}+c_{3}\eta_{t}^{2}.$

Therefore in the regime $c_{1}+c_{2}-2\gamma\beta>0$, we can drive the gap
${\mathbb{E}}_{t}[\varphi(x_{t+1})-\varphi(\bar{x})]$ below any tolerance with
an appropriate choice of $\eta_{t}>0$. Moreover, if $\varphi$ is
$\tilde{\alpha}$-strongly convex (for some $\tilde{\alpha}>0$), then we may
lower bound the left side by
$(\eta_{t}\tilde{\alpha}/2){\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}$. Elementary
algebraic manipulations then show that the parameter regime of convergence in
the distance ${\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}$ improves to
$c_{1}+c_{2}+\tilde{\alpha}-2\gamma\beta>0$. In summary, the function gap
inequality (3.2) allows to translate one-step improvements on static problems
$\min\varphi_{x_{t}}$ into one-step improvements on the target problem
$\min\varphi$. We will show that model based algorithms on well-conditioned
static problems satisfy a one-step improvement bound of the form (4.3) with
$c_{1}+c_{2}>0$, and then apply the outlined argument using (3.2).

###  4.5 Inexact repeated minimization (Section 9)

All the aforementioned stochastic algorithms draw a single sample in between
every change in distribution. In practice, however, modifying the sampling
distribution may be much more expensive than drawing a sample from the current
distribution $\mathcal{D}(x_{t})$. Following [36], we call the process of
modifying the distribution deployment. It is an interesting question if it is
possible to maintain the sample efficiencies of the aforementioned algorithms
for (implicitly) solving $\texttt{St}(\mathcal{D}(\bar{x}))$ while decreasing
the number of deployments. An answer to this question for the projected
stochastic gradient method appears in [36, Theorem 3.3]. Namely, consider
running inexact repeated minimization for iterations $t=0,1,\ldots$ with a
projected stochastic gradient method applied for $J_{t}$ iterations on each
subproblem. The authors show that setting $J_{t}=\mathcal{O}(t^{1.1p})$
ensures that iterates $x_{t}$ converge to $\bar{x}$ at the rate $O(t^{-p})$.
Here $p>0$ is a tuning parameter that controls the tradeoff between sampling
and deployment. We prove a closely related result for all the algorithms
analyzed in the previous sections; concisely, we show that the number of
deployments can be reduced to be logarithmic in problem parameters without
sacrificing sample efficiency.

We begin with the following theorem, which provides guarantees on the
efficiency of repeated minimization with model-based algorithms used as
inexact subsolvers.

######  Theorem 4.7 (Informal).

Define $\tilde{\alpha}=\alpha+\mu$ for stochastic proximal gradient and
proximal point methods and set $\tilde{\alpha}=\mu$ for the clipped gradient
method; in addition, set $\tilde{\rho}=\frac{\gamma\beta}{\tilde{\alpha}}$. In
the regime $\tilde{\rho}<1$, the three methods may be used as inexact solvers
within repeated minimization. The resulting methods will generate a point $x$
satisfying ${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$ using

$\mathcal{O}\left(\frac{1}{1-\tilde{\rho}}\cdot\left(\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\log\left(\frac{\sigma^{2}}{1-\tilde{\rho}}\cdot\frac{1}{L\varepsilon}\right)\right)\right)\qquad\textrm{deployments},$

and

$\mathcal{O}\left(\frac{\log((1-\tilde{\rho})^{-1})}{1-\tilde{\rho}}\cdot\left(\frac{L}{\tilde{\alpha}(1-\tilde{\rho})}\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\frac{\sigma^{2}}{\tilde{\alpha}(1-\tilde{\rho})^{2}\varepsilon}\right)\right)\qquad\textrm{samples}.$

Observe that the sample complexity in Theorems 4.6 and 4.7 are essentially the
same. The key difference is that the number of deployments in the latter is
only logarithmic in the problem parameters. The following theorem provides
guarantees on the efficiency of repeated minimization with an accelerated
stochastic gradient method used as an inexact solver.

######  Theorem 4.8 (Informal).

In the regime $\rho<\frac{1}{2}$, the accelerated stochastic proximal gradient
method may be used as an inexact solver within repeated minimization. The
resulting method will generate a point $x$ satisfying
${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$ using

$\mathcal{O}\left(\left(1-\tfrac{1}{2(1-\rho)}\right)^{-1}\left(\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\log\left(\frac{\sigma^{2}}{(1-\frac{\rho}{1-\rho})\varepsilon\sqrt{\alpha
L}}\right)\right)\right)\qquad\textrm{deployments},$

and

$\mathcal{O}\left(\left(1-\tfrac{1}{2(1-\rho)}\right)^{-1}\cdot\left(\sqrt{\kappa}\cdot\log\left(\frac{\varphi(x_{0})-\varphi(\bar{x})}{\varepsilon}\right)+\frac{\sigma^{2}}{(1-\tfrac{\rho}{1-\rho})\alpha\varepsilon}\right)\right)\qquad\textrm{samples}.$

Comparing Theorems 4.5 and 4.8, we see that the latter takes hold in the
nearly optimal parameter regime $\rho<\frac{1}{2}$ without the extra factor of
$\kappa^{-1/4}$. In addition, the number of deployments is only logarithmic in
the problem parameters. The proof strategy for Theorems 4.7 and 4.8 again
relies heavily on using the function gap inequality (3.2) to perturb Lyapunov
type arguments.

Sections 5-9 formally justify the results outlined in this section.

##  5 Calm and contractive methods

In this section, we analyze two conceptual algorithms with state-dependent
distributions:

(Proximal point) |  $\displaystyle x_{t+1}=\operatornamewithlimits{arg\,min}_{x}\,\left\\{f_{x_{t}}(x)+r(x)+\frac{1}{2\eta}\|x-x_{t}\|^{2}\right\\}$,
---|---
(Proximal gradient) |  $\displaystyle x_{t+1}={\rm prox}_{\eta r}(x_{t}-\eta\nabla f_{x_{t}}(x_{t}))$.

Thus in each iteration $t$, the two methods simply take a proximal point and
proximal gradient steps, respectively, on the static problem
$\texttt{St}(\mathcal{D}(x_{t}))$. The proximal point method in the extreme
case $\eta=\infty$ is called repeated minimization in [36]. The paper [36]
showed that when $r$ is the indicator function of a closed convex set and
$\rho<1$, repeated minimization and the proximal gradient method converge
linearly to $\bar{x}$. In this section, we provide a different and
complimentary viewpoint based on stability to distributional shifts.

###  5.1 An interlude: calmness of algorithms for $\mathtt{St}(\nu)$

We begin with an interlude quantifying the stability of algorithmic updates on
the parametric family of problems $\mathtt{St}(\nu)$ with $\nu\in\mathbb{P}$.
To this end, let $S_{\nu}(x)$ denote an update of a point $x$ by an algorithm
on the static problem $\mathtt{St}(\nu)$. Recall the notation
$f_{\nu}(x)=\operatorname*{\mathbb{E}}_{z\sim\nu}\ell(x,z)$ from Section 2.
Table 2 lists three basic examples that are worth keeping in mind: full
minimization, proximal-point, and proximal gradient updates. A desirable
property of an algorithm is that for any fixed $x$, the update map
$S_{\nu}(x)$ is Lipschitz continuous with respect to variations in $\nu$.

The following definition summarizes this stability property, relative to
perturbations of a fixed distribution $\mu$, which will later correspond to
the equilibrium distribution $\mathcal{D}(\bar{x})$.

######  Definition 5.1 (Calmness).

Fix a distribution $\mu\in\mathbb{P}$. We say that a map $S_{\nu}(x)$ is
$\tau$-calm relative to $\mu$ if the estimate holds:

$\|S_{\nu}(x)-S_{\mu}(x)\|\leq\tau\cdot
W_{1}(\nu,\mu),\qquad\forall\nu\in\mathbb{P}.$

Without further assumptions, standard algorithms can easily fail to be calm
even if the loss function is convex.111Consider the univariate function
$l(x,z)=\tfrac{1}{4}x^{4}+zx$ and define $\mu$ and $\nu_{k}$ to be point
masses at zero and $\frac{1}{k}$, respectively. Set
$x_{\mu}=\operatornamewithlimits{arg\,min}f_{\mu}$ and
$x_{\nu_{k}}=\operatornamewithlimits{arg\,min}f_{\nu_{k}}$. A quick
computation shows $|x_{\mu}-x_{\nu_{k}}|/W_{1}(\mu,\nu_{k})=k^{2/3}\to\infty$
as $k\to\infty$. As a remedy, we impose strong convexity assumptions on the
problem data.

######  Assumption 6 (Strong convexity).

Suppose that $r$ is closed and convex and that $f_{\mu}$ is $\alpha$-strongly
convex for some distribution $\mu\in\mathbb{P}$ and some constant $\alpha>0$.

Theorem 5.2 verifies that under Assumptions 1 and 6, the three basic updates
in Table 2 are indeed calm relative to $\mu$. The fourth column in Table 2
also lists the well known contraction factors of the updates $x\mapsto
S_{\mu}(x)$.

Updates | $\displaystyle S_{\nu}(x)=\operatornamewithlimits{arg\,min}_{y}~{}\\{\ldots\\}$ | $\begin{aligned} &{\rm Calmness}\\\ &~{}~{}\tau>0\end{aligned}$ | $\begin{aligned} &{\rm Contraction}\\\ &~{}~{}q\in[0,1)\end{aligned}$
---|---|---|---
Minimization | $f_{\nu}(y)+r(y)$ | $\beta/\alpha$ | $0$
Prox-point | $f_{\nu}(y)+r(y)+\frac{1}{2\eta}\|y-x\|^{2}$ | $\frac{\eta\beta}{1+\eta\alpha}$ | $\frac{1}{1+\eta\alpha}$
Prox-gradient | $\langle\nabla f_{\nu}(x),y\rangle+r(y)+\frac{1}{2\eta}\|y-x\|^{2}$ | $\eta\beta$ |  $\sqrt{1-\alpha\eta}$ ($\eta\leq 1/L$)
Table 2: Calm and contractive updates under Assumption 1, 6: first column
lists the names of the algorithms, second column specifies the updates, third
column lists the calmness constants, the fourth columns lists the contraction
factor of the map $x\mapsto S_{\mu}(x)$.

######  Theorem 5.2 (Calmness of the updates).

Suppose that Assumptions 1 and 6 hold. Then the updates of the repeated
minimization, proximal point, and proximal gradient methods are $\tau$-stable
for the constants $\tau>0$ appearing in Table 2.

###### Proof.

Our goal is to establish an upper bound
$\sup_{x}\|S_{\nu}(x)-S_{\mu}(x)\|\leq\tau W_{1}(\mu,\nu)$ for the three
algorithms. Consequently, let us fix a point $x$ throughout the proof and
define the updates corresponding to repeated minimization, proximal point, and
proximal gradient updates, respectively:

$\displaystyle S^{1}_{\nu}(x)$
$\displaystyle=\operatornamewithlimits{arg\,min}_{y}\,\bigl{\\{}f_{\nu}(y)+r(y)\bigr{\\}},$
$\displaystyle S^{2}_{\nu}(x)$
$\displaystyle=\operatornamewithlimits{arg\,min}_{y}\,\bigl{\\{}f_{\nu}(y)+r(y)+\tfrac{1}{2\eta}\|y-x\|^{2}\bigr{\\}},$
$\displaystyle S^{3}_{\nu}(x)$ $\displaystyle={\rm prox}_{\eta
r}\bigl{(}x-\eta\nabla f_{\nu}(x)\bigr{)}.$

We first verify the calmness constant for repeated minimization, $i=1$. To
this end, define the function $\varphi_{\nu}(y):=f_{\nu}(y)+r(y)$ and its
minimizer $y_{\nu}:=\operatornamewithlimits{arg\,min}\varphi_{\nu}$. First-
order optimality conditions guarantee the inclusions
$0\in\partial\varphi_{\mu}(y_{\mu})$ and
$0\in\partial\varphi_{\nu}(y_{\nu})=\nabla f_{\nu}(y_{\nu})+\partial
r(y_{\nu})$. In other words, there exist $\xi\in\partial r(y_{\nu})$ such that
$\nabla f_{\nu}(y_{\nu})+\xi=0$.

On the other hand, strong convexity of $\varphi_{\mu}$ guarantees
$\alpha\|y-y^{\prime}\|\leq\|w-w^{\prime}\|$ for all
$w\in\partial\varphi_{\mu}(y)$ and
$w^{\prime}\in\partial\varphi_{\mu}(y^{\prime})$. We set

$y=y_{\mu},\quad w=0\in\partial\varphi_{\mu}(y_{\mu}),\quad
y^{\prime}=y_{\nu},\quad w^{\prime}=\nabla
f_{\mu}(y_{\nu})+\xi\in\partial\varphi_{\mu}(y_{\nu}).$

Since $\nabla f_{\nu}(y_{\nu})+\xi=0$, we have $w^{\prime}=\nabla
f_{\mu}(y_{\nu})-\nabla f_{\nu}(y_{\nu})$ and thus can deduce

$\alpha\|y_{\mu}-y_{\nu}\|\leq\|\nabla f_{\mu}(y_{\nu})-\nabla
f_{\nu}(y_{\nu})\|\leq\beta\cdot W_{1}(\mu,\nu),$

where the last inequality follows from Lemma 2.1. Noticing that
$S_{\nu}(x)=y_{\nu}$ and $S_{\mu}(x)=y_{\mu}$, we thus arrive at the claimed
estimate $\tau=\beta/\alpha$ for the case $i=1$.

Calmness of the proximal point ($i=2$) and proximal gradient ($i=3$) updates
follow by applying what we have already proved (case $i=1$) but with the
different loss functions

$\displaystyle\varphi^{2}_{\nu}(y)$
$\displaystyle=f_{\nu}(y)+r(y)+\frac{1}{2\eta}\|y-x\|^{2},$
$\displaystyle\varphi^{3}_{\nu}(y)$ $\displaystyle=\langle\nabla
f_{\nu}(x),y\rangle+r(y)+\frac{1}{2\eta}\|y-x\|^{2},$

and recognizing $S^{i}_{\nu}(x)$ as the minimizers
$S^{i}_{\nu}(x)=\operatornamewithlimits{arg\,min}_{y}\,\varphi^{i}_{\nu}(y)$.
∎

###  5.2 Linear convergence of conceptual algorithms

We next pass to the setting where the distribution governing the data is
state-dependent. To this end, suppose that Assumptions 1, 2, 3(a), 4(a) hold.
We will show that linear convergence of repeated minimization, proximal point,
and proximal gradient methods is a direct consequence of the two independent
phenomenon:

  1. 1.

(Calm) The updates are $\tau$-calm (Theorem 5.2).

  2. 2.

(Contractive) The algorithms are $q$-contractive on the static problem
$\mathtt{St}(\mathcal{D}(\bar{x}))$. That is,
$\|S_{\bar{x}}(x)-S_{\bar{x}}(y)\|\leq q\|x-y\|$ for all
$x,y\in\operatorname*{dom\,}r$.

It is elementary to see that an algorithm satisfying these two properties is
automatically $(q+\tau\gamma)$-contractive under state dependent sampling.
This is the content of the following lemma.

######  Lemma 5.3 (Calm and contractive).

Fix a map $S_{\nu}(x)$ that is $\tau$-calm and such that the map $x\mapsto
S_{\mathcal{D}(\bar{x})}(x)$ is q-contractive with $\bar{x}$ as its fixed
point. Then the estimate holds:

$\|S_{\mathcal{D}(x)}(x)-\bar{x}\|\leq(q+\tau\gamma)\|x-\bar{x}\|\qquad\qquad\forall
x\in{\bf R}^{d}.$

###### Proof.

Abusing notation slightly and setting $S_{x}(y):=S_{\mathcal{D}(x)}(y)$, we
compute

$\displaystyle\|S_{x}(x)-\bar{x}\|=\|S_{x}(x)-S_{\bar{x}}(\bar{x})\|$
$\displaystyle\leq\|S_{x}(x)-S_{\bar{x}}(x)\|+\|S_{\bar{x}}(x)-S_{\bar{x}}(\bar{x})\|$
(5.1) $\displaystyle\leq\tau\cdot
W_{1}(\mathcal{D}(x),\mathcal{D}(\bar{x}))+q\|x-\bar{x}\|$ (5.2)
$\displaystyle\leq(q+\tau\gamma)\|x-\bar{x}\|.$ (5.3)

Here (5.1) uses the triangle inequality, (5.2) follows from calmness and
contractiveness, while (5.3) follows from Assumption 2. The proof is complete.
∎

Combining Lemma 5.3 with the constants $\tau$ and $q$ specified in Table 2
immediately yields linear convergence guarantees for the three conceptual
algorithms.

######  Corollary 5.4 (Repeated minimization, proximal point, and proximal
gradient methods).

Suppose that Assumptions 1, 2, 3(a), 4(a) hold. Then for any point $x$, the
following estimates hold:

$\frac{\|x^{+}-\bar{x}\|}{\|x-\bar{x}\|}\leq\begin{cases}\frac{\gamma\beta}{\alpha}&\mbox{if
}x^{+}=\operatornamewithlimits{arg\,min}_{y}\,\bigl{\\{}f_{x}(y)+r(y)\bigr{\\}},\\\\[4.30554pt]
\frac{1+\gamma\eta\beta}{1+\eta\alpha}&\mbox{if
}x^{+}=\operatornamewithlimits{arg\,min}_{y}\,\bigl{\\{}f_{x}(y)+r(y)+\frac{1}{2\eta}\|y-x\|^{2}\bigr{\\}},\\\\[4.30554pt]
\sqrt{1-\eta\alpha}+\gamma\eta\beta&\mbox{if }x^{+}={\rm prox}_{\eta
r}(x-\eta\nabla f_{x}(x))~{}\textrm{and}~{}\eta\leq\frac{1}{L}.\end{cases}$

Thus iterated minimization and the prox-point methods converge linearly to
$\bar{x}$ in the regime $\rho<1$, while the prox-gradient method converges
linearly to $\bar{x}$ in the regime $\rho<\frac{1}{2}$.

Corollary 5.4 shows that iterated minimization and proximal point methods
converge linearly in the parameter regime $\rho<1$. Moreover, as shown in
[36], repeated minimization can easily diverge outside this parameter regime.
The regime of convergence $\rho<\frac{1}{2}$ for the proximal gradient method
therefore appears slightly suboptimal. This regime can be trivially enlarged
when no regularization is present, i.e., when $r=0$. Indeed, with the choice
$\eta=\frac{2}{\alpha+L}$, the gradient method is $\frac{L-\alpha}{L+\alpha}$
contractive on the static problem $\mathtt{St}(\mathcal{D}(\bar{x}))$ (e.g.
[13, Theorem 3.12]). Lemma 5.3 therefore guarantees that the update $x^{+}$
satisfies

$\frac{\|x^{+}-\bar{x}\|}{\|x-\bar{x}\|}\leq\frac{L-\alpha}{L+\alpha}+\frac{2\gamma\beta}{L+\alpha}.$

Clearly, the right side is smaller than one if and only if $\rho<1$. A similar
guarantee based on a different argument appears in [30, Proposition 2.5].

In general regularized settings, the regime of convergence of the proximal
gradient method can be enlarged to $\rho<1$ through a different argument. See
the forthcoming guarantees for the proximal stochastic gradient method
(Theorem 7.3 with $\sigma^{2}=0$).

##  6 Reduction to online convex optimization

This section shows that virtually any algorithm designed for online convex
optimization can be applied under state-dependent sampling. We begin with a
short summary of online convex optimization, and refer the reader to the
surveys [23, 39] for further details.

###  6.1 Review of online convex optimization

The framework of online convex optimization can be interpreted as a repeated
game. At each iteration $t$, the player chooses a point $x_{t}$ from a convex
set $K\subset{\bf R}^{d}$, then a convex cost function $\ell_{t}:K\to{\bf R}$
is revealed and the player incurs the cost $\ell_{t}(x_{t})$. The goal of the
player is to minimize the regret, defined as the difference between the total
cost $\sum_{i=1}^{t}\ell_{i}(x_{i})$ incurred up to round $t$ and the minimum
cost of any fixed decision from hindsight, $\min_{x\in
K}\sum_{i=1}^{t}\ell_{i}(x)$. Here we consider a regularized version of online
convex optimization and define the regret up to round $t$ as

$R_{t}:=\sum_{i=1}^{t}\bigl{(}\ell_{i}(x_{i})+r(x_{i})\bigr{)}-\min_{x}\sum_{i=1}^{t}\bigl{(}\ell_{i}(x)+r(x)\bigr{)},$

where $r$ is a convex function that represents the indicator function of the
set $K$ or a more general regularization. In this setting, we can use the
online proximal gradient method,

$x_{t+1}={\rm prox}_{\eta_{t}r}(x_{t}-\eta_{t}\nabla\ell_{t}(x_{t})),$ (6.1)

as proposed in [17]. Other suitable algorithms include the regularized dual
average method [41] and variants of FTRL (Follow-The-Regularized-Leader)
method [29].

The framework of online convex optimization is more general than stochastic
optimization, since the loss function $\ell_{t}$ at each iteration may not
follow any probability distribution and can even be adversarial. On the other
hand, it requires more strict assumptions in order to have meaningful regret
analysis. In particular, the set $K$ needs be bounded, say with diameter $D$,
and the gradient of the cost functions are also bounded by a constant $G$,
i.e., $\|\nabla\ell_{t}(x)\|\leq G$ for all $x\in K$ and all $t$. Under these
assumptions, the methods mentioned above have bounded regret against any
reference point $x\in\operatorname*{dom\,}r$:

$R_{t}(x):=\sum_{i=1}^{t}\left(\bigl{(}\ell_{i}(x_{i})+r(x_{i})\bigr{)}-\bigl{(}\ell_{i}(x)+r(x)\bigr{)}\right)\leq
U_{t},$ (6.2)

where $U_{t}={\mathcal{O}}(GD\sqrt{t})$ for convex losses with
$\eta_{t}=D/(G\sqrt{t})$ and $U_{t}={\mathcal{O}}((G^{2}/\alpha)\ln(t))$ for
$\alpha$-strongly convex losses with $\eta_{t}=1/(\alpha t)$. See [17], [41]
and [29] for the details.

###  6.2 Reduction

We claim that one can directly apply online optimization algorithms in the
setting of state-dependent sampling, and derive their convergence rate from
the regret bounds (6.2). As usual, we let $\bar{x}$ be an equilibrium point
with respect to $\mathcal{D}(\cdot)$, set
$\varphi_{x}(y)={\mathbb{E}}_{z\sim\mathcal{D}(x)}[\ell(y,z)]+r(y)$, and use
the shorthand $\varphi=\varphi_{\bar{x}}$.

######  Theorem 6.1 (Reduction).

Suppose that Assumptions 1, 2, 3(a) hold. Consider an online algorithm that in
each iteration $t\geq 1$ encounters the loss function
$\ell_{t}(x_{t})=\ell(x_{t},z_{t})$ where $z_{t}\sim\mathcal{D}(x_{t})$.
Suppose that the uniform regret bound (6.2) holds for each $t\geq 1$. Then the
average iterate $\hat{x}_{t}:=\frac{1}{t}\sum_{i=1}^{t}x_{i}$ satisfies

${\mathbb{E}}[\varphi(\hat{x}_{t})]-\varphi(\bar{x})~{}\leq~{}\frac{U_{t}}{(1-2\rho)\,t}\qquad\forall
t\geq 1.$

###### Proof.

Taking the expectation in (6.2) and setting $x=\bar{x}$ yields

${\mathbb{E}}\left[R_{t}(\bar{x})\right]=\sum_{i=1}^{t}{\mathbb{E}}\bigl{[}\varphi_{x_{i}}(x_{i})-\varphi_{x_{i}}(\bar{x})\bigr{]}\leq
U_{t}.$

The function gap inequality (3.2) in turn implies

$\varphi(x_{i})-\varphi_{\bar{x}}(\bar{x})\leq\varphi_{x_{i}}(x_{i})-\varphi_{x_{i}}(\bar{x})+\gamma\beta\cdot\|x_{i}-\bar{x}\|^{2}.$

Strong convexity implies
$\|x_{i}-\bar{x}\|^{2}\leq\frac{2}{\alpha}(\varphi(x_{i})-\varphi(\bar{x}))$
and hence

$(1-2\rho)\bigl{(}\varphi(x_{i})-\varphi(\bar{x})\bigr{)}\leq\varphi_{x_{i}}(x_{i})-\varphi_{x_{i}}(\bar{x}).$

Therefore, in the setting $\rho<1/2$, we have

${\mathbb{E}}\biggl{[}\sum_{i=1}^{t}\bigl{(}\varphi(x_{i})-\varphi(\bar{x})\bigr{)}\biggr{]}~{}\leq~{}\frac{1}{1-2\rho}{\mathbb{E}}[R_{t}(\bar{x})]~{}\leq~{}\frac{1}{1-2\rho}U_{t}.$

Dividing both sides by $t$ and using convexity of $\varphi$ completes the
proof. ∎

Known regret bounds for the proximal gradient [17], regularized dual averaging
[41], and FTRL [29] algorithms directly yield a converge rate
$O(\log(t)/(1-2\rho)t)$ under state-dependent sampling and under the
assumptions used in the aforementioned papers.

Though Theorem 6.1 is attractive in its generality, it is far from
satisfactory. Indeed, the framework of online convex optimization is far more
general than stochastic optimization, since the loss function $\ell_{t}$ at
each iteration may not follow any probability distribution and can even be
adversarial. As a consequence, online convex optimization requires stringent
assumptions in order to have meaningful regret analysis, most notably
boundedness of the encountered gradients of the loss functions. Moreover
smoothness of the loss function does not play a significant role. We will see
in the next section that much finer convergence guarantees hold for stochastic
optimization under state-dependent distributions.

##  7 Stochastic gradient methods

In this section, we directly analyze the (accelerated) stochastic proximal
gradient method, without relying on regret bounds. The only consequence of
state-dependent distribution that will be relevant is that the stochastic
estimator of the gradient is biased and the bias is bounded as in (3.1). As a
result, we work with a broader model with a biased stochastic gradient oracle,
formalized next in Assumption 7.

######  Assumption 7 (Biased stochastic gradient oracle).

Consider the optimization problem

$\min_{x}~{}\varphi(x):=f(x)+r(x),$

and denote its minimizer by $\bar{x}$. We suppose that there exist constants
$L,B,\alpha>0$ satisfying the following.

  1. (a)

The function $f\colon{\bf R}^{d}\to{\bf R}$ is $\alpha$-strongly convex and
differentiable with $L$-Lipschitz gradient.

  2. (b)

The function $r\colon{\bf R}^{d}\to{\bf R}\cup\\{\infty\\}$ is closed and
convex.

  3. (c)

For every point $x$, we may draw a realization of a random vector $g(x)\in{\bf
R}^{d}$ satisfying the bias/variance bounds:

$\|{\mathbb{E}}[g(x)]-\nabla f(x)\|\leq
B\|x-\bar{x}\|\qquad\textrm{and}\qquad{\mathbb{E}}\|g(x)-{\mathbb{E}}[g(x)]\|^{2}\leq\sigma^{2}.$

Throughout, we define the condition number $\kappa:=\frac{L}{\alpha}$ and set
$\rho:=\frac{B}{\alpha}$.

It is clear that Assumptions 1, 2, 3(a) and 4(a) under the setting of state-
dependent distributions imply Assumption 7 with $g(x):=\nabla\ell(x,z)$ where
$z\sim\mathcal{D}(x)$, and $B:=\gamma\beta$. Consequently, all convergence
guarantees presented in this section can be interpreted under the setting of
state-dependent distributions by simply setting $B=\gamma\beta$.

The main consequence of the particular form of the bias in Assumption 7 (c) is
summarized in the following lemma. In essence, the lemma states that a strong
convexity type inequality holds between $x$ and $\bar{x}$, with $\nabla f(x)$
replaced by ${\mathbb{E}}[g(x)]$.

######  Lemma 7.1 (Approximate subgradient inequality).

Under Assumption 7, it holds that

$f(\bar{x})\geq
f(x)+\langle{\mathbb{E}}[g(x)],\bar{x}-x\rangle+\frac{\alpha(1-2\rho)}{2}\|x-\bar{x}\|^{2}\qquad\forall
x\in{\bf R}^{d}.$

###### Proof.

Strong convexity of $f$ guarantees

$\displaystyle f(\bar{x})$ $\displaystyle\geq f(x)+\langle\nabla
f(x),\bar{x}-x\rangle+\frac{\alpha}{2}\|x-\bar{x}\|^{2}$
$\displaystyle=f(x)+\langle{\mathbb{E}}[g(x)],\bar{x}-x\rangle+\frac{\alpha}{2}\|x-\bar{x}\|^{2}+\langle\nabla
f(x)-{\mathbb{E}}[g(x)],\bar{x}-x\rangle.$

The Cauchy-Schwarz inequality in turn yields the estimate

$\langle\nabla
f(x)-{\mathbb{E}}[g(x)],\bar{x}-x\rangle\geq-\|{\mathbb{E}}[g(x)]-\nabla
f(x)\|\cdot\|\bar{x}-x\|\geq-B\|x-\bar{x}\|^{2}.$

Combining the two inequalities above yields the desired result. ∎

###  7.1 Stochastic proximal gradient method

We are now ready to analyze the stochastic proximal gradient method,
summarized in Algorithm 1, under Assumption 7.

Input: initial $x_{0}$ and sequence
$\\{\eta_{t}\\}_{t=0}^{T}\subset(0,\infty)$.

Step $t=0,1,\ldots,T$:  $\displaystyle\textrm{Sample~{}}g_{t}=g(x_{t})$
$\displaystyle\textrm{Set~{}}x_{t+1}={\rm
prox}_{\eta_{t}r}(x_{t}-\eta_{t}g_{t})$

Algorithm 1 Stochastic gradient method

Throughout, we let ${\mathbb{E}}_{t}[\cdot]$ be the conditional expectation
given the iterates $x_{0},\ldots,x_{t}$. The following lemma provides a key
recursion quantifying the one-step progress of the algorithm. The argument
closely parallels the proof in the unbiased setting [20].

######  Lemma 7.2 (Key recursion).

Suppose that Assumption 7 holds and the step-size sequence satisfies
$\eta_{t}<\frac{1}{L}$. Then the iterates $\\{x_{t}\\}$ generated by Algorithm
1 satisfy

$\displaystyle 2\eta_{t}{\mathbb{E}}_{t}[\varphi(x_{t+1})-\varphi(\bar{x})]$
$\displaystyle\leq\left(1-\alpha\eta_{t}(1-2\rho)+\frac{\eta_{t}^{2}B^{2}}{1-\eta_{t}L}\right)\|x_{t}-\bar{x}\|^{2}-{\mathbb{E}}_{t}\|x_{t+1}-\bar{x}\|^{2}+\frac{\eta_{t}^{2}\sigma^{2}}{1-\eta_{t}L}.$

###### Proof.

Since by Assumption 7 the gradient $\nabla f$ is $L$-Lipschitz, we have

$\displaystyle\varphi(x_{t+1})$ $\displaystyle=f(x_{t+1})+r(x_{t+1})$
$\displaystyle\leq f(x_{t})+\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\rangle+r(x_{t+1})+\frac{L}{2}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle=f(x_{t})+\langle
g_{t},x_{t+1}-x_{t}\rangle+r(x_{t+1})+\frac{L}{2}\|x_{t+1}-x_{t}\|^{2}-\langle
g_{t}-\nabla f(x_{t}),x_{t+1}-x_{t}\rangle.$

Let $\delta_{t}>0$ be an arbitrary positive sequence. We use Young’s
inequality to bound the last inner-product term in the above inequality, which
results in

$\displaystyle\varphi(x_{t+1})$ $\displaystyle\leq f(x_{t})+\langle
g_{t},x_{t+1}-x_{t}\rangle+r(x_{t+1})+\frac{L}{2}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle\quad+\frac{\delta_{t}}{2}\|g_{t}-\nabla
f(x_{t})\|^{2}+\frac{1}{2\delta_{t}}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle=f(x_{t})+\langle
g_{t},x_{t+1}-x_{t}\rangle+r(x_{t+1})+\frac{1}{2\eta_{t}}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle\quad+\frac{\delta_{t}}{2}\|g_{t}-\nabla
f(x_{t})\|^{2}+\frac{\delta_{t}^{-1}-\eta^{-1}_{t}+L}{2}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle\leq f(x_{t})+\langle
g_{t},\bar{x}-x_{t}\rangle+r(\bar{x})+\frac{1}{2\eta_{t}}\|\bar{x}-x_{t}\|^{2}-\frac{1}{2\eta_{t}}\|x_{t+1}-\bar{x}\|^{2}$
$\displaystyle\quad+\frac{\delta_{t}}{2}\|g_{t}-\nabla
f(x_{t})\|^{2}+\frac{\delta_{t}^{-1}-\eta^{-1}_{t}+L}{2}\|x_{t+1}-x_{t}\|^{2},$
(7.1)

where the last inequality (7.1) follows from the fact that $x_{t+1}$ is by
construction the minimizer of the $\eta^{-1}_{t}$-strongly convex function
$f(x_{t})+\langle g_{t},\cdot-x_{t}\rangle+r+\frac{1}{2\eta_{t}}\|\cdot-
x_{t}\|^{2}$.

Next set $\delta_{t}:=\frac{\eta_{t}}{1-\eta_{t}L}$ to make the last term of
(7.1) zero. Taking conditional expectations and using Lemma 7.1, we deduce

$\displaystyle{\mathbb{E}}_{t}[\varphi(x_{t+1})]$
$\displaystyle\leq\varphi(\bar{x})-\frac{\alpha(1-2\rho)}{2}\|x_{t}-\bar{x}\|^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{t}}\|\bar{x}-x_{t}\|^{2}-\frac{1}{2\eta_{t}}{\mathbb{E}}_{t}\|\bar{x}-x_{t+1}\|^{2}+\frac{\delta_{t}}{2}{\mathbb{E}}_{t}\|g_{t}-\nabla
f(x_{t})\|^{2}.$ (7.2)

Next, we upper bound the last term in (7.2) as follows:

${\mathbb{E}}_{t}\|g_{t}-\nabla
f(x_{t})\|^{2}={\mathbb{E}}\|g_{t}-{\mathbb{E}}[g_{t}]\|^{2}+\|{\mathbb{E}}[g_{t}]-\nabla
f(x_{t})\|^{2}\leq\sigma^{2}+B^{2}\|x_{t}-\bar{x}\|^{2}.$

Combining this estimate with (7.2) and grouping like terms completes the
proof. ∎

With Lemma 7.2 at hand, obtaining convergence guarantees under various choices
of the control sequence $\eta_{t}>0$ is completely standard. We highlight one
such result based on using a constant sequence.

######  Theorem 7.3 (Constant step size).

Suppose Assumption 7 holds. Let $x_{t}$ be the iterates generated by Algorithm
1 with a fixed parameter $\eta>0$. Then the following are true.

  1. 1.

Suppose we are in the regime $\rho<1$ and set $\hat{\alpha}:=\alpha-B$. Then
with the parameter $\eta\leq\frac{1}{B^{2}/\hat{\alpha}+L}$, the estimate
holds:

${\mathbb{E}}\|x_{t}-\bar{x}\|^{2}\leq\left(1-\frac{2\eta\hat{\alpha}}{3}\right)^{t}{\mathbb{E}}\|x_{0}-\bar{x}\|^{2}+\frac{2\sigma^{2}\eta}{\hat{\alpha}}.$
(7.3)

  2. 2.

Suppose we are in the regime $\rho<\frac{1}{2}$ and set
$\hat{\alpha}:=\alpha-2B$. Then with the parameter
$\eta\leq\frac{1}{2(B^{2}/\hat{\alpha}+L)}$, the estimate holds:

${\mathbb{E}}[\varphi\left(\hat{x}_{t}\right)-\varphi(\bar{x})]\leq
2\left(1-\frac{\eta\hat{\alpha}}{2}\right)^{t}\left(\varphi(x_{0})-\varphi(\bar{x})\right)+\sigma^{2}\eta.$
(7.4)

where the average iterate is defined recursively by
$\hat{x}_{t}=(1-\frac{\hat{\alpha}\eta}{2})\hat{x}_{t-1}+\frac{\hat{\alpha}\eta}{2}x_{t}$.

###### Proof.

Observe first that the assumption $\eta\leq\frac{1}{2L}$ implies
$\frac{\eta^{2}\sigma^{2}}{1-\eta L}\leq 2\eta^{2}\sigma^{2}$. Therefore Lemma
7.2 yields the one step improvement:

$2\eta{\mathbb{E}}[\varphi(x_{t+1})-\varphi(\bar{x})]\leq\left(1-\alpha\eta(1-2\rho)+\frac{\eta^{2}B^{2}}{1-\eta
L}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}-{\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}+2\eta^{2}\sigma^{2}.$
(7.5)

Proof of claim 1: Lower bounding the left side of (7.5) using strong
convexity,
$\varphi(x_{t+1})-\varphi(\bar{x})\geq\frac{\alpha}{2}\|x_{t+1}-\bar{x}\|^{2}$,
and rearranging yields the guarantee:

${\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}\leq\left(1-\frac{2\alpha\eta(1-\rho)-\frac{\eta^{2}B^{2}}{1-\eta
L}}{1+\eta_{t}\alpha}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}+\frac{2\eta^{2}\sigma^{2}}{1+\eta\alpha}.$

The assumption $\eta<\frac{1}{B^{2}/\hat{\alpha}+L}$ directly implies
$\frac{\eta^{2}B^{2}}{1-\eta L}\leq\alpha\eta(1-\rho)$, and therefore we
deduce

${\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}\leq\left(1-\frac{\alpha\eta(1-\rho)}{1+\eta\alpha}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}+\frac{2\eta^{2}\sigma^{2}}{1+\eta\alpha}.$

Unrolling the recursion and using the estimate $\eta\alpha\leq\frac{1}{2}$
completes the proof of (7.3).

Proof of Claim 2: The assumption $\eta<\frac{1}{2(B^{2}/\hat{\alpha}+L)}$ by
construction guarantees $\frac{\eta^{2}B^{2}}{1-\eta
L}\leq\frac{\hat{\alpha}\eta}{2}.$ Therefore, the inequality (7.5) implies

$\displaystyle 2\eta{\mathbb{E}}_{t}[\varphi(x_{t+1})-\varphi(\bar{x})]$
$\displaystyle\leq\left(1-\frac{\hat{\alpha}\eta}{2}\right)\|\bar{x}-x_{t}\|^{2}-{\mathbb{E}}_{t}\|\bar{x}-x_{t+1}\|^{2}+2\eta^{2}\sigma^{2}.$

Applying Corollary A.3 for the recursion completes the proof of (7.4). ∎

Let us now translate Theorem 7.3 into an efficiency guarantee for finding an
approximate minimizer of $\varphi$. There are two standard restarting
techniques that achieve this goal. The first is based on restarting the
constant step algorithm with exponentially increasing mini-batches of
gradients $\frac{1}{m}\sum_{i=1}^{m}g_{t}^{i}$ in order to decrease the
variance. The second approach restarts the constant step algorithm with
geometrically decreasing parameters $\eta$. Both techniques are standard and
are detailed in Appendix B. The following corollary focuses on the latter
strategy for simplicity, though both strategies enjoy the same sample
complexity guarantees.

######  Corollary 7.4 (Efficiency of Algorithm 1 with geometrically decaying
schedule of $\eta$).

Suppose Assumption 7 holds. Then the following statements hold.

  1. 1.

(Distance) Suppose $\rho<1$ and that we have available an estimate
$\Delta\geq\|x_{0}-\bar{x}\|^{2}$. Define the modified convexity parameter
$\hat{\alpha}=\alpha-B$. Then Algorithm 1 may be augmented with the geometric
decay schedule in Algorithm 8 (Appendix B) under the identification

$c=\frac{2\hat{\alpha}}{3},\quad C=1,\quad
h(x)=\|x-\bar{x}\|^{2},\quad\delta_{0}=\frac{1}{B^{2}/\hat{\alpha}+L},\quad
D=\frac{2\sigma^{2}}{\hat{\alpha}}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[\|x-\bar{x}\|^{2}]\leq\varepsilon$ using

$\mathcal{O}\left(\left(\frac{B^{2}}{\hat{\alpha}^{2}}+\frac{L}{\hat{\alpha}}\right)\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma^{2}}{\hat{\alpha}^{2}\varepsilon}\right)\qquad\textrm{samples}.$

  2. 2.

(Function value) Suppose $\rho<\frac{1}{2}$ and that we have available an
estimate $\Delta\geq\varphi(x_{0})-\varphi(\bar{x})$. Define the modified
convexity parameter $\hat{\alpha}=\alpha-2B$. Then Algorithm 1 may be
augmented with the geometric decay schedule in Algorithm 8 (Appendix B) under
the identification

$c=\frac{\hat{\alpha}}{2},\quad C=2,\quad
h(x)=\varphi(x)-\varphi(\bar{x}),\quad\delta_{0}=\frac{1}{2(B^{2}/\hat{\alpha}+L)},\quad
D=\sigma^{2}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[\varphi(x)-\varphi(\bar{x})]\leq\varepsilon$ using

$\mathcal{O}\left(\left(\frac{B^{2}}{\hat{\alpha}^{2}}+\frac{L}{\hat{\alpha}}\right)\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma^{2}}{\hat{\alpha}\varepsilon}\right)\qquad\textrm{samples}.$

###  7.2 Accelerated Stochastic proximal gradient method

We next discuss the accelerated stochastic proximal gradient method in the
oracle model (Assumption 7). To state the algorithm, we require a few
auxiliary quantities. Setting the stage, define $\hat{\alpha}=\alpha-2B$ and
choose an arbitrary $\gamma_{0}\geq\hat{\alpha}$ and stepsize parameters
$\eta_{t}>0$. Define the two auxiliary sequences

$\displaystyle\delta_{t}$ $\displaystyle=\sqrt{\eta_{t}\gamma_{t}}$
$\displaystyle\textrm{for all }t\geq 0.$ (7.6) $\displaystyle\gamma_{t}$
$\displaystyle=(1-\delta_{t})\gamma_{t-1}+\delta_{t}\hat{\alpha}$
$\displaystyle\textrm{for all }t\geq 1.$

Algorithm 2 summarizes the accelerated stochastic gradient method, proposed in
[26].

Input: Initial $x_{0}\in{\bf R}^{d}$, $\gamma_{0}>0$, sequence
$\\{\eta_{t}\\}_{t\geq 0}\in[0,\infty)$, count $T\in\mathbb{N}$.

Step $t=0,1,\ldots,T$: Set  $\displaystyle x_{t}$
$\displaystyle=y_{t-1}-\eta_{t}g_{t},$ $\displaystyle y_{t}$
$\displaystyle=x_{t}+\beta_{t}(x_{t}-x_{t-1})$
$\displaystyle\qquad\textrm{where}\qquad\beta_{t}=\frac{\delta_{t}(1-\delta_{t})\eta_{t+1}}{\eta_{t}\delta_{t+1}+\eta_{t+1}\delta_{t}^{2}}.$

Algorithm 2 Accelerated stochastic gradient method

Our main result of analyzing Algorithm 2 is the following theorem. Notice that
here the sequence $\beta_{t}$ is not related to $\beta$ in Assumption 1.

######  Theorem 7.5 (Constant step accelerated method).

Suppose that we are in the regime
$\rho\leq\frac{1/2}{1+\sqrt{32+64\sqrt{3\kappa}}}$. Set
$\gamma_{0}=\hat{\alpha}$ and $\eta_{t}=\frac{1}{4L}$ for all $t\geq 0$. Then
the iterates generated by Algorithm 2 satisfy

${\mathbb{E}}\left[\varphi(x_{t})-\varphi(\bar{x})\right]\leq
2\left(1-\sqrt{\frac{\hat{\alpha}}{4L}}\right)^{t}\left(\varphi(x_{0})-\varphi(\bar{x})\right)+\frac{9\sigma^{2}}{16\sqrt{L\hat{\alpha}}}.$

Theorem 7.5 immediately yields an accelerated rate of convergence in the
setting $\rho=\frac{B}{\alpha}\leq\frac{1/2}{1+\sqrt{32+64\sqrt{3\kappa}}}$.
Indeed, Lemma B.1 trivially implies that combining Algorithm 2 with a
minibatch restart strategy (Algorithm 7) yields a procedure that will find a
point $x$ satisfying ${\mathbb{E}}[\varphi(x)-\min\varphi]\leq\varepsilon$
using

$\mathcal{O}\left(\sqrt{\kappa}\cdot\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma^{2}}{\alpha\varepsilon}\right)$

stochastic gradient samples, where $\Delta\geq\varphi(x_{0})-\varphi(\bar{x})$
is user specified.

The proof of Theorem 7.5 is quite long and technical, relying on the machinery
of stochastic estimate sequences [26]. Therefore, we have placed it in
Appendix C. The high level idea of the argument is as follows. Existing
arguments (in the unbiased setting) based on estimate sequences
$d_{t}(x)=d_{t}^{*}+\frac{\gamma_{t}}{2}\|x-v_{t}\|^{2}$ rely on lower
bounding the error ${\mathbb{E}}[d_{t}^{*}-\varphi(x_{t})]$; see e.g. [32,
26]. The usual path is through a sequence of clever algebraic manipulations.
During these manipulations, there is a term $\|y_{t}-v_{t}\|^{2}$ that
appears, which is lower-bounded by zero and ignored. In contrast, we show that
this term balances the incurred bias of the stochastic gradients.

##  8 Model-based algorithms

This section presents convergence guarantees for a wide class of algorithms of
a “proximal point type”, introduced in the two recent papers [2, 15] in the
static setting.

###  8.1 Model-based algorithms for a static problem

We begin by reviewing model-based algorithms for static problems and refine
the available convergence guarantees. Namely, the convergence guarantees
developed in the papers [2, 15] require the second moment of subgradients to
be bounded. We will show that when the loss function is smooth, we may instead
assume a bound on the variance.

Setting the stage, consider the static optimization problem

$\min_{x}~{}F(x)=f(x)+r(x)\qquad\textrm{with}\qquad
f(x)=\operatorname*{\mathbb{E}}_{z\sim{\mathcal{P}}}\ell(x,z),$

where ${\mathcal{P}}$ is some probability measure, the loss $\ell(x,z)$ is
differentiable in $x$, and $r\colon{\bf R}^{d}\to{\bf R}\cup\\{\infty\\}$ is a
closed function. In each iteration $t$, the algorithms we consider draw an
i.i.d set of $m$ samples $S_{t}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}{\mathcal{P}}$ and approximate the loss function
$\ell(\cdot,z_{t})$ by a simpler model $\ell_{x_{t}}(\cdot,S_{t})$ formed at
the basepoint $x_{t}$. The next iterate $x_{t+1}$ is then declared to be the
minimizer of the function
$\ell_{x_{t}}(\cdot,S_{t})+r+\frac{1}{2\eta_{t}}\|\cdot-x_{t}\|^{2}$. The
formal procedure is stated in Algorithm 3.

Input: initial $x_{0}$ and sequence
$\\{\eta_{t}\\}_{t=0}^{T}\subset(0,\infty)$.

Step $t=0,1,\ldots,T$:
$\displaystyle\textrm{Sample~{}}S_{t}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}{\mathcal{P}}$
$\displaystyle\textrm{Set~{}}x_{t+1}=\operatornamewithlimits{arg\,min}_{y}\,\biggl{\\{}\ell_{x_{t}}(y,S_{t})+r(y)+\frac{1}{2\eta_{t}}\|y-x_{t}\|^{2}\biggr{\\}}$

Algorithm 3 Model-based algorithm for static problems

Clearly, convergence guarantees of Algorithm 4 must depend both on the
regularity of the models $\ell_{x}(y,S)$ individually and on how well the
models approximate $f$. The following assumption formalizes these two
properties. It will be useful to keep track of two parameters
$\alpha_{1},\alpha_{2}\geq 0$, which measure “strong convexity” type
properties, along with a variance bound $\sigma_{0}>0$.

######  Assumption 8 (Models for static problems).

There exist constants $\alpha_{1},\alpha_{2},\sigma_{0}\geq 0$ such that the
following properties hold for all $x,y\in{\bf R}^{d}$ and for almost all
samples $S\stackrel{{\scriptstyle i.i.d}}{{\sim}}{\mathcal{P}}$:

  1. (a)

(Convexity) The model $\ell_{x}(\cdot,S)$ is convex and the sum
$\ell_{x}(\cdot,S)+r$ is $\alpha_{1}$-strongly convex.

  2. (b)

(Bias/variance) The model $\ell_{x}(\cdot,S)$ is differentiable at $x$ and
satisfies

$\operatorname*{\mathbb{E}}_{S}[\nabla\ell_{x}(x,S)]=\nabla
f(x)\qquad\textrm{and
}\qquad\operatorname*{\mathbb{E}}_{S}\|\nabla\ell_{x}(x,S)-\nabla
f(x)\|^{2}\leq\sigma^{2}_{0}.$

  3. (c)

(Accuracy) The estimate holds:

$\operatorname*{\mathbb{E}}_{S}[\ell_{x}(x,S)-\ell_{x}(y,S)]\geq
f(x)-f(y)+\frac{\alpha_{2}}{2}\|x-y\|^{2}.$

The convexity assumption (a) is self-explanatory. The Bias/variance property
(b) asserts that $\nabla\ell_{x}(x,S)$ is an unbiased estimator of $\nabla
f(x)$ and has finite variance $\sigma_{0}^{2}$. The accuracy assumption (c)
simply states that the gap $\ell_{x}(x,S)-\ell_{x}(y,S)$ is lower bounded in
expectation by the true gap $f(x)-f(y)$. Note that assumption (c) is trivially
implied by the two intuitive conditions:

$\operatorname*{\mathbb{E}}_{S}[\ell_{x}(x,S)]=f(x)\qquad\textrm{and}\qquad\operatorname*{\mathbb{E}}_{S}[\ell_{x}(y,S)]+\frac{\alpha_{2}}{2}\|x-y\|^{2}\leq
f(y),$

holding for all $x,y\in{\bf R}^{d}$. The first simply says that the model
$\ell_{x}(\cdot,S)$ evaluated at the basepoint $x$ coincides with $f(x)$ in
expectation, while the second asserts that the model $\ell_{x}(\cdot,S)$ lower
bounds $f$ in expectation.

An important consequence of Assumption 8 is that $F$ is strongly convex with
parameter $\alpha_{1}+\alpha_{2}$.

######  Lemma 8.1.

The function $F$ is $(\alpha_{1}+\alpha_{2})$-strongly convex.

###### Proof.

We will show that $F$ satisfies a strong form of a subgradient inequality. To
this end, fix a sample set $S\stackrel{{\scriptstyle
i.i.d}}{{\sim}}{\mathcal{P}}$, and a point $x\in{\bf R}^{d}$ along with a
subgradient $v\in\partial F(x)$. Notice that the inclusion $v-\nabla
f(x)\in\partial r(x)$ holds. Therefore, the vector $v-\nabla
f(x)+\nabla\ell_{x}(x,S)$ is a subgradient of $\ell_{x}(\cdot,S)+r$ at $x$. We
compute

$\displaystyle F(y)-F(x)$
$\displaystyle\geq\operatorname*{\mathbb{E}}_{S}[\ell_{x}(y,S)+r(y)-\ell_{x}(x,S)-r(x)]+\frac{\alpha_{2}}{2}\|y-\bar{x}\|^{2}$
(8.1) $\displaystyle\geq\operatorname*{\mathbb{E}}_{S}[\langle v-\nabla
f(x)+\nabla\ell_{x}(x,S),y-x\rangle]+\frac{\alpha_{1}+\alpha_{2}}{2}\|y-x\|^{2}$
(8.2) $\displaystyle=\langle
v,y-x\rangle+\frac{\alpha_{1}+\alpha_{2}}{2}\|y-x\|^{2},$ (8.3)

where (8.1), (8.2), and (8.3) follow from conditions (c), (a), and (b) of
Assumption 8, respectively. It follows immediately that $\partial F$ is
$(\alpha_{1}+\alpha_{2})$-strongly monotone. Therefore [37, Theorem 12.17]
directly implies that $F$ is $(\alpha_{1}+\alpha_{2})$-strongly convex, as
claimed. ∎

####  8.1.1 Examples: proximal point, proximal gradient, and clipped gradient

Let us look at three examples of models satisfying Assumption 8 and the
corresponding algorithms; see the accompanying Figure 1 and Table 3.
Specifically, for the three examples, we assume the following two conditions
on the loss and the regularizer:

  1. 1.

(Variance) There exists $\sigma>0$ satisfying

$\operatorname*{\mathbb{E}}_{z\sim{\mathcal{P}}}\|\nabla\ell(x,z)-\nabla
f(x)\|^{2}\leq\sigma^{2}\qquad\textrm{for all }x\in{\bf R}^{d}.$

  2. 2.

(Strong convexity) There exist $\alpha,\mu\geq 0$ such that $r$ is
$\mu$-strongly convex and for every $z\in Z$, the loss $\ell(\cdot,z)$ is
$\alpha$-strongly convex.

Algorithm 3 clearly treats $\ell$ and $r$ differently, and therefore $\alpha$
and $\mu$ play distinct roles. Notice that one can always modify the constants
$\alpha$ and $\mu$ while maintaining the sum $\alpha+\mu$, simply by
adding/subtracting a fixed quadratic $\frac{\lambda}{2}\|\cdot\|^{2}$ from
$\ell$ and $r$.

Method | Model $\ell_{x}(y,z)$ | $(\alpha_{1},\alpha_{2},\sigma_{0})$
---|---|---
Prox-point | $\ell(y,z)$ | $(\alpha+\mu,0,\sigma)$
Gradient | $\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle$ | $(\mu,\alpha,\sigma)$
Clipped-grad | $\max\\{\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle,0\\}$ | $(\mu,0,\sigma)$
Table 3: Stochastic proximal point, gradient, and clipped gradient methods.

######  Example 8.1 (Stochastic proximal point).

The simplest stochastic model of a loss is the loss itself:

$\ell_{x}(y,z)=\ell(y,z).$

Algorithm 3 equipped with these models is the proximal point method.
Assumption 8 trivially holds with parameters
$(\alpha_{1},\alpha_{2},\sigma_{0})=(\alpha+\mu,0,\sigma)$. More generally,
given a sample set $S\stackrel{{\scriptstyle i.i.d}}{{\sim}}{\mathcal{P}}$, we
may use the average model $\ell_{x}(y,S)=\frac{1}{|S|}\sum_{z\in S}\ell(y,z)$
whose gradient has the smaller variance $\sigma^{2}_{0}=\sigma^{2}/|S|$.

######  Example 8.2 (Stochastic proximal gradient).

Another class of models is induced by linearizations

$\ell_{x}(y,z)=\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle.$

Algorithm 4 equipped with these models reduces to the stochastic proximal
gradient method. Assumption 8(a) clearly holds with $\alpha_{1}=\mu$.
Assumption 8(b) holds trivially. Assumption 8(c) with $\alpha_{2}=\alpha$
follows from the expression
$\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(x)}\ell_{x}(x,z)=f_{x}(x)$ and
strong convexity of $f_{x}$. More generally, given a sample set
$S\stackrel{{\scriptstyle i.i.d}}{{\sim}}{\mathcal{P}}$, we may declare
$\ell_{x}(y,S)=\frac{1}{|S|}\sum_{z\in S}\ell_{x}(y,z)$ thereby decreasing the
variance $\sigma^{2}_{0}=\sigma^{2}/|S|$.

######  Example 8.3 (Stochastic clipped proximal gradient).

An interesting middle ground between proximal point and gradient models was
proposed in [2]. Namely, suppose that each loss $\ell(\cdot,z)$ is lower
bounded by some known constant, which we may without loss of generality assume
is zero. This assumption is completely innocuous in data scientific contexts.
Then we may use the clipped linear models

$\ell_{x}(y,z)=\max\\{\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle,0\\}.$

Algorithm 3 equipped with these models is the proximal clipped stochastic
gradient method. A quick computation shows that Assumption 8 holds with
$(\alpha_{1},\alpha_{2},\sigma_{0})=(\mu,0,\sigma)$. Given a sample set
$S\stackrel{{\scriptstyle i.i.d}}{{\sim}}{\mathcal{P}}$, we can form the two
models,

$\ell_{x}(x,S)=\frac{1}{|S|}\sum_{z\in
S}\ell(x,z)\quad\textrm{and}\quad\ell_{x}(y,z)=\max\biggl{\\{}\frac{1}{|S|}\sum_{z}\ell(x,z)+\langle\nabla\ell(x,z),y-x\rangle,0\biggr{\\}}.$

It is straightforward to verify that both models $\ell_{x}(\cdot,S)$ are
differentiable at $x$ with gradient
$\nabla\ell_{x}(x,S)=\frac{1}{|S|}\sum_{z\in S}\nabla\ell(x,z)$. Thus the
variance of the gradient improves to $\sigma^{2}_{0}=\sigma^{2}/|S|$.

####  8.1.2 Convergence guarantees.

We are now ready to analyze Algorithm 3. The main idea of the convergence
proof is to establish a one-step improvement guarantee on the function $F$.
Henceforth, we let ${\mathbb{E}}_{t}[\cdot]$ denote the expectation
conditioned on $x_{t}$.

######  Lemma 8.2 (One step improvement).

Suppose that Assumption 8 holds and that $\nabla f$ is $L$-Lipschitz
continuous. Fix a sequence $\eta_{t}<\frac{1}{L}$ for all $t\geq 0$. Then the
iterates generated by Algorithm 3 satisfy:

$\eta_{t}{\mathbb{E}}_{t}[F(x_{t+1})-F(y)]\leq\frac{1-\alpha_{2}\eta_{t}}{2}\|x_{t}-y\|^{2}-\frac{1+\alpha_{1}\eta_{t}}{2}{\mathbb{E}}_{t}\|x_{t+1}-y\|^{2}+\tfrac{\sigma^{2}_{0}\eta_{t}^{2}}{2(1-\eta_{t}L)},$
(8.4)

for all indices $t\geq 0$ and all $y\in{\bf R}^{d}$.

###### Proof.

Observe that the inequality we wish to prove is conditioned on $x_{t}$.
Therefore to simplify notation, set $x:=x_{t}$, $S:=S_{t}$, and
$x^{+}:=x_{t+1}$. Since $x^{+}$ is the minimizer of a
$(\eta_{t}^{-1}+\alpha_{1})$-strongly convex function
$\ell_{x}(\cdot,S)+r+\frac{1}{2\eta_{t}}\|\cdot-x\|^{2}$, we deduce

$\displaystyle\tfrac{\eta_{t}^{-1}+\alpha_{1}}{2}\|x^{+}-y\|^{2}\leq\left(\ell_{x}(y,S)+r(y)+\tfrac{1}{2\eta_{t}}\|y-x\|^{2}\right)-\left(\ell_{x}(x^{+},S)+r(x^{+})+\tfrac{1}{2\eta_{t}}\|x^{+}-x\|^{2}\right).$
(8.5)

We next lower bound $\ell_{x}(x^{+},S)$ using convexity: Assumption 8
guarantees

$\displaystyle\ell_{x}(x^{+},S)$
$\displaystyle\geq\ell_{x}(x,S)+\langle\nabla\ell_{x}(x,S),x^{+}-x\rangle.$

Combining this estimate with (8.5), multiplying through by $2\eta_{t}$, and
taking the expectation yields

$\displaystyle(1+\alpha_{1}\eta_{t}){\mathbb{E}}_{S}\|x^{+}-y\|^{2}$
$\displaystyle\leq\|x-y\|^{2}-2\eta_{t}{\mathbb{E}}_{S}[\ell_{x}(x,S)-\ell_{x}(y,S)]-{\mathbb{E}}_{S}\|x^{+}-x\|^{2}$
$\displaystyle\qquad-2\eta_{t}{\mathbb{E}}_{S}[\langle\nabla\ell_{x}(x,S),x^{+}-x\rangle]-2\eta_{t}{\mathbb{E}}_{S}[r(x^{+})-r(y)].$
(8.6)

Assumption 8(c) implies

$\displaystyle{\mathbb{E}}_{S}[\ell_{x}(x,S)-\ell_{x}(y,S)]$
$\displaystyle\geq f(x)-f(y)+\frac{\alpha_{2}}{2}\|x-y\|^{2}.$

Combining this estimate with (8.6) yields

$\displaystyle(1+\alpha_{1}\eta_{t}){\mathbb{E}}_{S}\|x^{+}-y\|^{2}$
$\displaystyle\leq(1-\alpha_{2}\eta_{t})\|x-y\|^{2}-2\eta_{t}{\mathbb{E}}_{S}[f(x)+r(x^{+})-f(y)-r(y)]$
$\displaystyle~{}~{}~{}-{\mathbb{E}}_{S}\|x^{+}-x\|^{2}-2\eta_{t}{\mathbb{E}}_{S}[\langle\nabla\ell_{x}(x,S),x^{+}-x\rangle].$
(8.7)

Next, smoothness of $f$ guarantees

$f(x)\geq f(x^{+})-\langle\nabla
f(x),x^{+}-x\rangle-\frac{L}{2}\|x^{+}-x\|^{2}.$ (8.8)

Taking expectations in (8.8) and combining the estimate with (8.7) yields

$\displaystyle(1+\alpha_{1}\eta_{t}){\mathbb{E}}_{S}\|x^{+}-y\|^{2}$
$\displaystyle\leq(1-\alpha_{2}\eta_{t})\|x-y\|^{2}-2\eta_{t}{\mathbb{E}}_{S}[F(x^{+})-F(y)]$
$\displaystyle~{}~{}+2\eta_{t}{\mathbb{E}}_{S}[\langle\nabla
f(x)-\nabla\ell_{x}(x,S),x^{+}-x\rangle]-(1-\eta_{t}L){\mathbb{E}}_{S}\|x^{+}-x\|^{2}.$

Young’s inequality in turn guarantees

$2\eta_{t}\langle\nabla
f(x)-\nabla\ell_{x}(x,S),x^{+}-x\rangle\leq\frac{\eta_{t}^{2}\|\nabla
f(x)-\nabla\ell_{x}(x,S)\|^{2}}{1-\eta_{t}L}+(1-\eta_{t}L)\|x^{+}-x\|^{2}.$

Combining the last two inequalities with the finite variance assumption 8(b)
yields

$\displaystyle(1+\alpha_{1}\eta_{t}){\mathbb{E}}_{S}\|x^{+}-y\|^{2}$
$\displaystyle\leq\left(1-\alpha_{2}\eta_{t}\right)\|x-y\|^{2}-2\eta_{t}{\mathbb{E}}_{S}[F(x^{+})-F(y)]+\frac{\sigma^{2}_{0}\eta_{t}^{2}}{1-\eta_{t}L}.$

Rearranging yields (8.4) as claimed. ∎

Using a constant parameter $\eta>0$ yields the following guarantee.

######  Theorem 8.3 (Constant step).

Suppose that Assumption 8 holds and that $\nabla f$ is $L$-Lipschitz
continuous. Fix a sequence
$\eta<\min\\{\frac{1}{2L},\frac{1}{\alpha_{1}},\frac{1}{\alpha_{2}}\\}$. Then
for all points $y\in{\bf R}^{d}$, the estimate holds

${\mathbb{E}}[F(\hat{x}_{t})-F(y)]\leq
2\left(1-\frac{(\alpha_{1}+\alpha_{2})\eta}{2}\right)\left(F(x_{0})-F(y)\right)+\sigma_{0}^{2}\eta,$

where we recursively define
$\hat{x}_{t}=\left(1-\frac{\eta(\alpha_{1}+\alpha_{2})}{1+c_{2}\eta}\right)\hat{x}_{t-1}+\frac{\eta(\alpha_{1}+\alpha_{2})}{1+c_{2}\eta}x_{t}$.

###### Proof.

The assumption $\eta<\frac{1}{2L}$ guarantees
$\tfrac{\sigma^{2}_{0}\eta^{2}}{2(1-\eta L)}\leq\sigma_{0}^{2}\eta$, and
therefore Lemma 8.2 implies

$\eta{\mathbb{E}}_{t}[F(x_{t+1})-F(y)]\leq\frac{1-\alpha_{2}\eta}{2}\|x_{t}-y\|^{2}-\frac{1+\eta\alpha_{1}}{2}{\mathbb{E}}_{t}\|x_{t+1}-y\|^{2}+\sigma^{2}_{0}\eta.$

Lemma A.3 directly implies

${\mathbb{E}}[F(\hat{x}_{t})-F(y)]\leq\left(1-\frac{(\alpha_{1}+\alpha_{2})\eta}{1+\alpha_{1}\eta}\right)\left(F(x_{0})-F(y)+\frac{\alpha_{1}+\alpha_{2}}{2}\|x_{0}-y\|^{2}\right)+\sigma_{0}^{2}\eta.$

Taking into account $\alpha_{1}\eta\leq 1$ and Lemma 8.1 completes the proof.
∎

Combining Algorithm 3 with the geometric decay schedule (Algorithm 8) yields
an algorithm with the following efficiency guarantee, which is immediate from
Lemma B.2.

######  Corollary 8.4 (Efficiency).

Suppose that Assumption 8 holds and that $\nabla f$ is $L$-Lipschitz
continuous. Fix an estimate $\Delta\geq F(x_{0})-\min F$. Then Algorithm 3 may
be augmented with the geometric decay schedule (Algorithm 8) under the
identification

$c=\frac{\alpha_{1}+\alpha_{2}}{2},\quad C=2,\quad h(x)=F(x)-\min
F,\quad\delta_{0}=\min\left\\{\frac{1}{2L},\frac{1}{\alpha_{1}},\frac{1}{\alpha_{2}}\right\\},\quad
D=\sigma_{0}^{2}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[F(x)-\min F]\leq\varepsilon$ after

$\mathcal{O}\left(\frac{L}{\alpha_{1}+\alpha_{2}}\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma_{0}^{2}}{(\alpha_{1}+\alpha_{2})\varepsilon}\right)\qquad\textrm{iterations}.$

###  8.2 Model-based algorithms under state-dependent distributions

Model-based algorithms easily adapt to the setting with state-dependent
distributions by allowing the sampling distribution to vary along the
iterations. The formal procedure is stated in Algorithm 4.

Input: initial $x_{0}$ and sequence
$\\{\eta_{t}\\}_{t=0}^{T}\subset(0,\infty)$.

Step $t=0,1,\ldots,T$:
$\displaystyle\textrm{Sample~{}}S_{t}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{D}(x_{t})$
$\displaystyle\textrm{Set~{}}x_{t+1}=\operatornamewithlimits{arg\,min}_{y}\,\biggl{\\{}\ell_{x_{t}}(y,S_{t})+r(y)+\frac{1}{2\eta_{t}}\|y-x_{t}\|^{2}\biggr{\\}}$

Algorithm 4 Model-based algorithm under state-dependent sampling

Naturally, we will impose Assumption 8 for all static problems
$\eqref{eqn:PS1}$ with ${\mathcal{P}}=\mathcal{D}(x)$.

######  Assumption 9 (Stochastic models under state feedback).

Suppose that Assumption 8 holds for the static problem
$\mathtt{St}(\mathcal{D}(x))$ for all $x\in{\bf R}^{d}$.

For the rest of the section, we suppose that Assumptions 2, 4(b), and 9 hold.
We are now ready to analyze Algorithm 4. The main idea of the convergence
proof is to combine the one-step improvement guarantee (8.4) for the
intermediate function $\varphi_{x_{t}}$ with the function gap inequality (3.2)
to obtain a one-step improvement on $\varphi$.

######  Corollary 8.5 (Key recursion).

Suppose the inequality $\eta_{t}<\frac{1}{L}$ holds for all $t\geq 0$. Then
the iterates generated by Algorithm 4 satisfy the estimate:

$\eta_{t}{\mathbb{E}}_{t}[\varphi(x_{t+1})-\varphi(\bar{x})]\leq\tfrac{1-(\alpha_{2}-\gamma\beta)\eta_{t}}{2}\|x_{t}-\bar{x}\|^{2}-\tfrac{1+(\alpha_{1}-\gamma\beta)\eta_{t}}{2}\|x_{t+1}-\bar{x}\|^{2}+\tfrac{\sigma^{2}_{0}\eta_{t}^{2}}{2(1-\eta_{t}L)}.$
(8.9)

###### Proof.

The function gap inequality (3.2) directly yields

$\displaystyle\varphi_{x_{t}}(x_{t+1})-\varphi_{x_{t}}(\bar{x})$
$\displaystyle\geq\varphi_{\bar{x}}(x_{t+1})-\varphi_{\bar{x}}(\bar{x})-\gamma\beta\|x_{t+1}-\bar{x}\|\cdot\|x_{t}-\bar{x}\|$
$\displaystyle\geq\varphi_{\bar{x}}(x_{t+1})-\varphi_{\bar{x}}(\bar{x})-\frac{\gamma\beta}{2}\|x_{t+1}-\bar{x}\|^{2}-\frac{\gamma\beta}{2}\|x_{t}-\bar{x}\|^{2},$

where the last inequality follows from Young’s inequality. Using this estimate
to lower bound the left side of (8.4) and rearranging completes the proof. ∎

The following theorem summarizes the convergence guarantees of the method with
a constant parameter $\eta>0$.

######  Theorem 8.6 (Convergence guarantees).

Let $x_{t}$ be the iterates generated by Algorithm 4 with a fixed parameter
$\eta>0$. Then the following are true.

  1. 1.

Suppose, we are in the regime $\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<1$
and set $\hat{\alpha}:=\alpha_{1}+\alpha_{2}-\gamma\beta$. Then with the
parameter
$\eta\leq\min\\{\frac{1}{2L},\frac{1}{\alpha_{1}},\frac{1}{\alpha_{2}}\\}$,
the estimate holds:

${\mathbb{E}}\|x_{t}-\bar{x}\|^{2}\leq\left(1-\frac{\hat{\alpha}\eta}{2}\right)^{t}\|x_{0}-\bar{x}\|^{2}+\frac{\sigma^{2}_{0}\eta}{2\hat{\alpha}}.$
(8.10)

  2. 2.

Suppose we are in the regime
$\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<\frac{1}{2}$ and set
$\hat{\alpha}:=\alpha_{1}+\alpha_{2}-2\gamma\beta$. Then with the parameter
$\eta\leq\min\\{\frac{1}{2L},\frac{1}{(\alpha_{1}-\gamma\beta)^{+}},\frac{1}{(\alpha_{2}-\gamma\beta)^{+}}\\}$,
the estimate holds:

${\mathbb{E}}[\varphi\left(\hat{x}_{t}\right)-\varphi(\bar{x})]\leq
2\left(1-\frac{\hat{\alpha}\eta}{2}\right)^{t}\left(\varphi(x_{0})-\varphi(\bar{x})\right)+\sigma^{2}_{0}\eta,$

where we recursively define
$\hat{x}_{t}=\left(1-\frac{\hat{\alpha}\eta}{1+(\alpha_{1}-\gamma\beta)\eta)}\right)\hat{x}_{t-1}+\frac{\hat{\alpha}\eta}{1+(\alpha_{1}-\gamma\beta)\eta)}x_{t}$.

###### Proof.

Notice that the assumption $\eta\leq\frac{1}{2L}$ implies
$\tfrac{\sigma^{2}_{0}\eta^{2}}{2(1-\eta L)}\leq\sigma_{0}^{2}\eta^{2}$.
Combining this estimate with Corollary 8.5 yields:

$\eta{\mathbb{E}}[\varphi(x_{t+1})-\varphi(\bar{x})]\leq\tfrac{1-(\alpha_{2}-\gamma\beta)\eta}{2}{\mathbb{E}}\|x_{t}-\bar{x}\|^{2}-\tfrac{1+(\alpha_{1}-\gamma\beta)\eta}{2}{\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}+\sigma^{2}_{0}\eta^{2}.$
(8.11)

Proof of Claim 1: Lower-bounding the left-side using Lemma 8.1 and rearranging
yields

$\frac{1+(2\alpha_{1}+\alpha_{2}-\gamma\beta)\eta}{2}{\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}\leq\frac{1-(\alpha_{2}-\gamma\beta)\eta}{2}{\mathbb{E}}\|x_{t}-\bar{x}\|^{2}+\sigma^{2}_{0}\eta^{2}.$
(8.12)

The assumption $\alpha_{1}+\alpha_{2}-\gamma\beta>0$ ensures that the left
side is positive, and therefore

${\mathbb{E}}\|x_{t+1}-\bar{x}\|^{2}\leq\left(1-\frac{2(\alpha_{1}+\alpha_{2}-\gamma\beta)\eta}{1+(2\alpha_{1}+\alpha_{2}-\gamma\beta)\eta}\right){\mathbb{E}}\|x_{t}-\bar{x}\|^{2}+\frac{\sigma^{2}_{0}\eta^{2}}{1+(2\alpha_{1}+\alpha_{2}-\gamma\beta)\eta}.$

The assumption $\eta\leq\frac{1}{\alpha_{2}}$ ensures that the coefficient
multiplying ${\mathbb{E}}\|x_{t}-\bar{x}\|^{2}$ lies in $(0,1)$. Iterating the
recursion and taking into account $(\hat{\alpha}+\alpha_{1})\eta\leq 3$
directly yields (8.10).

Proof of Claim 2: In light of the expression (8.11), we aim to apply Corollary
A.3 with $h(x):=\varphi(x)-\varphi(\bar{x})$,
$D_{t}:=\frac{1}{2}{\mathbb{E}}\|x_{t}-\bar{x}\|^{2}$,
$c_{1}:=\alpha_{2}-\gamma\beta$, and $c_{2}:=\alpha_{1}-\gamma\beta$. The
assumption
$\eta\leq\min\\{\frac{1}{(\alpha_{1}-\gamma\beta)^{+}},\frac{1}{(\alpha_{2}-\gamma\beta)^{+}}\\}$
directly implies $1-c_{1}\eta>0$ and $1+c_{2}\eta>0$. An application of
Corollary A.3 yields the estimate:

${\mathbb{E}}[\varphi\left(\hat{x}_{t}\right)-\varphi(\bar{x})]\leq\left(1-\frac{\hat{\alpha}\eta}{1+(\alpha_{1}-\gamma\beta)\eta}\right)^{t}\left(\varphi(x_{0})-\varphi(\bar{x})+\frac{\hat{\alpha}}{2}\|x_{0}-\bar{x}\|^{2}\right)+\sigma^{2}_{0}\eta.$

Lemma 8.1 in turn implies
$\frac{\hat{\alpha}}{2}\|x_{0}-\bar{x}\|^{2}\leq\varphi(x_{0})+\varphi(\bar{x})$.
Taking into account $(\alpha_{1}-\gamma\beta)\eta\leq 1$ completes the proof.
∎

The following corollary obtains efficiency guarantees by combining Algorithm 4
with the geometric decay schedule (Algorithm 8).

######  Corollary 8.7 (Efficiency of Algorithm 4 with geometrically decaying
schedule).

Suppose that Assumptions 2, 4(b), and 9 hold. Then the following are true.

  1. 1.

(Distance) Suppose we are in the regime
$\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<1$ and that we have available an
estimate $\Delta\geq\|x_{0}-\bar{x}\|^{2}$. Define the augmented strong
convexity parameter $\hat{\alpha}=\alpha_{1}+\alpha_{2}-\gamma\beta$. Then
Algorithm 4 may be augmented with the geometric decay schedule (Algorithm 8)
under the identification

$c=\frac{\hat{\alpha}}{2},\quad C=1,\quad
h(x)=\|x-\bar{x}\|^{2},\quad\delta_{0}=\min\left\\{\tfrac{1}{2L},\tfrac{1}{\alpha_{1}},\tfrac{1}{\alpha_{2}}\right\\},\quad
D=\frac{\sigma_{0}^{2}}{2\hat{\alpha}}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[\|x-\bar{x}\|^{2}]\leq\varepsilon$ using

$\mathcal{O}\left(\left(\frac{L+\alpha_{1}+\alpha_{2}}{\hat{\alpha}}\right)\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma_{0}^{2}}{\hat{\alpha}^{2}\varepsilon}\right)\qquad\textrm{samples}.$

  2. 2.

(Function value) Suppose we are in the regime
$\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<\frac{1}{2}$ and that we have
available an estimate $\Delta\geq\varphi(x_{0})-\varphi(\bar{x})$. Define the
augmented strong convexity parameter
$\hat{\alpha}=\alpha_{1}+\alpha_{2}-2\gamma\beta$. Then Algorithm 4 may be
augmented with the geometric decay schedule (Algorithm 8) under the
identification

$c=\frac{\hat{\alpha}}{2},\quad C=2,\quad
h(x)=\varphi(x)-\varphi(\bar{x}),\quad\delta_{0}=\min\left\\{\tfrac{1}{2L},\tfrac{1}{(\alpha_{1}-\gamma\beta)^{+}},\tfrac{1}{(\alpha_{2}-\gamma\beta)^{+}}\right\\},\quad
D=\sigma_{0}^{2}.$

The resulting procedure will generate a point $x$ satisfying
$\varphi(x)-\varphi(\bar{x})\leq\varepsilon$ using

$\mathcal{O}\left(\frac{L+\alpha_{1}+\alpha_{2}}{\hat{\alpha}}\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma_{0}^{2}}{\hat{\alpha}\varepsilon}\right)\qquad\textrm{samples}.$

###### Proof.

This is immediate from Theorem 8.6 and Lemma B.2. ∎

Efficiency guarantees of the stochastic proximal point, proximal gradient, and
clipped gradient methods under Assumptions 1, 2, 3(c), 4(b) follow directly
from Corollary 8.7 and the values of $\alpha_{1}$ and $\alpha_{2}$ in Table 3.

##  9 Inexact repeated minimization

All stochastic algorithms we have discussed so far in each iteration $t$ apply
a single step of a standard algorithm on the static problem
$\mathtt{St}(\mathcal{D}(x_{t}))$. An alternative strategy is to apply an
algorithm to the static problem $\mathtt{St}(\mathcal{D}(x_{t}))$ for a
moderate number of iterations and switch the distribution at the end of the
run. Algorithms based on this principle can be interpreted as inexact repeated
minimization. Such algorithms can be superior in the typical settings where
changing the distribution governing the static problem may be much costlier
than drawing a sample. We will informally call the process of changing the
distribution from $\mathcal{D}(x)$ to $\mathcal{D}(y)$ as deployment. In this
section, we will show that it is possible to maintain the sample complexity
derived in previous sections, while using a number of deployments that is only
logarithmic in the problem parameters.

###  9.1 Model-based algorithms

We begin by analyzing Algorithm 5, which effectively performs repeated
minimization with each subproblem solved approximately by a model-based
algorithm (Algorithm 4). We describe two versions of the procedure. The first
version uses the last iterate of each run to warmstart the next run, while the
second version instead uses the running average of the iterates. Throughout
the section, we suppose that Assumptions 2, 4(b), and 9 hold.

Input: initial $u_{0}$, sequences $\\{\eta_{j}\\}_{j=0}^{J}\subset(0,\infty)$
and $\\{J_{t}\\}_{t=0}^{T}\subset\mathbb{N}$.

for  _$t=0,1,\ldots,T$_ do

Set $x_{0}=u_{t}$

for  _$j=1,\ldots,J_{t}$_ do

$\displaystyle\textrm{Sample~{}}S_{j}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{D}(x_{0})$
$\displaystyle\textrm{Set~{}}x_{j}=\operatornamewithlimits{arg\,min}_{x}\,\biggl{\\{}\ell_{x_{0}}(x,S_{j})+r(x)+\frac{1}{2\eta_{j}}\|x-x_{j-1}\|^{2}\biggr{\\}}$

end for

Set  $u_{t+1}=\left\\{\begin{array}[]{ll}x_{J_{t}}&,\textrm{ if Version I}\\\
\displaystyle\hat{\Gamma}_{J_{t}}x_{0}+\sum_{j=1}^{J_{t}}\frac{\hat{\Gamma}_{J_{t}}\hat{\delta}_{j}}{\hat{\Gamma}_{j}}x_{j}&,\textrm{
if Version II}\end{array}\right.$ where we define
$\displaystyle\hat{\delta}_{j}=\tfrac{(\alpha_{1}+\alpha_{2}-\gamma\beta)\eta_{j}}{1+(\alpha_{1}-\gamma\beta)\eta_{j}}$
and $\displaystyle\hat{\Gamma}_{j}=\prod_{i=1}^{j}(1-\hat{\delta}_{i})$.

end for

Algorithm 5 Stagewise based Minimization

The following theorem shows a one-step improvement guarantee for Algorithm 5,
which explicitly balances the impact of the number of inner iterations $J_{t}$
and the step-size parameters $\eta_{j}$ on the overall performance.

######  Theorem 9.1 (One epoch improvement).

Suppose we are in the regime $\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<1$.

  1. 1.

(Version I) Choose a sequence $\eta_{j}\leq\frac{1}{2L}$. Then the iterates
$u_{t}$ generated by Version I of Algorithm 5 satisfy

${\mathbb{E}}\|u_{t+1}-\bar{x}\|^{2}\leq\left(\Gamma_{J_{t}}+\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\right){\mathbb{E}}\|u_{t}-\bar{x}\|^{2}+\tfrac{2\sigma^{2}_{0}}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\sum_{j=1}^{J_{t}}\frac{\eta_{j}\delta_{j}\Gamma_{J_{t}}}{\Gamma_{j}},$
(9.1)

where we set
$\delta_{j}=\frac{(2\alpha_{1}+2\alpha_{2}-\gamma\beta)\eta_{j}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}$
and $\Gamma_{j}=\prod_{i=1}^{j}(1-\delta_{i})$.

  2. 2.

(Version II) Choose a sequence
$\eta_{j}\leq\min\\{\frac{1}{2L},\frac{1}{(\gamma\beta-\alpha_{1})^{+}},\frac{1}{\alpha_{2}}\\}$.
Then the iterates $u_{t}$ generated by Version II of Algorithm 5 satisfy

${\mathbb{E}}[\varphi(u_{t+1})-\varphi(\bar{x})]\leq\left(2\hat{\Gamma}_{J_{t}}+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}\right){\mathbb{E}}[\varphi(u_{t})-\varphi(\bar{x})]+\sigma^{2}_{0}\sum_{j=1}^{J_{t}}\frac{\eta_{j}\hat{\delta}_{j}\hat{\Gamma}_{J_{t}}}{\hat{\Gamma}_{j}}.$
(9.2)

###### Proof.

Fix an index $t\in\\{0,\dots,T\\}$. We will consider the outcome of the inner
loop $j=1,\ldots,J_{t}$. To simplify notation therefore let us drop the
subscript $t$ from $u_{t}$. Setting $y=\bar{x}$ in Lemma 8.2 yields the
guarantee:

$\eta_{j}{\mathbb{E}}[\varphi_{u}(x_{j})-\varphi_{u}(\bar{x})]\leq\frac{1-\alpha_{2}\eta_{j}}{2}{\mathbb{E}}\|x_{j-1}-\bar{x}\|^{2}-\frac{1-\alpha_{1}\eta_{j}}{2}{\mathbb{E}}\|x_{j}-\bar{x}\|^{2}+\sigma^{2}_{0}\eta^{2}_{j},$
(9.3)

for all $j=1,\ldots,J_{t}$. The function gap inequality (3.2) in turn implies

$\displaystyle\varphi_{u}(x_{j})-\varphi_{u}(\bar{x})$
$\displaystyle\geq\varphi(x_{j})-\varphi(\bar{x})-\gamma\beta\|x_{j}-\bar{x}\|\cdot\|y-\bar{x}\|$
$\displaystyle\geq\varphi(x_{j})-\varphi(\bar{x})-\frac{\gamma\beta}{2}\|x_{j}-\bar{x}\|^{2}-\frac{\gamma\beta}{2}\|u-\bar{x}\|^{2},$

where the last estimate follows from Young’s inequality. Combining with (9.3)
and rearranging, we conclude

$\eta_{j}{\mathbb{E}}[\varphi(x_{j})-\varphi(\bar{x})]\leq\tfrac{1-\alpha_{2}\eta_{j}}{2}{\mathbb{E}}\|x_{j-1}-\bar{x}\|^{2}-\tfrac{1+(\alpha_{1}-\gamma\beta)\eta_{j}}{2}{\mathbb{E}}\|x_{j}-\bar{x}\|^{2}+\tfrac{2\sigma^{2}_{0}\eta^{2}_{j}+\gamma\beta\eta_{j}{\mathbb{E}}\|u-\bar{x}\|^{2}}{2}.$
(9.4)

Suppose now that we are running version I of Algorithm 5. Lower-bounding the
left-side of (9.4) using strong convexity,
$\varphi(x_{j})-\varphi(\bar{x})\geq\tfrac{\alpha_{1}+\alpha_{2}}{2}\|x_{j}-\bar{x}\|^{2}$
(Lemma 8.1), and rearranging yields

${\mathbb{E}}\|x_{j}-\bar{x}\|^{2}\leq\left(\frac{1-\alpha_{2}\eta_{j}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}\right){\mathbb{E}}\|x_{j-1}-\bar{x}\|^{2}+\frac{2\sigma^{2}_{0}\eta^{2}_{j}+\eta_{j}\gamma\beta{\mathbb{E}}\|u-\bar{x}\|^{2}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}.$

The coefficient of ${\mathbb{E}}\|x_{j-1}-\bar{x}\|^{2}$ is precisely
$1-\delta_{j}$. Unrolling the recursion, we conclude

${\mathbb{E}}\|x_{J_{t}}-\bar{x}\|^{2}\leq\Gamma_{J_{t}}{\mathbb{E}}\|x_{0}-\bar{x}\|^{2}+\sum_{j=1}^{J_{t}}\frac{2\sigma^{2}_{0}\eta^{2}_{j}+\eta_{j}\gamma\beta{\mathbb{E}}\|u-\bar{x}\|^{2}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}\cdot\frac{\Gamma_{J_{t}}}{\Gamma_{j}}.$
(9.5)

Next to simplify the sum, algebraic manipulations yield

$\sum_{j=1}^{J_{t}}\frac{\eta_{j}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}\cdot\frac{\Gamma_{J_{t}}}{\Gamma_{j}}=\frac{1}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\sum_{j=1}^{J_{t}}\frac{\delta_{j}\Gamma_{J_{t}}}{\Gamma_{j}}=\frac{1-\Gamma_{J_{t}}}{2\alpha_{1}+2\alpha_{2}-\gamma\beta},$
(9.6)

where the last equality uses Lemma A.1. Note also the expression

$\sum_{j=1}^{J_{t}}\frac{\eta_{j}^{2}}{1+\eta_{j}(2\alpha_{1}+\alpha_{2}-\gamma\beta)}\cdot\frac{\Gamma_{J_{t}}}{\Gamma_{j}}=\frac{1}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\sum_{j=1}^{J_{t}}\frac{\eta_{j}\delta_{j}\Gamma_{J_{t}}}{\Gamma_{j}}.$
(9.7)

Combining (9.6), (9.7), (9.5), and the equality $x_{0}=u$ completes the proof
of (9.1).

Suppose now that we are running version II of Algorithm 5. Then applying Lemma
A.2 to the recursion (9.4) directly implies

${\mathbb{E}}[\varphi(u_{t+1})-\varphi(\bar{x})]\leq\hat{\Gamma}_{J_{t}}\left({\mathbb{E}}[\varphi(x_{0})-\varphi(\bar{x})]+\tfrac{\alpha_{1}+\alpha_{2}-\gamma\beta}{2}\|x_{0}-\bar{x}\|^{2}+\sum_{j=1}^{J_{t}}\tfrac{(\alpha_{1}+\alpha_{2}-\gamma\beta)(2\sigma^{2}_{0}\eta_{j}^{2}+\gamma\beta\eta_{j}\|u-\bar{x}\|^{2})}{2\hat{\Gamma}_{j}(1+(\alpha_{1}-\gamma\beta)\eta_{j})}]\right).$

To simplify the right side, observe first
$\tfrac{\alpha_{1}+\alpha_{2}-\gamma\beta}{2}\|x_{0}-\bar{x}\|^{2}\leq\varphi(x_{0})-\varphi(\bar{x})$
(Lemma 8.1). Next the same argument that justified (9.6) and (9.7) implies the
expressions:

$\sum_{j=1}^{J_{t}}\frac{(\alpha_{1}-\alpha_{2}-\gamma\beta)\eta_{j}}{1+(\alpha_{1}-\gamma\beta)\eta_{j}}\cdot\frac{\hat{\Gamma}_{J_{t}}}{\hat{\Gamma}_{j}}=1-\hat{\Gamma}_{J_{t}}\qquad\textrm{and}\qquad\sum_{j=1}^{J_{t}}\frac{(\alpha_{1}+\alpha_{2}-\gamma\beta)\eta_{j}^{2}}{1+(\alpha_{1}-\gamma\beta)\eta_{j}}\cdot\frac{\hat{\Gamma}_{J_{t}}}{\hat{\Gamma}_{j}}=\sum_{j=1}^{J_{t}}\frac{\eta_{j}\hat{\delta}_{j}\hat{\Gamma}_{J_{t}}}{\hat{\Gamma}_{j}}.$

The claimed estimate (9.2) follows immediately. ∎

Looking at the estimate (9.2), it is natural to choose $J_{t}$ such that the
estimate,
$2\hat{\Gamma}_{J_{t}}+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}\leq\frac{1}{2}(1+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})$,
holds. The following result summarizes the guarantees of such a procedure when
the stepsizes $\eta_{j}$ are constant.

######  Corollary 9.2.

Suppose we are in the regime $\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<1$.

  1. 1.

(Version I) Choose a constant parameter $\eta\leq\frac{1}{2L}$ and set

$J_{t}=\left\lceil\left(1+\frac{1}{(2\alpha_{1}+2\alpha_{2}-\gamma\beta)\eta}\right)\log\left(\frac{2\alpha_{1}+2\alpha_{2}-\gamma\beta}{\alpha_{1}+\alpha_{2}-\gamma\beta}\right)\right\rceil\qquad\forall
t\geq 0.$

Then the iterates $u_{t}$ generated by Version I of Algorithm 5 satisfy

${\mathbb{E}}\|u_{t}-\bar{x}\|^{2}\leq\left(\frac{1}{2}(1+\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta})\right)^{t}{\mathbb{E}}\|u_{0}-\bar{x}\|^{2}+\tfrac{2\sigma^{2}_{0}\eta}{\alpha_{1}+\alpha_{2}-\gamma\beta}.$
(9.8)

  2. 2.

(Version II) Choose
$\eta\leq\min\\{\frac{1}{2L},\frac{1}{(\gamma\beta-\alpha_{1})^{+}},\frac{1}{\alpha_{2}}\\}$
and set

$J_{t}=\left\lceil\left(1+\frac{1}{(\alpha_{1}+\alpha_{2}-\gamma\beta)\eta}\right)\log\left(\frac{2(\alpha_{1}+\alpha_{2})}{\alpha_{1}+\alpha_{2}-\gamma\beta}\right)\right\rceil\qquad\forall
t\geq 0.$

Then the iterates $u_{t}$ generated by Version II of Algorithm 5 satisfy

${\mathbb{E}}[\varphi(u_{t})-\varphi(\bar{x})]\leq\left(\frac{1}{2}(1+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})\right)^{t}{\mathbb{E}}[\varphi(u_{0})-\varphi(\bar{x})]+\frac{2\sigma^{2}_{0}\eta}{1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}}.$
(9.9)

###### Proof.

With the constant parameter $\eta$, the estimate (9.1) becomes

${\mathbb{E}}\|u_{t}-\bar{x}\|^{2}\leq\left(\left(1-\tfrac{(2\alpha_{1}+2\alpha_{2}-\gamma\beta)\eta}{1+\eta(2\alpha_{1}+\alpha_{2}-\gamma\beta)}\right)^{j_{t-1}}+\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\right){\mathbb{E}}\|u_{t-1}-\bar{x}\|^{2}+\tfrac{2\sigma^{2}_{0}\eta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta},$

where we used the equality
$\sum_{j=1}^{j_{t-1}}\frac{\delta_{j}\Gamma_{j_{t-1}}}{\Gamma_{j}}=1-\Gamma_{j_{t-1}}$
(Lemma A.1). The definition of $j_{t-1}$ ensures that the coefficient of
${\mathbb{E}}\|u_{t-1}-\bar{x}\|^{2}$ is at most
$\frac{1}{2}(1+\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta})$ and
therefore

${\mathbb{E}}\|u_{t}-\bar{x}\|^{2}\leq\frac{1}{2}(1+\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}){\mathbb{E}}\|u_{t-1}-\bar{x}\|^{2}+\tfrac{2\sigma^{2}_{0}\eta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta},$

Unrolling the recursion in $t$ completes the proof of (9.8). Similarly, with
the constant parameter $\eta$, the estimate (9.2) becomes

${\mathbb{E}}[\varphi(u_{t})-\varphi(\bar{x})]\leq\left(2\left(1-\tfrac{\eta(\alpha_{1}+\alpha_{2}-\gamma\beta)}{1+(\alpha_{1}-\gamma\beta)\eta}\right)^{j_{t-1}}+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}\right){\mathbb{E}}[\varphi(u_{t-1})-\varphi(\bar{x})]+\sigma^{2}_{0}\eta.$

The definition of $j_{t-1}$ ensures that the coefficient of
${\mathbb{E}}[\varphi(u_{t-1})-\varphi(\bar{x})]$ is at most
$\frac{1}{2}(1+\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})$. Iterating the
recursion in $t$ completes the proof of (9.9). ∎

Consequently, we may equip Algorithm 5 with a geometrically decaying stepsize.
The efficiency estimates of the resulting procedure are recorded in the
following corollary.

######  Corollary 9.3.

Suppose that Assumptions 2, 4(b), and 9 hold, and that we are in the regime
$\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}<1$.

  1. 1.

(Version I) Suppose we have available an estimate
$\Delta\geq\|x_{0}-\bar{x}\|^{2}$. Define the augmented strong convexity
parameter $\hat{\alpha}=\alpha_{1}+\alpha_{2}-\gamma\beta$. Then Algorithm 5
(Version I) may be augmented with the geometric decay schedule (Algorithm 8)
with parameters:

$\psi(\delta)\equiv\frac{1}{2}\left(1-\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta}\right),\quad
C=1,\quad h=\|\cdot-\bar{x}\|^{2},\quad
D=\frac{2\sigma^{2}_{0}}{\alpha_{1}+\alpha_{2}-\gamma\beta},\quad\delta_{0}=\frac{1}{2L}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[\|x-\bar{x}\|^{2}]\leq\varepsilon$ using

$\mathcal{O}\left((1-\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta})^{-1}\cdot\left(\log\left(\frac{\Delta}{\varepsilon}\right)+\log\left(\frac{\sigma^{2}_{0}}{\hat{\alpha}L\varepsilon}\right)\right)\right)$
(9.10)

deployments and

$\mathcal{O}\left((1-\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta})^{-1}\log\left((1-\tfrac{\gamma\beta}{2\alpha_{1}+2\alpha_{2}-\gamma\beta})^{-1}\right)\cdot\left(\frac{L}{\hat{\alpha}}\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma_{0}^{2}}{\hat{\alpha}^{2}\varepsilon}\right)\right)$
(9.11)

samples.

  2. 2.

(Version II) Suppose we have available an estimate
$\Delta\geq\varphi(x_{0})-\min\varphi$. Define the augmented strong convexity
parameter $\hat{\alpha}=\alpha_{1}+\alpha_{2}-\gamma\beta$. Then Algorithm 5
(Version II) may be augmented with the geometric decay schedule (Algorithm 8)
with parameters:

$\psi(\delta)\equiv\frac{1}{2}\left(1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}\right),~{}C=1,~{}h(\cdot)=\varphi(\cdot)-\varphi(\bar{x}),~{}D=\frac{2\sigma^{2}_{0}}{1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}}},~{}\delta_{0}=\min\\{\tfrac{1}{2L},\tfrac{1}{(\gamma\beta-\alpha_{1})^{+}},\tfrac{1}{\alpha_{2}}\\}.$

The resulting procedure will generate a point $x$ satisfying
${\mathbb{E}}[\varphi(x)-\min\varphi]\leq\varepsilon$ using

$\mathcal{O}\left((1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})^{-1}\cdot\left(\log\left(\frac{\Delta}{\varepsilon}\right)+\log\left(\frac{\sigma^{2}_{0}}{1-\frac{\gamma\beta}{\alpha_{1}+\alpha_{2}}}\cdot\frac{1}{L\varepsilon}\right)\right)\right)$

deployments and

$\mathcal{O}\left(\left((1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})^{-1}\right)\cdot\log((1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})^{-1})\cdot\left(\frac{1}{\hat{\alpha}\delta_{0}}\log\left(\frac{\Delta}{\varepsilon}\right)+\frac{\sigma_{0}^{2}}{(1-\tfrac{\gamma\beta}{\alpha_{1}+\alpha_{2}})\hat{\alpha}\varepsilon}\right)\right)$

samples.

###### Proof.

We prove the efficiency of Version I of Algorithm 5; the proof for version II
is completely analogoues. The procedure invokes the algorithm in
$k=0,1,\ldots,K$ stages, where $K=\lceil
1+\log_{2}(\frac{D\eta_{0}}{\varepsilon})\rceil$. Applying Lemma B.2, the
number of deployments coincides with the sum

$\sum_{k=0}^{K}T_{k}=\left\lceil\frac{1}{\psi(\delta_{0})}\cdot\log\left(\frac{2C\Delta}{\varepsilon}\right)\right\rceil+\sum_{k=1}^{K}\left\lceil\frac{\log(4C)}{\psi(2^{-k}\delta_{0})}\right\rceil.$

Simplifying yields (9.10). The total number of samples used in stage $k$ is
simply