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.
Seed catalog · Showing the bundled record.
Problem statement
For a two-layer smooth network in NTK scaling, let its limiting kernel operator on a compact input law satisfy , and let , , . From noisy examples, determine the least width and gradient-training cost attaining excess squared risk 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
- 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.
- 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.
- 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.
- 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.