{"id":"6278de2e-63b8-4daf-a19f-fcc4a7bfb1ca","arxiv_id":"1908.02419","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Gradient descent on a network with a final hidden layer of width O(n) can interpolate any n-point dataset and reach a global optimum, and this linear rate is optimal.","lead":"This paper proves that gradient descent can reach a global training minimum for neural networks whose total size grows only linearly with the number of training examples. It also proves this linear rate is optimal and reports that such networks generalize on natural labels but not random labels.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof assumes a uniform input-separation margin that S_n does not provide; the for-all-datasets guarantee is therefore underived.","rationale":"The reader's weakest assumption correctly identifies the load-bearing gap: the proof of Theorem 1 makes essential use of a uniform positive separation γ among normalized inputs, but S_n contains datasets with arbitrarily small and zero separation. The proof's Corollary 2 and Lemma 2 require this margin, and the phrase 'by considering C sufficiently large' cannot make a fixed architecture work simultaneously for all datasets when the relevant p_ij values are not bounded below. This is a genuine proof-completeness problem in the universal quantifier over datasets, not merely a matter of presentation. I do not claim the theorem is false: for distinct inputs the rank-full property may hold almost surely by analyticity, and duplicate inputs with consistent labels may still be handled by a lower-rank feature matrix, but the paper does not supply that argument. The final-layer-only construction is also a real interpretive gap in the title/abstract, but the formal theorem permits zero learning rates, so the formal statement is less affected. The paper's proof for γ-separated datasets, its lower bound theorem, and the generalization analysis are coherent and provide partial support. Since the reader already rendered a CONDITIONAL verdict based on this concern, my stress-test does not move the verdict; UNCHANGED is appropriate.","tokens_in":15340,"tokens_out":14499,"duration_ms":184006,"concrete_test":"Take the family of normalized datasets S_k with x1=(1,0,...,0), x2=(√(1-1/k), 1/√k, 0,...,0), so ||x1-x2||^2=2-2√(1-1/k)→0, plus the duplicate case x1=x2 with conflicting labels. For H=2 and the fixed architecture chosen in the proof, compute p_12^(1)=E(σ(g)-σ(g'))^2 for the chosen activation and substitute into equation (18) at l=1. Verify that as k→∞ the left-hand side tends to 0 and for the duplicate pair is exactly 0, while cγ has no positive lower bound over S_n; hence no finite C can satisfy the displayed inequality for all k. This confirms that the uniform-margin step in the proof of Theorem 1 is not justified by the assumptions on S_n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV.A proves Theorem 1 by fixing constants C and requiring, for every pair i≠j, ||x_i^(H-1)||^2 - <x_i^(H-1),x_j^(H-1)> > cγ, where cγ depends only on γ=||x_i-x_j||^2. The proof obtains this by 'considering C sufficiently large' so the O(Σ β/√m_l) concentration error in Corollary 2 is smaller than p_ij^(H-1)/2. But S_n contains arbitrarily close and even identical normalized inputs, so no positive uniform γ exists. For x_i=x_j, p_ij^(0)=0 and inductively p_ij^(l)=0; equation (18) would require 0>cγ, impossible for any C. Consequently Lemma 2 cannot be applied: the feature matrix M(w,b) has duplicate rows for duplicate inputs, rank(M)<n, and the proof's step of exactly interpolating f*(X) via the last layer is unavailable. For near-duplicates, p_ij^(H-1) can be made smaller than any fixed concentration tolerance by shrinking the input gap, so a single architecture and constant C cannot cover all S∈S_n as Definition 1 requires. The proof as written establishes a γ-separated version of the theorem, not the stated universal quantifier over all datasets. Secondary but related: the constructed η has zero entries for the first H layers, so the 'all layers' claim is only about the objective, not about updating those layers.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a formal notion of probable trainability P_{n,H,δ}(d), and claims that for any depth H≥2 there is a network with Õ(n m_y + m_x H^2 + H^5) parameters such that gradient descent with per-coordinate learning rates reaches the functional global minimum L(f*) up to ε for every normalized dataset with probability at least 1−δ. The proof proceeds by fixing a random initialization, using concentration to show that the penultimate representations are well separated, proving that the random feature matrix M(w,b) has full row rank, and then solving the remaining convex last-layer problem. The paper also proves a lower bound showing that d ≥ n m_y is necessary, and gives a generalization bound together with experiments on several image datasets. A central gap is that the proof of Theorem 1 assumes a positive uniform separation margin γ that the dataset class S_n does not provide, and the learning-rate vector used in the proof has zero entries for all hidden layers; the advertised claim that all layers are optimized is therefore not derived as stated.","tokens_in":15593,"tokens_out":13872,"duration_ms":155822,"significance":"If the universal claim in Theorem 1 were correct, this would be a substantial advance: it would reduce the over-parameterization required for trainability from polynomial or 2^O(H) factors to Õ(n), prove a matching lower bound up to logarithms, and connect trainability to generalization. The paper also contains a clean random-feature reduction, a self-contained volume/Sard lower-bound argument, and informative experiments that support the qualitative predictions. However, the margin assumption in the proof and the last-layer-only update mean the main theorem as stated is not established; a corrected, possibly weaker theorem with a separation condition or a new uniform argument would still be valuable. The lower-bound and generalization sections appear largely sound.","major_comments":[{"comment":"The proof introduces a quantity γ with p^(0)_ij = ||x_i−x_j||^2 ≥ γ and then asserts that, by considering C sufficiently large, equation (18) holds with a lower bound cγ that depends only on γ. In Definition 1 the architecture f, and hence C and all layer widths, must be fixed once for all datasets S ∈ S_n, but S_n contains datasets with arbitrarily close or even identical normalized inputs; no positive uniform γ exists over S_n. For such datasets the concentration error O(1/(cC)) in equation (17) cannot be made smaller than p^(H−1)_ij/2 for all pairs with a single fixed C; in the duplicate case p^(l)_ij = 0 for every l, so inequality (18) would read 0 > cγ. Consequently the hypothesis of Lemma 2 is not verified for all S, the step rank(M(w,b)) = n is not established, and the exact interpolation f(X,ψ(θ0,W*)) = f*(X) is not proved for the full dataset class. As written, the proof establishes Theorem 1 only for datasets with a uniform separation margin.","section":"Section IV.A, equations (17)-(18) and Lemma 2"},{"comment":"The proof sets η_i = 1/(c_z ζ) only for the output-layer coordinates and η_i = 0 otherwise, so the generated gradient-descent iterates leave every hidden-layer parameter at its random initial value. This means the advertised statement that gradient descent finds a global minimum of the non-convex optimization of all layers is not derived: the optimization actually performed is convex optimization of the final linear layer on fixed random features. The formal statement of Theorem 1 may be compatible with such an η, but the title, abstract, and introduction should either be restricted to the claim as proved or the proof must be extended to positive learning rates for the hidden layers.","section":"Section IV.A, after equation (21)"},{"comment":"There is also a quantifier issue in the step leading to the full-rank event. For each fixed dataset S the rank-deficiency set may have measure zero, but Theorem 1 requires a 1−δ statement that holds for every S ∈ S_n, an uncountable family. The margin-based concentration argument is the only place where uniformity over S is provided, and it fails for the reason above; an additional covering/net argument, a restriction of S_n, or another uniform mechanism is needed to justify the universal claim.","section":"Section IV.A, equations (17)-(18)"}],"minor_comments":[{"comment":"The quantity γ is used in the inequality p^(0)_ij = ||x_i−x_j||^2 ≥ γ before it is defined; the paper should state explicitly whether γ is a universal constant, a dataset-dependent margin, or a parameter of the proof, and it should specify its role in the quantifier structure of Theorem 1.","section":"Corollary 2"},{"comment":"The remark that the constant cγ depends only on γ is insufficient because p^(H−1)_ij also depends on the activation function σ and on the entire collection of inputs; the text should provide the precise dependence so that the required size of C relative to the data can be checked.","section":"Section IV.A, equation (18)"},{"comment":"The sentence '... ≤ cθ for some constant in ε>0' is garbled; according to Definition 1, cθ must be chosen before ε, and the proof should be rewritten to make clear that cθ is independent of ε.","section":"End of proof of Theorem 1"},{"comment":"With the choice δ'_k = 6δ'/(π^2 k^2), the union-bound logarithm in inequality (35) should be ln(π^2 k^2/(6δ'))/(2n), not ln(π^2⌈ς‖W^T‖_{2,∞}⌉^2/δ')/(2n); the displayed bound is still valid up to absolute constants, but the derivation as written does not match the displayed formula.","section":"Appendix, proof of Proposition 1"},{"comment":"The axis label is rendered as 'C| /uni0304W /uni22A4|2̄ ∞' and the caption refers to 'C‖W^T‖_{2,∞}' without defining C; the normalization constant should be defined for the reader.","section":"Figure 2(d)"}],"recommendation":"major_revision","confidential_remarks":"The main theorem's universal quantifier over datasets is not supported by the proof as written, and the title/abstract overclaim relative to the last-layer-only learning-rate construction. I would ask the authors to either prove a version under an explicit separation condition or supply a genuinely uniform argument for the full class S_n, and to reconcile the 'all layers' language with the actual update rule. The lower-bound volume argument and the random-feature reduction are worth preserving, and a revised claim with these gaps fixed would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this paper has a real contribution and a real gap. The contribution is showing that an MLP with O~(n) parameters (plus dependence on H and widths) can interpolate any normalized dataset by gradient descent, improving on the n^8-type bounds in prior work. It also comes with a matching Omega(n m_y) lower bound via a Jacobian/volume argument that looks solid. The construction is a clean random-features argument: fix all layers but the last, make the last hidden layer wide enough, show the random feature matrix has full rank with high probability, and then do convex optimization in the last layer.\n\nThe soft spot is that the theorem as stated overclaims what the proof shows. The gradient descent step sets eta_i = 0 for every layer except the last (Section IV.A, after Lemma 3), so the algorithm only updates the output layer. The phrase 'non-convex optimization of all layers' means the objective value matches the global minimum of the full functional, not that all parameter blocks are trained. That is a mismatch between the title/abstract and the proof technique.\n\nSecond, and more serious, the proof of Theorem 1 requires that for every pair of distinct training inputs, the hidden representations at layer H-1 satisfy ||x_i^(H-1)||^2 - <x_i^(H-1), x_j^(H-1)> > cγ, with γ a positive constant coming from input separation. But the dataset class S_n only normalizes inputs; it allows arbitrarily close or identical inputs. For duplicate inputs, the Gram matrix has duplicate rows, rank(M) < n, and the interpolation step fails. The proof says 'by considering C sufficiently large' to make the concentration error smaller than the margin, but that cannot work uniformly because the margin can be zero. The universal quantifier 'for all S in S_n' is not derived; what is derived is a guarantee for datasets that are γ-separated at the input level.\n\nThe lower bound of Theorem 2 and the generalization bound in Proposition 1 are not affected by these issues, as far as I can tell. The lower bound uses a separate volume argument, and the generalization bound only needs the architecture from the upper-bound construction plus a bound on weight norms.\n\nIf I were editing this, I'd send it out: the lower bound and the O~(n) construction deserve careful reviewing, and the gap in the main theorem is fixable—either by weakening the claim to last-layer training or by adding a separation assumption to the dataset class. But the current version should not be published as is.","headline":"The headline guarantee overreaches the proof—only the last layer is trained and the for-all-datasets claim needs a separation margin—but the O~(n) bound and the lower bound are genuinely new and worth referee time.","tokens_in":16126,"tokens_out":2545,"would_cite":true,"duration_ms":26326,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deep net trainability proven with O(n) parameters","keywords":["gradient descent","global minimum","trainability","over-parameterization","deep neural networks","generalization bound","margin loss","parameter lower bound"],"falsifier":"Construct a normalized training set with two identical input vectors but different labels, or with inputs approaching each other so the pairwise hidden margin tends to zero; take the fixed architecture from Theorem 1 and run the prescribed gradient descent. If the training loss fails to reach the global minimum within the claimed $O(c_r\\zeta/\\epsilon)$ iterations, the theorem's \"for all datasets\" claim is false as stated. A direct calculation would be to evaluate $p^{(H-1)}_{ij}$ from Corollary 2 for two nearly equal inputs and check whether the constant $C$ in the proof can remain bounded independently of the dataset.","tokens_in":1715,"feed_emoji":"🧠","tokens_out":2552,"duration_ms":74257,"temperature":0.7,"pith_summary":"The paper aims to prove that ordinary gradient descent can reach a global minimum of the training loss for deep neural networks whose size grows only linearly with the number of training samples. Previously known trainability guarantees required polynomial sizes such as $n^6$ or $n^8$ parameters, far larger than networks used in practice; here the requirement is $\\widetilde{O}(n m_y)$ parameters, with $n$ the sample count and $m_y$ the output dimension. The authors also prove a matching lower bound, so this linear rate cannot be improved except by logarithmic factors. They further show that the trainable networks generalize to unseen data under a margin loss, with a bound that tracks the growth of the weight norm, which explains why natural labels generalize while random labels do not. If correct, the paper closes a large part of the gap between trainability theory and the sizes of neural networks actually used.","feed_headline":"Deep net trainability proven with O(n) parameters","feed_subtitle":"Gradient descent reaches a global minimum with network size growing linearly in the dataset, not polynomially.","key_machinery":"The load-bearing object is the random feature matrix of the last hidden layer, $M(\\tilde{w},\\tilde{b}) \\in \\mathbb{R}^{n \\times (m_H+1)}$, whose rows are the final hidden representations of the training inputs together with a constant column. The proof shows that after Gaussian initialization, with high probability this matrix has full row rank $n$ whenever the last hidden layer has at least $n$ neurons: concentration estimates ensure that distinct inputs keep a positive separation in the hidden space, and an analyticity argument (Lemma 2) shows rank deficiency happens only on a measure-zero set of weights. Full row rank means the last layer alone can interpolate any target values, so the nonconvex problem reduces to a convex least-squares-type problem in the last layer; gradient descent on that layer then converges at rate $c_r\\zeta/t$. The lower bound uses the rank theorem and a volume estimate of the image of the parameter map to show that $d<n m_y$ cannot fit arbitrary labels without huge weights.","core_discovery":"On the paper's own terms, the central discovery is a trainability guarantee for deep feedforward networks with $H \\ge 2$ hidden layers: for any normalized dataset of $n$ input–output pairs, any convex Lipschitz loss, and any $\\delta>0$, there is a network architecture with $d = O(((n + m_x H^2 + H^5 \\log(Hn^2/\\delta)) \\log(Hn^2/\\delta) + n m_y))$ parameters such that gradient descent with a per-coordinate learning rate reaches an $\\epsilon$-global minimum of the empirical risk with probability at least $1-\\delta$. The last hidden layer needs only $O(n)$ neurons, and earlier layers need only logarithmic widths. The matching lower bound says no architecture with fewer than $n m_y$ parameters can interpolate arbitrary labels without parameter norms growing like $n^{\\beta}$, so the linear dependence on $n$ is optimal up to a logarithmic factor. The generalization result bounds expected 0–1 error by an empirical margin loss plus a term proportional to the output-layer weight norm divided by $\\sqrt{n}$, and the experiments illustrate that this weight norm stays small for natural MNIST labels and grows for randomly corrupted labels.","pith_inferences":["A testable extension suggested by the proof: the minimal last-layer width for guaranteed convergence should scale with the inverse of the smallest pairwise distance among training inputs, and an experiment could vary duplicate closeness and measure where gradient descent starts to fail.","The full-rank feature matrix condition could be used as a data-dependent certificate of trainability: compute the smallest singular value of the hidden Gram matrix during training and predict convergence before it happens.","The volume-based lower bound likely generalizes to any smooth parametric function class, yielding a general principle that fitting arbitrary labels to $n$ points with $d$ parameters forces weight norms to grow at least like $n^{\\Omega((n m_y/d)-1)}$.","Because the upper bound is proven for analytic activations that approximate ReLU, the theory may extend to ReLU by a limiting argument, but the margin condition would then need separate treatment for exactly zero hidden differences."],"forward_implications":["Networks with parameter count linear in the number of training samples are provably trainable to global optimality by gradient descent, bringing the theory into the regime of real architectures such as PreActResNet18.","The lower bound shows no trainability guarantee can do better than $\\Omega(n m_y)$ parameters up to log factors, so the linear rate is the right target for future work.","For shallow networks with $H=1$, the guarantee requires $O(n(m_x+m_y))$ parameters, so depth reduces the parameter cost when the input dimension is large.","The generalization bound ties test error to the output-layer weight norm, giving a concrete mechanism by which the same network memorizes random labels with large norm but generalizes on natural labels with small norm."],"supporting_citations":[{"why":"Provides the previous best deep-network trainability guarantee requiring $\\widetilde{\\Omega}(2^{O(H)}n^8)$ parameters, the baseline Theorem 1 improves upon.","marker":"[17]"},{"why":"Represents the over-parameterized convergence theory whose polynomial parameter dependence of at least $n^{60}$ is reduced to linear in this paper.","marker":"[16]"},{"why":"A later improved over-parameterized analysis with $\\widetilde{\\Omega}(H^{12}n^8)$ parameters, listed as a comparison baseline.","marker":"[19]"},{"why":"Gives shallow-network trainability with $\\widetilde{\\Omega}(n^2(m_x+m_y))$ parameters, extended here to deep networks with $\\widetilde{O}(n m_y)$.","marker":"[15]"},{"why":"Supplies the fact that the zero set of a nonzero real-analytic function has Lebesgue measure zero, used in Lemma 2 to show full rank with probability one.","marker":"[20]"},{"why":"Supplies the margin-based Rademacher generalization bound used in Proposition 1.","marker":"[24]"},{"why":"Provides the MNIST dataset used in the experiments for the generalization and random-label comparison.","marker":"[21]"}],"fun_headline_variants":["Gradient descent provably finds global minima in practical deep nets","O(n) parameters suffice for GD to reach global minimum","Global convergence proven for practical-sized deep nets","GD finds global minima with optimal linear parameter scaling"],"cache_read_input_tokens":18304,"weakest_assumption_plain":"The proof needs every pair of distinct training inputs to end up with hidden representations separated by at least a fixed positive margin, and it chooses the network width dependent on that margin; since the theorem claims to cover all normalized datasets, including ones with arbitrarily close or identical inputs, the universal guarantee relies on a margin that the dataset class itself does not enforce.","fun_headline_variants_meta":{"raw":{"variants":["Gradient descent provably finds global minima in practical deep nets","O(n) parameters suffice for GD to reach global minimum","Global convergence proven for practical-sized deep nets","GD finds global minima with optimal linear parameter scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002187,"raw_usage":{"total_tokens":8466,"prompt_tokens":935,"completion_tokens":7531,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":7468}},"tokens_in":551,"tokens_out":7531,"duration_ms":54548,"temperature":1.0,"reasoning_tokens":7468,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:03:30.572315+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a normalized training set with two identical input vectors but different labels, or with inputs approaching each other so the pairwise hidden margin tends to zero; take the fixed architecture from Theorem 1 and run the prescribed gradient descent. If the training loss fails to reach the global minimum within the claimed $O(c_r\\zeta/\\epsilon)$ iterations, the theorem's \"for all datasets\" claim is false as stated. A direct calculation would be to evaluate $p^{(H-1)}_{ij}$ from Corollary 2 for two nearly equal inputs and check whether the constant $C$ in the proof can remain bounded independently of the dataset.","supporting_citations":[{"cited_title":"Empirical margin di stributions and bounding the generalization error of combined classifiers,","cited_arxiv_id":null,"evidence_quote":"Supplies the margin-based Rademacher generalization bound used in Proposition 1."},{"cited_title":"Gradien t-based learning applied to document recognition,","cited_arxiv_id":null,"evidence_quote":"Provides the MNIST dataset used in the experiments for the generalization and random-label comparison."}],"review_version":1}