Many learning problems are nested. An outer variable, such as a regularization strength, a policy, or a meta-initialization, is tuned according to how well an inner problem solved for that outer value performs. Examples include tuning the inner model's parameters, or estimating a value function. In practice the inner problem is never solved exactly. We run a few gradient steps and move on. In streaming and reinforcement-learning settings, the data feeding those inner steps is also not independent: each sample is correlated with the last, like successive states of a Markov chain. Theory has treated these two facts separately. Inexact-solver analyses tell us how fast the inner error must shrink, but they assume deterministic or independent noise. Analyses of correlated data tell us how much correlation slows learning, but they assume either a single-level problem or a fixed two-speed update schedule. Nobody has asked the practical question that joins them: on a correlated stream, how long should each inner solve run?
Our answer is to stop each inner solve when its remaining error becomes statistically indistinguishable from the noise floor that the correlated data imposes. That floor can be estimated online with batch means, a classical tool from Markov chain Monte Carlo. Batch means estimates the long-run variance of a correlated average, which grows with the chain's mixing time $\tau_{\text{mix}}$ (roughly, how many steps it takes before samples become nearly independent). The algorithm therefore never needs $\tau_{\text{mix}}$ as an input. It spends more samples on inner solves when data is highly correlated, fewer when it is not, and progressively more as the outer variable converges. We pair this algorithm with a benchmark suite in which mixing time is a controlled dial. That suite addresses the fourth direction directly: rate claims in this area are almost never checked against finite-sample behavior.
Core Claim
Under Markovian data, the inner error of a bilevel step has two parts. The first is optimization error, which more inner steps reduce. The second is a bias-plus-variance floor from correlated sampling, which more inner steps on the same short segment cannot reduce below roughly $\sqrt{\tau_{\text{mix}}/m}$, where $m$ is the segment length. The first part comes from standard Markov-chain concentration via blocking. Solving the inner problem below this floor wastes samples. Stopping above it biases the hypergradient, which is the gradient of the outer objective through the inner solution. We claim three things:
- A verifiable stopping test can balance the two parts without knowing $\tau_{\text{mix}}$ or Lipschitz constants. The test compares the segment-averaged inner gradient against a batch-means estimate of its own standard error.
- With a strongly convex lower level and geometrically mixing data, the resulting single-stream method attains the single-level rate up to logarithms in the total number of samples $T$. Concretely, it should reach a squared hypergradient norm of order $\tau_{\text{mix}}/T$ under a Polyak–Łojasiewicz outer objective (a standard condition guaranteeing gradient methods converge like they do on convex problems). The $\tau_{\text{mix}}$ dependence should be no worse than in single-level Markovian SGD.
- Its finite-time transient will be shorter than tuned two-timescale and auxiliary-averaging methods when mixing is slow.
The test at outer step $k$ is the following. Let the inner solver consume a contiguous segment of $m$ samples. Let $\bar g_k$ be the average inner gradient over the most recent half of that segment, and let $\hat\sigma_k^2$ be the batch-means estimate of its long-run variance, computed from $B$ non-overlapping sub-batches. Inner iterations stop once
$$\|\bar g_k\| \le c\,\hat\sigma_k \sqrt{B/m},$$
with $c$ an absolute constant (we will fix $c=2$). The quantity $\hat\sigma_k\sqrt{B/m}$ is the estimated standard error of $\bar g_k$, so the test says that the inner gradient is no longer distinguishable from zero given the data's correlation. The outer step then uses a hypergradient built from the same segment: the inner iterate plus a few conjugate-gradient steps on the adjoint linear system, the system whose solution supplies the implicit-differentiation correction. The next segment starts from a warm-started inner iterate. Segments lengthen on their own as the outer variable settles, because $\bar g_k$ shrinks more slowly than the standard error once the inner problem is nearly solved.
Relation to Prior Work
The closest work sits on three sides of this proposal.
The first side is Markovian two-timescale analysis, which motivates the problem. Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise proves the general nonlinear Markovian two-timescale rate is $\mathcal{O}(1/n^{2/3})$. It recovers $\mathcal{O}(1/n)$ only when the slow update carries no independent noise, and it runs no experiments. Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise shows that for linear systems Markovian noise changes only constants. Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications shows that faster-mixing chains yield lower asymptotic covariance. All three keep fixed step-size schedules and exact single-step updates. None lets the inner effort adapt to the observed correlation, which is the lever we add.
The second side is rate-closing methods for nested stochastic problems, which supply our strongest competitor. Fast two-time-scale stochastic gradient method with applications in reinforcement learning adds auxiliary running averages with a third step size $\lambda_k$. This lifts the rate to $\mathcal{O}(1/k)$, but the proof assumes i.i.d. noise; the Markovian extension is only conjectured, and $\lambda_k$ must be tuned. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms (SABA) matches single-level rates through variance reduction over a finite sum. That approach has no meaning on a non-repeating stream. Our method differs from both by replacing a hand-set averaging schedule with a data-driven stopping time. The averaging window is chosen by the chain's measured correlation rather than by a constant that encodes it.
The third side is adaptive inexactness and mixing adaptivity, which supply the methods we reuse. An Adaptively Inexact First-Order Method for Bilevel Optimization with Application to Hyperparameter Learning (MAID) adapts inner tolerances through a verifiable backtracking test, but only for deterministic problems and only asymptotically. We borrow its warm-start-plus-conjugate-gradient structure and its insistence on verifiability, replacing the deterministic line search with a statistical test. Accelerating Inexact HyperGradient Descent for Bilevel Optimization (RAHGD) and Inexact first-order primal-dual algorithms show how scheduled inner accuracy preserves outer rates, again with deterministic oracles. Adapting to Mixing Time in Stochastic Optimization with Markovian Data (MAG) adapts to unknown $\tau_{\text{mix}}$ with multilevel Monte Carlo gradients, a randomized telescoping estimator that trades bias for variance. Its open problems are exactly the two we target: it is single-level only, and it suffers variance spikes that need ad hoc truncation. Batch means estimates the same long-run variance without randomized exponential multipliers, which is why we expect it to be more stable.
Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractability constrains the design. It finds that processing every sample on a single path beats thinning and restarted replications. Our method therefore consumes the stream contiguously and never discards samples to manufacture independence.
Research Program
The theoretical part proves one finite-time result. The setting is a strongly convex lower level, a smooth outer objective, and a stationary, geometrically mixing data chain that does not depend on the iterate. The analysis splits each segment's inner error with the Poisson-equation decomposition used by Chandak et al., giving a martingale part plus a residual of order $\tau_{\text{mix}}/m$. It then proves that batch means estimates the long-run variance within a constant factor with high probability once $m \gtrsim \tau_{\text{mix}}\log T$. Finally, it shows the stopping rule therefore triggers within a constant factor of the oracle segment length, the length that someone knowing $\tau_{\text{mix}}$ would choose.
The outer analysis then follows the dynamic-tolerance argument of Chambolle et al., with the stochastic tolerance in place of the deterministic one. We target $\widetilde{\mathcal{O}}(\tau_{\text{mix}}/T)$ for a Polyak–Łojasiewicz outer objective and $\widetilde{\mathcal{O}}((\tau_{\text{mix}}/T)^{1/2})$ for the squared gradient norm of a nonconvex outer objective. We do not claim results for nonconvex lower levels.
We will treat the controlled case, where the data chain depends on the policy as in actor-critic methods, empirically only. We will state it as a limitation rather than prove it.
The empirical part builds a public suite of nested problems in which correlation strength is a knob. Each task can be run at several mixing times while holding the stationary distribution fixed, so rate and constant claims can finally be read off as curves against $\tau_{\text{mix}}$.
Baselines
The naive reference is a fixed inner loop: a constant number of inner SGD steps per outer step, run on the stream as it arrives, with the inner-loop length and both step sizes grid-searched. This is what practitioners do, and any adaptive method must beat it to matter.
The standard theoretical baseline is plain two-timescale stochastic approximation with the textbook schedule, the setting analyzed by Chandak et al. Its predicted $\mathcal{O}(1/n^{2/3})$ behavior gives us a slope to compare against.
The strongest competitor is Fast TTSA from Fast two-time-scale stochastic gradient method with applications in reinforcement learning, run directly on Markovian samples. It is strongest because it already closes the rate gap under i.i.d. noise, and its authors conjecture only a logarithmic penalty under Markovian noise. If that conjecture holds with a well-tuned $\lambda_k$, the remaining question is tuning cost and transient length, not rate. Its best reported figure in the file is on LQR actor-critic: the fast variant reached a low error threshold in roughly 500 iterations against more than 2000 for standard actor-critic. That figure is for i.i.d. sampling. For our Markovian tasks we found no reported result on Lacuna for Fast TTSA under correlated sampling.
The second strong competitor is a bilevel extension of MAG: multilevel Monte Carlo estimates of the inner gradient and the hypergradient, AdaGrad steps, and truncation as in Dorfman and Levy. On their two-state chain we found no reported numerical result on Lacuna, only the qualitative finding that MAG degrades more gracefully than SGD as mixing slows.
We will also run MAID's deterministic backtracking applied naively to minibatches, to show what goes wrong when a deterministic tolerance test meets noise.
Fairness is enforced through a single sample budget $T$ drawn from the same stream realization for every method, with identical warm starts. Every baseline receives the same random-search budget of 50 configurations per task per mixing level, selected on a held-out seed. Our method receives the same 50 configurations, but only over its outer step size, because its inner effort is not tuned. The comparison will separately report results with each baseline tuned at the slowest-mixing level and then reused across levels, which is the deployment-realistic setting.
Beating Fast TTSA means two things. First, equal or lower final outer suboptimality at budget $T$ across mixing levels. Second, a strictly smaller drop in performance when hyperparameters tuned at one mixing level are transferred to another.
Two ablations isolate the key ingredient. In the oracle ablation, the stopping threshold is replaced by the true long-run variance, which measures the cost of estimating it. In the i.i.d.-formula ablation, it is replaced by the ordinary sample standard deviation, which ignores correlation. If the i.i.d.-formula ablation performs as well as the full method, the mixing-adaptive part of the claim is false.
Why not just…?
Why not just run Fast TTSA on Markovian data and accept a log penalty? This is the real threat. Nothing in the file rules it out, and the authors' conjecture predicts it will work asymptotically. Our expected advantage is narrower and testable. The averaging step $\lambda_k$ implicitly encodes $\tau_{\text{mix}}$, so a value tuned for fast mixing should under-average when mixing is slow. Our transfer-across-mixing-levels experiment measures exactly this. If tuned Fast TTSA matches us at every mixing level with a single setting, we will report the contribution as the theory and benchmark only, not a better algorithm.
Why not just plug MAG's multilevel gradients into a bilevel loop? Its estimator was designed for this kind of adaptivity, but its variance spikes come from exponentially rare long rollouts. The file notes they required truncation even at a single level. Composing two such estimators, one for the inner gradient and one for the hypergradient, multiplies those spikes. We will measure the 99th-percentile hypergradient norm and final error with and without truncation. Batch means should show bounded tails because it never reweights by a random power of two.
Why not just break the correlation with a replay buffer or by thinning the stream? Thinning throws away samples. Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractability found single-path processing beats thinned and restarted variants on autoregressive Lasso. A replay buffer reduces correlation only when it is much longer than $\tau_{\text{mix}}$, which reintroduces the unknown quantity and costs memory. We include a buffer of matched memory as an extra baseline.
Proposed Experiments
The suite contains five tasks.
The first is bilevel ridge-penalty tuning on the symmetric two-state chain regression of Dorfman and Levy, with the chain's switching probability swept to vary $\tau_{\text{mix}}$ over two orders of magnitude.
The second is regularization tuning for Lasso on autoregressive covariates following Wang et al., with the autoregressive coefficient as the mixing knob. The non-smooth inner problem is handled with a proximal inner step.
The third is regularized logistic-regression hyperparameter tuning on a9a and on MNIST hypercleaning, as used by RAHGD and MAID, with samples supplied by a random walk over a nearest-neighbor graph of the data. On the wikiVote graph we compare simple and non-backtracking random walks, following the Central Limit Theorem paper. That paper predicts the non-backtracking walk lowers error, and our method should convert that lower variance into shorter inner segments automatically.
The fourth is TDC policy evaluation on 50-state, 50-action random MDPs with trajectory sampling.
The fifth is LQR actor-critic as in Zeng and Doan, which is our one controlled-chain stress test.
The metrics are outer suboptimality or squared hypergradient norm against samples consumed and against wall-clock time. We will also report fitted log-log slopes against the predicted $-1$ and $-2/3$, the empirical dependence of final error on $\tau_{\text{mix}}$, the realized inner-segment lengths compared with the oracle lengths, and tail statistics of the hypergradient. Ten seeds per configuration are used, with intervals reported.
Three checks are decisive.
First, final error at fixed $T$ should scale linearly in $\tau_{\text{mix}}$ for our method, while the fixed-inner-loop baseline should degrade faster. Our method should also beat the i.i.d.-formula ablation by a widening margin as mixing slows.
Second, realized segment lengths should track oracle lengths within a constant factor across the sweep.
Third, on the transfer test, our method should lose less performance than Fast TTSA and bilevel MAG. A null result on the third check would narrow our claim to theory plus benchmark. A null result on the first would refute the claim outright.
References
- Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
- Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
- Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
- Fast two-time-scale stochastic gradient method with applications in reinforcement learning
- A framework for bilevel optimization that enables stochastic and global variance reduction algorithms
- An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learning
- Accelerating Inexact HyperGradient Descent for Bilevel Optimization
- Inexact first-order primal-dual algorithms
- Adapting to Mixing Time in Stochastic Optimization with Markovian Data
- Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractability