Research map / Learning theory and algorithms / Sample complexity
Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks
Roey Magen, Ohad Shamir
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use zero initialization with a Frobenius-norm constraint | General Lipschitz matrix predictors · Size-independent learning | sample complexity: m ≥ (LB/ε)^{cL^2B^2/ε^2}; fat-shattering dimension exp(cL^2B^2/ε^2) | Mixed |
| Replace zero initialization with nonzero W0 | General Lipschitz matrix predictors · Size-independent learning | fat-shattering dimension: m | Hurt |
| Constrain the first layer by Frobenius norm and later layers by spectral norms | Deep networks with general Lipschitz activations · Size-independent learning | sample complexity: m ≥ (LB/ε)^{cL^2B^2/ε^2} | Improved |
| Require smoothness of the activation | One-hidden-layer networks with W0≠0 · Size-independent learning | sample complexity | Mixed |
| Use SGD for convex Lipschitz losses instead of relying on uniform convergence | Vector-valued linear predictors · Convex loss, bounded Euclidean inputs | excess risk: BL/√m | Improved |
| Use element-wise Lipschitz activations and a peeling argument for deeper networks | Deep neural networks with W0=0 · Size-independent learning | sample complexity: m ≥ c(kL^{k-1}bR_{k-2} log^{3(k-1)/2}(m) · ∏_{i=1}^{k-1} B_i)^2/ε^2 | Improved |
Closest papers by meaning
- Generalization Bounds for Neural Networks via Approximate Description Length (NeurIPS 2019 · similarity 0.89)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.85)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.85)
- Deep linear networks for regression are implicitly regularized towards flat minima (NeurIPS 2024 · similarity 0.85)
- Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
