Source-linked AI summary
Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise
Emeric Battaglia, Jian-Feng Cai, Junren Chen, Anna Ma, Deanna Needell, Tong Wu
TL;DR
The paper addresses unclear tolerable corruption levels and hidden constants in QRK for corrupted linear systems. It analyzes streaming QRK under Massart and oblivious noise, deriving explicit bounds and showing linear convergence with corruption up to approximately 7% under Massart noise.
Problem
Prior QRK analyses left the maximum tolerable corruption level and explicit required subsample size unclear.
Method
The paper analyzes streaming QRK using fresh samples at each iteration under Massart and oblivious noise, exploiting their independence across iterations.
Results
Streaming QRK converges linearly with D = O(log T) samples per iteration, tolerating β ≈0.069 under Massart noise and β ≈0.32 under oblivious noise.
Takeaways & Limitations
The analysis provides explicit, computable bounds on corruption tolerance and subsample size, including D = 25 for Massart noise and D = 13 for oblivious noise when q = 0.75, β = 0.01, and T = 20000.
Takeaways & Limitations
Under Massart noise, corruption locations are random but corruption values may be chosen adversarially.
Abstract
from arXiv · showhide
Quantile randomized Kaczmarz (QRK) has proven to be an efficient solver for corrupted linear systems and has received much attention. It was recently shown by Cai et al. (SIAM J. Matrix Anal. Appl. 47(2):802-823, 2026) that using $O(\log T/\log(1/β))$ samples for computing the quantile is necessary and sufficient for QRK to converge linearly over $T$ iterations when solving linear systems with a $β$-fraction of arbitrary corruptions, as long as $β$ is small enough. However, it remains unclear how large the corruption level $β$ can be, and how to compute the required subsample size $D$ explicitly, without hidden constants. This paper studies streaming linear systems with Massart noise via QRK using an order-optimal batch size $D=O(\log T)$ in each update. The independence of samples from previous iterations in the streaming setting enables a sharper analysis, yielding explicit, computable bounds on both the tolerable corruption level and the required subsample size. In particular, we establish linear convergence for corruption levels of up to approximately 7%. We also discuss how the constants improve under oblivious noise.
1 Introduction
This paper studies streaming QRK for corrupted linear systems, addressing the tolerable corruption level and explicit subsample sizes needed for linear convergence. It obtains explicit guarantees under Massart and oblivious noise, including corruption tolerance near 7% under Massart noise.
- Prior methods: QRK improves randomized Kaczmarz robustness by filtering updates whose residual exceeds a quantile computed from a size-D subsample.Classical randomized Kaczmarz is not generally robust to sparse adversarial corruption, whereas QRK performs an update only when the residual is below the empirical quantile.
- Prior methods: D = O(log T/log(1/β)) samples are necessary and sufficient for finite-horizon QRK convergence, reducing to D = O(log T) when β is a small constant.The earlier result also implies D = O(log n) when T = n^O(1), versus D = m for full-sample quantiles.
- Open questions: The paper addresses the unresolved problem of computing explicit tolerable corruption levels and order-minimal subsample sizes for QRK.Prior work required sufficiently small or sufficiently large unspecified constants, leaving explicit values unclear when D is much smaller than m.
- This paper: Streaming QRK draws fresh potentially corrupted samples at every iteration, enabling sharper analysis through independence and explicit expectations.The setting serves as a surrogate for a highly overdetermined ensemble and models both Massart and oblivious noise.
- Main contributions: β∗(0.85) ≈ 0.069 is the maximum Massart corruption level established, while streaming QRK uses only O(log T) fresh samples per iteration.This improves upon the β ≈ 0.005 guarantee cited from earlier work.
- Main contributions: D = 25 samples guarantee convergence for β = 0.01, q = 0.75, and T = 20000 under Massart noise.The paper characterizes this required subsample size explicitly and computably, although it describes the bound as conservative.
- Main contributions: Under oblivious noise, the tolerable corruption level reaches β∗obl(0.65) ≈ 0.32, and D = 13 suffices when q = 0.75, β = 0.01, and T = 20000.These stronger guarantees still use only O(log T) fresh samples per iteration.
2 Preliminaries
The preliminaries define streaming QRK, its fresh-measurement update structure, and the Massart and oblivious corruption models. They also introduce the normalized residual and quantile quantities used in the analysis.
- 2.1 Streaming QRK: Fresh measurement vectors are sampled independently of the current iterate and previous iterations in the streaming setting.This distinguishes streaming QRK from ensemble methods that repeatedly sample rows from a fixed matrix.
- 2 Preliminaries: The paper assumes measurement vectors are i.i.d. uniform on the unit sphere and uses Chernoff bounds for binomial random variables.Theoretical analysis assumes relevant proportions such as qD are integers, with rounding corrections of order 1/D omitted.
- 2.1 Streaming QRK: Streaming QRK uses D+1 fresh measurements per iteration: D compute the empirical quantile and one performs the update.The update measurement is accepted only when its absolute residual is at most the computed threshold.
- 2.2 Corruption models: Under Massart noise, corruption indicators are independent Bernoulli(β), while corruption values may be chosen jointly and adversarially using available information.The adversary cannot choose which measurements are corrupted, but can choose their corruption values using information such as the true solution and measurement vectors.
- 2.2 Corruption models: Under oblivious noise, each measurement is independently corrupted with probability β, and corruption values are chosen independently of the measurement vectors and other randomness.Values may be fixed in advance or drawn independently.
- 2 Preliminaries: The analysis uses a normalized clean residual Z, its absolute-value quantiles Φα, and a truncated second moment.For large n, Z is approximately N(0, 1), which supports explicit numerical evaluations later in the paper.
3 Main Results
Streaming QRK obtains high-probability linear convergence under Massart noise by controlling subsampled quantiles and one-step contractions. The analysis characterizes the maximum tolerable corruption and gives explicit logarithmic subsample-size guarantees, with sharper bounds under oblivious noise.
- Quantile bounds: Two-sided probabilistic bounds control the fluctuating subsampled quantile Qq,k+1 under both Massart and oblivious noise.The bounds use fresh streaming samples and apply uniformly over adversarial corruption values in the Massart model.
- Massart noise: Streaming independence enables explicit expectation calculations and a sharper convergence analysis than fixed-matrix ensemble settings.Fresh samples are independent of previous iterations, and this independence yields exact expectation consequences for the analysis.
- Massart noise: cadv > 0 is the key Massart contraction condition, while the failure probability over T iterations is bounded by Tβ exp(−DKL(1 −q∥β + α′) · D).Under the resulting conditions, the error contracts linearly with high probability.
- Maximum tolerable corruption and subsample size: β∗ separates feasible and infeasible corruption levels: F(q, β) remains positive below β∗, while ΩD is empty above β∗.For β < β∗, the feasible set contains subsample sizes of order O(log T), and the minimum required D∗ is well defined.
- Oblivious noise: Under oblivious noise, the sharper joint one-step analysis yields a larger maximum tolerable corruption level β∗obl and a smaller minimum subsample size D∗obl than under Massart noise.The oblivious bound is never worse than the adversarial bound, and explicit O(log T)-type subsample guarantees remain available.
4 Numerical Results
The paper makes the theoretical thresholds β∗ and D∗ explicit and computable, then compares them with simulations under Massart and oblivious noise. The bounds generally track empirical success transitions, with Massart results showing particularly close agreement.
- Computation of β∗ and D∗: Binary search computes β∗ for fixed q and D∗ for fixed T, δf, q, and β below β∗.The D∗ search checks feasible α and α′ against failure-probability and contraction constraints.
- Massart noise: 0.069 is the approximate peak Massart corruption threshold at q = 0.85, while D∗ = 25 at β = 0.01 under the representative settings.The settings use q = 0.75, δf = 0.1, and T = 20000 for the D∗ example.
- Oblivious noise: Known corruption distributions can improve the thresholds, including Gaussian corruption through an expectation-based error-increase function.The paper reports Gaussian(0.60) = 0.397 > 0.320.
- Numerical simulations: For fixed T, empirical success generally increases with D, and D∗ tracks the transition closely under Massart noise.Figure 3 uses β = 0.01 and overlays D∗ as a function of T.
- Numerical simulations: Under oblivious noise, the clearest empirical transition occurs at D = 5, while D∗ is consistent with sporadic lower-success pairs having D > 5.The comparison uses the theoretical bound overlaid against empirical success probabilities.
- Numerical simulations: For fixed β, success generally increases with D under both models, and D∗ tracks the empirical transition but becomes more conservative at larger β.Figure 4 uses T = 20000 and reports empirical success across (D, β) pairs.
5 Conclusion
The paper establishes explicit, computable QRK guarantees for streaming corrupted linear systems under Massart and oblivious noise. It obtains O(log T) samples per iteration, tolerates substantially higher corruption under oblivious noise, and finds close empirical agreement with the derived thresholds.
- Conclusion: Streaming QRK converges linearly using D = O(log T) samples per iteration, with explicit bounds on corruption and subsample size.The analysis exploits fresh-sample independence across iterations.
- Conclusion: The tolerable corruption levels reach approximately β ≈0.069 under Massart noise and β ≈0.32 under oblivious noise.At q = 0.75, β = 0.01, and T = 20000, the required sizes are D = 25 and D = 13, respectively.
- Conclusion: Theoretical thresholds D∗ closely track empirical success transitions, particularly under Massart noise.The bounds can improve when the corruption distribution is known, such as for Gaussian noise.