AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks

Roey Magen, Ohad Shamir

NeurIPS 2023 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of learning distributions · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
Use zero initialization with a Frobenius-norm constraintGeneral Lipschitz matrix predictors · Size-independent learningsample complexity: m ≥ (LB/ε)^{cL^2B^2/ε^2}; fat-shattering dimension exp(cL^2B^2/ε^2)Mixed
Replace zero initialization with nonzero W0General Lipschitz matrix predictors · Size-independent learningfat-shattering dimension: mHurt
Constrain the first layer by Frobenius norm and later layers by spectral normsDeep networks with general Lipschitz activations · Size-independent learningsample complexity: m ≥ (LB/ε)^{cL^2B^2/ε^2}Improved
Require smoothness of the activationOne-hidden-layer networks with W0≠0 · Size-independent learningsample complexityMixed
Use SGD for convex Lipschitz losses instead of relying on uniform convergenceVector-valued linear predictors · Convex loss, bounded Euclidean inputsexcess risk: BL/√mImproved
Use element-wise Lipschitz activations and a peeling argument for deeper networksDeep neural networks with W0=0 · Size-independent learningsample complexity: m ≥ c(kL^{k-1}bR_{k-2} log^{3(k-1)/2}(m) · ∏_{i=1}^{k-1} B_i)^2/ε^2Improved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy