PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-stationary Stochastic Optimization

O. Besbes, Y. Gur, A. Zeevi

arXiv:1307.5449v2math.PRcs.LGstat.ML

TL;DR

Non-stationary stochastic optimization lacks the fixed-cost-function assumption of stationary settings. This paper uses a variation budget to connect online convex optimization with stochastic approximation and shows that sublinear variation permits long-run-average optimality and sublinear dynamic-oracle regret.

  • Problem

    The paper studies how changing cost functions affect achievable performance in sequential stochastic optimization when stationarity does not hold.

  • Method

    The paper models a sequence of convex cost functions and bridges adversarial online convex optimization with non-stationary stochastic approximation.

  • Results

    When variation is sublinear in T, long-run-average optimal policies exist and sublinear regret against a dynamic oracle is achievable.

  • Takeaways & Limitations

    A sublinear variation budget permits performance guarantees in a temporally changing stochastic environment.

  • Takeaways & Limitations

    The framework does not provide performance guarantees relative to a dynamic-oracle benchmark in the non-stationary stochastic setting.

Abstract

from arXiv · show

We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve long-run-average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: adversarial online convex optimization; and the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the "price of non-stationarity," which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one.

1 Introduction and Overview

The paper models sequential stochastic optimization with a time-varying sequence of convex cost functions constrained by a variation budget. It characterizes when dynamic-oracle regret can be sublinear, quantifies non-stationarity’s cost, and connects adversarial online convex optimization with stochastic approximation to construct optimal policies.

  • The non-stationary SA problem: The non-stationary formulation replaces one unknown cost function with a sequence of convex functions and feedback that depends on the current function.The feedback may provide noisy function values or noisy gradients, with a corresponding sequence of minimizers defining the moving target.
  • Necessary and sufficient conditions for sublinear regret: Sublinear regret has a sharp variation-budget dichotomy: it is impossible when VT is linear in T, but achievable when VT is sublinear in T.Thus, sublinear variation is both the threshold for long-run-average optimality and the regime supporting sublinear regret relative to the dynamic oracle.
  • Complexity characterization: The paper characterizes minimax regret orders for convex and strongly convex settings, with α equal to 1/3 or 1/2 depending on convexity and feedback.Suitable rate-optimal policies attain the derived lower bounds.
  • The “price of non-stationarity” and policy construction: The results express the price of non-stationarity through the variation-budget radius and show that sublinear-regret and rate-optimality properties can transfer from adversarial online convex optimization.This bridge provides a meta principle for adapting well-performing online policies to the non-stationary stochastic setting, although static hindsight benchmarks do not guarantee performance against a dynamic oracle.

2 Problem Formulation

The paper formulates non-stationary stochastic optimization over convex costs with noisy cost or gradient feedback and non-anticipating policies. It restricts temporal evolution through a variation budget and evaluates policies against a dynamic oracle, contrasting this target with static-oracle OCO.

  • Preliminaries and admissible polices: Decisions occur in a convex, compact action set, with each action followed by noisy cost or gradient feedback.The feedback is conditionally unbiased for either the cost or its gradient, with uniformly bounded second moment.
  • Preliminaries and admissible polices: Admissible policies are measurable, non-anticipating mappings of past actions and observations, while dependence on a random variable permits randomized strategies.The policy class is denoted Pφ and depends on the feedback structure.
  • Temporal uncertainty and regret: The variation budget VT restricts how admissible cost-function sequences change over time under a sup-norm variation measure.The budget still permits continuous changes, discrete shocks, and non-constant rates of change.
  • Temporal uncertainty and regret: Regret is measured against a dynamic oracle, with nature selecting the worst sequence subject to the variation budget; sublinear and rate-optimal policies are defined accordingly.The dynamic oracle benchmarks performance against the period-by-period optimum, while minimax regret is the least worst-case regret guaranteed by an admissible policy.
  • Contrasting with the adversarial online convex optimization paradigm: Unlike static-oracle adversarial OCO, the dynamic-oracle benchmark can make a single fixed action sub-optimal at every epoch, causing OCO algorithms to incur linear regret.The paper nevertheless states that OCO algorithms can be adapted to perform well in the non-stationary stochastic setting.

3 A General Principle for Designing Efficient Policies

The section establishes that linear variation budgets make dynamic-oracle long-run-average optimality impossible, while sublinear budgets permit sublinear regret through restarting adversarial online optimization algorithms. Its central principle connects static-benchmark performance within batches to dynamic-benchmark performance across the non-stationary horizon.

  • Performance limits: When VT is at least order T, every admissible policy incurs regret of order T, ruling out long-run-average optimality against the dynamic oracle.The analysis therefore focuses on variation budgets sublinear in T, where sublinear regret is achievable.
  • A class of candidate policies: The candidate policy restarts an adversarial online optimization algorithm A every batch of size ∆T, producing a history-adapted policy for the stochastic non-stationary setting.The procedure accepts 1 ≤ ∆T ≤ T and selects actions using A within each batch.
  • First order performance: If VT = o(T), the restarting policy is long-run-average optimal when ∆T = o(T/VT) and the adversarial subroutine has φ(F,T) = o(T).This gives a construction in the stochastic non-stationary setting from any adversarial OCO algorithm with sublinear regret under the same structure and feedback.
  • Key ideas behind the proof: The restarting analysis decomposes dynamic-benchmark regret into within-batch static-benchmark regret and the static-to-dynamic benchmark gap, whose aggregate is at most order ∆T VT.The first term reflects the subroutine's performance over ⌈T/∆T⌉ batches, while the second is controlled by functional variation within batches.
  • Key ideas behind the proof: The batch size balances two effects: large ∆T improves the subroutine's approach to the static oracle, whereas small ∆T makes static oracles approach the dynamic oracle.The section states that this restarting mechanism transfers not only first-order optimality but also rate optimality from OCO to non-stationary stochastic approximation.

4 Rate Optimality: The General Convex Case

This section establishes matching lower and upper bounds for rate optimality under noisy gradient feedback in the general convex case. Restarted OGD achieves the minimax regret across variation scales, linking non-stationary stochastic optimization to adversarial online convex optimization.

  • Lower bound on achievable performance: A fundamental lower bound is established for every admissible policy under the gradient-feedback structure in Assumption 1.The proof uses batches containing randomly selected, nearly flat functions that remain difficult to distinguish while respecting the variation constraint.
  • Upper bound on performance: Restarting transfers rate optimality from adversarial OCO to the non-stationary stochastic setting by using an adapted OGD subroutine.The batch size is selected to balance tracking performance within batches against variation relative to the dynamic oracle.
  • Upper bound on performance: Restarted OGD is rate optimal, so the minimax regret under noisy gradient observations matches the lower bound.The result holds for deterministic or random initial actions of the OGD subroutine.
  • Rate characterization: When VT = T^α for 0 ≤ α ≤ 1, minimax regret is of order T^(2+α)/3, ranging from T^2/3 for constant variation to T for linear variation.This characterizes the full spectrum of variation scales and is consistent with the linear-variation case in Proposition 1.
  • Alternative algorithms: The restarting procedure provides a general template: rate-optimal non-stationary stochastic policies can be derived from rate-optimal OCO algorithms.The section conjectures that this lifting principle extends to rate-optimal procedures in the general non-stationary stochastic setting.

5 Rate Optimality: The Strongly Convex Case

This section studies rate optimality for strongly convex, non-stationary stochastic optimization under localized variation and noisy feedback. Restarting adversarially rate-optimal procedures transfers essentially optimal regret rates to the stochastic setting, including noisy gradient and cost access.

  • Preliminaries: Strong convexity is imposed through Hessian bounds HId ⪯ ∇2f_t(x) ⪯ GId, while variation is localized around the convex hull of minimizers.The analysis emphasizes local properties around minima and measures functional variation using a uniform norm over that region.
  • Rate optimality: Regret of order V_T^1/3 T^2/3 is achievable relative to the dynamic oracle for linear costs using a restarted adversarial policy.The corresponding lower bound follows by adapting the proof of Theorem 2.
  • First-order optimality: First-order optimality carries over from online convex optimization whenever the variation budget V_T is sublinear.The proof of the earlier proposition remains valid under the strongly convex structure.
  • Noisy gradient feedback: Theorem 4 shows that restarting tuned OGD yields rate optimality up to a logarithmic term under noisy gradient feedback.The construction uses the restarting procedure with tuned OGD as its subroutine, porting adversarial rate optimality to the non-stationary stochastic setting.
  • Noisy cost feedback: Theorem 5 establishes the same transfer under noisy cost access using restarted EGS, with regret of order T 2/3 and multiplicative factor [2.09, 2.88].The multiplicative constant increases when observations are noisier.

6 Concluding Remarks

The concluding remarks identify critical variation scales separating stationary and non-stationary regret regimes, with sufficiently small variation recovering stationary minimax rates. They also show that restarting remains long-run-average optimal under sufficiently accurate budget estimates, while adaptive policies and sharper regret constants remain open problems.

  • On the transition from stationary to non-stationary settings: Critical variation scales separate stationary and non-stationary regimes, and sufficiently small variation makes their minimax regret rates coincide.These scales diminish with T and measure how small temporal variation must be for non-stationarity to become insignificant in regret.
  • On the transition from stationary to non-stationary settings: The critical transition points differ across cost and feedback structures.The paper summarizes these differences through minimax regret rates for V_T = T^α and corresponding critical variation scales.
  • Inaccurate or no information on the variation budget: When the real variation budget is close enough to its estimate, restarting still guarantees long-run average optimality, though performance is dominated by accurate tuning.The relevant guarantee uses the real budget V_T while the restarting parameter is tuned using the estimate V̂_T.
  • Inaccurate or no information on the variation budget: For strongly convex costs with cost observation, tuning at V̂_T = T^α while V_T = T^(α+δ) guarantees sublinear regret of order T^(2/3+α/3+δ) when δ < 1 − α/3 − 2/3.If α = 0 and δ = 1/4, the procedure may guarantee order T^(11/12), whereas accurate tuning guarantees order T^(3/4).
  • Open problems: Designing adaptive policies without a-priori variation-budget knowledge and characterizing minimax regret more finely, including multiplicative constants, remain open problems.The adaptive-policy challenge persists because nature faces essentially no restrictions on how the variation budget is consumed.

A Proofs of main results

The proofs establish convergence for restarting policies under sublinear variation, a V_T^1/3 lower bound via indistinguishable quadratic environments, and OGD-based regret guarantees. They also adapt the lower-bound construction to strongly convex costs with modified parameters.

  • Proposition 1: If V_T = o(T), choosing Δ_T = o(T/V_T) with Δ_T →∞ makes the normalized bound converge to zero.This completes the proof of the restarting-policy optimality result.
  • Theorem 2: Any policy in P_φ(1) must incur regret of order V_T^1/3 on a class of sequences switching between two quadratic functions across batches.The restricted sequence class is shown to satisfy the variation constraint, and the proof uses KL-divergence and testing bounds.
  • Theorem 3: The OGD restarting policy with η_t = rG√Δ_T achieves the bound 2rG · T/√Δ_T + 2V_TΔ_T.The proof combines adversarial single-best-action regret within batches with the variation cost across batches.
  • Theorem 4: For strongly convex costs, the lower-bound proof changes δ and the batch length Δ̃_T, while retaining the same batchwise construction and adjusted regret analysis.The constructed sequences use strongly convex quadratic functions with interior minimizers.

Appendix C), we have: GA · Online Companion: Non-stationary Stochastic Optimization

Appendix C develops the noisy-cost-feedback proof by introducing a KL-divergence bound under Assumption 2 and applying it within a batch-based regret analysis. The companion is authored by Omar Besbes, Yonatan Gur, and Assaf Zeevi, affiliated with Columbia University and Stanford University.

  • Appendix C), we have: GA: The proof follows Theorem 2’s structure, with noisy feedback changing the KL-divergence bound, the selected batch size, and the resulting regret analysis.The appendix explicitly identifies these three consequences of the different feedback structure.
  • Appendix C), we have: GA: The proof defines a function class using the quadratic functions f1 and f2 from (A-12) and partitions T into batches as in (8).This construction is introduced in Step 1 of the proof.
  • Appendix C), we have: GA: For a fixed policy π ∈ Pφ(0), the analysis specifies decisions within each batch and bounds the KL divergence for an arbitrary batch using batch size ˜∆T.The subsequent inequalities invoke Lemma A-3 and related arguments from earlier theorem proofs.
  • Appendix C), we have: GA: Lemma A-3 bounds KL divergence for noisy cost observations under feedback structure φ = φ(0) and Assumption 2.The bound applies for any τ ≥ 1 and f, g ∈ F, with ˜C inherited from Assumption 2.
  • Appendix C), we have: GA: The appendix applies Lemma A-2 with ϕt = 1{Xt > x0} for any x0 ∈ X to obtain a bound valid for every t in each batch.The proof also uses the quadratic identity involving f1 and x∗1.
  • Appendix C), we have: GA: βRπ is lower-bounded by 1/64 · 24/3 ˜C1/3 · V 1/3_T T 2/3.The stated lower bound follows after introducing y0 as the unique solution of y = exp{−y}.
  • Online Companion: Non-stationary Stochastic Optimization: The online companion is authored by Omar Besbes, Yonatan Gur, and Assaf Zeevi.The listed affiliations are Columbia University, Stanford University, and Columbia University, respectively.

B Proofs of additional results

The appendix proves the additional lower and upper bounds, establishes supporting feedback lemmas, and shows that OGD without restarting can suffer linear regret despite limited variation. In particular, restarted OGD achieves a (9rG + 4)·V_T^1/3 T^2/3 bound, while carefully constructed alternating quadratic costs expose the failure of unrestarted OGD.

  • Proof of Proposition 1: Proposition 1 restricts nature to sequences alternating between two specific cost functions, with V′ ⊂ V, and derives a linear-order regret lower bound under the stated variation condition.The proof first verifies inclusion of the restricted sequence class and then shows that every admissible policy incurs regret of at least order T on that class.
  • Proof of Proposition 3: Proposition 3 proves that restarted OGD satisfies the regret bound (9rG + 4) · V_T^1/3 T^2/3.The analysis partitions the horizon into batches and selects the batch size to obtain the stated variation-dependent rate.
  • Proofs of Lemma A-1 and Lemma A-3: The proofs of Lemmas A-1 and A-3 derive the required feedback identities from the history dependence and feedback-structure assumptions.The argument establishes the result for φ = φ(1) and extends it to φ = φ(0) using Assumption 2.
  • Performance analysis of OGD algorithm without restarting: Example 3 shows that OGD without restarting yields linear regret for a broad set of variation budgets under alternating quadratic costs.Nature alternates g1(x) = (x − α)^2 and g2(x) = x^2 across batches, causing the algorithm’s actions to repeat across batches.
  • Failure of OGD without restarting: With η_t = C/t, selecting Δ_T of order T and α = 1 yields a fixed-constant variation budget V_T while regret remains linear.The construction states that the variation budget V_T is a fixed constant and that a constant C2 gives the linear-regret conclusion.

C Auxiliary results for OCO settings · C.1 Preliminaries

This section develops auxiliary regret bounds for online convex optimization with respect to the single best action. It formalizes admissible online algorithms under noisy feedback and a precommitted sequence of cost functions.

  • C.1 Preliminaries: The auxiliary results bound regret against the single best action in the adversarial setting.
  • C.1 Preliminaries: The considered feedback structures, φ(0) and φ(1), provide noisy access to the cost or gradient.
  • C.1 Preliminaries: Admissible online algorithms are defined through measurable action mappings driven by a shared random variable U.
  • C.1 Preliminaries: The feedback-dependent history uses k = 1 for φ = φ(0) and k = d for φ = φ(1).
  • C.1 Preliminaries: The mappings {At : t = 1, . . . , T} and distribution Pu define the admissible algorithm class Pφ, with filtration {Ht, t = 1, . . . , T}.
  • C.1 Preliminaries: Unlike much OCO work allowing adversarial epoch-by-epoch cost adjustments, this setting has nature commit to the function sequence in advance.
  • C.1 Preliminaries: The precommitted sequence and noisy observations align the OCO auxiliary setting with the paper’s non-stationary stochastic framework.

C.2 Upper bounds

This section establishes adversarial upper bounds for EGS under φ(0) and OGD under φ(1), with constants independent of the horizon T. The EGS result uses noisy gradient access, while the OGD bound adapts prior noiseless-gradient analysis to φ(1).

  • EGS under φ(0): EGS under feedback structure φ(0) achieves an adversarial upper bound with a constant independent of T.The result applies the EGS algorithm with at = 2d/Ht and δt = ht = a_t^1/4.
  • EGS under φ(0): The EGS analysis uses a coordinate-wise randomized gradient estimator, projection onto Xδt, and noisy cost feedback.The estimator samples a random sign and coordinate, then projects the resulting step over the interior action set.
  • EGS under φ(0): Epochs with δt > ν add at most a constant independent of T to regret, depending only on ν, dimension d, and the second derivative bound H.Because δt converges to zero, only finitely many such epochs occur, with the count independent of T.
  • OGD under φ(1): OGD under feedback structure φ(1) achieves an adversarial upper bound with a constant independent of T using ηt+1 = 1/Ht.The proof adapts Theorem 1 of Hazan et al. (2007) to the φ(1) feedback structure.
  • OGD under φ(1): 2H (1 + log T) bounds the OGD analysis after summing over the horizon.This term follows from selecting ηt = 1/Ht and summing the per-time-step inequality.

C.3 Lower bounds

The section establishes lower bounds on achievable adversarial performance under two feedback structures. Together with matching upper bounds, these results show rate optimality for EGS with strongly convex costs and noisy cost observations, and for OGD with general convex costs and noisy gradient observations.

  • C.3 Lower bounds: Lemmas C-6 and C-7 establish lower bounds on the best achievable performance in the adversarial setting under structures (Fs, φ(0)) and (F, φ(1)), respectively.These lemmas apply under Assumptions 2 and 1, respectively.
  • C.3 Lower bounds: Together with Lemma C-4’s upper bound, Lemma C-6 establishes that EGS is rate optimal for strongly convex cost functions with noisy cost observations.The lower and upper bounds jointly characterize the achievable rate in this setting.
  • C.3 Lower bounds: Lemma C-7 matches the upper bound in Lemma 3.1 of Flaxman et al. (2005), establishing rate optimality for OGD with carefully selected step-sizes under general convex costs and noisy gradient observations.The result concerns the structure (F, φ(1)).

D Numerical Results

Numerical experiments show that restarted OGD and EGS achieve regret rates consistent with theory across changing-cost settings and feedback structures. Restarting generally outperforms non-restarted policies, while fixed step sizes can be better on some finite horizons without guarantees against the dynamic oracle.

  • Numerical setup: Experiments evaluate restarted OGD and EGS under changing quadratic costs, noisy gradient or cost feedback, multiple noise levels, horizons, and variation patterns.The simulations use σ ∈ {0.1, 0.3, 1}, T ∈ {1000, 5000, . . . , 37000}, and 10^3 replications.
  • Results and discussion: R^2 > 0.98 in all linear fits, while the standard error of percentage loss remained below 5% of average policy performance.Tables 3 and 4 report estimated coefficients and average loss relative to the dynamic oracle.
  • Results and discussion: 0.5 and 0.67 are the theoretical regret-rate benchmarks matched by estimated α for restarted OGD under φ(1) and restarted EGS under φ(0), respectively.Estimated c ranges are [0.05, 0.94] for restarted OGD and [2.09, 2.88] for restarted EGS.
  • Results and discussion: Restarted policies consistently outperform their non-restarted counterparts, and their multiplying constant typically increases as observation noise σ increases.Both restarted and non-restarted policies become closer to the dynamic oracle as T grows.
Loading 1307.5449v2…