{"id":"fa56ac56-574b-4ac5-b5df-91a4f2222d30","arxiv_id":"2412.04245","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new no-free-lunch construction and empirical scaling study argue that robust classification can require exponentially more data than standard classification, and that dataset size largely drives certified robust accuracy.","lead":"This paper gives a theoretical example where learning a classifier that is accurate and robust to small perturbations requires exponentially more training data than learning an ordinary accurate classifier, even though a perfect robust classifier exists. It also reports scaling experiments on CIFAR-10, MNIST, and CIFAR-100 suggesting that dataset size is the main factor limiting robust accuracy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central theorem is sound, but the empirical 'main factor' claim rests on certified-accuracy scaling and on an unproven causal role for low-variance PCs; attack-based robust accuracy is never measured.","rationale":"The reader's weakest assumption focuses on whether the low-magnitude PCA directions are the actual cause of the robust generalization gap. That is a real gap in the explanatory story, but I see it as one part of a broader and more load-bearing issue: the empirical scaling evidence measures certified robust accuracy, not robust accuracy itself, and the causal step from worst-case construction to CIFAR-10 is an extrapolation. The central theoretical contribution, Theorem 1, is carefully argued and sound: the no-free-lunch style lower bound is valid, and Theorem 2's covering argument is correct. The scaling experiments and the capacity/architecture controls are suggestive and reasonably executed. However, the abstract's 'main factor' phrasing goes beyond what the controlled experiments establish, since no attack-based robust accuracy is reported for the scaled models and the PCA ablation is not causal. This supports the existing CONDITIONAL verdict rather than changing it: the paper's core theorem stands, but the empirical headline should be tempered or supplemented with attack-based measurements and a causal PCA manipulation.","tokens_in":17886,"tokens_out":23070,"duration_ms":261138,"concrete_test":"Train the same CPL ConvNet on CIFAR-10 subsets of size 1k, 4k, 16k, and 50k using the exact protocol of Figure 1, and for each model report both CRA and an empirical robust-accuracy estimate, e.g., 20-step PGD with the same L2 budget of 36/255. If the PGD robust accuracy reproduces the same linear-log scaling with a comparable slope, the dataset-size claim concerns actual robustness; if the CRA slope is substantially larger than the PGD slope, the headline should be rephrased as a claim about certified accuracy under the 1-Lipschitz training recipe.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim in the abstract—that 'the amount of training data is the main factor determining the robust performance'—requires that the certified-robust-accuracy (CRA) scaling observed in Figure 1 reflects the actual robust accuracy of the learning problem, not just the behavior of the specific 1-Lipschitz certified pipeline. The paper controls for compute (Figure 5), capacity (Section 5.3), and architecture (Section 5.4), but every scaling curve reports CRA, a lower bound on robust accuracy. If the gap between CRA and true robust accuracy shrinks as the training set grows, the empirical scaling could overstate the role of dataset size. The PCA mechanism in Section 5.2 is likewise correlational: removing the low-variance PCs from the full data changes CRA by only about 1% (Table 1, 1-512 vs 1-3072), and adding them to the high-variance PCs changes CRA by about 4% (31% to 35%), so the causal role of those directions in the data-scaling effect is not demonstrated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies why robust classifiers generalize poorly. It proves a 'No Free Robustness' theorem (Theorem 1) constructing, for every dataset size n, a family of binary classification problems over d = O(log n) dimensions in which a perfectly robust classifier exists and a trivial linear classifier achieves 100% standard accuracy, yet any learning algorithm requires a sample size exponential in d to obtain better-than-chance robust accuracy. It also proves an upper bound (Theorem 2) for L-infinity-robust learning via 1-nearest-neighbor classification with n = O((1/delta)^d) samples. Empirically, the paper reports that on MNIST, CIFAR-10, and CIFAR-100 the certified robust accuracy of 1-Lipschitz models grows roughly linearly in the logarithm of the training-set size, that low-variance principal components support non-robust but not robust classification, that 1-Lipschitz architectures can robustly overfit the training set, and that the same architecture can reach either high accuracy or high certified robustness depending on the loss function. The paper is accompanied by code.","tokens_in":18046,"tokens_out":11446,"duration_ms":112774,"significance":"If the results hold, the paper makes a valuable contribution by cleanly separating the sample complexity of robust and non-robust learning and by giving a concrete counterexample to the intuition that existence of a robust classifier plus easy standard learning implies easy robust learning. The proofs of Theorems 1 and 2 are explicit and checkable: the averaging over the uniform ensemble of Boolean functions in Theorem 1 is a standard no-free-lunch argument, and the covering argument in Theorem 2 is straightforward. The empirical study is broad and controls for compute, capacity, and architecture. The main weakness is that the headline empirical conclusion is based on certified robust accuracy, a lower bound, rather than on attack-based robust accuracy, and that the causal role of low-variance principal components is asserted rather than demonstrated. These issues are fixable and do not undermine the theoretical core, but they do affect the strength of the paper's central empirical claim.","major_comments":[{"comment":"Theorem 1 as stated does not quantify the adversarial radius epsilon even though robust accuracy in Eq. (2) depends on epsilon. The proof's lower bound uses an attack that sets the non-robust feature x_d to 0, which has norm delta; for any epsilon < delta the classifier f(x) = sign(x_d) would itself be 100% robust on the constructed distributions, contradicting property 3. The theorem should state explicitly that the robust accuracy statements hold for epsilon = delta (or for every epsilon >= delta), where delta is the feature magnitude chosen in the construction. Without this quantifier, the formal statement is incomplete.","section":"Section 3, Theorem 1"},{"comment":"The headline empirical claim that \"the amount of training data is the main factor determining the robust performance\" is supported only by certified robust accuracy (CRA), a lower bound on the true robust accuracy defined in Eq. (2). All scaling curves in Figures 1, 2, and 6 report CRA for 1-Lipschitz models or randomized-smoothing estimates; no attack-based robust accuracy (e.g., PGD or AutoAttack) is reported for the same model checkpoints. If the gap between CRA and true robust accuracy changes with dataset size, the scaling behavior in Figure 1 could overstate the role of dataset size. The conclusion should either be restricted to certified robust accuracy or supplemented by empirical robustness measurements.","section":"Section 5.1 and Abstract"},{"comment":"The PCA experiments are correlational and do not establish that low-magnitude directions cause the data-scaling gap. Table 1 shows that adding PCs 513-3072 to PCs 1-16 raises test CRA only from 31% to 35%, while it raises test accuracy from 43% to 86%; conversely, removing the low-variance PCs from the full set changes test CRA only from 62% to 61% (1-3072 vs 1-512). These results are consistent with the presence of useful non-robust features, but they do not demonstrate that these directions are the mechanism behind the robust generalization gap. The sentence in Section 5.2 claiming that \"CIFAR-10 as a real dataset shares some characteristics with the hypercube example\" should be softened, or an intervention experiment should be provided.","section":"Section 5.2, Table 1"}],"minor_comments":[{"comment":"The notation L(Xr, phi(Xr))(x~r) is ambiguous; the learner's training set S contains the full examples (x, y) with the non-robust feature x_d = delta * phi(x_r), not just (Xr, phi(Xr)). Please clarify the shorthand.","section":"Section 3, Eq. (10)"},{"comment":"The statement that \"doubling the size of the dataset seems to reliably increase the certified robust accuracy by about 5%\" is not directly readable from Figures 1 and 2, whose training sizes are spaced by factors of 4; please state whether the 5% figure comes from a fitted slope or from additional dataset sizes.","section":"Section 5.1"},{"comment":"\"Doubling the dataset size improves the performance less and less\" should read \"doubling the compute\" or \"increasing the number of epochs\", since this subsection varies compute while keeping the dataset size fixed.","section":"Section 9.1"},{"comment":"\"which no robust classifier is not able to exploit\" contains a double negative and should be corrected to \"which no robust classifier is able to exploit.\"","section":"Section 5.2"},{"comment":"\"We just currently fail do both (robust fitting and generalizing) at the same.\" contains typos; it should read \"fail to do both ... at the same time.\"","section":"Section 7"},{"comment":"\"for come value c\" should be \"for some value c\", and \"the nnt training example\" should be \"the n-th training example.\"","section":"Section 12"},{"comment":"The remark that L2 robustness might require O(c^d d^{d/2}) samples is stated without proof or reference; please either provide a derivation, cite a source, or label it as a conjecture.","section":"Section 8, Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the related-work coverage is adequate. The main risks are the missing epsilon quantifier in Theorem 1 and the overstatement of the empirical conclusion based on certified rather than actual robust accuracy; both are fixable. I see no concerns about novelty or attribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: Theorem 1 is a genuinely new and clean No-Free-Lunch-style result, and the paper deserves serious referee time. But the headline empirical claim—that dataset size is the main factor—is stated more strongly than the evidence supports, and the accepted version should soften it.\n\nWhat's new: Schmidt et al. showed a polynomial sample-complexity gap for robust vs standard classification on Gaussians. Prach and Lampert construct a family of distributions where any learner needs 2^d examples to get 51% robust accuracy, while a perfect robust classifier exists and a simple linear classifier gets 100% standard accuracy. The construction is simple: a low-magnitude feature perfectly predicts the label, but a perturbation of size δ kills it; the robust features are a random Boolean function hard to learn from n samples. The proof is short and I checked the averaging step; it's sound. Theorem 2 gives a matching exponential upper bound via a covering argument for 1-NN, also standard and correct. That's a real contribution: the exponential gap was not in the prior work they cite.\n\nEmpirically, the paper does useful controlled experiments. They hold compute fixed, show that compute alone saturates, that 1-Lipschitz models can robustly overfit the training set, and that the same architecture can reach 93% accuracy or 61.7% CRA depending only on the loss. That rules out capacity and architecture as the current bottleneck. The PCA experiments show there are low-variance directions in CIFAR-10 that support 85% standard accuracy but only 9% robust accuracy—a nice existence proof consistent with the theory.\n\nSoft spots, in proportion. The abstract says 'the amount of training data is the main factor determining robust performance.' The experiments show data scaling helps a lot, compute saturates, and capacity/architecture don't explain the gap. But all robust numbers are certified robust accuracy (CRA), a lower bound on true robust accuracy. If the CRA-to-true-robust gap shrinks as the dataset grows, the scaling curve overstates the role of data. They never measure attack-based robust accuracy. Also, the PCA results are correlational: adding low-variance PCs to the high-variance ones moves CRA from 31% to 35%, and removing them from full data barely changes anything (61% to 62%), so the story that these directions are what makes robust learning data-hungry is not yet demonstrated. And there are no error bars on the scaling curves. None of this sinks the theory, but the 'main factor' language needs to be tempered to something like 'data-limited under current certified-training methods.'\n\nWho's it for: anyone working on certified robustness or robust generalization. Cite Theorem 1 in related work. Send it to review; it will improve with a revision that softens the empirical claims and preferably reports one attack-based robust accuracy check on a subset of the test set.","headline":"Theorem 1 is a clean, genuinely new exponential lower bound for robust classification, and the paper deserves review; just soften the 'main factor' empirical claim.","tokens_in":18624,"tokens_out":2398,"would_cite":true,"duration_ms":25027,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a 'No Free Robustness' theorem: for any dataset size there is a classification family where a perfect robust classifier exists and accurate learning is easy, yet every learner needs exponentially many samples to beat…","keywords":["adversarial robustness","certified robustness","1-Lipschitz networks","sample complexity","robust generalization","No Free Robustness","principal component analysis","data scaling"],"falsifier":"Train a 1-Lipschitz classifier on CIFAR-10 after rescaling the low-variance principal components (e.g., components 2049–3072) to unit magnitude: if certified robust accuracy stays near zero despite the amplification, the paper's claim that low magnitude blocks robust use of these directions would be refuted; if it jumps, the data-scaling explanation is supported.","tokens_in":17623,"feed_emoji":"🛡️","tokens_out":9604,"duration_ms":83354,"temperature":0.7,"pith_summary":"Adversarial robustness research has mostly asked whether accurate robust classifiers exist or whether they are too expensive to train. This paper argues the real bottleneck is data: it constructs a family of binary classification problems in which a perfectly robust classifier provably exists and an accurate non-robust classifier is trivial to learn, yet any learning algorithm needs an amount of training data exponential in the input dimension to reach even 51% robust accuracy. The construction splits each input into high-magnitude features that are hard to relate to the label and one low-magnitude feature that reveals the label but is destroyed by any perturbation. On real data, the paper reports that certified robust accuracy (a provable lower bound on robustness) rises reliably with training-set size on CIFAR-10, MNIST, and CIFAR-100, and that low-variance principal-component directions support non-robust but not robust classification. If the authors are right, improving robust classifiers is mainly a data-collection and data-generation problem, not an architecture or optimization problem.","feed_headline":"Provable: robust learning can need exponential data","feed_subtitle":"Even when a perfect robust classifier exists and accurate learning is easy, data size—not architecture—sets the ceiling.","key_machinery":"The load-bearing object is a constructed data family $\\mathcal{F} = \\{D_\\phi : \\phi \\in \\Phi\\}$, where $\\Phi$ is the set of all Boolean functions on $\\{\\pm1\\}^{d-1}$. A sample draws robust features $x_1,\\dots,x_{d-1}$ uniformly from the hypercube, sets a non-robust feature $x_d = \\delta\\,\\phi(x_1,\\dots,x_{d-1})$, and labels the point $y = \\mathrm{sign}(x_d)$. The sign of $x_d$ makes non-robust learning trivial, while its small magnitude $\\delta$ means a perturbation of size $\\le \\delta$ can zero it, so a robust classifier must reconstruct $\\phi$ from the hard high-dimensional features. Averaging over the uniform prior on $\\Phi$ yields the no-free-lunch lower bound. The empirical side uses certified robust accuracy for 1-Lipschitz networks via the Lipschitz-margin bound, AOL and CPL 1-Lipschitz layers as the trainable parameterizations, and PCA projections to expose low-variance directions that carry non-robust signal.","core_discovery":"The paper's central discovery is Theorem 1 ('No Free Robustness'): for any dataset size $n$, with input dimension $d = \\lceil \\log_2 n \\rceil + 7$, there is a family $\\mathcal{F}$ of binary classification problems such that (1) every problem in $\\mathcal{F}$ has a classifier with 100% robust accuracy, (2) a simple linear rule reading the low-magnitude feature achieves 100% ordinary test accuracy, and (3) for any learning algorithm, averaged over $\\mathcal{F}$ and over training sets of size $n$, the learned classifier has robust accuracy below 51%. The obstruction is that a robust classifier cannot rely on the low-magnitude feature $x_d = \\delta\\phi(x_1,\\dots,x_{d-1})$, since a perturbation of size $\\delta$ can set it to zero; the classifier must instead learn the arbitrary Boolean function $\\phi$ on the remaining $d-1$ bits, which a no-free-lunch argument shows requires essentially $2^d$ examples. The paper pairs this lower bound with a matching upper bound (Theorem 2): if any $L_\\infty$-robust classifier with margin $\\delta$ exists, then roughly $(1/\\delta)^d$ examples suffice for a 1-nearest-neighbor rule to achieve 99% robust accuracy. Empirically, the paper shows on CIFAR-10 that doubling the training set raises certified robust accuracy by about 5%, that the trend extends to diffusion-generated data, and that projecting CIFAR-10 onto principal components 513–3072, which hold about 2% of the variance, still allows 85% non-robust test accuracy while robust training on that subspace fails.","pith_inferences":["A natural test of the causal story the paper does not run: rescale CIFAR-10's tail principal components (e.g., 2049–3072) to unit magnitude before robust training; if certified robust accuracy jumps, low magnitude is the operative blocker, and if it stays near zero, the PCA findings are correlational.","The authors' estimate of CIFAR-10's intrinsic dimension, $d^* \\approx 28$, implies around $10^{31}$ examples would be needed for a 1-nearest-neighbor classifier to be robust at unit distance, which suggests raw data collection alone cannot close the robustness gap and feature amplification or representation learning will be needed.","If dataset size is the dominant factor, then comparisons between robust-training methods are only meaningful at matched training-set sizes; otherwise reported gains may reflect extra data rather than algorithmic improvements.","The construction offers a diagnostic for other datasets: measure how much non-robust accuracy survives in low-variance linear subspaces; datasets with high such accuracy should exhibit the same data-hungry robustness scaling as CIFAR-10."],"forward_implications":["Doubling the training set reliably raises certified robust accuracy by about 5% on CIFAR-10, and the effect continues on MNIST, CIFAR-100, and with up to one million diffusion-generated images, so robustness comparisons should report and control for dataset size.","CIFAR-10 contains linear subspaces with tiny variance that are nevertheless useful for non-robust classification — principal components 513–3072 alone give 85% test accuracy — so robust classifiers are cut off from real predictive signal, not just from noise.","A single 1-Lipschitz architecture can be trained to 93.2% ordinary accuracy or to 61.7% certified robust accuracy by changing only the loss function, and 1-Lipschitz models can robustly overfit the training set, showing that architecture capacity is not the current bottleneck.","Scaling up compute alone yields diminishing returns on certified robust accuracy, while scaling up data keeps improving it, so future certified-robustness gains should come primarily from more or better training data."],"supporting_citations":[{"why":"Supplies the No Free Lunch theorem used to prove property 3 of Theorem 1, bounding average adversarial error by the chance that a test point's robust features were unseen.","marker":"[35]"},{"why":"Prior work showing robust generalization can require more data; the paper's Theorem 1 strengthens this to an exponential gap even when a perfect robust classifier exists.","marker":"[34]"},{"why":"Source of the robust-versus-non-robust feature distinction that the PCA subspace experiments in Section 5.2 test directly.","marker":"[20]"},{"why":"Derives the Lipschitz-margin bound that defines certified robust accuracy, the metric used in all scaling experiments.","marker":"[38]"},{"why":"Provides the 1-Lipschitz ConvNet architecture and training protocol used for the CIFAR/MNIST scaling and overfitting experiments.","marker":"[31]"},{"why":"Defines the AOL 1-Lipschitz linear layer used in the AOL MLP experiments.","marker":"[29]"},{"why":"Defines the CPL 1-Lipschitz linear layer used in the CPL ConvNet experiments.","marker":"[24]"},{"why":"Supplies the one-million-image diffusion-generated CIFAR-10-style dataset used to extend the scaling curve beyond 50k examples.","marker":"[40]"},{"why":"The current best 1-Lipschitz model (LiResNet) whose 78.1% certified robust accuracy provides the upper endpoint of the extended scaling comparison.","marker":"[19]"}],"fun_headline_variants":["Robust learning may demand exponential data","Data size, not architecture, is key for robust accuracy","No free robustness: exponential data for robust learning","Even when a robust classifier exists, learning it can be exponential"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sweeping conclusion that training-data size, not architecture or optimization, governs robust performance on real images rests on the assumption that the low-magnitude principal-component directions found in CIFAR-10 cause the robust generalization gap rather than merely correlating with it.","fun_headline_variants_meta":{"raw":{"variants":["Robust learning may demand exponential data","Data size, not architecture, is key for robust accuracy","No free robustness: exponential data for robust learning","Even when a robust classifier exists, learning it can be exponential"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001373,"raw_usage":{"total_tokens":5643,"prompt_tokens":1105,"completion_tokens":4538,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":721,"completion_tokens_details":{"reasoning_tokens":4476}},"tokens_in":721,"tokens_out":4538,"duration_ms":35554,"temperature":1.0,"reasoning_tokens":4476,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:36:43.607699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a 1-Lipschitz classifier on CIFAR-10 after rescaling the low-variance principal components (e.g., components 2049–3072) to unit magnitude: if certified robust accuracy stays near zero despite the amplification, the paper's claim that low magnitude blocks robust use of these directions would be refuted; if it jumps, the data-scaling explanation is supported.","supporting_citations":[{"cited_title":"Understanding Machine Learning: From Theory to Algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the No Free Lunch theorem used to prove property 3 of Theorem 1, bounding average adversarial error by the chance that a test point's robust features were unseen."},{"cited_title":"Adversarially robust gener- alization requires more data","cited_arxiv_id":null,"evidence_quote":"Prior work showing robust generalization can require more data; the paper's Theorem 1 strengthens this to an exponential gap even when a perfect robust classifier exists."},{"cited_title":"Adversar- ial examples are not bugs, they are features","cited_arxiv_id":null,"evidence_quote":"Source of the robust-versus-non-robust feature distinction that the PCA subspace experiments in Section 5.2 test directly."},{"cited_title":"Lipschitz-margin training: Scalable certification of pertur- bation invariance for deep neural networks","cited_arxiv_id":null,"evidence_quote":"Derives the Lipschitz-margin bound that defines certified robust accuracy, the metric used in all scaling experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the 1-Lipschitz ConvNet architecture and training protocol used for the CIFAR/MNIST scaling and overfitting experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the AOL 1-Lipschitz linear layer used in the AOL MLP experiments."},{"cited_title":"A dynamical system perspective for Lipschitz neural networks","cited_arxiv_id":null,"evidence_quote":"Defines the CPL 1-Lipschitz linear layer used in the CPL ConvNet experiments."},{"cited_title":"Better diffusion models further improve adversarial training","cited_arxiv_id":null,"evidence_quote":"Supplies the one-million-image diffusion-generated CIFAR-10-style dataset used to extend the scaling curve beyond 50k examples."},{"cited_title":"A recipe for improved certifiable robustness","cited_arxiv_id":null,"evidence_quote":"The current best 1-Lipschitz model (LiResNet) whose 78.1% certified robust accuracy provides the upper endpoint of the extended scaling comparison."}],"review_version":1}