A two-layer ReLU network can be trained with a convex program, a problem with a single optimum that a solver finds reliably. The trick is to fix, in advance, which neurons are "on" for which data points. Kim and Pilanci draw random hyperplanes to set those on/off patterns and solve a convex problem over output weights. They prove the result is within a $O(\sqrt{\log n})$ factor of the true non-convex optimum on $n$ points. That proof assumes independent Gaussian inputs. Much real data arrives instead as a trajectory: sensor streams, molecular simulations, agent rollouts. Consecutive points are nearly identical there, and the effective number of independent observations is $n\gamma_{ps}$ rather than $n$, where $\gamma_{ps}$ (the pseudo-spectral gap) measures how fast the process forgets its past. This proposal asks whether the number of random neurons a convex relaxation needs on such data is governed by $n\gamma_{ps}$ instead of $n$.
Put plainly: on a slowly mixing trajectory, a random hyperplane rarely separates consecutive points. The set of distinct activation patterns therefore collapses toward the number of "effectively independent" stretches of the trajectory. If that is right, one can estimate $\gamma_{ps}$ from the single observed trajectory and use it to choose how many random neurons to sample. The result would be a polynomial-time estimator that comes with two checks computed from the same trajectory: a duality gap certifying the optimization, and an empirical PAC-Bayes bound certifying generalization. If the hypothesis is wrong, we learn instead that dependence breaks the relaxation's tightness. That too is a result nobody has, because the Kim–Pilanci analysis says nothing about correlated inputs.
Core Claim
The claim is empirical first and theoretical second. On stationary mixing input sequences, let $m_\varepsilon$ be the number of sampled random gates needed for the relaxed convex program to reach relative optimality gap $\varepsilon$. We hypothesize that $m_\varepsilon$ scales with the effective sample size $n\gamma_{ps}$ and only logarithmically in $1/\varepsilon$, not with the nominal $n$.
The logarithmic-in-precision part borrows its intuition from the subset-sum view of strong lottery tickets. Optimal Lottery Tickets via Subset Sum shows that $O(\log(1/\epsilon))$ random samples per target weight suffice when you are allowed to select among them. The analogy is only that: here we select random gates and fit their output weights convexly, rather than pruning frozen weights. The convex program's sparsity penalty selects a small subset of the sampled gates. That makes the relaxation a "half lottery ticket": the first layer stays random and frozen, and only its selection and output weighting are learned.
There are two competing hypotheses, and we test both. H0 says dependence is irrelevant and $m_\varepsilon$ tracks $n$. H2 says dependence hurts: temporally clustered inputs make the empirical covariance lopsided, and the cone-sharpness argument behind the $\sqrt{\log n}$ gap weakens. Distinguishing among the three is the first deliverable.
Research Program
The object of study is the gated convex program from Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time. That paper supplies the method. Our contribution is to analyze and size it under dependence.
Given a trajectory $X\in\mathbb{R}^{n\times d}$ with targets $y\in\mathbb{R}^n$, draw $m$ Gaussian gate vectors $h_j$. Each gate defines a diagonal 0/1 matrix $D_j=\mathrm{diag}(\mathbf 1[Xh_j\ge 0])$ recording which points it switches on. We then solve
$$\min_{u_1,\dots,u_m}\ \Big\|\sum_{j=1}^m D_j X u_j - y\Big\|_2^2+\beta\sum_{j=1}^m\|u_j\|_2 ,$$
where $u_j\in\mathbb{R}^d$ are the learned per-gate weights and $\beta$ is the weight-decay strength. The group penalty zeroes out most gates, which is the selection step. The relative optimality gap is measured against the exact convex reformulation, which enumerates arrangements and is feasible at small $n$ and $d$. At larger sizes it is measured against the best of many SGD runs on the non-convex network.
Stage one measures $m_\varepsilon$ on controlled processes where $\gamma_{ps}$ is known in closed form. Inputs are vector AR(1) processes $x_t=\rho x_{t-1}+\sqrt{1-\rho^2}\,\xi_t$ with Gaussian noise $\xi_t$. Every marginal is exactly $\mathcal N(0,I)$, so the only departure from Kim–Pilanci's assumptions is temporal dependence. We sweep $\rho$ to vary the mixing rate. We add finite-state Markov chains and the Ornstein–Uhlenbeck process, with a teacher two-layer ReLU network generating targets. For each $(n,\rho)$ we record $m_\varepsilon$ and the number of distinct activation patterns. We fit $m_\varepsilon$ against $n$, $n\gamma_{ps}$ and $\log(1/\varepsilon)$.
Stage two attempts the matching theory. The plan is to redo the arrangement-counting and cone-sharpness steps with a blocking argument: interlaced blocks separated by gaps, as in An Empirical Bernstein Inequality for Dependent Data in Hilbert Spaces. The target statement is that the gap bound holds with $n$ replaced by $n\gamma_{ps}$ up to lower-order terms. We will report honestly if the proof only yields the pessimistic H2 direction.
Stage three builds the practical estimator. We estimate $\gamma_{ps}$ from the trajectory with the single-trajectory estimator of Empirical PAC-Bayes bounds for Markov chains, set $m$ from the stage-one scaling law, and solve the convex program. We then report two certificates. One is the duality gap of the solved program. The other is a Catoni-style PAC-Bayes bound whose temperature is calibrated with the estimated gap.
Stage three is exactly what Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds leaves open. Its Gibbs posterior achieves the minimax rate $(n\gamma_{ps,n})^{-2\beta/(2\beta+d)}$ (here $\beta$ is target smoothness), but it needs a known lower bound on $\gamma_{ps}$ and has no tractable sampler. Our version is limited to two-layer networks and trades the minimax guarantee for polynomial-time computation. The Karagulyan–Alquier bounds, for their part, were only shown for simple hypothesis classes; we apply them to a neural class whose optimization is itself certified.
The main applied testbeds come from the Empirical Bernstein paper: noisy ordered MNIST sequences and alanine dipeptide molecular dynamics. For these the ground-truth mixing is unknown and the estimator is required.
Baselines
The naive reference sizes the gate pool as if the data were independent, with $m$ chosen from the nominal $n$, and reports an i.i.d. PAC-Bayes bound. This is the "do nothing about dependence" point. Our method beats it only if it reaches the same optimality gap and held-out error with substantially fewer gates. On the certificate side, the naive i.i.d. bound should be shown to under-cover the true risk on slowly mixing chains, while ours keeps coverage. True risk is computed on long fresh trajectories from the simulator.
The strongest existing method for the optimization question is Kim–Pilanci's relaxation at their recommended width, run on identical trajectories with the same solver and the same $\beta$ grid. On the certificate question, the strongest competitor is the Karagulyan–Alquier empirical PAC-Bayes bound applied to an SGD-trained network. For that baseline the file reports bounds "often below 0.5 for binary classification tasks" at $n\ge 1000$ on finite-state chains and AR(1) processes. Beating it means a tighter valid bound on the same processes and sample sizes, because our optimization gap is certified rather than assumed.
For the Kim–Pilanci relaxation itself, the only reported quantity is the theoretical $O(\sqrt{\log n})$ gap; no reported numeric result was found on Lacuna for its classification accuracy.
Two further competitors use the same parameter budget and wall-clock time. The first is ordinary SGD training of a two-layer ReLU network of equal width, with its learning rate tuned on a later block of the trajectory. The second is edge-popup from What's Hidden in a Randomly Weighted Neural Network? on a frozen random two-layer network, which is the direct lottery-ticket analogue of selecting random gates. The only lottery-ticket number in the file is from the subset-sum paper: a pruned random host retained the 97.19% MNIST accuracy of its 500-hidden-unit target with about 21 random coefficients per weight. That was on i.i.d. images and is a reference point, not a like-for-like target.
The key ablation replaces the estimated $\gamma_{ps}$ with the oracle value (known for AR(1)) and with a crude batch-means effective-sample-size estimate. This isolates whether the Karagulyan–Alquier estimator matters or any rough dependence estimate would do.
Why not just…?
Why not just thin the trajectory and apply the i.i.d. theorems? Thinning at interval $k$ does make Kim–Pilanci's assumptions approximately true. However, Conformal Predictions under Markovian Data shows the right $k$ depends on the unknown mixing rate, so thinning needs the same estimate we use. It also discards a $1-1/k$ fraction of the data. We run thinning with the estimated and the oracle $k$. If thinned-data held-out error matches ours at slow mixing, the fitting side of our proposal adds nothing, and we would say so. The width-sizing law would still stand.
Why not just overparameterize using nominal $n$ and stop worrying? This is the real threat. Extra gates cost compute but may not cost accuracy, so the naive baseline may match us on test error. Our case then rests on two things. The first is compute: the convex solve scales as $O(d^3m^3)$, so shrinking $m$ from $n$-scale to $n\gamma_{ps}$-scale is a cubic saving when $\gamma_{ps}\ll 1$. The second is certificate validity. If the stage-one fits show H0, that $m_\varepsilon$ tracks $n$, this alternative wins and the sizing claim is refuted.
Why not just train with SGD and validate on a held-out later block? For predictive accuracy alone, blocked validation is probably competitive, and we expect SGD to match us on test error at moderate width. What SGD cannot supply is a certified optimization gap. Uniform-stability generalization bounds are also known to be loose for overparameterized models, as argued in Generalization Bounds for Dependent Data using Online-to-Batch Conversion. The comparison therefore centers on bound tightness and coverage, not on accuracy.
Decisive Experiments
The first decisive check is the scaling fit on AR(1) inputs with $\rho\in\{0,0.5,0.9,0.99\}$ and $n$ from $10^3$ to $10^5$. If the log of $m_\varepsilon$ is better explained by $\log(n\gamma_{ps})$ than by $\log n$ across the sweep, and distinct-pattern counts show the same collapse, H1 holds. If $m_\varepsilon$ grows faster at high $\rho$ at fixed $n$, H2 holds, and the relaxation's guarantees need repair for dependent data.
The second check is end to end on Ornstein–Uhlenbeck processes, finite-state chains, noisy ordered MNIST sequences and alanine dipeptide. We report four things against every baseline above: gates used, relative optimality gap, held-out error on the future segment, and certificate coverage and tightness over at least fifty independent trajectories.
The third check is the estimator ablation. If the batch-means estimate sizes $m$ as well as the Karagulyan–Alquier estimator, we will recommend the simpler estimator and keep the more careful one only for the PAC-Bayes certificate.
References
- Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time
- An Empirical Bernstein Inequality for Dependent Data in Hilbert Spaces and Applications
- Empirical PAC-Bayes Bounds for Markov Chains
- Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds
- What's Hidden in a Randomly Weighted Neural Network?
- Conformal Predictions under Markovian Data
- Generalization Bounds for Dependent Data using Online-to-Batch Conversion