PaperlayerView exact revision on arXiv

Source-linked AI summary

Ergodic Mirror Descent

John C. Duchi, Alekh Agarwal, Mikael Johansson, Michael I. Jordan

arXiv:1105.4681v3math.OCstat.ML

TL;DR

Stochastic optimization often must use samples coupled over time rather than independent draws from the target distribution, especially when that distribution is unknown or difficult to sample. The paper applies standard mirror-descent updates to samples from an ergodic process and establishes convergence guarantees in expectation and with high probability. It also gives a lower bound showing those rates are tight up to numerical constants.

  • Problem

    Dependent-data optimization has often lacked finite-sample and high-probability guarantees, while independent samples from the target distribution may be unavailable.

    Source: §1 · p. 2

  • Method

    Ergodic Mirror Descent applies stochastic mirror-descent updates using samples from a process that converges to the target distribution.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    The method has convergence guarantees in expectation and with high probability for a large class of ergodic processes, and a lower bound shows the rates are tight up to numerical constants.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis provides finite-sample convergence rates for statistical estimators with dependent data and applies to settings including combinatorial optimization.

    Source: §4.2 · p. 12, §7 · p. 27

    The sharper convergence bound requires knowledge of the process's mixing rate; choosing the polynomial step size incorrectly can significantly slow convergence.

    Source: §4.4 · p. 17

Abstract

from arXiv · show

We generalize stochastic subgradient descent methods to situations in which we do not receive independent samples from the distribution over which we optimize, but instead receive samples that are coupled over time. We show that as long as the source of randomness is suitably ergodic---it converges quickly enough to a stationary distribution---the method enjoys strong convergence guarantees, both in expectation and with high probability. This result has implications for stochastic optimization in high-dimensional spaces, peer-to-peer distributed optimization schemes, decision problems with dependent data, and stochastic optimization problems over combinatorial spaces.

1 Introduction

The paper studies stochastic optimization when samples arrive from a time-coupled process rather than as independent draws from the target distribution. It extends standard stochastic descent to this setting and establishes convergence guarantees governed in part by how quickly the process approaches stationarity.

1 Introduction

  • The optimization target is an expected convex objective, but the available samples come from a process converging to its stationary distribution rather than independent draws from that distribution.This relaxation matters when the distribution is unknown, independent samples are unavailable, or sampling from high-dimensional or combinatorial spaces is difficult.Source: §1 · pp. 1–2
  • Earlier work on dependent stochastic data was largely asymptotic and generally lacked finite-sample or high-probability convergence guarantees.The paper supplies such guarantees for stochastic optimization with exogenous correlated noise.Source: §1 · p. 2
  • Ergodic Mirror Descent uses standard stochastic subgradient or mirror-descent steps with process samples, generalizing incremental subgradient methods to correlated sampling.Motivating settings include control data coupled over time, distributed sensor measurements, and dependent statistical data.Source: §1 · p. 2
  • Three theorems establish convergence in expectation and with high probability, including when mixing times are random; a lower bound shows the rates are tight up to numerical constants.The rates depend on problem quantities and the process's mixing time.Source: §1 · p. 2

2 Assumptions and algorithm

Ergodic Mirror Descent applies mirror-descent updates using samples from a process converging to a stationary distribution. Its guarantees rely on regularity of the objective functions and assumptions controlling how quickly the process mixes.

2 Assumptions and algorithm

  • The analysis assumes a compact feasible set and function regularity, expressed through either finite single-step variance or Lipschitz continuity of the sample functions.The Lipschitz condition implies bounded subgradients and also makes the expected objective Lipschitz.Source: §2 · pp. 3–4
  • At each step, Ergodic Mirror Descent uses the current process sample to form a stochastic subgradient update of its parameter in the feasible set.The update generalizes stochastic mirror descent; with a particular prox-function it reduces to projected gradient descent.Source: §2 · p. 3
  • Mixing time measures how many additional steps are needed for the conditional sample distribution to approach the stationary distribution.The paper defines this using total variation and Hellinger distances.Source: §2 · pp. 4–5
  • Assumption C requires uniformly bounded mixing times and is weaker than φ-mixing; finite-state and uniformly ergodic Markov chains satisfy it.Assumption C requires convergence of conditional sample distributions, not convergence over the entire future σ-field.Source: §2 · p. 5
  • Assumption D allows mixing times to be random and covers a wider range of processes, including autoregressive processes.It weakens the uniform-mixing requirement by allowing conditional mixing times to depend on the process state.Source: §2 · p. 5

3 Main results

The section establishes expected and high-probability convergence guarantees for EMD, then uses an information-theoretic lower bound to show that its rates are sharp up to numerical constants.

3.1 Convergence guarantees

  • EMD has convergence guarantees in expectation and with high probability when the stated assumptions hold.The high-probability rate adds a deviation-control term; its dominant terms, up to logarithmic factors, also appear in the expected bound.Source: §3 · p. 5, §3.1 · pp. 6–7
  • With non-increasing stepsizes satisfying the stated asymptotic conditions, the EMD method converges.The conditions include Tα(T) → ∞ and (1/T)∑_{t=1}^T α(t) → 0.Source: §3.1 · p. 6
  • The final convergence theorem replaces uniform mixing with probabilistic mixing, broadening the guarantees to state-dependent mixing processes.The paper applies this theorem to autoregressive estimation and a fault-tolerant distributed optimization scheme.Source: §3.1 · p. 7
  • For geometrically mixing processes, the simplified rates subsume the i.i.d. results, where the paper also establishes constant-factor sharpness.The i.i.d. mixing times are one, and the paper states that its rates subsume existing i.i.d. results.Source: §3.1 · pp. 7–8
  • The results do not require Markovianity or homogeneity; they require an existing mixing time, possibly one that exists only with reasonably high probability.The paper also notes that some ergodic processes mix more slowly than the geometric-rate case treated in its simplified corollary.Source: §3.1 · p. 8

3.2 Lower bounds and optimality guarantees

  • Theorems 1–3 are unimprovable by more than numerical constants, and EMD attains the minimax-optimal convergence rate.The lower bound establishes the optimality of the presented results.Source: §3.2 · p. 10

4 Examples and Consequences

The examples apply Ergodic Mirror Descent to peer-to-peer optimization, hard-to-sample combinatorial spaces, probabilistically mixing processes, and slowly mixing processes. Together, they illustrate convergence guarantees across these settings, including an asymptotic guarantee for slowly mixing ergodic processes.

4.1 Peer-to-peer optimization and Markov incremental gradient descent

  • For peer-to-peer optimization, the analysis gives sharper convergence rates than earlier Markov incremental gradient descent results, with a substantially stronger bound for expander graphs.For an expander, the new bound’s spectral-gap term is O(1), while the compared earlier bound is Ω(n).Source: §4.1 · pp. 11–12

4.2 Optimization over combinatorial spaces

  • For rankings consistent with a partial order, EMD is applied using a Markov chain over the difficult-to-sample permutation space, yielding a high-probability guarantee.The example concerns a combinatorial space where uniform sampling is difficult but a rapidly mixing chain can be constructed.Source: §4.2 · pp. 12–13

4.3 Probabilistically mixing processes

  • For random communication matrices, the analysis uses the second eigenvalue of E[P(1)⊤P(1)] to obtain a high-probability convergence corollary for randomized Markov incremental gradient descent.The transition matrices are i.i.d. and doubly stochastic; the analysis notes that this expected-matrix eigenvalue can be smaller than the second eigenvalue of each random matrix.Source: §4.3 · pp. 13–14
  • For nonlinear ARMA processes, the paper gives a convergence corollary under stability and moment conditions that imply geometric mixing.The stated conditions include ρ1(A) < 1, h(ξ) = o(∥ξ∥) as ∥ξ∥→∞, fixed Σ, and finite second moment of the innovations.Source: §4.3 · pp. 14–15

4.4 Slowly mixing processes

  • For polynomially mixing Markov chains, the paper gives a finite-sample rate, while under Assumption C it also establishes asymptotic convergence for any ergodic process.The sharper finite-sample bound requires knowledge of the mixing rate; choosing the polynomial incorrectly can significantly slow convergence.Source: §4.4 · pp. 15–17

5 Numerical results

The simulations compare EMD with sampling strategies and test its performance under non-Euclidean geometry and mis-specified step sizes. They find that sequential EMD remains effective when mixing-time estimates are poor, while the non-Euclidean variant performs better in the distributed learning experiment.

5.1 Sampling strategies

  • Multiple replications can be biased even after infinitely many gradient steps if the chosen simulation length does not make samples converge precisely to the stationary distribution.The mixing time may be unknown, and this approach requires simulating the process to generate independent samples.Source: §5.1 · p. 19
  • With sufficiently large mixing-time estimates, multiple-replication SGD and EMD have comparable optimization error; underestimation makes the replication approach fail, while EMD still converges.The comparison uses optimization error as a function of gradient steps.Source: §5.1 · p. 19, Figure 1 · p. 19
  • The multiple-replications approach is inapplicable to real, unsimulated data sources such as streaming, online optimization, or statistical applications; EMD still applies.Source: §5.1 · p. 19
  • Using process samples sequentially as in EMD is more computationally efficient than trying to draw independent samples at each iteration.The comparison concerns the number of samples from the autoregressive process.Source: Figure 1 · p. 19, §5.1 · p. 20

5.2 Robustness and non-Euclidean geometry

  • In the distributed support-vector-machine experiment, the non-Euclidean ℓp variant has better performance than the Euclidean variant.The comparison uses a 4-connected cycle with 50 nodes and d = 500; the plotted bands show the 5th and 95th percentiles across 50 simulations.Source: Figure 2 · p. 20, §5.2 · p. 21
  • Across the tested step-size multipliers, EMD is affected by mis-specification, but performance degradation appears not extraordinary for γ roughly between 10^-1 and 10.The experiment reports mean optimality gap after 10,000 iterations across 50 experiments; theoretical predictions appear to capture empirical behavior.Source: §5.1 · p. 20, §5.2 · p. 21

6 Analysis

The analysis establishes expected and high-probability convergence guarantees for EMD using ergodic samples, including when mixing times are random. It also develops a lower-bound construction for optimization with dependent samples.

6.1 Definitions, assumptions, and optimization-based results

  • The analysis defines measurable subgradients and the filtration of observed samples; under the stationary distribution, expected subgradients belong to the objective subdifferential.The optimization setup also uses a compactness bound on the Bregman divergence and standard lemmas for EMD updates.Source: §6.1 · p. 22

6.2 Expected convergence rates

  • A lag τ lets the process mix between parameter selection and sample evaluation, making the later sample nearly independent of the current iterate and its function value nearly unbiased.The expected-rate proof combines this mixing argument with bounds on four sums in the expansion.Source: §6.2 · pp. 22–23

6.3 High-probability convergence

  • Martingale theory gives a high-probability version of the convergence bound by controlling the random sum using an appropriately subsampled sequence and Azuma’s inequality.The subsampled sequence behaves approximately as a martingale because later samples are nearly stationary given earlier observations.Source: §6.3 · p. 24

6.4 Random mixing

  • For random mixing times, the proof first obtains a high-probability uniform bound on mixing times, then uses it in the convergence argument.The result extends to accuracies whose total-variation mixing time is at most T; when it exceeds T, the bound holds vacuously.Source: §6.4 · p. 25

6.5 Lower bounds on optimization accuracy

  • The lower-bound construction repeats each sampled pair across blocks of τ steps; the resulting information bound supports a lower bound for optimization with dependent samples.Within a block the pairs are equal, while different blocks are independent conditional on the hidden vector.Source: §6.5 · pp. 26–27

7 Conclusions

The paper extends stochastic subgradient and mirror descent to dependent samples generated by an ergodic process. It reports reasonably fast convergence under reasonable ergodicity assumptions and identifies sharper bounds for some Markovian settings as future work.

7 Conclusions

  • EMD achieves reasonably fast convergence under reasonable assumptions on the ergodicity of the process generating samples.Source: §7 · p. 27
  • The analysis provides finite-sample convergence rates for statistical estimators with dependent data without requiring the full machinery of empirical process theory.Source: §7 · p. 27
  • The paper’s lower bounds show its analysis is tight to numerical constants, while sharper results may be possible for special cases with sufficiently favorable Markovianity properties.Source: §7 · p. 27

A Proofs of Optimization Results

The appendix proves optimization lemmas used in the EMD analysis by bounding progress from each update and relating step displacement to Bregman divergence.

A Proofs of Optimization Results

  • The first proof bounds progress from one EMD step using first-order convexity and the subgradient, then sums the resulting bound.Source: A Proofs of Optimization Results · p. 28
  • For the comparison with an optimum, the proof applies the update’s optimality condition at x*, then uses Fenchel–Young and strong convexity inequalities with non-increasing step sizes.Source: A Proofs of Optimization Results · p. 28
  • The update’s optimality condition relates the gradient difference to step displacement, which is then bounded using the two directional Bregman divergences.Source: A Proofs of Optimization Results · p. 29

B Mixing and expected function values

The proof controls expected function-value differences using convexity, mixing assumptions, and bounds on iterate movement. It also relates the resulting bound to expectations under the stationary distribution.

B Mixing and expected function values

C Proof of Proposition 1

The proof of Proposition 1 controls deviations by decomposing the sum into bounded-difference martingales and conditional expectations. It bounds the martingale component with a high-probability argument.

C Proof of Proposition 1

  • The proof defines Z_t as the difference between the sampled function-value gap and its expected function-value gap at the delayed iterate.Z_t := f(x(t − τ + 1)) − F(x(t − τ + 1); ξ_t) + F(x⋆; ξ_t) − f(x⋆).Source: C Proof of Proposition 1 · p. 32
  • For each offset j, the proof constructs Doob martingales from the terms indexed by blocks of length τ.The martingale differences are adapted to the stated filtration, with index sets I(j) specifying the terms included.Source: C Proof of Proposition 1 · p. 32
  • Compactness and Assumption B are used with measurability to establish a bound for the terms in the representation.The remaining conditional-expectation terms are bounded using Lemma 12, and summing the bound completes the proof.Source: C Proof of Proposition 1 · p. 32
  • The sum of Z_t is represented as τ bounded-difference martingales plus conditional expectations, and its martingale part is bounded using Azuma’s inequality.The proof combines the triangle inequality and a union bound for this control.Source: C Proof of Proposition 1 · p. 32

D Probabilistic Mixing

The probabilistic-mixing proofs use concentration and covering arguments to control mixing-time deviations. The Lemma 5 bound sets its confidence parameter as a function of δ and T.

D Probabilistic Mixing

  • The proof uses Markov’s inequality and the identity γa/|log γ| = exp(−a) for 0 < γ < 1 in an intermediate bound.The argument is stated to hold for any τ ∈ N.Source: D Probabilistic Mixing · p. 33
  • A covering-number argument is used to bound the event that τTV(P[s], ε) exceeds τTV(P, ε) + c for some s and ε ≥ εT.The proof applies a union bound and Assumption D to this event.Source: D Probabilistic Mixing · p. 33
  • c = κ[log(1/δ) + 2 log(T)] gives the stated Lemma 5 bound.The expression follows by setting the final equation equal to δ and solving.Source: D Probabilistic Mixing · p. 33

Related papers

Loading 1105.4681v3…