ai-research-survey

scan.json (23855B)

---

 {
   "paper": {
     "title": "Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit",
     "authors": ["Boaz Barak", "Benjamin L. Edelman", "Surbhi Goel", "Sham Kakade", "Eran Malach", "Cyril Zhang"],
     "year": 2022,
     "venue": "Neural Information Processing Systems",
     "arxiv_id": "2207.08799",
     "doi": "10.48550/arXiv.2207.08799"
   },
   "scan_version": 2,
   "active_modules": ["experimental_rigor"],
   "methodology_tags": ["theoretical", "benchmark-eval"],
   "key_findings": "Neural networks trained with SGD can learn k-sparse parities of n bits in nO(k) iterations, nearly matching SQ lower bounds, across a variety of architectures (MLPs, Transformers, PolyNets, single neurons). Despite flat loss curves for most of training, SGD makes hidden progress by gradually amplifying sparse features via a Fourier gap in the population gradient, rather than performing random search. The paper provides theoretical proofs for convergence on MLPs and disjoint-PolyNets, and demonstrates phase transitions and grokking phenomena in this setting.",
   "checklist": {
     "artifacts": {
       "code_released": {
         "applies": true,
         "answer": false,
         "justification": "No code repository URL is provided in the paper. Appendix D.3 mentions implementation in PyTorch but provides no link to code."
       },
       "data_released": {
         "applies": true,
         "answer": true,
         "justification": "The data is synthetically generated from well-defined distributions (sparse parity distributions over {±1}^n). The generation procedure is fully specified, making the data trivially reproducible."
       },
       "environment_specified": {
         "applies": true,
         "answer": false,
         "justification": "Appendix D.3 mentions PyTorch and GPU types (NVIDIA Tesla P100, P40, RTX A6000) but provides no requirements.txt, library versions, or environment specification."
       },
       "reproduction_instructions": {
         "applies": true,
         "answer": false,
         "justification": "No step-by-step reproduction instructions are provided. Hyperparameters are scattered across the appendix but there are no scripts or README for reproducing experiments."
       }
     },
     "statistical_methodology": {
       "confidence_intervals_or_error_bars": {
         "applies": true,
         "answer": true,
         "justification": "Figure 10 shows 95% bootstrap confidence intervals for median convergence times. Figure 14 shows interquartile ranges with whiskers."
       },
       "significance_tests": {
         "applies": true,
         "answer": false,
         "justification": "No statistical significance tests are performed. Claims about scaling (nO(k)) are supported by visual inspection of log-log plots rather than formal tests."
       },
       "effect_sizes_reported": {
         "applies": true,
         "answer": true,
         "justification": "The paper reports concrete scaling exponents (α such that tc ∝ n^(αk)) in Figure 9, providing magnitude context for convergence time relationships."
       },
       "sample_size_justified": {
         "applies": true,
         "answer": false,
         "justification": "The number of random trials (25 for main results, 1000 for scaling plots) is stated but not justified. No power analysis or justification for why these numbers suffice."
       },
       "variance_reported": {
         "applies": true,
         "answer": true,
         "justification": "Variance is reported through multiple mechanisms: 95% bootstrap CIs (Figure 10), interquartile ranges (Figure 14), convergence time histograms (Figure 2), and multiple training curves from different seeds."
       }
     },
     "evaluation_design": {
       "baselines_included": {
         "applies": true,
         "answer": true,
         "justification": "Random search is used as a baseline comparison (green curves in Figure 4 left and Figure 14), and SQ lower bounds serve as theoretical baselines."
       },
       "baselines_contemporary": {
         "applies": true,
         "answer": true,
         "justification": "The baselines are the known theoretical computational limits (SQ lower bounds), which are the appropriate comparison for this problem. The paper positions against concurrent work by Telgarsky (2022) and Damian et al. (2022)."
       },
       "ablation_study": {
         "applies": true,
         "answer": true,
         "justification": "The paper systematically varies architectures (15+ configurations), batch sizes, learning rates, initializations, loss functions, and problem parameters (n, k) to understand which components matter."
       },
       "multiple_metrics": {
         "applies": true,
         "answer": true,
         "justification": "Multiple metrics are used: classification error, convergence time, Fourier gap, weight movement norm (hidden progress measure), and loss curves."
       },
       "human_evaluation": {
         "applies": false,
         "answer": false,
         "justification": "Human evaluation is irrelevant for a theoretical/empirical study on synthetic learning problems."
       },
       "held_out_test_set": {
         "applies": true,
         "answer": true,
         "justification": "The main results use online learning (fresh i.i.d. samples at each iteration). Validation accuracy is computed on a separate batch of 2^13 = 8192 samples (Appendix D.2)."
       },
       "per_category_breakdown": {
         "applies": true,
         "answer": true,
         "justification": "Results are broken down per architecture (15+ settings), per batch size, per learning rate, per (n,k) problem instance, in Figures 7-9 and extensive appendix tables."
       },
       "failure_cases_discussed": {
         "applies": true,
         "answer": true,
         "justification": "Less robust configurations are discussed: settings (*i), (*ii), (*iii) require larger batch sizes. Figure 2 (right) shows scaling degradation at larger n. Appendix C.2 discusses counterintuitive failure modes."
       },
       "negative_results_reported": {
         "applies": true,
         "answer": true,
         "justification": "Several negative results: Transformer setting (*iii) requires Adam instead of SGD, underparameterized models (r<k) cannot reach 100% accuracy, scaling exponents worsen at larger n (Figure 2 right), and layer-by-layer learning fails for deep polynomial networks (Appendix C.7)."
       }
     },
     "claims_and_evidence": {
       "abstract_claims_supported": {
         "applies": true,
         "answer": true,
         "justification": "Abstract claims about nO(k) convergence, phase transitions, and hidden progress via Fourier gap are all supported by both empirical results (Figures 1, 7-10) and theoretical analysis (Theorems 4, 6, 7)."
       },
       "causal_claims_justified": {
         "applies": true,
         "answer": true,
         "justification": "The paper's causal claims (SGD amplifies features via Fourier gap rather than random search) are supported by both formal proofs (Theorems 4, 6, 7) and controlled empirical ablations (varying individual parameters while holding others fixed)."
       },
       "generalization_bounded": {
         "applies": true,
         "answer": true,
         "justification": "The paper is careful to bound claims to the sparse parity setting: 'these insights extend from parity learning to more complex...problem settings' is posed as an open question (Section 6), not a claim. The broader impact statement notes the 'heavily-idealized synthetic problem setting.'"
       },
       "alternative_explanations_discussed": {
         "applies": true,
         "answer": true,
         "justification": "The paper explicitly considers and empirically refutes the 'stumbling in the dark' (random search) hypothesis with four lines of evidence (Section 3.2), and discusses NTK as an alternative explanation (Section 4.1, Theorem 5)."
       },
       "proxy_outcome_distinction": {
         "applies": true,
         "answer": true,
         "justification": "The paper's claims match the granularity of its measurements: convergence times, classification error, and Fourier gaps are measured and reported directly without broader framing beyond the synthetic setting."
       }
     },
     "setup_transparency": {
       "model_versions_specified": {
         "applies": false,
         "answer": false,
         "justification": "The paper does not use pre-trained LLMs. All models are trained from scratch with fully specified architectures."
       },
       "prompts_provided": {
         "applies": false,
         "answer": false,
         "justification": "The paper does not use prompting. All experiments train neural networks from scratch."
       },
       "hyperparameters_reported": {
         "applies": true,
         "answer": true,
         "justification": "Hyperparameters are extensively documented: learning rates, batch sizes, weight decay schedules, initialization schemes, and architecture configurations are all specified in Section 3, Appendix D.1, and figure captions."
       },
       "scaffolding_described": {
         "applies": false,
         "answer": false,
         "justification": "No agentic scaffolding is used. The paper trains standard neural networks with SGD."
       },
       "data_preprocessing_documented": {
         "applies": true,
         "answer": true,
         "justification": "The data generation process is fully specified: uniform distribution over {±1}^n with parity labels. The synthetic data requires no preprocessing. Section 2 provides complete formal definitions."
       }
     },
     "limitations_and_scope": {
       "limitations_section_present": {
         "applies": true,
         "answer": true,
         "justification": "Section 6 (Conclusion) discusses open questions including extension to small-batch settings, other architectures and losses, and the gap between theory and the full range of empirical settings."
       },
       "threats_to_validity_specific": {
         "applies": true,
         "answer": true,
         "justification": "The paper identifies specific limitations: the theoretical result requires sign vector initialization while experiments work with other initializations (Section 4.1), batch size scaling with nΩ(k) is required theoretically but B=1 works empirically, and scaling exponents worsen at larger n (Figure 2 right, Appendix C.2)."
       },
       "scope_boundaries_stated": {
         "applies": true,
         "answer": true,
         "justification": "The paper explicitly states scope: 'this work largely focuses on the online learning case' (Section 6), notes the synthetic setting does not directly address real-world tasks, and poses extension to 'more complex...real-world combinatorial problem settings' as future work."
       }
     },
     "data_integrity": {
       "raw_data_available": {
         "applies": true,
         "answer": false,
         "justification": "No raw experimental data (convergence times, training logs) is made available. The synthetic data itself is trivially reproducible but experimental results are not downloadable."
       },
       "data_collection_described": {
         "applies": true,
         "answer": true,
         "justification": "Data generation is fully specified: synthetic parity distributions with uniform random inputs. Experimental procedure (number of trials, convergence criteria, validation methodology) is described in Appendix D.2."
       },
       "recruitment_methods_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants. Data is synthetically generated from a well-defined mathematical distribution."
       },
       "data_pipeline_documented": {
         "applies": true,
         "answer": true,
         "justification": "The pipeline from data generation to result reporting is documented: synthetic data → SGD training → convergence time measurement → aggregation (10th percentile, median). Appendix D.2 describes validation batch sizes and convergence criteria."
       }
     },
     "conflicts_of_interest": {
       "funding_disclosed": {
         "applies": true,
         "answer": true,
         "justification": "Acknowledgements section states: 'Sham Kakade acknowledges funding from the Office of Naval Research under award N00014-22-1-2377.'"
       },
       "affiliations_disclosed": {
         "applies": true,
         "answer": true,
         "justification": "Author affiliations are listed: Harvard University, Microsoft Research, University of Pennsylvania, Hebrew University of Jerusalem."
       },
       "funder_independent_of_outcome": {
         "applies": true,
         "answer": true,
         "justification": "The Office of Naval Research funding has no apparent stake in the theoretical results about learning parities. Microsoft Research affiliation exists but the paper evaluates no Microsoft products."
       },
       "financial_interests_declared": {
         "applies": true,
         "answer": false,
         "justification": "No competing interests or financial interests statement is included in the paper."
       }
     },
     "contamination": {
       "training_cutoff_stated": {
         "applies": false,
         "answer": false,
         "justification": "The paper does not evaluate a pre-trained model's capability on any benchmark. All models are trained from scratch on synthetic data."
       },
       "train_test_overlap_discussed": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — models are trained from scratch on synthetic distributions, not pre-trained models evaluated on benchmarks."
       },
       "benchmark_contamination_addressed": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — the paper uses synthetic data generated from mathematical distributions, not pre-existing benchmarks that could be in training data."
       }
     },
     "human_studies": {
       "pre_registered": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "irb_or_ethics_approval": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "demographics_reported": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "inclusion_exclusion_criteria": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "randomization_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "blinding_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "attrition_reported": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       }
     },
     "cost_and_practicality": {
       "inference_cost_reported": {
         "applies": true,
         "answer": false,
         "justification": "No per-experiment cost or latency is reported, though the paper mentions total compute in Appendix D.3."
       },
       "compute_budget_stated": {
         "applies": true,
         "answer": true,
         "justification": "Appendix D.3 states: 'approximately 1500 CPU hours' for main experiments and 'approximately 200 GPU hours' for GPU-accelerated experiments, with specific GPU types listed."
       }
     },
     "experimental_rigor": {
       "seed_sensitivity_reported": {
         "applies": true,
         "answer": true,
         "justification": "Results are reported across many random seeds: 25 trials for main results (Figures 7-8), 1000 trials for scaling plots (Figure 10), and 10^6 trials for convergence time distributions (Figure 2 left)."
       },
       "number_of_runs_stated": {
         "applies": true,
         "answer": true,
         "justification": "Number of runs is explicitly stated: 25 random trials (Figure 7-8), 1000 runs (Figure 10), 10^6 trials (Figure 2 left), 5 runs for training curves (Figure 1)."
       },
       "hyperparameter_search_budget": {
         "applies": true,
         "answer": true,
         "justification": "The search space is stated: learning rates from {0.001, 0.01, 0.1, 1}, batch sizes from {1, 2, 4, ..., 1024}, three initialization schemes, three loss functions. Best learning rate is reported explicitly."
       },
       "best_config_selection_justified": {
         "applies": true,
         "answer": true,
         "justification": "Figure 7 reports results for the best learning rate, and the search space is explicit. The paper reports results across all configurations rather than cherry-picking, showing the full grid in Figures 7-9."
       },
       "multiple_comparison_correction": {
         "applies": false,
         "answer": false,
         "justification": "No formal statistical hypothesis tests are performed, so multiple comparison correction is not applicable."
       },
       "self_comparison_bias_addressed": {
         "applies": true,
         "answer": false,
         "justification": "The paper introduces PolyNets and compares against standard architectures without discussing potential bias in this comparison. However, the main claims are about matching theoretical lower bounds rather than outperforming other methods."
       },
       "compute_budget_vs_performance": {
         "applies": true,
         "answer": true,
         "justification": "The core contribution is characterizing performance (convergence time) as a function of computational budget (iterations), shown extensively in Figures 1, 7, 10."
       },
       "benchmark_construct_validity": {
         "applies": true,
         "answer": true,
         "justification": "The paper extensively discusses why sparse parity is a meaningful benchmark: it has known computational limits (SQ lower bounds), separates statistical from computational difficulty, and is connected to broader phenomena like grokking and emergent capabilities."
       },
       "scaffold_confound_addressed": {
         "applies": false,
         "answer": false,
         "justification": "No scaffolding is involved. The paper trains neural networks with standard SGD."
       }
     },
     "data_leakage": {
       "temporal_leakage_addressed": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — all models are trained from scratch on synthetic data, not pre-trained models evaluated on benchmarks."
       },
       "feature_leakage_addressed": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — synthetic data with known ground truth. No risk of feature leakage by construction."
       },
       "non_independence_addressed": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — data is i.i.d. by construction from synthetic distributions."
       },
       "leakage_detection_method": {
         "applies": false,
         "answer": false,
         "justification": "Not applicable — no pre-trained models or pre-existing benchmarks used."
       }
     }
   },
   "claims": [
     {
       "claim": "A variety of neural networks (MLPs, Transformers, sinusoidal neurons, PolyNets) successfully learn k-sparse n-dimensional parities in at most c·n^(αk) SGD steps, for small constants c, α.",
       "evidence": "Figures 1, 7-10 show convergence times across 15+ architecture configurations, 3 initialization schemes, multiple batch sizes and learning rates, for n≤30, k≤4. 10th percentile convergence times and median convergence times are reported.",
       "supported": "strong"
     },
     {
       "claim": "SGD does not learn parities via random exhaustive search ('stumbling in the dark'), but rather makes continual hidden progress via Fourier gap amplification.",
       "evidence": "Four empirical arguments against random search (Section 3.2): convergence times scale with k, no early convergence in histograms (Figure 2 left), sensitivity to initialization not SGD samples (Figure 2 center), elbows in scaling curves (Figure 2 right). Theoretical analysis shows population gradient encodes relevant features (Theorems 4, 6, 7).",
       "supported": "strong"
     },
     {
       "claim": "SGD on 2-layer MLPs of width 2^Θ(k), with batch size n^O(k), converges to a solution with at most ε error in at most 2^O(k)·poly(1/ε) iterations (Theorem 4).",
       "evidence": "Full proof in Appendix B.1. The result relies on Fourier gap analysis of the majority function and is proven for ReLU activation with sign vector initialization and hinge loss.",
       "supported": "strong"
     },
     {
       "claim": "For disjoint-PolyNets, gradient flow exhibits a phase transition: it spends a 1−o(1) fraction of convergence time with error ≥49% (Theorem 6).",
       "evidence": "Full proof in Appendix B.3-B.4 for both ±1 and Gaussian initializations. Supported empirically in Figure 5.",
       "supported": "strong"
     },
     {
       "claim": "In the finite-sample setting, neural networks exhibit grokking: delayed generalization after initial overfitting.",
       "evidence": "Figure 4 (right) and Figure 15 show grokking for width-100 ReLU MLPs at small sample sizes. Weight decay modulates the statistical-computational tradeoff (Appendix C.5).",
       "supported": "moderate"
     }
   ],
   "red_flags": [],
   "cited_papers": [
     {
       "title": "Beyond the Imitation Game: Quantifying and Extrapolating the Capabilities of Language Models",
       "authors": ["Aarohi Srivastava", "Abhinav Rastogi"],
       "year": 2022,
       "arxiv_id": "2206.04615",
       "relevance": "BIG-bench benchmark identifying emergent capabilities in language models at critical scale thresholds."
     },
     {
       "title": "Language models are few-shot learners",
       "authors": ["Tom B Brown"],
       "year": 2020,
       "arxiv_id": "2005.14165",
       "relevance": "GPT-3 paper demonstrating emergent few-shot learning capabilities in large language models."
     },
     {
       "title": "Training compute-optimal large language models",
       "authors": ["Jordan Hoffmann"],
       "year": 2022,
       "arxiv_id": "2203.15556",
       "relevance": "Chinchilla scaling laws for compute-optimal training of large language models."
     },
     {
       "title": "Grokking: Generalization beyond overfitting on small algorithmic datasets",
       "authors": ["Alethea Power"],
       "year": 2022,
       "arxiv_id": "2201.02177",
       "relevance": "Documented grokking phenomenon of delayed generalization in neural networks on algorithmic tasks."
     },
     {
       "title": "Neural tangent kernel: Convergence and generalization in neural networks",
       "authors": ["Arthur Jacot"],
       "year": 2018,
       "relevance": "Foundational work on NTK regime; this paper shows results outside the NTK regime where feature learning is essential."
     },
     {
       "title": "Attention is all you need",
       "authors": ["Ashish Vaswani"],
       "year": 2017,
       "relevance": "Transformer architecture used as one of the evaluated architectures for learning parities."
     },
     {
       "title": "Failures of gradient-based deep learning",
       "authors": ["Shai Shalev-Shwartz", "Ohad Shamir", "Shaked Shammah"],
       "year": 2017,
       "relevance": "Prior work demonstrating computational hardness of learning parities for gradient-based algorithms."
     },
     {
       "title": "A mechanistic interpretability analysis of grokking",
       "authors": ["Neel Nanda", "Tom Lieberum"],
       "year": 2022,
       "relevance": "Complementary analysis of hidden progress in Transformers trained on arithmetic tasks exhibiting grokking."
     }
   ]
 }