PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic optimization with decision-dependent distributions

Dmitriy Drusvyatskiy, Lin Xiao

arXiv:2011.11173v2math.OC

TL;DR

When decisions change the data distribution, directly solving the induced-distribution objective is generally out of reach. The paper interprets state-dependent stochastic algorithms as inexact static methods with a linearly decaying bias, and establishes linear convergence for repeated minimization and proximal point when ρ < 1.

  • Problem

    When data distributions depend on decisions, directly solving the induced-distribution objective is generally out of reach, motivating stochastic methods on successive induced static problems.

    Source: §1.1 · p. 3

  • Method

    Under mild conditions, state-dependent stochastic algorithms act as inexact versions of their static-problem counterparts, with bias decaying linearly in distance to equilibrium.

    Source: §1.1 · p. 3

  • Results

    Repeated minimization and proximal-point methods converge linearly when ρ < 1.

    Source: §5.2 · p. 22

  • Takeaways & Limitations

    State-dependent stochastic methods can be interpreted as implicitly solving the static problem induced by their equilibrium.

    Source: §1.1 · p. 3, §4 · p. 9

    Accelerated methods are guaranteed only when ρ ≲ κ^-1/4, and whether the extra κ^-1/4 factor is necessary remains open.

    Source: §4.3 · p. 15

Abstract

from arXiv · show

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 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.

1 Introduction

Stochastic optimization typically assumes a fixed sampling distribution, but deployed decisions can change the population that generates data. This paper studies standard stochastic algorithms for finding decisions optimal under their own induced distributions.

1 Introduction

  • When decisions change the data distribution, standard stochastic optimization’s fixed-distribution assumption fails, motivating analysis of stochastic methods under feedback-driven shifts.Examples include people changing features to improve their chance of a positive classification and lending decisions altering later credit-score distributions.Source: §1 · p. 2

1.1 Problem setting

  • An equilibrium is a decision optimal for the distribution it induces; under mild conditions, state-dependent stochastic algorithms implicitly solve that equilibrium’s static problem.Their error or bias decays linearly with distance to the equilibrium, and sufficiently weak state dependence permits the same efficiency estimates as on the induced static problem.Source: §1.1 · p. 3

1.2 Application: strategic classification

  • Strategic classification illustrates the setting: agents adapt features in response to a classifier, so the institution seeks to minimize classification error under the resulting response distribution.The paper does not restrict the framework to strategic behavior; it requires the distribution map to have a relatively small Lipschitz constant.Source: §1.2 · pp. 3–4

1.3 Related work

  • The work extends performative-prediction analyses to a wider range of stochastic algorithms, while online-convex-optimization reductions entail stronger boundedness assumptions.The stated guarantees cover stochastic gradient, clipped gradient, proximal point, and dual averaging methods, including accelerated and proximal variants.Source: §1.3 · pp. 4–5

1.4 Outline of the paper

  • The paper first develops distribution-shift sensitivity lemmas, formalizes assumptions including Lipschitz continuity of distributions in decisions, and then presents results in Sections 5–9.Source: §1.4 · p. 5

2 Sensitivity to distributional shift

This section develops sensitivity bounds for how distribution changes affect expected losses and gradients. Its key refinement controls function gaps multiplicatively, which can yield quadratic error when distribution distance tracks iterate distance.

2 Sensitivity to distributional shift

  • The analysis treats state-dependent updates as steps on static problems that vary over iterations, using problem stability under distribution perturbations.Source: §2 · p. 6
  • Wasserstein-1 distance bounds the deviation between gradients under two distributions, under the stated smoothness assumption.Source: §2 · p. 6
  • The function-gap bound is multiplicative in iterate distance and distribution distance; when the latter is on the order of iterate distance, the error is quadratic.The paper motivates this bound because a linear bound on absolute function-value error is too crude for algorithm analysis.Source: §2 · pp. 6–7

3 Assumptions under state-dependent sampling

The section defines equilibrium for state-dependent sampling and states assumptions used to analyze it. It identifies ρ < 1 as the regime where typical stochastic algorithms implicitly solve the static problem induced by an equilibrium.

3 Assumptions under state-dependent sampling

  • The analysis assumes the distribution map D(·) is Lipschitz, controlling how much the sampling distribution changes with the decision.Under the stated assumptions, function-value differences across distributions are bounded in proportion to the distance between their indexing decisions and evaluation points.Source: §3 · p. 7
  • An equilibrium point x̄ solves the static problem St(D(x̄)); it is generally distinct from a minimizer of the overall decision-dependent problem.The distance between them can be bounded under strong convexity assumptions [41, Theorem 4.3].Source: §3 · pp. 7–8
  • The paper assumes an equilibrium exists and uses context-dependent variants of strong convexity and smoothness in its convergence analysis.The existence assumption is supported by sufficient conditions including strong convexity or continuity, convexity, and a compact regularizer domain.Source: §3 · p. 8

3.1 The interesting parameter regime ρ < 1

  • When ρ < 1, typical stochastic algorithms implicitly solve the static problem St(D(x̄)) induced by an equilibrium point x̄.The repeated-minimization map is a contraction in this regime; it can diverge when ρ ≥ 1.Source: §3.1 · p. 9
  • With state-dependent sampling, the stochastic gradient is unbiased for the current distribution’s gradient but biased relative to the equilibrium-distribution gradient.For ρ < 1, the two gradients are well aligned, with the angle’s cosine given as 1 − ρ².Source: §3.1 · p. 9
  • In the Gaussian illustration, the vector fields have acute angles and trajectories converge to the origin for ρ ∈ (0, 1), while trajectories may diverge at ρ = 1.25.The origin is the unique equilibrium in the example when ρ² ≠ 1.Source: §3.1 · p. 9
  • The example’s intuition is made precise for r = 0; with regularization, the cited estimate is not useful because its right-hand side may stay bounded away from zero.The subsequent arguments use the underlying deviation bound directly.Source: §3.1 · p. 9

4 Outline of the main results

The section outlines algorithms that solve the static problem induced by the equilibrium decision and provide equilibrium guarantees across proximal, online, stochastic-gradient, model-based, and inexact repeated-minimization methods. It also describes repeated minimization with stochastic or accelerated proximal-gradient methods as inexact solvers, with sample complexity comparable to online methods and only logarithmically many deployments.

4.1 Calm and contractive algorithms (Section 5)

  • Calmness of updates to distribution shifts plus contraction on the equilibrium-induced static problem yields linear convergence; repeated minimization and proximal point work for ρ < 1, while proximal gradient also converges for ρ < 1.The update contracts toward the equilibrium with ratio q + γτ. Experiments show proximal point can succeed in a wider regime than repeated minimization, which may oscillate.Source: §4.1 · p. 11

4.2 Reduction to online convex optimization (Section 6)

  • When ρ < 1/2, online algorithms with regret O(log t) yield an average iterate with convergence rate O(log(t)/(1−2ρ)t) under state-dependent sampling.The reduction covers proximal gradient, regularized dual averaging, and FTRL; unlike finer stochastic analyses, it requires bounded gradients and a bounded domain, while finite variance can replace gradient bounds in stochastic optimization.Source: §4.2 · pp. 12–13

4.3 Stochastic gradient methods (Section 7)

  • Direct analysis of stochastic gradient descent yields controlled function-gap convergence when ρ < 1/2 and squared-distance convergence when ρ < 1; accelerated stochastic gradient is possible in the slightly suboptimal regime ρ ≲ κ^-1/4.The gradient estimator is biased, with bias proportional to distance from equilibrium.Source: §4.3 · pp. 13–14

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

  • Model-based stochastic proximal-gradient, proximal-point, and clipped-gradient methods achieve squared-distance error at most ε when ˜ρ < 1, with appropriate step sizes.They approximate each sampled loss using a model: linear for proximal gradient, the loss itself for proximal point, and a truncated linear model for clipped gradient; the latter requires r to be μ-strongly convex.Source: §4.4 · pp. 16–17

4.5 Inexact repeated minimization (Section 9)

  • Inexact repeated minimization extends the analyzed algorithms to reduce deployments to logarithmically many in problem parameters without sacrificing sample efficiency.Deployment means modifying the sampling distribution, which can be more expensive than drawing another sample.Source: §4.5 · p. 18
  • For ˜ρ = γβ < 1, stochastic proximal gradient and proximal point use ˜α = α + μ, while clipped gradient uses ˜α = μ as inexact solvers achieving E[ϕ(x) − ϕ(¯x)] ≤ ε.Source: §4.5 · pp. 18–19
  • Theorem 4.7's sample complexity is essentially the same as Theorem 4.6's, while repeated minimization uses only logarithmically many deployments; on Example 3.1 it performed similarly to online algorithms.The experiment capped deployments at 20 and scheduled inner iterations according to Corollary 9.3.Source: §4.5 · p. 19, Figure 7 · p. 19
  • The accelerated stochastic proximal-gradient variant also supports repeated minimization in the nearly optimal regime ρ < 1, without an extra factor κ^-1/4 and with logarithmically many deployments.Source: §4.5 · pp. 19–20

5 Calm and contractive methods

The section analyzes state-dependent updates through their stability under distributional perturbations. Combining this stability with contraction on the equilibrium's static problem yields linear convergence guarantees.

5 Calm and contractive methods

  • The section frames state-dependent updates as proximal-point or proximal-gradient steps on the induced static problem St(D(xt)); repeated minimization is the proximal-point case with η = ∞.Source: §5 · p. 20

5.1 An interlude: calmness of algorithms for St(ν)

  • Under strong convexity, repeated-minimization, proximal-point, and proximal-gradient updates are τ-stable to distribution changes, with constants listed in Table 2.Source: §5.1 · pp. 20–21, Table 2 · p. 21

5.2 Linear convergence of conceptual algorithms

  • Under Assumptions 1, 2, 3(a), and 4(a), repeated minimization, proximal point, and proximal gradient converge linearly to x̄ when ρ < 1.Source: §5.2 · pp. 22–23

6 Reduction to online convex optimization

The section reduces state-dependent stochastic optimization to online convex optimization: regret bounds yield convergence guarantees for average iterates. The reduction is broad, but it inherits online optimization’s stronger assumptions.

6.1 Review of online convex optimization

  • Online convex optimization permits losses that are not sampled from a distribution, but meaningful regret bounds require a bounded domain and bounded gradients.The domain has diameter D, and gradient norms are bounded by G.Source: §6.1 · p. 23

6.2 Reduction

  • The reduction applies online algorithms under state-dependent sampling and bounds the average iterate’s expected objective gap by the regret bound scaled by 1/((1−2ρ)t).Theorem 6.1 assumes Assumptions 1, 2, and 3(a), and requires a uniform regret bound.Source: §6.2 · pp. 23–24
  • Known regret bounds give an O(log(t)/((1−2ρ)t)) convergence rate under state-dependent sampling for proximal gradient, regularized dual averaging, and FTRL.The guarantees use the assumptions of the respective online optimization analyses.Source: §6.2 · p. 24

7 Stochastic gradient methods

The section treats decision-dependent sampling as a biased stochastic-gradient problem, with bias bounded linearly by distance to the solution. It derives convergence guarantees for proximal gradient and accelerated variants under distinct parameter regimes.

7 Stochastic gradient methods

  • State-dependent sampling is modeled by a gradient oracle whose bias is at most B∥x−x̄∥ and whose variance is at most σ².For the state-dependent-distribution setting described, B is set to γβ.Source: §7 · p. 25

7.1 Stochastic proximal gradient method

  • For stochastic proximal gradient, geometric stepsize decay yields distance accuracy when ρ<1 and function-value accuracy when ρ<1/2.The distance guarantee uses an initial squared-distance estimate; the function-value guarantee uses an initial objective-gap estimate.Source: §7.1 · p. 28

7.2 Accelerated Stochastic proximal gradient method

  • The accelerated stochastic proximal gradient method has a convergence guarantee in the regime ρ≤1/2, with γ0=α̂ and stepsize ηt=1/(4L).The accelerated method can also be combined with minibatch restart to obtain an ε-accurate point using stochastic gradient samples.Source: §7.2 · p. 29
  • The accelerated analysis uses a term previously discarded as nonnegative: ∥yt−vt∥² balances the stochastic-gradient bias.Source: §7.2 · p. 29

8 Model-based algorithms

Section 8 extends proximal-point-type algorithms from static problems to decision-dependent distributions, developing static and state-dependent convergence and efficiency guarantees. It also gives an ε-gap guarantee for the resulting procedure and efficiency guarantees for three stochastic methods under specified assumptions.

8.1 Model-based algorithms for a static problem

  • For smooth losses, static model-based convergence guarantees need only a bounded variance, rather than the bounded second moment of subgradients required by [3] [16].The analysis also establishes that the objective F is (α1 + α2)-strongly convex under the model assumptions.Source: §8.1 · pp. 29–31

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

  • Stochastic proximal point, proximal gradient, and clipped proximal gradient arise from different model choices; the clipped model assumes each loss is lower bounded.The proximal-gradient model uses linearizations, while the clipped model is an intermediate choice between proximal point and gradient models.Source: §8.1.1 · pp. 31–32

8.1.2 Convergence guarantees.

  • With smooth f and Assumption 8, a constant-step model-based method has convergence guarantees, and a geometric decay schedule yields an ε-accurate function value.The efficiency guarantee uses an estimate of the initial function gap.Source: §8.1.2 · pp. 33–34

8.2 Model-based algorithms under state-dependent distributions

  • Under state-dependent sampling, model-based algorithms use distributions D(x_t); their key recursion combines static one-step improvement with a function-gap inequality.The analysis assumes Assumptions 2, 4(b), and 9.Source: §8.2 · p. 34
  • With a fixed step, Theorem 8.6 gives convergence guarantees in regimes governed by α1, α2, and γβ.The theorem presents separate regimes and bounds for distance and function-value convergence under stated step-size conditions.Source: §8.2 · p. 35
  • With geometric decay, Algorithm 4 has efficiency guarantees for both distance to the equilibrium and function value, under the respective regimes and initial-gap estimates.The distance guarantee bounds the initial squared distance; the function-value guarantee bounds the initial objective gap.Source: §8.2 · p. 36
  • The procedure generates x with ϕ(x)−ϕ(¯x)≤ε, and efficiency guarantees for stochastic proximal point, proximal gradient, and clipped gradient follow under Assumptions 1, 2, 3(c), and 4(b).The efficiency guarantees follow from Corollary 8.7 and the values of α1 and α2 in Table 3.Source: §8.2 · p. 36

9 Inexact repeated minimization

This section develops inexact repeated minimization strategies that solve each decision-induced static problem over multiple iterations before changing the distribution, maintaining sample complexity with logarithmically many deployments. It presents model-based and accelerated variants, as well as two stagewise restart strategies—growing minibatches or decreasing step-sizes—that warm-start each stage from the previous output.

9 Inexact repeated minimization

  • Inexact repeated minimization can preserve the sample complexity of earlier algorithms while reducing deployments to a logarithmic number.It does so by running an algorithm on the static problem induced by the current decision for a moderate number of iterations before switching distributions.Source: §9 · p. 36

9.1 Model-based algorithms

  • Algorithm 5 approximately solves each induced static problem, using either the last iterate or the running average to warmstart the next run, and guarantees one-epoch improvement.The theorem assumes its stated parameter regime; Version I and Version II use different step-size conditions.Source: §9.1 · p. 37
  • With a geometric stepsize schedule and an available initial-error estimate, either Algorithm 5 version can produce an ε-accurate point under the stated parameter regime.Version I measures accuracy by squared distance, while Version II measures it by objective gap.Source: §9.1 · pp. 39–40

9.2 Accelerated method

  • The stagewise accelerated stochastic gradient method retains the sample efficiency of its online counterpart while requiring only logarithmically many deployments.The result combines Algorithm 6 with the minibatch restart strategy.Source: §9.2 · pp. 42–43

A Averaging lemma

  • The appendix’s averaging lemma bounds the value of a convex function at a running-average iterate from a weighted recursion under stated coefficient conditions.The lemma provides an averaging tool for stochastic iterates.Source: A Averaging lemma · pp. 46–47
  • The constant-parameter corollary establishes an estimate under the assumptions of Lemma A.2, though its form is not included in the supplied passage.It assumes fixed δ_t = δ and ω_i = ω.Source: A Averaging lemma · p. 48

B Stagewise scheme for improved efficiency

  • The section proposes complementary restarts: exponentially increasing minibatches to reduce gradient-estimator variance, or geometrically decreasing step-sizes.Both strategies are intended to improve the efficiency of constant-step stochastic algorithms.Source: B Stagewise scheme for improved… · p. 48

B.1 Minibatch restart

  • Minibatch restart targets E[h(y)] ≤ ε and reduces gradient variance by a factor of m with batch size m, but is suited to settings where minibatch computation is feasible.The procedure uses exponentially increasing batch sizes and warm-starts each stage from the preceding output; it may be unsuitable when minibatch updates are computationally prohibitive.Source: §B.1 · pp. 48–49

B.2 Geometric decay schedule

  • Geometric decay sets δ_k = δ_0 2^-k and targets E[h(y_k)] ≤ 2Dδ_k per stage, ultimately returning a point with E[h(y_K)] ≤ ε.The schedule warm-starts from the previous stage; the passage notes a linear-ψ case ψ(δ) = cδ but omits the efficiency estimate’s form.Source: §B.2 · pp. 49–50

C Proof of Theorem 7.5

The proof uses estimate sequences to control expected objective error, then applies the resulting bound under parameter choices that meet Theorem 7.5’s regime.

C Proof of Theorem 7.5

  • In expectation, the local models evaluated at x̄ lower-bound ϕ(x̄), supplying a key condition for the basic estimate-sequence lemma.The section constructs estimate sequences by aggregating local models across iterations.Source: C Proof of Theorem 7.5 · p. 51
  • The proof establishes the objective-error estimate through a sequence of bounds and an induction on the estimate-sequence error term.The error term is updated recursively using δt and ηt before the final guarantee is obtained.Source: C Proof of Theorem 7.5 · pp. 51–52
  • Theorem 7.5 follows by applying the estimate-sequence bound after choosing ηt = 1/(4L) and γ0 = ˆα and satisfying its parameter regime.The proof states that these choices yield the required δt values and that solving for ρ gives the regime assumed by Theorem 7.5.Source: C Proof of Theorem 7.5 · p. 52

C.1 Proof of Theorem C.2

The proof extends the estimate-sequence argument to account for the bias in stochastic gradients, then controls the resulting error terms to establish the needed bound.

C.1 Proof of Theorem C.2

  • The proof carries the deviation between the true gradient and expected stochastic gradient forward to offset bias, rather than discarding a nonnegative term as in the static setting.It defines the bias as Δt := ∇f(yt−1) − E[gt].Source: §C.1 · p. 52
  • The argument combines estimate (C.8) with Lemmas C.3 and C.4 to obtain a subsequent result, and its approach closely parallels [31, Theorem 3], which builds on Nesterov’s treatment [37, p. 78].Source: §C.1 · pp. 52–53
  • The argument seeks to bound Pt by a constant multiple of ηtσ², which supports the recursive choice of the estimate-sequence error ξt.The section simplifies Pt and uses bounds on the stochastic-gradient and bias terms to complete the induction.Source: §C.1 · pp. 53–54

D.1 Proof of Lemma C.3

The passage states that the proof is complete.

D.1 Proof of Lemma C.3

  • The proof is complete.No further claim is stated in this passage.Source: §D.1 · p. 54

D.2 Proof of Lemma C.4

The appendix proofs control proximal updates under distance-dependent gradient error and use the resulting estimates to derive an angle condition. They rely on smoothness, proximal-map nonexpansiveness, and elementary inequalities.

D.2 Proof of Lemma C.4

  • The Lemma C.4 proof accounts for bias using smoothness and proximal-map nonexpansiveness, then applies Young’s inequality to complete the bound.Source: §D.2 · pp. 54–55

D.3 Proof of Lemma C.5

  • Lemma D.1 assumes η ≤ 2/L and gradient error bounded by B times distance to the solution, then supplies a proximal update estimate used to prove Lemma C.5.The proof specializes the lemma with y = y_{t−1} and v = E[g_t].Source: §D.3 · p. 55

E Estimate (3.4) implies an angle condition

F Numerical experiments on strategic classification

The experiments use a strategic-classification task built from historical financial records, with individuals adapting three features after classifier deployment. The stated parameter estimate is crude, and numerical methods work well over a wider regime.

F Numerical experiments on strategic classification

  • The strategic-classification experiment uses 15,000 Kaggle financial records, ten features, and a regularized logistic-loss classifier.The label indicates whether 90 days have passed since delinquency; features are standardized and the data are subsampled equally by label.Source: F Numerical experiments on strategic… · p. 57
  • Individuals strategically adapt credit utilization, open credit lines, and real-estate loans after deployment, while their labels remain unchanged.The feature update corresponds to linear utility and quadratic adaptation cost.Source: F Numerical experiments on strategic… · p. 57
  • For γ ∈ (0, α/2), the parameter estimate is described as crude, and numerical methods work well in a much wider regime.Source: F Numerical experiments on strategic… · p. 57
Loading 2011.11173v2…