Source-linked AI summary
Minimax-Optimal Predictive Flow Matching under Distribution Drift
Aadithya Srikanth, Vaneet Aggarwal
TL;DR
The paper asks how to bound predictive flow-matching regret when targets drift and each field must be deployed before current data arrive. DyProd-FM selects among fits trained on historical prefixes, and the analysis establishes optimal rates under two variation measures for fixed classes. The target-law result relies on smoothing conditions, and the network class has bounded activations.
Problem
Predictive flow matching must choose a field before the current batch arrives, even though historical data may describe an obsolete target and discarding history loses repeated-sampling benefits.
Source: §1 · p. 1Method
DyProd-FM refits flow matching on geometrically growing historical prefixes and uses a sleeping Prod master to select among the fits without a drift budget.
Source: §1 · p. 2Results
Matching lower bounds show that the relative-risk and target-law regret rates are optimal in T and their budgets up to logarithmic factors, apart from approximation and fitting costs.
Source: §1 · p. 2Takeaways & Limitations
The target-law rate applies to a nonconvex neural class without parameter-curvature assumptions, using flow-matching structure and base smoothing.
Source: §3.3 · p. 4The bounded-activation condition excludes unclipped ReLU-type networks.
Source: §3.3 · p. 4
Abstract
from arXiv · showhide
Flow matching learns a generative velocity field by regression, but under distribution drift a field must be deployed before the current data arrive. We study this predictive problem for a fixed, possibly nonconvex, neural class, with dynamic regret against the best represented field of each round. We propose DyProd-FM, which refits flow matching on dyadic historical prefixes and selects among the fits with a sleeping Prod master. Without knowing any drift budget, it attains regret $\widetilde{O}(\min\{N_\omega+1,1+\sqrt{T\Omega}\})$ in the relative velocity risk variation $\Omega$ and $\widetilde{O}(\min\{N_\mu+1,1+T^{1/3}V_\mu^{2/3}\})$ in the target-law variation $V_\mu=\sum_t W_2(\mu_{t+1},\mu_t)$, up to approximation and fitting costs. Matching lower bounds for fixed classes show that both rates are optimal in $T$ and in the budgets up to logarithmic factors. Prior optimal dynamic-regret guarantees rely on a convex decision set with strongly convex or exp-concave losses, whereas our class may be nonconvex and no curvature in its parameters is assumed. The target-law rate rests on a second-order link between the two variations, which the base noise of flow matching provides.
1 Introduction
The paper studies predictive flow matching when the target changes and the current field must be chosen before the fresh batch arrives. It introduces DyProd-FM, gives regret rates under two drift measures, and links target-law drift to relative-risk drift through base smoothing.
1 Introduction
- Relative-risk variation measures drift in comparisons among represented fields, while target-law variation measures class-independent W2 movement of the target.The target-law variation is estimable from samples.Source: §1 · p. 1
- DyProd-FM refits on geometrically growing historical prefixes and selects among fits without knowing the drift budget.Its guarantees use dynamic velocity regret against the best represented field at each round.Source: §1 · pp. 1–2
- The regret bounds adapt to either relative velocity-risk variation or target-law variation, with matching fixed-class lower bounds establishing optimality up to logarithmic factors.Both guarantees include approximation and fitting costs.Source: §1 · p. 2
- Base smoothing and approximate quadratic growth yield a second-order bound on excess risk from target movement, with approximation and smoothing remainders.The smoothing condition excludes uniform flow time but admits truncated uniform, Beta, and logit-normal laws.Source: §1 · p. 2
- The analysis addresses heterogeneous historical batches, fast selection among fits, and drift transfer for a nonconvex class without parameter-curvature assumptions.Squared-loss structure controls master score differences by velocity risks, while historical transfer is first-order in relative-risk variation and second-order in target-law variation.Source: §1 · pp. 1–2
2 Related Work
The paper builds on fixed-target flow-matching theory and dynamic-regret methods, while extending tracking guarantees to predictive flow matching with drifting targets. Its target-law rate shares known variation exponents but applies to a nonconvex neural class.
2 Related Work
- Fixed-target flow-matching work studies velocity accuracy and statistical error, while this paper considers excess current error when deployment precedes each fresh batch and targets drift.Sahoo et al. (2026) provide fixed-target rates and a rare-mixture lower bound.Source: §2 · p. 2
- The analysis draws on strongly adaptive interval guarantees and sleeping-expert Prod for tracking changing comparators.The related dynamic-regret foundations include Herbster and Warmuth (1998), Zinkevich (2003), and Besbes et al. (2015).Source: §2 · p. 2
- The target-law rate has the same exponents as total-variation forecasting, but applies to a nonconvex neural class with curvature supplied by flow-matching regression and base smoothing.Baby and Wang (2019) establish the forecasting rate; Baby and Wang (2021, 2022) attain it for proper learners with convex decision sets and curved losses.Source: §2 · p. 2
3 Problem Setting
The setting uses fresh, independent batches and evaluates a deployed field against the current class optimum. It distinguishes class-relative risk drift from class-free target-law drift and imposes bounded-network and smoothing conditions for its guarantees.
3.1 Sampling and Velocity Risk
- A field is selected using earlier batches before the current batch arrives, and dynamic velocity regret compares it with the current represented-class optimum.Learning rounds track environmental change, distinct from flow time used to generate a sample.Source: §3.1 · pp. 2–3
3.2 Two Measures of Nonstationarity
- Relative-risk variation tracks changes in comparisons among represented fields, whereas target-law variation sums W2 movement and does not depend on the class.Common additive shifts in all fields’ risks contribute zero relative-risk variation; under Assumption 5, relative-risk variation is bounded by target-law variation up to remainders.Source: §3.2 · pp. 3–4
3.3 Assumptions
- The neural class is fixed and bounded, and the guarantees assume a fitting routine with accuracy ϵopt; target-law results additionally require an affine path, a smooth base density, and a suitable flow-time law.The smoothing condition excludes uniform flow time but admits truncated uniform, Beta, and logit-normal laws; bounded activations exclude unclipped ReLU-type networks.Source: §3.3 · pp. 4–5
4 Main Results
DyProd-FM maintains fits trained on different historical prefixes and uses sleeping Prod to select a represented field before each fresh batch. Its guarantees adapt to count- or variation-based drift measures, with approximation and fitting costs, and matching lower bounds establish rate optimality up to logarithmic factors.
4.1 The Learner: DyProd-FM
- DyProd-FM keeps fits with different starting times and uses sleeping Prod to select one before the fresh batch arrives.Each active lifetime fits the largest power-of-two prefix of its past and refits when that prefix doubles.Source: §4.1 · p. 5
4.2 Theoretical Guarantees
- The bounds adapt to the smaller change-count or variation cost for both drift measures; the target-law variation branch scales as T^1/3 V_μ^2/3.Approximation and fitting costs remain additive.Source: §4.2 · pp. 6–7
- With fixed dimension, batch size, architecture, and regularity scales, the theorem constants grow only polylogarithmically in T; persistent approximation error contributes a separate term.The approximation contribution is H_T aT or H⁺_T aT, depending on the branch.Source: §4.2 · p. 7
- Matching lower bounds for fixed classes show both rates are optimal in T and the drift budgets up to polylogarithmic factors, factors of m, and additive fitting costs.Only the target sequence varies in the lower-bound construction.Source: §4.2 · p. 7
5 Proof Outline of the Main Results
The proof combines fast estimation from heterogeneous histories, second-moment control for selecting among historical fits, and drift transfer with horizon partitions. For target-law drift, base smoothing yields a second-order transfer that supports the variation bound.
5.1 Historical Estimation for Changing Targets
- Pooling heterogeneous histories reduces sampling error at rate 1/(mq), but a common field can incur positive drift-induced residual even when every round is realizable.The historical estimation bound keeps this common-comparator residual explicit.Source: §5.1 · pp. 7–8
5.2 Aggregation over Dyadic Lifetimes
- The squared flow-matching loss bounds score-difference second moments by velocity risks, allowing Prod selection to preserve a fast rate without averaging represented fields.The selection overhead is O(B log M_e) per lifetime.Source: §5.2 · p. 8
5.3 Relative-Risk Transfer and Proof of Theorem 1
- For relative-risk tracking, horizon partitions trade interval costs against internal variation, while change-based splits remove internal variation altogether.The resulting regret takes the smaller count-based or block-length-based cost, plus approximation and fitting terms.Source: §5.3 · p. 8
5.4 Base Smoothing and Target-Law Transfer
- Base smoothing makes target-law movement a base-noise shift plus a label shift and bounds the earlier-fit excess-risk contribution at second order in Wasserstein distance.With bounded endpoints and an almost-sure label bound, the smoothing remainder ε_sm is zero.Source: §5.4 · p. 9
Appendix E.1.7 gives the detailed proof. Equation (36) bounds ΩT by a multiple of V µ
The target-law analysis uses quadratic drift transfer and horizon partitions to obtain its variation-dependent regret bound. The conclusion presents both regret rates as minimax-optimal for fixed classes up to logarithmic factors, while identifying open settings.
Appendix E.1.7 gives the detailed proof. Equation (36) bounds ΩT by a multiple of V µ
- The quadratic transfer yields a target-law variation branch of order T^1/3 V_µ^2/3, with approximation, fitting, and smoothing remainders.The proof takes the smaller of this branch and the count branch; the smoothing contribution includes 37ϵ_sm T V_µ.Source: Appendix E.1.7 · p. 9, §5.5 · p. 10
- Smoothing vanishes near the target endpoint, so the argument does not cover uniform flow time.The paper identifies nonaffine interpolations, target-law rates under uniform flow time, dependence on m, and computational training guarantees as open.Source: Appendix E.1.7 · p. 9, §6 · p. 10
5.5 Proof of Theorem 2 from Target-Law Transfer
- When N_µ ≥ T, Theorem 1 supplies the count branch under the same flow-time law.The target-law proof partitions the horizon into maximal pieces and sums interval bounds before taking the smaller branch.Source: §5.5 · p. 10
6 Conclusion
- The conclusion states that one proper, budget-free learner attains minimax-optimal rates for fixed classes up to logarithmic factors.The appendix introduction frames the related-work discussion around drifting targets, budget-free regret for nonconvex classes, and two measures of nonstationarity.Source: §6 · p. 10, A Extended Related Work · p. 13
A.1 Flow Matching, Rectified Flow, and Stochastic Interpolants
The related work distinguishes the paper’s drifting-target, predictive setting from fixed-target flow-matching theory and convex dynamic-regret results. It connects the paper’s methods to prior work while marking the scope of its analysis and lower bounds.
A.1 Flow Matching, Rectified Flow, and Stochastic Interpolants
- Linear and sine–cosine paths and affine schedules fit the analysis, while latent-noise interpolants, nonaffine paths, and non-independent pairings fall outside target-law results.A logit-normal flow-time law used in rectified-flow training satisfies the paper’s flow-time assumption.Source: §A.1 · p. 13
A.2 Statistical Theory of Flow Matching
- Earlier flow-matching analyses study fixed targets and i.i.d. samples, whereas this work studies predictive deployment under drifting targets and dynamic regret.The paper retains an approximate-global-fitting interface rather than proving convergence of a generic neural optimizer.Source: §A.2 · p. 13
A.3 Nonstationary Online Learning and Dynamic Regret
- Relative-risk variation charges changes that distinguish represented fields, while target-law variation measures movement of the targets themselves.Dyadic lifetimes borrow geometric-covering ideas, and the sleeping-Prod master’s fast bound uses squared-loss control of score-difference second moments.Source: §A.3 · pp. 13–14
A.4 Fast Dynamic Regret and Total-Variation Forecasting
- The target-law rate has total-variation forecasting exponents T^1/3 V_µ^2/3 for a proper learner over a nonconvex neural class.The paper attributes the curvature to the flow-matching regression identity and base smoothing, rather than parameter-space strong convexity or exp-concavity.Source: §A.4 · p. 14
A.5 Fast Statistical Rates and Localization
- For nonconvex represented classes, the Bernstein comparison retains an approximation-error term; a deterministic cover and one-sided Bernstein inequalities yield expectation bounds.For the parametric class, the localized route gives the same order.Source: §A.5 · p. 14
A.6 Minimax Lower Bounds
- The lower bounds vary only the target sequence while keeping the class and problem scales fixed across horizon and budget.A trainable slope lets the hard class follow a far target component, avoiding constructions that shrink the class as budgets change.Source: §A.6 · p. 14
B.1 Notation
- The notation table defines T, m, and d as horizon, triples per round, and dimension, and distinguishes target-law variation V_µ from relative-risk variation Ω.It also names N_µ and N_ω as the corresponding change-count caps.Source: §B.1 · p. 15
B.2 Algorithm and Implementation Details
This appendix specifies the gated historical fitting procedure and its predictability conditions, and develops the bounds, estimation identities, and concentration arguments used to analyze it. It also explains how nonconvexity, model approximation, endpoint truncation, and heterogeneous histories affect those results.
B.2 Algorithm and Implementation Details
- PREFIXFM runs standard flow-matching training on a gated historical prefix, with optimizer accuracy treated as an assumption and flow-time laws chosen to satisfy the theorem-specific conditions.The optimizer and iteration count determine the fitting error; the analysis does not establish accuracy guarantees for particular training routines.Source: §B.2 · p. 15
B.2.1 Initialization and Predictability
- Dyadic fits use only their own completed prefix data, while pre-batch fields, predictable fallback, and normalized sleeping-Prod weights ensure candidates are formed before evaluation.Longer fits warm-start from completed half-length fits with optimizer state reset; lifetimes sharing a start share fits.Source: §B.2.1 · p. 16
B.3.1 Conditioning and Predictability; B.3.2 Finiteness, Measurability, and the Regression Identity
- Conditioning on the environment and past fixes candidates and probabilities while fresh batches and selection seeds remain independent; square-loss orthogonality yields the regression identity and measurable risks.Deterministic lifetime endpoints and uniform concentration over candidate parameters avoid applying fixed-sample results to stopping-time histories.Source: §B.3.1 · p. 16, §B.3.2 · p. 17
B.3.3 Risk Oscillation and an Offset Example
- When targets alternate between N(0, 1) and N(0, 4), constant fields have unchanged relative risk and ω_t = 0 despite absolute risk changes of 3 per alternation.The example shows that the regret budget ignores common risk increments and does not claim that the fields accurately generate both targets.Source: §B.3.3 · p. 17
B.4.1 Compactness and Network Bounds; B.4.2 Gated State Radius and Joint Loss Cover
- Compact network parameters give bounded, Lipschitz fields and parameter sensitivity; the gated proxy-loss class has a uniform cover whose complexity depends on trainable parameter count and network constants.The cover applies to complete vector-output networks, and its architecture-dependent constants are not all logarithmic.Source: §B.4.1 · pp. 17–18, §B.4.2 · p. 18
B.4.3 Learned Dynamics and Approximation Boundaries
- Bounded globally Lipschitz fields generate unique learned ODE solutions, but bounded outputs can impose approximation error, and the guarantees may be loose for overparameterized or excluded activation classes.The gated radius is necessary for the entropy calculation because parameter sensitivity need not hold uniformly over the full input space.Source: §B.4.3 · p. 19
B.5 Endpoint Gating and Original-Risk Transfer; B.5.1 Consequences Used by the Statistical Proof; B.5.2 Tail Formulations and Bounded-Support Recovery
- Endpoint gating bounds proxy loss and transfers its risk to original risk with additive truncation error; known bounded support permits using the original loss directly with zero error.The shared gate retains rejected samples in the denominator, and the gated regression target need not equal the original conditional mean.Source: §B.5 · p. 19, §B.5.1 · p. 20, §B.5.2 · p. 20
C Useful Results to Prove Theorems 1 and 2; C.1 Historical Statistical Estimation; C.1.1 A Derived Approximate Bernstein Inequality
- For heterogeneous deterministic histories, the common best represented field admits approximate Bernstein variance control with residual error, without requiring parameter-space curvature.The residual may be positive even when each round is realizable, and separated tied minimizers show why it cannot generally be removed.Source: §C.1.1 · p. 21, §C.1 · p. 21, C Useful Results to Prove Theorems 1… · p. 21
C.1.1 A Derived Approximate Bernstein Inequality
- For nonconvex classes, the approximation term in the inequality is substantive; its example marks a proof boundary, not a regret lower bound.The variance is not bounded by zero excess risk.Source: §C.1.1 · p. 21
C.1.2 Uniform Concentration for a Fixed History
- Uniform concentration uses independent, centered bounded observations, Bernstein without an identical-distribution reduction, and a ζ-cover union bound with failure probability e^-z.The fixed-field variance is at most 8Bn[r_H(v) + 2ā_H], and the linear Bernstein remainder is enlarged from 2Bu/(3n) to 2Bu/n.Source: §C.1.2 · pp. 21–22
- The resulting event controls every field after ζ-cover approximation and permits a data-dependent approximate minimizer without requiring independence from the history.The comparison transfers bounds from a cover center to the field using proxy-loss and population-excess approximation terms.Source: §C.1.2 · p. 22
C.1.3 Proof of Proposition 1
Historical estimation yields a fast statistical contribution in stationary settings, with an approximation-dependent interaction when the class is misspecified. Historical-to-current transfer then bounds candidate regret using variation, with a second-order target-law counterpart under an additional flow-time assumption.
C.1.3 Proof of Proposition 1
- In a stationary realizable problem, the leading statistical contribution is BΓ/n; in a stationary misspecified problem, an interaction of order BΓā_H/n remains.That interaction precludes a blanket 1/n proper-selection claim for arbitrary nonconvex classes.Source: §C.1.3 · p. 23
C.1.4 First-Order Historical-to-Current Transfer
- Historical-to-current transfer gives first-order oscillation-budget bounds for every flow-time law, while Lemma E.7 gives second-order target-law bounds under Assumption 5.The proof identifies cancellation of common risk offsets in the historical comparison.Source: §C.1.4 · p. 23
C.1.5 A Localized Rademacher Route
The localized Rademacher route reaches the same statistical order as the cover route up to logarithmic factors, while the aggregation analysis supplies pathwise and population guarantees for DyProd-FM. Historical fits and disjoint dyadic covers support the online bounds, with computational costs and fitting assumptions made explicit.
C.1.5 A Localized Rademacher Route
- The localized route extends the i.i.d. inequality to independent, non-identically distributed observations by using their average law and average variance.The argument uses concentration and symmetrization for independent coordinates, then the sub-root fixed-point bound.Source: §C.1.5 · p. 24
- Both estimation routes have statistical order BP/n up to logarithmic factors, but localization does not remove the parameter-count dependence.The cover route has explicit constants; the localized route inherits unspecified concentration constants.Source: §C.1.5 · pp. 23, 25
C.2.1 Pathwise Potential Bound
- The sleeping Prod potential gives a lifetime guarantee for every bounded score sequence, without a stochastic assumption.The master’s population guarantee separately relies on fresh regression feedback, predictable candidates, and squared loss.Source: §C.2.1 · p. 25, §C.2.2 · p. 26
C.2.2 Population Transfer and the Fast Master
- The master controls population regret by bounding score-difference second moments, whose population component persists as batch size grows.This separates the 1/m gain in base estimation from the batch-size-independent aggregation cost.Source: §C.2.2 · p. 26
C.2.3 Historical Fits over a Lifetime
- Dyadic historical prefixes yield lifetime fits whose expected costs can be summed despite overlapping training data.No union bound over experts is needed because each prefix bound holds in expectation.Source: §C.2.3 · pp. 26–27
C.2.4 Resource Accounting and Computational Scope
- The implementation makes O(T) fitting calls and processes O(mT log T) examples, but this data-volume count is not an optimizer running-time guarantee.The guarantee is conditional on the fitting routine satisfying Assumption 4.Source: §C.2.4 · p. 27
C.3 Disjoint Dyadic Covers
- A consecutive interval can be partitioned into at most 2(1 + ceil(log2 T)) disjoint dyadic lifetimes, with at most two pieces of each length.These covers let interval bounds be applied without overlapping internal variation edges.Source: §C.3 · p. 27
D Proof of Theorem 1
Theorem 1’s proof combines lifetime and master bounds with interval partitions to establish count- and variation-based guarantees. The supporting lemmas for Theorem 2 develop Hellinger tools, a representation of target moves, and label-tail control.
D Proof of Theorem 1
- The proof combines historical lifetime bounds, fast master bounds, and dyadic interval covers before applying change-count and variation partitions.The resulting theorem statement is under the predictive protocol, Assumptions 1–4, and the caps in Equation (9).Source: D Proof of Theorem 1 · pp. 28–29
- At fixed architectural and endpoint scales, the suppressed logarithmic factors depend on P and T; when those scales vary with the horizon, the explicit theorem is the relevant statement.The proof establishes Γ = O(1 + P log(emT)) under the stated fixed-scale conditions.Source: D Proof of Theorem 1 · p. 29
E.1.1 Hellinger Tools
- A translation of the base distribution has squared Hellinger distance at most ι∥σ∥2/8.This controls the change of measure used in the target-law argument.Source: §E.1.1 · p. 30
E.1.2 The Base-Shift Representation
- A target move can be represented as a shift of the base noise together with a shift of the label at the same flow-time input.Conditioned on the coupled targets and flow time, the shifted base has law νσr.Source: §E.1.2 · p. 30
E.1.3 Label Tails
- The label-tail lemma bounds the probability-weighted squared-label tail using the endpoint moment assumptions.Its threshold is Mz = cZ(1 + M).Source: §E.1.3 · p. 31
E.1.4 Proof of Lemma 1
The supporting analysis links target movement to risk changes through base smoothing and approximate quadratic growth, then uses second-order drift transfer to derive historical and interval bounds. Its conclusions retain approximation, smoothing, and fitting residuals where specified.
E.1.4 Proof of Lemma 1
- Base smoothing bounds changes in comparisons between fields without requiring class-level Lipschitzness or regularity of the targets.The proof uses the output bound Bv and does not difference a represented field at two inputs.Source: §E.1.4 · p. 31
E.1.5 Approximate Quadratic Growth
- Flow matching supplies an approximate quadratic-growth relation for every nonconvex class, with approximation error as its only residual.The relation is exact in the realizable case.Source: §E.1.5 · p. 32
E.1.6 Second-Order Drift Transfer
- Second-order drift transfer bounds current excess risk by earlier excess risk, a squared drift term, and approximation residuals.One stated bound is Ft(u) ≤ 3Fs(u) + 14ℏ2 + 12as + 10at + 4ρ.Source: §E.1.6 · p. 32
E.1.7 Proof of Proposition 2
- The relative-risk variation is bounded by terms linear and quadratic in target-law movement, with smoothing remainders.The proposition sums these one-step bounds over consecutive rounds.Source: §E.1.7 · p. 32
E.1.8 Proof of Proposition 3; E.1.9 Admissible Flow-Time Laws
- For linear paths with Beta(a,b) flow time, the relevant moment is finite exactly when b > 2; endpoint behavior also constrains admissible schedules.For the sine–cosine path, the stated moment bound acquires a factor π2/4.Source: §E.1.9 · p. 33, §E.1.8 · p. 33
E.1.10 Historical Transfers
- Historical target-law transfer bounds use the cumulative Wasserstein movement from the history to the current round, with approximation and smoothing remainders.The transfer is stated pointwise for every represented field before taking expectations over data.Source: §E.1.10 · p. 33
E.1.11 Historical Fits over a Lifetime
- Dyadic historical fits yield a lifetime bound by summing estimation and drift costs across prefixes.The statistical terms scale with BΓ log(enI)/m, while the lifetime bound also includes approximation, current-risk, and residual terms.Source: §E.1.11 · pp. 33–34
E.1.12 Interval Bound
- Combining the lifetime estimate with the shared master bound gives an interval bound, which extends to consecutive intervals using disjoint dyadic covers.The resulting drift terms depend on both linear and squared internal target-law variation.Source: §E.1.12 · p. 34
E.2.1 Total-Variation Partition
The target-law proof partitions rounds by variation and combines interval bounds to obtain a rate. Fixed-class lower-bound constructions provide matching benchmarks, including a Gaussian counting construction whose information structure limits what a predictive learner can know before deployment.
E.2.1 Total-Variation Partition
- Partitioning by target-law variation and applying the interval bound yields the target-law branch of Theorem 2 under its stated assumptions and caps.The count branch follows from Theorem 1 because Nω ≤ Nμ.Source: §E.2.1 · pp. 34–35
F Minimax Lower Bounds
- At fixed scales, the lower bounds use one fixed class per construction, with only the target sequence varying, and apply to proper learners.The constructions use fixed architectural and problem constants independent of T and the budget.Source: F Minimax Lower Bounds · p. 36
F.1 Information Structure and a Two-Point Reduction
- Under the sine–cosine schedule, the learner’s information before a round is bounded in total variation by the target-draw information from rounds where the sequences differ.This gives a two-point reduction for the lower-bound arguments.Source: §F.1 · p. 36
F.2 The Gaussian Family
- For Gaussian targets, the represented field indexed by the target mean is optimal, and stale fields incur squared-mean error.The family also yields a positive historical approximation residual despite being realizable round by round.Source: §F.2 · p. 37
F.3 Counting Lower Bounds
- Gaussian targets with N mean changes force regret of order N + 1 in both variation settings for every learner.The construction places independent signs on consecutive blocks, making the learner’s information independent of each new block sign at its first round.Source: §F.3 · p. 37
F.4 The Rare-Mixture Family for Relative-Risk Variation
The lower-bound constructions keep the class fixed while varying target distributions. The rare-mixture family supports a relative-risk lower bound, while Gaussian targets provide the target-law variation construction.
F.4 The Rare-Mixture Family for Relative-Risk Variation
- A fixed rare-mixture class uses a trainable slope to move its cutoff into the tails, letting the class detect a small-mass far component as that component moves.The targets are mixtures of a standard Gaussian bulk and a far Gaussian component with mass η; the class and architectural bounds remain fixed as η varies.Source: §F.4 · pp. 37–38
- For the rare-mixture family, equal consecutive signs give zero relative-risk variation, while opposite signs yield variation bounded by 4ηR.The risk geometry over the class is used to construct the relative-risk lower bound for proper learners in this fixed class.Source: §F.4 · pp. 38–39
- The rare-mixture lower-bound construction uses blocks of independent signs; before a block’s sign is revealed, the learner’s information differs by at most total variation 1/4.The construction chooses η = 1/(4mH) for blocks of length H and keeps the final sign for any remaining rounds.Source: §F.4 · p. 39
- The relative-risk lower bound applies to proper learners in one fixed admissible class, not to every larger neural class or arbitrary measurable fields.The family also has approximation and target-law costs accounted for in the stated lower-bound comparison.Source: §F.4 · p. 39
F.5 The Gaussian Family for Target-Law Variation
- The target-law lower-bound construction uses Gaussian targets with means that change in blocks, with independent signs and means bounded by R0.The construction is presented for every learner and a flow-time law satisfying Assumption 5(c).Source: §F.5 · p. 40
F.6 Matching the Upper Bounds
The fixed-class lower bounds match the upper bounds in their exponents of T and the drift budgets. The resulting rates are optimal up to logarithmic factors, with additional complexity and fitting-cost qualifications.
F.6 Matching the Upper Bounds
- The counting comparison pairs the Gaussian-family lower bound with the upper bound, with the fitting cost retained in the upper bound.The passage states that the Gaussian family has zero approximation cost for this comparison.Source: §F.6 · p. 40
- For relative-risk and target-law variation, the upper-bound comparisons include approximation and fitting terms alongside the corresponding lower bounds.The rate-level optimality conclusion is qualified by polylogarithmic factors in mT and factors polynomial in m.Source: §F.6 · p. 40
- The upper and lower bounds have matching exponents of T and the drift budgets, establishing rate optimality up to logarithmic factors.At fixed scales, the comparison also allows factors polynomial in m and additive fitting costs.Source: §F.6 · p. 40