← All AI/ML open problems

Kernel learning · Statistical learning theory · Neural architecture & complexity / Open question

How Wide Must a Kernel-Like Network Be?

Kernel theory can prove a good statistical rate using a network much larger than practical learning seems to require. The excess width may be a proof artifact or a real computational price. Efficiency payoff: Match useful kernel generalization with less overparameterization, cheaper sampled features and fewer gradient evaluations.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

For a two-layer smooth network in NTK scaling, let its limiting kernel operator T\mathcal T on a compact input law satisfy tr⁡(T(T+λI)−1)≤Qλ−γ\operatorname{tr}(\mathcal T(\mathcal T+\lambda I)^{-1})\leq Q\lambda^{-\gamma}, and let f∗=Trgf_*=\mathcal T^r g, ∥g∥L2≤1\|g\|_{L^2}\leq1, 1/2≤r≤11/2\leq r\leq1. From nn noisy examples, determine the least width and gradient-training cost attaining excess squared risk O~(n−2r/(2r+γ))\widetilde O(n^{-2r/(2r+\gamma)}) while remaining within a fixed small relative empirical-NTK drift. Seek matching width/cost lower bounds, not merely some polynomial width.

Assumptions and scope

  • Use a fixed bounded smooth activation such as tanh, independent Gaussian initialization, and a centered output subtracting the initial network so initial prediction is zero. Inputs are in a fixed compact ball; independent label noise is sub-Gaussian. The source/effective-dimension constants and gamma in (0,1] are supplied hypotheses.
  • Specify minibatch sampling, regularization or early stopping, step schedule and finite-width approximation conditions. The benchmark requires small kernel drift through the chosen stopping time; a feature-learning algorithm outside that regime does not prove the same width bound.
  • Charge Jacobian/gradient evaluation, leverage-score estimation, sketch construction, linear solves and all training samples. An exact kernel matrix or optimal sampling distribution is not free. Compare actual finite-network training with exact and sketched kernel regression, and state additional assumptions needed for a matching lower bound.

What would settle it?

Sharper sufficient and necessary width/iteration/sample laws under the fixed source class and lazy-training constraint, with an implementable costed scheme. The known minimax statistical rate and existence of polynomial-width guarantees are baselines.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Zhou et al. already transfer minimax source/capacity rates to smooth GD/SGD networks at polynomial width. NTK feature sketching, leverage initialization and faster finite-width kernel computation are established. This target asks for the sharp joint resource frontier and remains an editorial framework-level specialization. This is an editorial, source-motivated research target. The preliminary review through 2026-11-20 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Zhou et al. — Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent ↗partial theory · source checked 2026-11-20

    Primary abstract checked: finite-width/horizon approximation and minimax rates under source/effective-dimension conditions with polynomial width. The new target is sharp necessary width and total cost, not first sample-efficient NTK-based training.

  2. Zandieh et al. — Scaling Neural Tangent Kernels via Sketching and Random Features ↗partial theory · source checked 2026-11-20

    Scholarly abstract checked: near-input-sparsity feature construction and spectral NTK approximation using sketching/leverage scores. Efficient approximate NTK regression already exists.

  3. Novak, Sohl-Dickstein and Schoenholz — Fast Finite Width Neural Tangent Kernel ↗related algorithm · source checked 2026-11-20

    Scholarly abstract checked: architecture-aware algorithms improve exponents of finite-width NTK computation and memory. Explicit kernel construction cost is a baseline to beat or avoid.

  4. Lee et al. — Generalized Leverage Score Sampling for Neural Networks ↗partial theory · source checked 2026-11-20

    Scholarly abstract checked: leverage-score initialization, spectral approximation and regularized-network/NTK-ridge connections already exist. Data-aware sampling is not an unexplored existence question.