Why Is Coordinate-Wise Missingness as Hard as Arbitrary Replacement?

0. Link verification, versions, and reproducibility audit

All links below were actually accessed on 2026-09-12. “Not found” means no corresponding author-released resource was located on paper pages, arXiv metadata, or public searches; it does not mean the authors promise never to release it.

Version assessment. The final PMLR version appeared in the COLT 2026 volume dated 2026-06-29; arXiv v2 was updated 2026-07-14. Page references below follow the 45-page PMLR PDF; arXiv dates are used only for version auditing, not result values.

1. Candidate pool, deduplication, and random selection

The day's category is Theory and Trustworthiness. The local ml-report-index.mdwas checked first: the past 14 days covered DocVXQA, Emergent Misalignment, Ambient Creativity, VIKI-R, Scale Search, and other interpretability, safety, generative-privacy, and quantization topics. Coordinate-wise robust regression/adversarial MNAR is a distinct topic and method line.

Candidates came from official COLT 2026 PMLR Volume 336, with arXiv, accepted/program pages, and public paper searches cross-checking titles/dates. ACL Anthology is not suitable for this theory pool; Papers with Code and Hugging Face Daily Papers incompletely cover theorem papers, so listing there was not required. The final pool contains 31 full papers:

Strictly executed shuf -i 1-31 -n 1returned 23, selecting this report's core paper. The final paper, appendix, versions, and four direct related-work chains were accessible and sufficient for a deep report, so zero redrawswere needed. The candidate-pool snapshot is separately stored at candidates_2026-09-12.tsv; selection was not based on citations, popularity, or the report author's preference.

2. Motivation: why can a little damage in each column still destroy regression?

Classical Huber contamination budgets whole rows: an ε fraction of samples may be arbitrarily corrupted, with the remainder fully reliable. This paper budgets each column: after seeing all clean data, an adversary may delete up to ηn entries X_jfor every feature j, or replace them arbitrarily without revealing locations. Labels permit the same fraction of deletions/replacements. This captures overlapping multisensor failures, cross-institution field joins, distributed measurement, and poisoning: one bad field prevents a row from being treated as clean, although every column appears mostly intact.

First, a naive union bound amplifies η to roughly η(d+1). A1 treats every row containing a bad coordinate as entirely corrupted, so it works only when ηd<0.49, with error O(ηdσ)(Fact 4, PDF p3; Appendix A.1, p19). This is severe in high dimensions: at d=10,000 and η=0.01%, ηd=1 violates A1's conditions even though only one in ten thousand entries per column is bad.

Second, knowing deletion locations may provide no informational advantage. Intuitively, seeing ⊥ should be easier than facing a plausible fabricated value. Yet the lower bounds use only deletion while algorithmic upper bounds allow stronger arbitrary replacement, matching up to constants over almost all parameter space (Table 1, PDF pp4–5). This is not failure to exploit missingness markers, but nonidentifiability: the adversary selectively hides coordinates where two regression models differ, making observations identical.

Third, error need not vanish as n→∞. The paper studies contamination bias persisting with unlimited samples. In Theorem 5, n enters only a correction to a testing-failure probability near 1/2, whose effect vanishes as n grows (PDF p4, footnote 2). More data does not solve a mechanism that has lost identifiability.

The strongest quantitative phenomenon is a dimension-dependent transition: the critical contamination rate for nontrivial estimation is Θ(1/√d)rather than the familiar sample-level constant 1/2 (PDF p5). When η≥√(7/d) , any estimator may incur Ω(||β||) error, while the zero-vector A3 has exactly ||β||error and is therefore already order-optimal.

3. Paper narrative: three upper bounds, four lower-bound regimes, one counterintuitive equivalence

Rather than inventing a complex optimizer, the paper turns a previously poorly characterized problem into a nearly complete phase diagram.

First, it gives three simple upper bounds. A1 lifts coordinate contamination to sample contamination and invokes robust linear regression. A2 uses the isotropic-Gaussian identity E[yX]=βto perform one-dimensional robust mean estimation coordinate by coordinate. A3 simply returns zero. These suit extremely small η with strong signal, intermediate η, and excessive contamination or weak signal, respectively (Fact 4, p3; Tables 2–4, p20).

Second, instead of designing a fourth algorithm, it proves no estimator can systematically beat those upper bounds. Theorem 5 splits constructions into small-β, large-η, medium-η, and small-η regimes. One coupling cannot cover them all: when noise σ is small relative to signal ||β|| , conditional Gaussians approach singularity and basic TV coupling fails. The authors successively use the last dimension as noise, random coordinate permutations, separate couplings for coordinate halves, and further decomposition of label contributions (§1.2, PDF pp5–7).

Third, upper and lower bounds meet. Upper bounds allow arbitrary replacement; lower bounds need only deletion and never need to hide labels. Thus, under this worst-case model,missing and corrupted data have equivalent optimal error; difficulty can arise entirely from missing X, without corrupting y (PDF p5).

Three tradeoffs matter. First, broad coverage rests on strong assumptions:X~N(0,I)with known isotropic covariance. Second, conclusions concern error orders, not finite-sample constants;0.49、0.24 is an applicability constant for an upper-bound algorithm, not a universal safety threshold. Third, the unified algorithm in Theorem 14 adaptively selects A1/A2/A3 but still needs η and sufficiently large, hierarchically separated hidden constants (Appendix A.3, pp21–22).

4. Equation-level formalization and proof mechanisms

4.1 Clean model and two adversaries

Clean data satisfy

X ~ N(0, I_d)
y = βᵀX + ξ,      ξ ~ N(0, σ²)
Goal: estimate β from n altered samples, with loss ||β̂-β||₂.

The coordinate-wise missingness adversary first sees the entire dataset, then for each j∈[d] deletes up to ηn entries X_j; it may also delete ηn labels. The replacement adversary has the same budget but substitutes arbitrary values without exposing locations (Definitions 1–3, PDF p2). This data-dependent MNAR model is stronger than MCAR, MAR, or fixing the missingness pattern before sampling.

4.2 Three upper bounds

A1 uses a union bound. Treating a row as bad whenever any coordinate changes gives a bad-row fraction at most

ε ≤ η(d+1) ≈ ηd。

Applying Huber sample-level robust regression yields ||β̂-β||=O(ηdσ), valid when ηd<0.49. Appendix A.1 notes that Diakonikolas et al. 2023 can be used with sample complexity Õ(d/ε²)(core PDF p19).

A2 follows the moment identity:

E[yX] = E[(βᵀX+ξ)X] = E[XXᵀ]β + E[ξX] = Iβ = β。

Each product yX_j can be corrupted through X_j and y by at most η each, totaling 2η; its variance is controlled by O(||β||²+σ²) . Running one-dimensional robust estimation separately on d coordinates and combining them gives

||β̂-β|| = O(η√d · √(||β||²+σ²)),     η<0.24。

A3 returns zero, deterministically yielding ||β̂-β||≤||β||. All three are polynomial-time. Fact 4 states that they use O(poly(d/η)) samples and satisfy the upper bounds with probability at least 0.99 (PDF pp3,19).

4.3 Lower bounds: from estimation to indistinguishable testing

If two parameters β,β′produce identical observed distributions after contamination, every estimator incurs at least ||β-β′||/2 error in one world. The authors construct single-sample couplings (X,y),(X′,y′)where each coordinate disagrees with probability at most η. Deleting disagreement locations makes both datasets identical (Lemma 9 and §2, PDF pp7–9).

Basic hybrid coupling decomposes the change between X|y and X′|y into d steps, changing one mean coordinate at step i. Maximal coupling for adjacent one-dimensional differences makes disagreement probability equal TV distance, requiring only a few deletions in one column per step (Lemma 10, Claim 11, PDF pp8–10).

At low noise, conditional covariance approaches singularity and direct TV paths degenerate. Lemma 13 couples only the first d−1 coordinates, sets the last as a residual satisfying the sum constraint, then randomly permutes coordinates. The last coordinate's certain disagreement is spread into a per-coordinate probability of approximately ( |t-t′|+1 )/d(technical overview, PDF p6). Medium η splits coordinates in half; extremely small η additionally separates coordinate and label contributions to avoid the 1/d floor from at least one disagreement (PDF pp6–7).

4.4 Executable pseudocode: logical outline of the unified strategy

input: coordinate corruption rate η, corrupted samples S

1. Select eligible candidates based on η:
   - η < 0.49/d: A1, A2, A3 are all eligible
   - 0.49/d ≤ η < √(7/d): compare only A2, A3
   - η ≥ √(7/d): return A3 directly
2. Run candidate estimators to obtain β̂1, β̂2, β̂3.
3. Robustly estimate σ² from A1 residuals y - β̂1ᵀX using a one-dimensional trimmed mean; construct e1≈ηdσ.
4. Similarly estimate e2≈η√d·√(||β||²+σ²).
5. If C e1 < e2, return β̂1;
   otherwise, if ||β̂2|| > C' e2, return β̂2;
   otherwise return 0.

This is a structured rendering of Theorem 14's proof, not line-by-line code from the paper (Appendix A.3, PDF pp21–22). The paper gives only existential constants C≪C′≪C″, not directly executable numerical values.

5. Key mechanisms and engineering details

Engineering details here concern implementability, not GPU configurations. The paper reports no measured runtime, memory, software stack, seeds, preprocessing, or code entry. Only polynomial time and sample orders are established, not end-to-end efficiency.

6. Datasets, benchmarks, and metrics

This paper has no experimental dataset, empirical benchmark, training process, or model weights. That is not an omission: it studies population-level minimax error. This section therefore maps the usual dataset–metric structure to model family–adversary–risk function:

Statistical significance is inapplicable: there are no repeated trials, standard deviations, confidence intervals, or p-values. Fact 4 gives success probability at least 0.99; Theorem 5's lower-bound event has probability 1/2 - (d+1)e^{-Ω(c²ηn)}/2. These are theoretical guarantees, not empirical significance (PDF pp3–4).

7. Complete main-results matrix: parameter regimes, not invented benchmarks

There is no five-benchmark×six-method experimental table. To avoid disguising theorems as measurements, this report reconstructs seven disjoint parameter regimes from Tables 2–4; optimal means bounds match within constants. Write b=||β||。

Source: core Table 1 (PDF p4) and expanded Tables 2–4 (p20). The main table's O/Ω hide different absolute constants, so ordinary absolute-pp or relative-percentage improvements cannot be computed. A claim such as A2 improving A1 by exactly 37% would be fabricated.

Theorem 5's original four lower-bound regimes are:

• If b≤σ, error Ω(min(b,η√dσ))；
• If η≥√(7/d), error Ω(b)；
• If (2+c)/d≤η≤√(7/d), error Ω(cη√d b)；
• If η≤1/d, error Ω(min(ηdσ,η√d b))。

These orders align with A1/A2/A3 in Table 1's covered regions. The caveat is that the medium-η lower bound requires η≥(2+c)/dwhile the summary interval starts at 0.49/d , leaving a narrow band of width a constant multiple of 1/d without literal full coverage (Table 1 asterisk, PDF p4).

8. Layered ablations, hyperparameter sensitivity, and transitions

8.1 How to describe “ablation” honestly

There are no empirical ablations. A rigorous substitute asks which parameter regimes lose matching bounds when a theoretical component is removed:

This is proof ablation, not an experiment. It explains each component's necessity in the proof chain, not average practical performance gains.

8.2 Hyperparameter sensitivity

Learning rates, batch sizes, and iteration counts are not reported. Four theoretical sensitivity parameters are d, η, σ, and b. Two boundaries govern the transition:η≈1/d determines whether A1 can still exploit whole-row robust regression;η≈1/√d determines whether nontrivial estimation is possible.

The following table is recomputed by this report from the paper's formulas, not an experiment. Column two shows the natural scale 1/√d; column three gives Theorem 5(b)'s explicit sufficient threshold √(7/d)：

Thus increasing dimension from 100 to 10,000 reduces the natural critical scale tenfold, from 10% to 1%; the explicit sufficient high-contamination threshold falls from 26.46% to 2.65%. However, √7 is only a theorem constant. The Θ(1/√d) claim does not mean real systems abruptly fail at that exact value.

8.3 Statistical significance

The paper reports no standard deviations, CIs, multiple seeds, or significance tests. Available probabilities are theoretical: upper bounds succeed with at least 0.99 probability; lower bounds force any algorithm to fail with probability near 1/2. Hidden constants and differing probability conventions prevent conclusions about statistically significant finite-n superiority among A1/A2/A3.

9. Contributions, reusable designs, and transfer potential

The first genuine contribution is completeness: rather than showing difficulty in one regime, the authors combine three existing upper bounds with multiple new lower bounds to close most of the (η,σ,b,d) space within constants. This turns the usefulness of missingness markers from algorithmic intuition into a minimax conclusion.

The second contribution is locating the source of difficulty. All lower bounds hold even when y is never masked (PDF p5); label corruption does not drive the result. Selectively hidden covariate coordinates do. For sensor fusion and tabular-data governance, checking label quality alone cannot eliminate nonidentifiability.

The third contribution is coupling construction. Using the last dimension as noise and then randomly permuting is an elegant local-sacrifice/global-dilution pattern. Coordinate/label partitioning shows lower bounds must adapt to parameter regimes rather than rely on one universal hard instance.

Reusable designs include:

• List trivial estimators first, forcing complex algorithms to compete with learning nothing;
• Translate coordinate budgets into per-coordinate coupling disagreements, not just total TV;
• Use upper-bound applicability regions to identify the phases lower bounds must cover;
• Convert parameter error through L(β̂)=σ²+||β̂-β||² into prediction MSE;
• If only r coordinates are attackable, replace d with r and b with ||β_S|| (Appendix A.4, p22).

For transfer, the paper derives ReLU-like GLM lower bounds: when η≥√(7/d) , MSE is Ω(||β||²); in the medium-η regime it is Ω(c²η²d||β||²)(Appendix A.4, p23). These transfer lower bounds, not matching algorithms. Coupling may extend to unknown covariance, non-Gaussian heavy tails, sparse β, low-rank or graph-structured coordinates, but error scales may depend on conditioning, effective dimension, or structural redundancy.

10. Related-work chain: how problems transfer and designs change

10.1 Liu et al. 2021: the language and coupling of coordinate-wise contamination

Problem solved. Liu et al. define coordinate-wise adversaries and d_ENTRYfor Gaussian mean estimation. In structured x=Az settings, they use m_A to measure how many rows must be removed to reduce A's row-space dimension. Theorems 4–6 show structural redundancy can reduce worst-case dimension-amplified error to the order of αn/m_A ; missing data can be recovered by solving linear systems before mean estimation (ICML PDF pp4–6).

Remaining gap. The task is mean estimation, not regression. Recover-then-estimate relies on known/exploitable structure; recovery generally becomes harder under replacement contamination, with NP-hard obstacles discussed. Whether visible deletion is easier than arbitrary replacement remained unresolved in general.

How the core paper responds. The new paper lifts coordinate coupling to (X,y) joint Gaussians and conditional distributions, proving equal-order difficulty for both models in linear regression.

How the key design transfers. d_ENTRY 's coordinate-wise disagreement becomes Lemma 9's per-coordinate disagreement coupling. Regression must also preserve y marginals and handle X|y covariance approaching singularity, motivating last-dimension noise, coordinate randomization, and partitioned coupling.

10.2 Hu & Reingold 2021: high missingness need not mean unlearnability

Problem solved. This work studies robust means with highly incomplete data: every coordinate appears in at least γN samples, while εN whole samples may be arbitrarily corrupted. Under γ≥C₀ε , it obtains dimension-independent error in nearly linear Õ(Nd log(1/δ)) time. Theorem 1's sub-Gaussian error is O(√((d+log(1/δ))/(γN)) + (ε/γ)√log(γ/ε))（AISTATS PDF p3）。

Remaining gap. Missingness is fixed before values are sampled, preventing value-dependent selective hiding; contamination is budgeted by whole sample. Iterative random imputation can therefore reduce missing data to established robust-mean procedures.

How the core paper responds. The new paper lets adversaries observe values before choosing deletions per column, entering strong MNAR where even unlimited samples cannot remove bias.

How the key design transfers. Both emphasize per-coordinate coverage, but in opposite directions: Hu–Reingold gives sufficient conditions for learning despite heavy missingness; the new paper identifies nonidentifiability when missingness depends on values. Missingness timing, not rate alone, is decisive.

10.3 Diakonikolas et al. 2023: sample-level robust regression underpins A1

Problem solved. Under Huber whole-sample contamination, Theorem 1.4 uses n≫(d/ε²)polylog(d/ε) samples and (nd+1/ε^{2+c})polylog(d/ε) time to achieve O(σε/c) parameter error with probability at least 0.9 (arXiv PDF p3).

Remaining gap. Sample-level ε does not distinguish one bad coordinate from an entirely bad row. Applying it directly to coordinate contamination requires ε≈ηd, losing √d or even d structural gains.

How the core paper responds. A1 remains optimal for extremely small η and strong signal rather than becoming obsolete. A2 fills other regimes using moment structure; new lower bounds show this piecewise combination is already order-optimal.

How the key design transfers. The 2023 algorithm is an upper-bound building block, not the new paper's novelty. The novelty is proving when even this crude union bound cannot be improved.

10.4 Loh & Wainwright 2012: error can vanish with n under random missingness

Problem solved. This work studies high-dimensional sparse regression with randomly missing/noisy covariates, constructing unbiased corrected Gram matrices and cross moments. Despite nonconvexity, projected gradient converges geometrically near a global optimum (AoS PDF pp1–5). In the missing-at-random special case, each entry is independently observed with probability 1-ρ_j , and Corollary 2's error depends on 1/(1-ρ_max) and covariance conditioning (§3.2.2, PDF p14).

Remaining gap. MCAR masks are independent of X, so corrected moments concentrate as samples grow. This does not cover nonidentifiability caused by adversarial value-dependent deletion.

How the core paper responds. The new paper shifts from finite-sample estimation and nonconvex optimization to minimax bias that persists with infinite data, clarifying that the two missingness mechanisms cannot be unified by rate alone.

How the key design transfers. E[yX]=β remains a shared theme, but MCAR uses inverse-probability/Gram corrections; strong MNAR requires coordinate-wise robustification and pays η√d√(b²+σ²)。

10.5 Nonlinear technical evolution

                         ┌─ MCAR / random missingness
Rubin's missingness taxonomy ─┤    └─ Loh–Wainwright 2012
                              │       Unbiased moment correction + tractable nonconvexity
                              │       Error can vanish as n grows
                              │
                              └─ adversarial missingness
                                   ├─ Hu–Reingold 2021
                                   │   Precommitted missingness + whole-sample outliers
                                   │   Iterative imputation, nearly linear time
                                   │
                                   └─ Liu et al. 2021
                                       d_ENTRY + structural redundancy m_A
                                       recover → estimate
                                           │
Huber sample contamination ── 2023 nearly linear robust regression ─┐
                                                                   ├─→ 2026 core paper
Liu's coordinate-wise coupling ─────────────────────────────────────┘    A1/A2/A3 upper-bound mosaic
                                                                        conditional-Gaussian coupling
                                                                        last dimension as noise + partitioned coupling
                                                                        missing ≍ replacement
                                                                        η≈1/√d transition

The driver is not merely stronger adversaries, but identifying which assumption enables learning: missingness rate, timing, coordinate dependence, covariance structure, or visibility of corruption. The key shift is from designing imputers to constructing indistinguishable observations. Once two true models explain the same incomplete observations, no sophisticated imputer can fill the information gap.

10.6 Cross-paper comparison

11. Limitations acknowledged by the paper

1. Unknown covariance. The authors explicitly identify X~N(0,Σ), Σ≠I with unknown Σ as the primary open problem; both the current E[yX]=β identity and conditional-Gaussian construction directly use I (Appendix A.6, PDF p26).
2. Sample complexity is not optimal. Current algorithms use Õ(d/η²) samples, but target error can be large with b in some regimes, while the clean baseline needs only d/u²to achieve error u. Optimal sample complexity remains unknown (Appendix A.6, p26).
3. GLMs and intermediate-strength missingness remain unresolved. ReLU-like models have only lower-bound corollaries; tightness and polynomial-time matching algorithms are unknown. The continuum between fully adversarial and fully random deletion is also uncharacterized (Appendix A.6, p26).

12. Independent critique: evidence-to-inference chains

1. [External validity] Because all matching results assume X~N(0,I) and A2's identity becomes E[yX]=Σβunder general Σ, one cannot treat η≈1/√d as universal for correlated features, heavy-tailed tables, or deep representations. Conditioning and structural effective dimension may replace d.
2. [Finite-sample usability] Because the main results give only O/Ω with hidden constants, while A1/A2 constants 0.49 and 0.24 come from particular analyses, the matrix establishes order-optimality but cannot guide production choices such as switching A1 versus A2 at η=0.3%.
3. [Statistical strength] Because lower-bound events occur with probability near 1/2 while upper bounds succeed with at least 0.99, both establish minimax orders but do not match the same high-probability criterion. Tail risk is therefore not tightly characterized.
4. [Algorithmic novelty attribution] Because A1 uses 2023 robust regression, A2 uses coordinate-wise one-dimensional robust means, and A3 is zero, the algorithmic contribution is mainly composition and adaptive selection. Most originality lies in lower-bound coupling, not a new robust optimizer.
5. [Reproducibility] Because there is no code, data, measured runtime, or finite-sample simulation, and Theorem 14 gives only C≪C′≪C″, polynomial implementability does not mean readers can reproduce a numerically stable system with practical constants.
6. [Model strength] Because the adversary observes the entire dataset before selecting deletions by column, this is very strong MNAR. The result is a worst-case safety envelope, not evidence that ordinary random sensor dropout and malicious replacement are equally hard on average.
7. [Boundary completeness] Because Table 1 shows the medium regime starting at 0.49/d while Theorem 5(c) actually requires (2+c)/d, claiming complete closure of all parameter space is too strong. The precise statement is nearly complete except for a narrow technical band of constant-times 1/d width.
8. [Objective limitations] Because the paper studies parameter recovery ||β̂-β||and assumes complete test-time X, it does not handle prediction with both training and test missingness. That problem may require modeling 2^d missingness patterns and is not directly solved here (related-work discussion, PDF pp24–25).

13. Open challenges: actionable head-to-head experiments

13.1 Theory

• Unknown-Σ comparison. Under the same (d,η,σ,b) , compare Σ=I, known nondiagonal Σ, and unknown Σ. Test A2, whiten-then-A2, and robust covariance+regression; report parameter error against condition number κ. Determine whether the critical rate depends on 1/√d、1/√effective-rank or κ.
• High-probability minimax comparison. Fix failure probability δ∈{0.1,0.01,0.001}; derive/validate sample requirements for both bounds, avoiding the current mismatch between 0.99 success and failure near 1/2.
• Structural sparsity comparison. For s-sparse β and r attackable coordinates, compare bounds using d, s, or r as the transition scale. With one adversarial masker, test whether Appendix A.4's d→r substitution can improve further through sparse support.
• Intermediate-strength MNAR. Continuously increase the Lipschitz constant or information budget of deletion probability r(x) from zero to infinity. Compare MCAR, realizable contamination, and fully adaptive deletion to locate the transition from consistency to constant bias.

13.2 Engineering and applications

• Finite-sample algorithm contest. For d∈{100,1k,10k} and η spanning 0.49/d with 1/√d , implement A1/A2/A3/the unified algorithm at equal CPU-hour budgets. Report median/p95 parameter error, runtime, memory, and failure rate to test whether constants reverse asymptotic rankings.
• Empirical deletion-versus-replacement difficulty. On the same clean table, optimize attacks producing visible ⊥ or hidden replacements with equal per-column η. Compare tuned imputation+regression, A2, and robust-covariance methods. If missingness remains easier, minimax equivalence may be pessimistic for natural data.
• Clean-label comparison. Lower bounds require no bad y. Keep every label clean and attack high-leverage, random, or maximum-gradient X entries to test whether selective missingness rather than label noise drives difficulty.
• Real sensor logs. Replay real dropout on multisensor data with complete ground truth, then apply a worst-case masker at the same budget. Measure the gap between average missingness and safety worst cases instead of treating a theoretical red line as typical behavior.

13.3 Emerging directions

• Local linearization of deep representations. Freeze an encoder and apply coordinate attacks to a final-layer linear probe. Fit thresholds against raw feature dimension d versus representation effective rank, testing whether the transition is closer to 1/√rank。
• LLM activations / sparse autoencoders. Apply coordinate missingness to SAE features or MoE expert routing; compare visible masking with hidden activation replacement. Measure downstream degradation and recovery error to test whether visible locations still offer no advantage in neural representations.
• Federated heterogeneous tables. When clients hold different feature subsets, compare align/impute-first pipelines with coordinate-robust moments at equal communication budgets, measuring excess risk to connect per-column budgets to real data silos.

14. Recent-work radar

All following official COLT 2026 / PMLR 336 pages were verified. They are future directions, not substitutes for the core related-work readings.

1. On efficient robust regression with subquadratic samples: unknown covariance, condition number κ, and sample–time tradeoffs directly address the core paper's main open problem. Its nearly linear algorithm uses Õ(d/ε⁴) samples to achieve O(√(εκ)) prediction error, but still assumes whole-sample contamination.
2. High-Dimensional Gaussian Mean Estimation under Realizable Contamination: places missingness between MCAR and arbitrary MNAR and proves SQ/low-degree information–computation gaps, directly neighboring intermediate-strength mechanisms.
3. A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance: combines unknown covariance and mean-shift contamination; relevant to the unknown-Σ question, though the contamination model differs.
4. Testing Noise Assumptions of Learning Algorithms: tests noise assumptions rather than directly building robust learners, suggesting deployable preliminary diagnostics for whether the strong adversary is too pessimistic.
5. Statistical Learning from Attribution Sets: constructs unbiased risk estimates from candidate attribution sets, representing weak supervision with missing label links but known structure.
6. Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness: uses generalized smoothness to characterize learnability under distributional adversaries, offering abstract tools for the random–adversarial continuum.
7. Is Memorization Helpful or Harmful? Prior Information Sets the Threshold: also centers on phase transitions, but thresholds depend on prior Fisher information and variance, providing a methodological comparison with dimension-driven thresholds.

15. Conclusion: three takeaways

First, coordinate-wise missingness is not solved by simple mean imputation. If missingness depends on values, an adversary can erase evidence distinguishing regression models and leave constant bias even with infinite data.

Second, the optimal approach is a regional combination of A1 (whole-row robustness), A2 (coordinate-wise moments), and A3 (zero estimation). The main technical contribution proves that this simple combination is unimprovable over nearly all parameter space.

Third, the most striking quantity is η≈Θ(1/√d): higher dimension requires less malicious missingness per column. This threshold depends strictly on Gaussian isotropy and worst-case adversaries; unknown covariance, natural missingness, and finite-sample constants remain key gaps for practical use.

Report footnote. Candidates, random selection, versions, and external links were verified on 2026-09-12. With no empirical main table, this report invents no benchmarks, standard deviations, ablations, or pp gains. Charts only show dimension scaling recomputed from theorem thresholds.ml-report-index.md This entry was appended. HTML uses the Warm Editorial Report template and passed its structural validator (0 errors / 0 warnings). Playwright is available, but neither /usr/bin/chromium、/opt/pw-browsers nor Playwright's expected cache contains an executable browser. Light/dark/mobile screenshot review therefore could not honestly be completed, and playwright installwas not run. Responsive table containers, mobile media queries, theme variables, and static HTML validation were used instead, but do not equal browser visual acceptance.