PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Universality of Online Discrepancy

Sunghyeon Jo, Taekyun Lee

arXiv:2610.00103v1math.PRcs.DS

TL;DR

The paper addresses whether the Gaussian upper bound extends to non-Gaussian inputs under a finite-fourth-moment assumption. It couples signed vectors to controlled Brownian paths and establishes that the exact limiting optimum for Rademacher inputs equals the Gaussian optimum.

  • Problem

    Whether the Gaussian upper bound has a matching non-Gaussian version under a finite-fourth-moment assumption remained open.

    Source: §1 · p. 1

  • Method

    The proof couples signed vectors to controlled Brownian paths, while tracking errors across all coordinates.

    Source: §1.2 · p. 3

  • Results

    Under the same finite-fourth-moment assumption, the exact limiting optimum for Rademacher inputs equals the Gaussian optimum.

    Source: §1 · p. 1

  • Takeaways & Limitations

    This resolves the question of whether the Gaussian upper bound extends to non-Gaussian inputs under that assumption.

    Source: §1 · p. 1

    The weakest tail condition sufficient for universality remains open; the stated assumption is a finite fourth moment.

    Source: §1 · p. 1, §7.2 · p. 29

Abstract

from arXiv · show

We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as $M/N\to\alpha\in(0,\infty)$, the optimal value divided by $\sqrt N$ converges to a limit $R_\alpha$ independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In particular, it determines the exact asymptotic optimum for Rademacher inputs. For every $\kappa>R_\alpha$, we construct a randomized online algorithm whose final signed sum has $\ell^\infty$ norm at most $\kappa\sqrt N$ with high probability; for $\kappa<R_\alpha$, every online algorithm has vanishing success probability. Consequently, the online threshold of the symmetric binary perceptron is universal at every positive margin. The main step is a coupling that transfers Brownian controls to non-Gaussian inputs, while truncation controls rare large entries.

1 Introduction

The exact limiting optimum was known for Gaussian inputs, while a matching upper bound for non-Gaussian inputs remained open. This paper resolves that question under a finite-fourth-moment assumption and develops the resulting universality and online threshold.

1 Introduction

  • The Gaussian optimum and a general lower bound were known, but the matching non-Gaussian upper bound—and thus the exact limiting optimum—remained open.The paper resolves this question under the same finite-fourth-moment assumption.Source: §1 · p. 1

1.1 Our results

  • The limiting discrepancy coefficient is distribution-independent under the stated moment assumptions, and for Rademacher inputs it equals the Gaussian optimum.For the online SBP threshold, the coefficient is the same across the laws in Theorem 1.1; densities below the threshold are achievable, while above it the supremal success probability vanishes.Source: §1 · p. 1, §1.1 · pp. 2–3
  • For κ > Rα, the quantitative upper bound applies uniformly to centered, variance-one laws with bounded fourth moment, with constants depending only on the theorem parameters.The tail term vanishes for each fixed law; the stated quantitative bounds require a fixed positive gap κ − Rα.Source: §1.1 · p. 3

1.2 Overview of the proof

  • The proof transfers Brownian controls to non-Gaussian inputs by coupling signed vectors, controlling accumulated errors across coordinates, and truncating entries to manage large values.The lower-bound argument uses compactness of empirical drift and martingale path measures; when κ < Rα, admissible limiting Brownian controls cannot have all terminal coordinates in [−κ, κ].Source: §1.2 · pp. 3–5
  • The upper-bound construction follows an approximated Brownian control before a split, then uses a correction drift and Föllmer drift to confine the final fluctuation.The dissipative feedback stabilizes the Euler scheme under accumulated coupling errors, while bounded auxiliary drift handles exceptional trajectories.Source: §1.2 · p. 4

1.3 Related work

  • The paper distinguishes its exact proportional-regime constant from prior polynomial-time bounds for symmetric sub-Gaussian coordinates and from Gaussian-only feasibility characterizations.The cited prior bound addresses arbitrary prescribed horizons and efficient computation; the cited Gaussian-matrix work studies algorithms with a dimension-independent Lipschitz constant.Source: §1.3 · p. 5

2 The Brownian control problem

The section formalizes online signing and defines a Brownian control value that serves as the Gaussian benchmark for the discrepancy objective.

2.1 Online algorithms and normalization

  • The online algorithm chooses each sign after observing the current vector, and the section defines the optimal expected terminal discrepancy in the proportional-dimension setting.Source: §2.1 · p. 6

2.2 The Brownian control value

  • The Brownian control value is defined using controls progressively measurable in the natural Brownian filtration and subject to a drift constraint.Source: §2.2 · p. 6
  • The infimum defining the Brownian value is attained, and R(c) is continuous and nonincreasing for c > 0.Source: §2.2 · p. 6
  • Projecting an optimal control onto the natural Brownian filtration preserves its terminal bound and pointwise L2 constraint.Source: §2.2 · p. 6

3 A coupling for non-Gaussian signings

The section constructs a coupling from non-Gaussian signings to independent-coordinate inputs and an auxiliary fair sign, then controls drift errors to transfer Brownian controls.

3 A coupling for non-Gaussian signings

  • Truncation makes the coupling applicable under a finite fourth-moment assumption, while the algorithm updates its state using truncated entries.Source: §3 · p. 7

3.1 Realizing a prescribed mean drift

  • A randomized sign choice realizes a prescribed mean drift for truncated inputs using a smooth sign function and a normal-approximation estimate.Source: §3.1 · pp. 7–8

3.2 An auxiliary sign for nonsymmetric inputs

  • For nonsymmetric inputs, the signing is coupled to a fair Rademacher sign and an independent-coordinate vector, with moment bounds on the resulting error.Source: §3.2 · pp. 8–9

3.3 Delocalizing the prescribed drift

  • Fresh independent Rademacher perturbations delocalize the prescribed drift, increasing its normalized Euclidean norm by at most γ while keeping terminal drift vanishing.Source: §3.3 · p. 10

3.4 Iteration and strong approximation

  • Iteration yields a martingale-plus-bias decomposition, and strong approximation transfers the coordinate paths to Brownian motion with errors whose exceedance probabilities can be made polynomially small.Source: §3.4 · pp. 11–13

4 The online algorithm

This section constructs and analyzes an online algorithm using Brownian controls and confining feedback, establishing high-probability admissibility and target discrepancy. It selects parameters and uses truncation and tail estimates to transfer the guarantee to original inputs with a common fourth-moment bound.

4 The online algorithm

  • For each fixed κ0>Rα, the proposition provides polynomial bounds for truncated inputs, while a tail estimate controls the contribution from untruncated entries.The proof bounds failure and expected excess above κ using the truncated discrepancy above κ0 and the unsigned tail sums.Source: §4 · p. 13

4.1 Choice of the Brownian control

  • For a target a>Rα, the Brownian control can be chosen as a bounded, finite-rational simple predictable control on a horizon T=1−h, with fixed positive slack.The approximation preserves the uniform-in-time L2 budget.Source: §4.1 · pp. 14–15

4.2 Confining the final block

  • The final block combines a correction toward the target interval with Föllmer feedback that confines coordinate noise; truncating the feedback costs linearly in δN.The discretized feedback admits polynomial probability bounds when coupled to its continuous truncated process.Source: §4.2 · pp. 15, 17

4.3 The algorithm and its computational cost

  • For every κ>Rα, Algorithm 1 achieves a final signed-sum norm at most κ√N with high probability, uniformly over the stated input class near aspect ratio α.The guarantee holds for sufficiently large N and laws with a common fourth-moment bound K.Source: §4.3 · p. 19
  • With fixed theorem parameters and precomputed control data, each arrival uses O(M) arithmetic operations and O(M) working memory.The scalar feedback evaluations include the smooth sign function and the logarithmic derivative of the heat semigroup.Source: §4.3 · pp. 19–20

4.4 Analysis of the algorithm

  • The analysis couples the algorithm to Brownian strong approximations applied separately before and after the split.Source: §4.4 · p. 20
  • All drift-admissibility tests pass with probability 1−O(N^-θ), yielding final discrepancy at most κ√N with probability tending to one.Source: §4.4 · pp. 20, 22

4.5 Choosing the control parameters

  • Parameter choices give failure probability O(N^-θ) and expected excess O(N^-A), with the strict budget inequalities holding in a fixed neighborhood of M/N=α.Source: §4.5 · p. 23

4.6 Effect of the discarded entries

  • For each fixed law, discarded-entry tails vanish, so the truncated-input algorithm transfers to original inputs and yields the limiting upper bound, uniformly over classes with uniformly integrable fourth moments.The argument applies the truncated-input signs to the original columns and lets κ decrease to R_α.Source: §4.6 · p. 23

5 Lower bounds

The lower-bound analysis shows that below the Brownian control value Rα, online algorithms cannot succeed with nonvanishing probability. It connects limits of empirical paths to admissible Brownian controls to establish this infeasibility.

5 Lower bounds

  • The lower bounds assume mean-zero, unit-variance entries with a finite fourth moment, and the proof of the expected lower bound uses the empirical-path limit.The rectangular scaling adapts the Gaussian argument to the proportional regime.Source: §5 · p. 24, §5.1 · p. 25, §5.2 · p. 25

5.1 Empirical path measures

  • Empirical path-measure laws are tight, and every limit is supported on laws whose canonical processes have Brownian martingale part and admissible drift.The result holds for randomized online algorithms and sequences with M/N → α.Source: §5.1 · p. 24

5.2 Infeasibility below the Brownian value

  • For mean-zero, unit-variance entries with finite fourth moment, every online algorithm has vanishing success probability at any fixed κ < Rα.For algorithms whose expected discrepancy approaches Rα, the discrepancy also converges to Rα in probability and in mean absolute deviation.Source: §5.2 · p. 25

6 Moment bounds and independent entries

Higher moments sharpen the fixed-gap bounds, while the independent-entry extension establishes the same limiting optimum when entry distributions vary across coordinates, subject to uniform integrability of fourth moments.

6.1 Bounds under higher moments

  • For q > 4, Rosenthal’s inequality sharpens the fixed-gap failure-probability and expected-excess bounds under a common qth-moment bound.The section states that the same construction gives the higher-moment rate in Corollary 1.4.Source: §6.1 · p. 26

6.2 Independent entries

  • With independent entries whose distributions may differ and whose fourth moments are uniformly integrable, the optimal expected online discrepancy converges to Rα.The upper and lower bounds extend to these arrays; the lower-bound argument uses independent-coordinate estimates in place of permutation symmetry.Source: §6.2 · pp. 26–28

7 The online threshold of the symmetric binary perceptron

The discrepancy curve is continuous and strictly increasing in density, so each positive margin determines a unique online threshold. The section also gives an endpoint bound and identifies an open problem in characterizing the small-margin constant.

7.1 Monotonicity of the discrepancy curve

  • R is continuous and strictly decreasing, so α ↦ Rα is continuous and strictly increasing from zero to infinity.This monotonicity makes the equation Rα = κ have a unique solution for each positive margin.Source: §7.1 · p. 28

7.2 The threshold and its asymptotics

  • For every admissible entry law, the online symmetric binary perceptron threshold is determined by the unique density solving Rα = κ.The theorem identifies this threshold with the supremal achievable density whenever Rα is below the margin and infeasible when it is above.Source: §7.2 · p. 28
  • The reported result is the bound 1.09 ≤ V∞1 ≤ 1.97.Source: §7.2 · p. 29
  • The weakest tail condition for universality, optimality of the higher-moment rate, and efficient implementation of near-optimal Brownian controls remain open questions.The section also asks what numerical precision such an implementation requires.Source: §7.2 · p. 29

AI Usage Disclosure

GPT-5.6 Sol assisted with exploratory proof discussions and manuscript drafting and revision; the authors accept responsibility for the paper’s contents and correctness.

AI Usage Disclosure

  • GPT-5.6 Sol assisted with exploratory proof discussions and manuscript drafting and revision; the authors take full responsibility for the paper’s contents and correctness.Source: AI Usage Disclosure · p. 29

A Projection and approximation of Brownian controls

This appendix develops tools for working with Brownian controls and couplings, including projection, bounded and simple predictable approximations, and measurable kernels.

A.1 Projection onto the Brownian filtration

  • Projection onto the Brownian filtration gives a conditional-expectation representation while preserving convex constraints and an energy bound.The projected control is the conditional expectation of the original control given the Brownian filtration.Source: §A.1 · pp. 29–30

A.2 Bounded approximations

  • Bounded approximations can be projected onto the Brownian filtration without losing boundedness or the pointwise L2 budget.The approximation argument applies on fixed finite horizons, including horizons obtained by rescaling the budget.Source: §A.2 · p. 30

A.3 Approximation by simple predictable controls

  • Simple predictable controls approximate the projected control using bounded, globally Lipschitz functions of finitely many past Brownian evaluations.The approximants can be chosen to have finite rational descriptions.Source: §A.3 · pp. 30–31

B Measurability of the coupling

  • A measurable maximal coupling attaches a variable with the target law while preserving the already sampled variable.Applied successively, the kernels produce independent target-law coordinates while preserving the original online trajectory.Source: B Measurability of the coupling · pp. 31–32

C Föllmer drifts and Euler approximation

  • The appendix tracks reduced drift budgets, deterministic terminal cutoffs, and bounds uniform over coordinates in its Föllmer-drift and Euler-approximation arguments.It builds on results in [14] and [22].Source: C Föllmer drifts and Euler approximation · p. 32

C.1 Localization and the score martingale

The appendix represents a target terminal law through a score-driven diffusion and constructs compactly supported densities whose support radius shrinks with the time horizon.

C.1 Localization and the score martingale

  • The logarithmic derivative of a smoothed density serves as the drift in a diffusion representation whose terminal law is fΓ_h.The drift integral has a continuous terminal limit, and the representation extends to time h.Source: §C.1 · pp. 32–33

C.2 Construction of the compactly supported density

  • A cutoff construction yields compactly supported densities with radius tending to zero as h decreases.The radius tends to zero because h log(1/h) tends to zero.Source: §C.2 · pp. 33–34

C.3 Euler approximation

The appendix bounds the Euler approximation error and specifies parameter choices for quantitative probability estimates in the online algorithm.

C.3 Euler approximation

  • Coupling the diffusion and Euler scheme with the same Brownian path supports terminal error bounds that remain valid after the cutoff.The cited estimates use terms of order O(N^-1) and O(δ_N + N^-1), followed by a union bound over M = O(N) rows.Source: §C.3 · pp. 34–35

D Quantitative estimates for the online algorithm

D.1 Choice of parameters

  • The parameter choices make the required probability exponents available under a fourth-moment bound on the original entries.Higher input moments are used only after truncation; choosing θ = 2A + 3 yields O(N^-A) bounds in Proposition 4.1.Source: §D.1 · p. 35

D.2 Empirical moment bounds

The appendix bounds empirical moments using Rosenthal’s inequality, Markov’s inequality, and union bounds, then controls discretization errors by Gaussian tails. These estimates support polynomial or exponential probability bounds under the stated growth conditions.

D.2 Empirical moment bounds

  • Rosenthal’s inequality applied to centered |A_j,i|^s yields the empirical-moment estimate, which also holds with s replaced by any 1 ≤ r ≤ s.Markov’s inequality and a union bound give the first estimate; JN = O(N) and M ≍ N give the second.Source: §D.2 · p. 36
  • By (4.27), ideal Euler-scheme drifts supply (D.2), and (4.2) makes the (D.3) exponent smaller than −θ; pre-split drift empirical moments have exponential tails, while final-time calculation gives (4.46)'s polynomial probability bound.The terminal variable is Gaussian plus a bounded drift and has moments of all orders.Source: §D.2 · p. 36

D.3 Discretization of the observation times

  • Rounding each observation or block time down to the nearest 1/N grid point produces Brownian increments controlled by Gaussian tails and a union bound over O(M) increments.The finite set of times is the one specified in Definition 4.3.Source: §D.3 · p. 36

D.4 Admissibility and terminal integrability

The admissibility proof constructs a good event and rules out a first failed test by comparing candidate drifts with ideal Brownian drifts. On that event, the terminal identity applies, and the truncated discrepancy has a bounded second moment.

D.4 Admissibility and terminal integrability

  • The applied drifts obey the required bounds on every trajectory, including after a failed test, while comparisons with intended drifts are restricted to times before τ.After failure, the drift is replaced by γη_k and remains so thereafter.Source: §D.4 · pp. 36–37
  • A first failed test is ruled out by comparing its candidate drift with the ideal Brownian drift and using slack and perturbation bounds to pass the norm, energy, magnitude, and delocalization tests.For tests through k0, the observations used to form the candidate drift precede that test; for later tests, the split-time comparison and Lipschitz Euler updates provide the comparison.Source: §D.4 · p. 37
  • P(G_N^c) = O(N^-θ), and on G_N all admissibility tests pass, so the terminal identity applies.The good event combines coupling, Brownian rounding, perturbation, empirical-norm, confinement, and small-norm bounds.Source: §D.4 · p. 37
  • The terminal signed sum is a vector of independent N(0, 1) variables plus an Ls error of order N−(s−4)/(6s), a bound for truncated discrepancy Dtr.The Gaussian maximum has L2 norm O(√log M); the bias and martingale terms have bounded L2 norms.Source: §D.4 · p. 37
Loading 2610.00103v1…