{"id":"20cb599f-29aa-44d5-bd6b-42e009a6b309","arxiv_id":"2505.12353","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A nonlinear adjoint operator rewrites nonlinear least-squares losses as norms of a data-dependent matrix, enabling leverage-score and row-norm sampling with subspace-embedding-style guarantees.","lead":"This paper rewrites nonlinear predictions as matrix products, then extends importance sampling, a way to pick the most informative data points, from linear models to nonlinear ones. It proves approximation guarantees for the sampled training objective and tests the scores on regression and image classification tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Example 3.4's score-domination bound fails when many adjoint rows vanish, so the NN application of Theorem 3.1 is unsupported.","rationale":"The reader's weakest assumption correctly identified the bounded-ratio conditions as restrictive and noted the θ* coverage gap in the ε-net argument. My stress-test focuses on a more specific and more damaging flaw: Example 3.4's derivation of the parameter-independent score domination is internally incorrect when some adjoint rows vanish. This is not a disagreement with the theorem as a conditional statement; Theorem 3.1 may be true whenever its β-domination premise holds. The problem is that the paper's main neural-network example does not actually establish that premise. The same inactive-neuron mechanism can affect any network with gated homogeneous units, including the ReLU networks used in the classification experiments. The experiments compute scores at the trained θ*, so they do not test the parameter-independent mechanism required by Theorem 3.1. The paper still has value: the adjoint operator identity, the fixed-θ sampling guarantee, and Example 3.3 for Swish-type generalized linear predictors are legitimate contributions. The neural-network guarantee, however, is unsupported unless Example 3.4 is repaired by either restricting C to configurations with a guaranteed active fraction or by redesigning the sampling distribution so that the denominator lower bound survives. Because the correct response is a major revision rather than acceptance or outright rejection, the reader's CONDITIONAL verdict is unchanged.","tokens_in":19955,"tokens_out":10821,"duration_ms":114773,"concrete_test":"Run a small script for Example 3.4 with m=1, φ(z)=z, d=1, data x_i ∈ {+1,-1} with 20% positive entries, and C = {(a,b) : a^2 ≥ 1, a^2+b^2 ≤ 2}. Pick θ=(1,1). Compute the nonlinear norm scores τ_i(θ) from Definition 3.4 and the linear norm scores τ_i of the matrix bX, then check whether τ_i(θ) ≤ (1/β)τ_i holds with β = min{c1l,1}/max{c2u,1} = 1/2. The active rows will give τ_i(θ) = 5/n and τ_i = 1/n, so the inequality fails. Varying the fraction q of positive x_i shows the failure ratio scales as 1/q, localizing the defect to the denominator lower bound when inactive rows are present.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 rests on the premise that there is a parameter-independent distribution {τ_i} with βτ_i(θ) ≤ τ_i for all θ in C. Example 3.4 claims to establish this for ReLU-style networks with β = min{c1l,1}/max{c2u,1}. The proof derives c1l||x_i||^2 ≤ ||f*_i(θ)||^2 ≤ c2u||x_i||^2 and then uses these individual bounds both in the numerator and in the denominator of τ_i(θ) = ||bf*_i(θ)||^2 / ||bF*(θ)||^2_F. The lower bound fails whenever no hidden unit is active for a data point: if ⟨b_j, x_i⟩ ≤ 0 for all j, then f*_i(θ) = 0. The paper dismisses this with 'as otherwise f*_i(θ) = 0', but that case is precisely what breaks the denominator lower bound ||bF*(θ)||^2_F ≥ min{c1l,1}(||X||^2_F + m^2Σ_j φ_j(0)^2). When a fraction of rows are inactive, the nonlinear denominator sums only over active rows while the linear denominator sums over all rows. For an active row, τ_i(θ) can then exceed (1/β)τ_i by roughly 1/q, where q is the active fraction. Concretely, take m=1, φ(z)=z (so c1=c2=1), θ=(a,b)=(1,1), data with 20% of x_i positive and 80% negative, and C defined by a^2≥1, a^2+b^2≤2. Each active row has nonlinear norm score 5/n while its linear norm score is 1/n, so τ_i(θ)/τ_i = 5 > 1/β = 2. Thus the claimed domination does not hold on C, and Theorem 3.1 cannot be invoked for the ReLU network example. The gap is not merely the bounded-ratio restriction noted by the reader; it occurs even with φ(z)=z because of inactive ReLU units. Consequently, the paper's claim of approximation guarantees for neural networks rests on an unproven example, although the fixed-theta sampling theory and the generalized-linear-predictor analysis remain intact.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a framework for importance sampling in nonlinear least-squares problems. The central device is the adjoint operator f*(θ)=∫_0^1 ∂θ f(tθ)dt, which yields the exact identity f(θ)=⟨bθ,bf*(θ)⟩ and hence L(θ)=‖bF*(θ)bθ‖² for squared loss. The authors define nonlinear norm and leverage scores from the rows of bF*(θ), prove a fixed-θ subspace embedding, and then claim a parameter-independent guarantee: under a score-domination condition βτ_i(θ)≤τ_i on a set C containing θ*, sampling s=O((p log(p/δ)+p²log(p/ε))/(β ε²)) points gives L(θ*_S)≤L(θ*)+O(ε) with high probability. Applications are given to single-index models and to two-layer ReLU networks, with experiments on regression and classification tasks.","tokens_in":20429,"tokens_out":14551,"duration_ms":152628,"significance":"If the main theorem were fully correct, the adjoint representation would be an elegant unification of linear RandNLA embeddings with nonlinear importance sampling, and the guarantee (2) would improve on the multiplicative-constant bounds of Gajjar et al. (2024). The exactness of the representation f(θ)=⟨bθ,bf*(θ)⟩, the explicit adjoint computations for single-index and ReLU models, and the reproducible empirical illustrations are genuine strengths. However, the advertised neural-network guarantee rests on a score-domination argument that fails for inactive ReLU units, and the proof of Theorem 3.1 has a union-bound gap at θ*. For generalized linear predictors under the stated bounded-ratio assumptions, the framework is plausible, but the paper overclaims its scope.","major_comments":[{"comment":"The derivation of β=min{c1l,1}/max{c2u,1} for ReLU networks is invalid for data rows with no active hidden unit. In Appendix A.2 the sentence 'as otherwise f*_i(θ)=0' is used to justify the uniform lower bound c1l‖x_i‖²≤‖f*_i(θ)‖², but a row with no active unit contributes zero to the denominator Σ_i‖bf*_i(θ)‖², so the denominator lower bound used in the score bound fails. Concretely, take m=1, φ(t)=t, θ=(a,b)=(1,1), C defined by a²≥1 and a²+b²≤2, and data with 20% of the x_i satisfying ⟨b,x_i⟩>0 and 80% satisfying ⟨b,x_i⟩≤0. For each active row, τ_i(θ)/τ_i=5, while 1/β=2, so βτ_i(θ)≤τ_i fails on C. Theorem 3.1 therefore cannot be invoked for the stated ReLU-NN example unless an additional assumption guarantees that every data point has at least one active hidden unit for all θ∈C and the active fraction is accounted for in β.","section":"Section 3.3.1, Example 3.4 / Appendix A.2"},{"comment":"The union-bound argument covers the ε-net N_ε, but the final step 'Combining this with (11)' requires the embedding inequality LS(θ*)≤(1+ε)L(θ*) at the true optimum θ*, which is not a net point. The proof as written does not establish (10) at θ*. This is repairable by adding θ* to N_ε or by deriving a Lipschitz-perturbed version of (11), but as written the proof of Theorem 3.1 is incomplete.","section":"Section 3.3.2 / proof of Theorem 3.1"},{"comment":"The theorem statement omits the Lipschitz constant L(f,X,R) introduced in Section 3.3.2, although the proof's additive error is ε/(1−ε)(L(θ*)+(2−ε)R·L(f,X,R)). Since R is chosen 'large enough' and L depends on f, X, and R, the guarantee (2) is meaningful only after fixing these quantities. The authors should either state explicit hypotheses under which R·L(f,X,R) is bounded in the relevant asymptotic regime or define the O(ε) term with the dependence on these constants made explicit.","section":"Theorem 3.1 / Section 3.3.2"}],"minor_comments":[{"comment":"The displayed inequality uses a constant c1 that has not been defined; from the context the intended constant is l, i.e., the factor should be 1/l rather than 1/c1.","section":"Section 3.3.1, Example 3.3"},{"comment":"The definition of the admissible set C is inconsistent between the main text, which has min_j(a_j)²≥l, and Appendix A.2, which appears to have min_j(a*_j)²≥l; please make the intended condition clear.","section":"Example 3.4 / Appendix A.2"},{"comment":"The classification experiments use BCE loss and a sigmoid output, while Theorem 3.1 covers squared loss and Appendix A.3 requires positively homogeneous f. The paper should state explicitly that the classification results are empirical and are not covered by Theorem 3.1.","section":"Section 4 / Appendix A.3"},{"comment":"The change of variables t=(s/h(θ))^{1/α} is written assuming h(θ)>0; for h(θ)<0, the signed substitution and integral orientation need care. Because the single-index and ReLU examples allow negative values of the relevant homogeneous function, a sentence handling the sign of h(θ) would make the proof complete.","section":"Appendix A.1, proof of Proposition 3.1"},{"comment":"The nonlinear leverage score is undefined when bF*(θ) has rank zero or when the pseudoinverse projection vanishes; the paper should state the nondegeneracy assumptions under which these scores are well defined and sum to one.","section":"Definition 3.3"}],"recommendation":"major_revision","confidential_remarks":"The advertised neural-network guarantee is the main selling point of the paper, and the current invalidity of Example 3.4's domination condition is substantial. I do not see a novelty or citation concern; the route to a publishable revision is to repair the score-domination assumptions, close the θ* gap in the union bound, and re-state the theorem with explicit constants. If the NN claim cannot be repaired, the authors should limit their theoretical claims to the generalized-linear/single-index setting for which the assumptions are satisfiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the adjoint-operator representation is a genuinely useful new way to think about importance sampling for nonlinear losses, and the fixed-theta analysis is correct. But the paper's headline claim—that the sampling scores give approximation guarantees for neural networks—does not survive contact with the proof of Example 3.4. The main theorem is not supported for ReLU networks as stated.\n\nWhat is actually new: the identity f(theta) = <btheta, bf*(theta)> with f* defined as a ray integral is clean, gives the nonlinear dual matrix, and yields natural generalizations of leverage and norm scores. For a fixed theta, the subspace embedding argument is standard RandNLA and goes through. Example 3.3's analysis for generalized linear predictors under a bounded-ratio activation condition, with beta = l/u and C = 1, is a real improvement over the C >> 1 guarantees of Gajjar et al., though the dimension dependence is quadratic rather than linear. That part is worth taking seriously.\n\nThe soft spots are concentrated in the parameter-independent step. Example 3.4 claims a uniform domination bound for ReLU networks, but the bound is false. The proof's lower bound c1 l ||x_i||^2 <= ||f*_i(theta)||^2 requires at least one active hidden unit per data point. When some rows have zero active units, the denominator ||bF*(theta)||_F^2 sums over the active rows only, and any active row's nonlinear score is inflated relative to the linear baseline. A concrete calculation confirms it: with m=1, phi(z)=z, theta=(1,1), and 20% positive x_i, the nonlinear norm score for an active row is 5x the linear score, while the claimed beta gives 1/beta = 2. So the domination does not hold on C, and Theorem 3.1 cannot be invoked for the ReLU networks in the experiments. This is not a bounded-ratio technicality; it is structural to activations with dead units.\n\nThere is also a separate gap in the epsilon-net argument: inequality (11) needs the subspace embedding at theta*, but the union bound only covers net points. The fix is easy—add theta* to the net or run a Lipschitz comparison—but it adds an explicit O(epsilon R L(f,X,R)) term, and L(f,X,R) is never quantified. That is a minor issue in the sense that it is patchable, but the theorem currently hides it.\n\nThe experiments are oracle-style: scores are computed at the trained optimum, not via the parameter-independent estimates the theory needs. The regression experiments use a Swish-type activation with c1 > 0, so they are not evidence for the ReLU case.\n\nWho this is for: people working on randomized sampling for nonlinear training will want to see the adjoint representation even if they distrust the NN claim. I would send this to peer review, but with a clear instruction that the NN guarantee must be either fixed or removed, and the Lipschitz dependence made explicit.","headline":"The adjoint-based framework for nonlinear importance sampling is clean and worth knowing, but the neural-network guarantee collapses on Example 3.4's score-domination bound, and the main proof needs a patch around theta*.","tokens_in":20956,"tokens_out":8217,"would_cite":false,"duration_ms":72417,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Sampling by nonlinear adjoint-based scores gives nonlinear models the same additive loss guarantee as linear subspace embeddings, with no large multiplicative constant.","keywords":["importance sampling","nonlinear adjoint operator","leverage scores","randomized numerical linear algebra","nonlinear least squares","subspace embedding","sample complexity","outlier detection"],"falsifier":"Take a small synthetic single-index model with a Swish-type activation where the constants $l,u$ (hence $\\beta=l/u$) are known, sample by the linear leverage scores exactly at the sample size prescribed in Theorem 3.1, and estimate the probability that $L(\\theta^\\star_S)>L(\\theta^\\star)+O(\\varepsilon)$; if that probability exceeds $\\delta$, or if the excess loss does not decrease like $O(\\varepsilon)$ while $L(f,X,R)$ is held fixed, the $\\varepsilon$-net/Lipschitz step hides more than the stated guarantee.","tokens_in":19729,"feed_emoji":"🎯","tokens_out":11072,"duration_ms":103956,"temperature":0.7,"pith_summary":"Importance sampling—picking which data points to train on—has a rigorous theory for linear models, where row norms and leverage scores tell you which rows matter and subspace embeddings guarantee that a small sampled matrix behaves like the full one. This paper builds the same theory for nonlinear models. Its central device is the nonlinear adjoint operator, $f^\\star(\\theta)=\\int_0^1 \\partial_\\theta f(t\\theta)\\,dt$, which rewrites any absolutely continuous map as $f(\\theta)=\\langle \\hat\\theta, \\hat f^\\star(\\theta)\\rangle$, turning a nonlinear least-squares loss into a matrix norm $\\| \\widehat{F^\\star}(\\theta)\\hat\\theta\\|^2$. That single rewrite makes leverage scores and norm scores definable for nonlinear models, and the paper proves Theorem 3.1: if a parameter-free score dominates the nonlinear score by a constant $\\beta$ on a set containing the optimum, sampling $s=O\\!\\big((p\\log(p/\\delta)+p^2\\log(p/\\varepsilon))/(\\beta\\varepsilon^2)\\big)$ points gives a solution whose full-data loss is at most $L(\\theta^\\star)+O(\\varepsilon)$, with probability at least $1-\\delta$. The guarantee is additive, with no large multiplicative constant, unlike prior single-neuron sampling results.","feed_headline":"Nonlinear leverage scores match linear sampling guarantees","feed_subtitle":"An adjoint-operator rewrite turns nonlinear losses into matrix norms, so fewer samples keep the optimum to O(ε).","key_machinery":"The central object is the nonlinear adjoint operator of a map, $f^\\star(\\theta)=\\int_0^1 \\frac{\\partial}{\\partial\\theta}f(t\\theta)\\,dt$, which makes the map writable as an inner product $f(\\theta)=\\langle\\hat\\theta,\\hat f^\\star(\\theta)\\rangle$. Stacking these rows gives the nonlinear dual matrix $\\widehat{F^\\star}(\\theta)$, so the nonlinear least-squares objective becomes $\\|\\widehat{F^\\star}(\\theta)\\hat\\theta\\|^2$ and the standard linear tools—subspace embeddings, leverage scores, norm scores—apply pointwise in $\\theta$. Proposition 3.1 computes the adjoint explicitly when the map is $g\\circ h$ with $h$ positively homogeneous, which covers generalized linear predictors and ReLU networks. The bounded-ratio condition $\\beta \\tau_i(\\theta)\\le \\tau_i$ is what upgrades these pointwise guarantees to a uniform, parameter-independent sampling probability; the $\\varepsilon$-net and the Lipschitz continuity of the sampled loss are what convert the pointwise embedding into the final additive bound on $L(\\theta^\\star_S)$.","core_discovery":"The paper claims that the familiar linear machinery of importance sampling extends to nonlinear maps $f_i:\\mathbb{R}^p\\to\\mathbb{R}$ once each map is written through the adjoint representation $f_i(\\theta)=\\langle \\hat\\theta,\\hat f_i^\\star(\\theta)\\rangle$, with $\\hat f_i^\\star(\\theta)=[f_i^\\star(\\theta); f_i(0)]$ and $\\hat\\theta=[\\theta;1]$. The adjoint $f_i^\\star(\\theta)=\\int_0^1 \\partial_\\theta f_i(t\\theta)\\,dt$ is the parameter-average of the gradient along the ray from $0$ to $\\theta$. For positively homogeneous inner functions (single-index models, ReLU and multi-neuron networks), the adjoint has a closed form. Defining nonlinear leverage and norm scores as the row scores of the dual matrix $\\widehat{F^\\star}(\\theta)$, and sampling rows with those probabilities, gives for every fixed $\\theta$ the usual subspace-embedding guarantee $(1-\\varepsilon)L(\\theta)\\le L_S(\\theta)\\le(1+\\varepsilon)L(\\theta)$. The paper then shows how to make the scores parameter-free: if the activation obeys a uniform bounded-ratio condition—$l\\le\\phi^2(t)/t^2\\le u$ for single-index models, $c_1\\le(\\phi(t)-\\phi(0))^2/t^2\\le c_2$ plus bounds on the parameter set for networks—then linear scores dominate the nonlinear scores on a set $C$ containing the optimum, with $\\beta=l/u$ or $\\beta=\\min\\{c_1l,1\\}/\\max\\{c_2u,1\\}$. With an $\\varepsilon$-net and a Lipschitz-continuity control on the sampled loss, the paper proves the main theorem: sampling $s$ points by the parameter-free scores yields $L(\\theta^\\star_S)\\le L(\\theta^\\star)+O(\\varepsilon)$ with high probability. The same scores are then demonstrated as a sampling rule that lowers training cost on regressions and as a diagnostic that surfaces mislabeled or hard images in classification tasks.","pith_inferences":["The adjoint representation suggests a general recipe: any nonlinear map with a computable integral-of-gradient could inherit importance scores without going through the specific single-index or ReLU examples worked out here; a natural extension is to residual networks or kernel feature maps with homogeneous building blocks.","If the bounded-ratio condition can be relaxed to hold only on the data manifold rather than the full parameter ball, the same machinery might reach deep ReLU networks, where $\\phi^2(t)/t^2=0$ on the negative half-line currently excludes them from the theorem.","The $\\varepsilon$-net step introduces the $p^2\\log(p/\\varepsilon)$ term and an unquantified Lipschitz constant; replacing the net with chaining or metric-entropy arguments could plausibly recover the linear-in-$p$ sample complexity, bringing nonlinear sampling in line with the linear benchmark."],"forward_implications":["Training on $s=O((p\\log(p/\\delta)+p^2\\log(p/\\varepsilon))/(\\beta\\varepsilon^2))$ sampled points yields a model whose full-data squared loss is within $O(\\varepsilon)$ of the optimum, with probability at least $1-\\delta$.","The same nonlinear leverage and norm scores can cut training cost on large nonlinear datasets while preserving near-optimal loss, since sampling now comes with the same theoretical backing that linear subspace embeddings provide.","In classification experiments, the scores surface the most informative and hardest examples: mislabeled and noisy images receive the highest nonlinear leverage scores, offering a post-hoc diagnostic for outlier detection and model explainability.","The scoring step is parameter-free: under the $\\beta$-ratio condition, the sampling distribution is fixed ahead of time, so the chicken-and-egg coupling between sampling and estimation is reduced to a constrained optimization over a set $C$ that contains the optimum."],"supporting_citations":[{"why":"Supplies the subspace-embedding and approximate-matrix-multiplication guarantees that give the pointwise (1±ε) norm preservation for the dual matrix.","marker":"Woodruff et al. (2014)"},{"why":"Provides the modern framework and sample-size bounds for leverage-score and row-norm sampling that the paper adapts to the nonlinear dual matrix.","marker":"Martinsson & Tropp (2020)"},{"why":"Establishes the importance-sampling and score-approximation arguments used to show that sampling with near-optimal probabilities only costs a β factor.","marker":"Drineas & Mahoney (2018)"},{"why":"The prior single-index sampling result with linear sample complexity but a large constant C; Theorem 3.1 is explicitly positioned as achieving C=1 with quadratic dimension dependence.","marker":"Gajjar et al. (2024)"},{"why":"The earlier Lipschitz single-neuron active-learning analysis that the paper compares against and improves in Remark 3.3.","marker":"Gajjar et al. (2023)"},{"why":"The source for ε-net construction, covering-number bounds, and the union-bound argument used to make the embedding uniform over the parameter set in Theorem 3.1.","marker":"Vershynin (2018)"}],"fun_headline_variants":["Leverage scores go nonlinear with matching guarantees","Sampling nonlinear models: adjoint-based scores hit linear-grade bounds","Adjoint operator generalizes importance sampling to nonlinear maps","Nonlinear leverage scores: beyond linearity, same sampling guarantees","A linear-style sampling bound for any nonlinear model via adjoint scores"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The activation's ratio $\\phi(t)^2/t^2$ must stay between two fixed positive constants over all inputs the model can produce on the relevant parameter set, so a parameter-independent score can bound the true nonlinear score on all of $C$.","fun_headline_variants_meta":{"raw":{"variants":["Leverage scores go nonlinear with matching guarantees","Sampling nonlinear models: adjoint-based scores hit linear-grade bounds","Adjoint operator generalizes importance sampling to nonlinear maps","Nonlinear leverage scores: beyond linearity, same sampling guarantees","A linear-style sampling bound for any nonlinear model via adjoint scores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000462,"raw_usage":{"total_tokens":2390,"prompt_tokens":1102,"completion_tokens":1288,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":1205}},"tokens_in":718,"tokens_out":1288,"duration_ms":10430,"temperature":1.0,"reasoning_tokens":1205,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:35:41.019949+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small synthetic single-index model with a Swish-type activation where the constants $l,u$ (hence $\\beta=l/u$) are known, sample by the linear leverage scores exactly at the sample size prescribed in Theorem 3.1, and estimate the probability that $L(\\theta^\\star_S)>L(\\theta^\\star)+O(\\varepsilon)$; if that probability exceeds $\\delta$, or if the excess loss does not decrease like $O(\\varepsilon)$ while $L(f,X,R)$ is held fixed, the $\\varepsilon$-net/Lipschitz step hides more than the stated guarantee.","supporting_citations":[{"cited_title":"and Mahoney, M","cited_arxiv_id":null,"evidence_quote":"Establishes the importance-sampling and score-approximation arguments used to show that sampling with near-optimal probabilities only costs a β factor."},{"cited_title":"M., Xingyu, X., Hegde, C., Musco, C., and Li, Y","cited_arxiv_id":null,"evidence_quote":"The prior single-index sampling result with linear sample complexity but a large constant C; Theorem 3.1 is explicitly positioned as achieving C=1 with quadratic dimension dependence."},{"cited_title":"Active learning for single neuron models with lipschitz non-linearities","cited_arxiv_id":null,"evidence_quote":"The earlier Lipschitz single-neuron active-learning analysis that the paper compares against and improves in Remark 3.3."}],"review_version":1}