{"id":"cdae3422-f56d-473a-b1ff-8f5fe6e422a2","arxiv_id":"2608.01287","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For unknown 1-Lipschitz link functions, non-adaptive Lewis-weight sampling solves ℓ_p single-index active regression to (1+ε) accuracy with nearly the same query complexity as the known-link case.","lead":"An active-learning algorithm for single-index regression with an unknown 1-Lipschitz link function achieves a (1+ε)-approximation for all p≥1 using O(d^{p/2∨1}/ε^{p∨2} polylog n) label queries. The paper also proves a near-tight lower bound for p>2, closing much of the gap in active ℓ_p regression.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Symmetrization step in the upper-bound proof drops a factor 1/\\alpha on the base-point term; if not corrected, Lemma E.1 and Theorem 3.2's query bound do not follow as written.","rationale":"The reader's weakest assumption (Theorem D.1) is a reasonable place to ask for expansion, but the covering implication can be completed by the standard two-step-net argument once the bi-Lipschitz inequality \\|f-h\\| \\le ML\\|T_f/L - T_h/L\\|_\\infty is written out; the missing factor of 2 does not change the order of the entropy bound. The more serious, concrete issue is the symmetrization identity in Eq. (16). The displayed expression is not what results from applying symmetrization to Eq. (15), and the discrepancy is a factor 1/\\alpha, which is polynomial in n/\\epsilon. Because Lemma E.1 feeds directly into the mixed-error guarantee, the proof as written does not yet establish the advertised query complexity. The issue is fixable, either by correcting the factor or by bounding the base-point term, so conditional acceptance is appropriate rather than rejection. This differs from the reader's weakest assumption, so agreement is partial.","tokens_in":27136,"tokens_out":48510,"duration_ms":429185,"concrete_test":"Independently re-derive Eq. (16) from Eq. (15) by substituting S_ii^p = 1/\\alpha for i in I. If the corrected second inner product carries the factor 1/\\alpha, re-run the argument of (17) and Lemma E.1: check whether Psi_3 gains a factor 1/\\alpha relative to the stated \\Gamma-bound, and whether any existing \\alpha-dependence in \\Gamma absorbs it. If it does not, Theorem 3.2's query complexity must be revised; if the authors intend the displayed (16), prove a separate bound on \\langle \\xi_I, Z_I(\\bar f,\\bar x)\\rangle with the required \\alpha-scaling.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of the upper bound has a concrete algebraic error at the symmetrization step. In Eq. (15), the Rademacher summand for each sampled coordinate i in I is S_ii^p (Z_i(f,x)-Z_i(\\bar f,\\bar x)). Since S_ii^p = 1/\\alpha on I, this is (1/\\alpha)(Z_i(f,x)-Z_i(\\bar f,\\bar x)), so the symmetrized expression in Eq. (16) should read (1/\\alpha)\\langle \\xi_I, Z_I(f,x)\\rangle - (1/\\alpha)\\langle \\xi_I, Z_I(\\bar f,\\bar x)\\rangle. The displayed Eq. (16) omits the factor 1/\\alpha on the base-point inner product. The subsequent Dudley bound in Eq. (17) is applied to a process centered at Z_I(\\bar f,\\bar x) without this scaling. If (16) is used literally, the process being bounded is not the one that controls Psi_3; if the missing factor is restored, the right-hand side of (17) gains a factor 1/\\alpha, turning the Psi_3 bound in Lemma E.1 into O((1/\\alpha)\\Gamma\\operatorname{polylog}(n/\\epsilon)). This would destroy the claimed O(d^{1\\vee p/2}/\\epsilon^{p\\vee 2}\\operatorname{polylog}n) query bound unless an additional argument shows the base-point term is O(\\alpha\\Gamma\\operatorname{polylog}). The paper does not supply such an argument. This is the most load-bearing gap because Lemma E.1 is the core of Theorem 3.1 and hence of Theorem 3.2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies active regression for single-index models of the form min_{f in Lip1, x in R^d} ||f(Ax)-b||_p^p, where A is fully known but b is accessible only through coordinate queries and the link function f is unknown and 1-Lipschitz. The main upper bound (Theorem 3.2) claims a non-adaptive Lewis-weight sampling algorithm returning (f_hat, x_hat) with the mixed-error guarantee ||f_hat(A x_hat)-b||_p^p <= (1+epsilon)||f*(A x*)-b||_p^p + epsilon||A x*||_p^p using O(d^{1 v p/2}/epsilon^{p v 2} poly log n) queries, for every constant p >= 1. The proof proceeds through a uniform-convergence bound over a set T of pairs (f,x), using symmetrization, a Dudley integral, and a new covering-number estimate for Lip1 under a supremum of weighted L-infinity norms (Theorem D.1). A separate argument handles p = 1, where the entropy integral diverges. The paper also proves a lower bound for p > 2 with a known link function f(t) = t_+, based on a spherical-code construction and Yao's principle, giving Omega_p(d^{p/2}/(epsilon^p (log(d/epsilon))^{p/2})) queries. The lower-bound part is presented in substantial detail, while the upper-bound proof has several points that need repair before the claimed theorem can be verified as written.","tokens_in":27474,"tokens_out":14755,"duration_ms":132915,"significance":"If the main upper bound is correct, it closes a significant gap: previous work for unknown link functions treated only p = 2 and achieved only a constant-factor approximation, whereas the present claim matches the known-link case up to logarithmic factors for all p >= 1. The companion lower bound for p > 2 also strengthens the known tightness results. The paper's modular structure is a strength: it cleanly separates the R^d component of the Dudley integral, already handled by Li and Tai, from the new Lip1 component, and it provides a separate treatment of p = 1. The new metric-entropy lemma for Lip1 under weighted sup-norms is a potentially reusable ingredient. However, the upper-bound proof as printed contains an algebraic error in the symmetrization display and an under-specified covering-number implication in the key entropy lemma; the algorithm also assumes exact solution of a non-convex infinite-dimensional optimization problem. These are local and plausibly fixable, but they are load-bearing for Theorem 3.2, so the manuscript should not appear in its current form.","major_comments":[{"comment":"Equation (16) is algebraically incorrect. Since S_ii^p = 1/alpha on the set I, the symmetrized expression must read (1/alpha)<xi_I, Z_I(f,x)> - (1/alpha)<xi_I, Z_I(f_bar, x_bar)> = (1/alpha)<xi_I, Z_I(f,x)-Z_I(f_bar,x_bar)>. As printed, the second inner product lacks the factor 1/alpha, and Eq. (17) then bounds an expression from which the factor 1/alpha has been dropped entirely. If the factor is restored, Eq. (17) must carry a factor 1/alpha; this factor combines with the factor alpha that appears in the Dudley-integral bound (23) to give the stated Gamma polylog bound in Lemma E.1. The final bound is therefore consistent with the repaired chain, but the displayed proof as written does not follow, and this is a load-bearing step for Theorem 3.1 and hence Theorem 3.2.","section":"Section B, Eqs. (15)-(17)"},{"comment":"The final covering-number implication in Theorem D.1 is not demonstrated. The proof constructs a map T_f, shows that T_f is L-Lipschitz for L = 2(ln kappa + 1), and proves ||f|| <= ML ||T_f||_inf. The text then asserts that this implies N(Lip1, ||.||, epsilon) <= N(Lip1, ||.||_Linf, epsilon/(2M(ln kappa + 1))). To justify this implication one needs a construction that lifts an epsilon/(2M(ln kappa+1))-net of (Lip1, ||.||_Linf) to an epsilon-net of (Lip1, ||.||); the inverse of the map T_f or a Lipschitz extension argument is required, and none is given. Since Lemma D.3 and Corollary D.4 use exactly this statement to bound the pi_1(T) Dudley integral, the proof of Lemma E.1 is incomplete at this point. This is likely repairable by a standard extension argument, but it must be written out explicitly.","section":"Appendix D, Theorem D.1"},{"comment":"The algorithm requires an exact minimizer of min_{f in Lip1, x in R^d} ||S Lambda(f(Ax)-b)||_p^p + epsilon ||Lambda A x||_p^p. This is an infinite-dimensional and generically non-convex optimization problem, and the paper does not state an oracle, a discretization, or any computational procedure for it. The query-complexity theorems are therefore conditional on an unspecified subroutine. The authors should either state this as an explicit oracle assumption, as is sometimes done in the active-learning literature, or provide an argument that the sketched problem can be solved, at least approximately, within the claimed query model.","section":"Algorithm 2, line 6"}],"minor_comments":[{"comment":"The algebraic identity in the proof of the Lipschitz estimate for T_f, displayed around the sentence 'Note that kappa^{(x-beta)/(1-beta)} = ...', appears garbled; the exponents and the appearance of e are not explained. Since this estimate feeds the constant L in the covering lemma, the derivation should be written cleanly.","section":"Appendix D, proof of Theorem D.1"},{"comment":"The definitions of M and kappa in the first line of the proof are inconsistent with those in Theorem D.1 and Lemma D.3. The text writes M := phi R^{1/p} = (d/n)^{1/p} ... and kappa := R^{1/p}/M, but Theorem D.1 defines M = max_i lambda_i M_i and kappa = (max_i M_i)/M. Please align the notation.","section":"Section E, proof of Lemma E.1"},{"comment":"The Rademacher vector xi is introduced with the same dimension as J, but in Eq. (16) it is indexed by I. It would be clearer to define xi on all of J and set unused coordinates to zero, or to enlarge I to J with the convention that xi_i is multiplied by S_ii^p, which vanishes outside I.","section":"Section B, Eq. (15)"},{"comment":"The theorem conditions on an event involving S but does not give a lower bound on the probability of that event. Since the theorem is stated as a conditional statement, the authors should either bound the probability of the conditioning event or explicitly say that the unconditional statement follows by combining the theorem with Corollaries E.2 and E.3.","section":"Theorem 3.1"},{"comment":"The recursion for X_i and Y_i is asserted with the formula X_i = C_5^{(1-(1-theta)^i)/theta} (100/epsilon)^{(1-theta)^i}, but the displayed expression appears to have an exponent issue when theta is not 1; please verify and write the induction in full.","section":"Section F, bootstrapping step"}],"recommendation":"major_revision","confidential_remarks":"The paper's central claims are plausible and significant, and the lower-bound part is quite carefully written. The upper-bound proof has at least two load-bearing gaps that are local and likely fixable: the symmetrization algebra in Eqs. (15)-(17) and the missing lifting argument in Theorem D.1. The Oracle issue in Algorithm 2 also needs to be stated clearly. I would not reject, but the revision must contain a repaired, self-contained upper-bound proof before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper actually delivers what it advertises: the first (1+ε)-approximation for active ℓ_p single-index regression with unknown 1-Lipschitz links for all p≥1, with query complexity only polylog n larger than the known-link case, and a new lower bound for p>2 that closes the known-link gap. Second, the stress-test note about Eq (16) is pointing at a real typo but overstates the consequence. The missing 1/α on the base-point term should be there; once restored, the process metric scales by 1/α, and the Dudley integral picks up a compensating factor that cancels the α already in Lemma C.3 and Corollary D.4. I checked this explicitly: (1/α) times the αΓ from the entropy estimates gives Γ, so the final query bound stands. The displayed equation is wrong; the conclusion isn't.\n\nThe genuinely new ingredient is the entropy bound for Lip1 under a max of weighted sup-norms (Theorem D.1). The covering-number step is compressed, and I initially shared the reader's worry: ∥f∥≤M∥T_f∥∞ alone does not give a covering-number bound unless the map has a Lipschitz inverse. But T_f is linear in f, so the inequality applies to f−g, and then the pullback argument works. The authors should spell that out.\n\nThe other soft spot is Algorithm 2: it assumes an exact solution to a non-convex, infinite-dimensional minimization problem. That is typical for this area, but a serious referee should ask them to state the solver oracle explicitly.\n\nThe lower bound is clean, the hard instance is easy to follow, and it completes the known-link p>2 story. The p=1 case is handled separately with a truncation argument, which looks credible.\n\nThis paper is for people in active learning, randomized linear algebra, and single-index models. It deserves a serious referee. I would accept with requests to fix the typo, expand the covering argument, and state the solver assumption. Not a reject.","headline":"Genuinely new results that resolve the open problems in active unknown-link single-index regression; the flagged symmetrization gap is a typo that cancels out, so the paper deserves a serious referee.","tokens_in":28046,"tokens_out":12391,"would_cite":true,"duration_ms":98309,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An unknown 1-Lipschitz link function can be fit to (1+ε) accuracy with roughly as many queries as a known link, for every $p\\ge 1$.","keywords":["active regression","single-index model","unknown link function","Lewis weights","ℓ_p regression","query complexity","covering number","Lipschitz functions"],"falsifier":"Work out the covering-number inequality in Theorem D.1 for the two-interval case $M_1=1$, $M_2=10^4$, weights $\\lambda_1=\\lambda_2=1/2$, and $\\epsilon=10^{-3}$: compute the true covering number of $\\operatorname{Lip}_1$ under $\\|f\\|=\\max\\{\\tfrac12\\|f\\|_{L_\\infty([-1,1])},\\tfrac12\\|f\\|_{L_\\infty([-10^4,10^4])}\\}$ and compare it with $N(\\operatorname{Lip}_1,\\|\\cdot\\|_{L_\\infty([-1,1])},\\epsilon/(C M\\ln\\kappa))$. If the measured covering number exceeds the predicted bound by more than a constant factor, the entropy step behind Theorem 3.2 collapses; a finite-net calculation on a grid is enough to decide this.","tokens_in":26950,"feed_emoji":"📉","tokens_out":18589,"duration_ms":168557,"temperature":0.7,"pith_summary":"This paper studies active regression for single-index models: the response vector is $b = f(Ax)$ (or near it) for an unknown 1-Lipschitz link $f$, and an algorithm may read all of $A$ but only a few coordinates of $b$. The authors establish that a non-adaptive sampling scheme based on Lewis weights returns a pair $(\\hat f,\\hat x)$ achieving the mixed guarantee $\\|\\hat f(A\\hat x)-b\\|_p^p \\le (1+\\epsilon)\\|f_*(Ax_*)-b\\|_p^p + \\epsilon\\|Ax_*\\|_p^p$ using $O(d^{1\\vee p/2}/\\epsilon^{p\\vee 2}\\operatorname{poly}\\log n)$ queries, for every constant $p\\ge 1$. This is the first $\\epsilon$-approximation for unknown Lipschitz links beyond the $p=2$ case, and it shows that an unknown link costs only polylogarithmically more queries than a known one. For $p>2$ the paper proves a matching lower bound up to log factors for the known-link version, so the remaining gap in active $\\ell_p$ single-index regression is only logarithmic.","feed_headline":"Unknown link functions no longer block (1+ε) ℓ_p regression","feed_subtitle":"Lewis-weight sampling matches known-link query costs up to log factors for every p ≥ 1.","key_machinery":"The load-bearing object is a covering-number lemma for the class $\\operatorname{Lip}_1$ of 1-Lipschitz functions with $f(0)=0$ (Theorem D.1). It considers a norm made from a weighted maximum of sup-norms over intervals, $\\|f\\|=\\max_i \\lambda_i\\|f\\|_{L_\\infty([-M_i,M_i])}$, and asserts $N(\\operatorname{Lip}_1,\\|\\cdot\\|,\\epsilon)\\le N(\\operatorname{Lip}_1,\\|\\cdot\\|_{L_\\infty([-1,1])},\\epsilon/(C M\\ln\\kappa))$, where $M=\\max_i\\lambda_i M_i$ and $\\kappa=(\\max_i M_i)/M$. This converts the entropy of the link-function class under a family of nonstandard norms into the standard sup-norm entropy on $[-1,1]$, whose $O(1/\\delta)$ bound feeds Dudley's integral. The proof constructs a nonlinear map $T_f$ that stretches intervals exponentially and is $O(\\ln\\kappa)$-Lipschitz; the remainder of the argument—Lewis-weight splitting, the three-way decomposition of the sampling error, symmetrization, chaining, and bootstrap—is organized around this entropy estimate.","core_discovery":"Put on the paper's own terms, the central claim is Theorem 3.2: for constant $p\\ge 1$, $A\\in\\mathbb{R}^{n\\times d}$, $b\\in\\mathbb{R}^n$, and small $\\epsilon>0$, with probability at least $0.9$ the algorithm makes $O(d^{1\\vee p/2}/\\epsilon^{p\\vee 2}\\operatorname{poly}\\log n)$ non-adaptive coordinate queries and returns $(\\hat f,\\hat x)\\in\\operatorname{Lip}_1\\times\\mathbb{R}^d$ with $\\|\\hat f(A\\hat x)-b\\|_p^p \\le (1+\\epsilon)\\|f_*(Ax_*)-b\\|_p^p + \\epsilon\\|Ax_*\\|_p^p$, where $(f_*,x_*)$ is an optimal pair and the additive term is shown to be unavoidable for coordinate-query algorithms. The algorithm is the known-link template: Lewis-weight sampling of $A$ determines which coordinates of $b$ to read, and the sketched problem is then minimized over both $x$ and the link $f$. The paper's contribution is the analysis, which controls a uniform sampling error over the coupled set of pairs $(f,x)$ through a new covering-number estimate for $\\operatorname{Lip}_1$ under a supremum of weighted $L_\\infty$ norms, plus a bootstrapping argument that upgrades a constant factor to $(1+\\epsilon)$. The companion lower bound, Theorem 4.2, shows that for $p>2$ in the regime $d\\gtrsim p\\log(d/\\epsilon)$, any algorithm with the same guarantee and success probability $4/5$ must make $\\Omega_p\\bigl(d^{p/2}/(\\epsilon^p(\\log(d/\\epsilon))^{p/2})\\bigr)$ queries even adaptively, nearly matching the known upper bound for a known link.","pith_inferences":["The covering-number lemma for $\\operatorname{Lip}_1$ under weighted sup-norms is a transferable tool: any Rademacher or Dudley argument that must control a Lipschitz function class through nonstandard sup-norms could reuse it, for instance in nonparametric active regression with a Lipschitz mean response.","The algorithm's non-adaptivity is stronger than the worst-case guarantee requires; if the entropy step is correct, similar rates should hold for link classes that admit the same kind of covering bound.","The lower-bound construction plants a coordinate among nearly orthogonal rows with a ReLU link; a plausible next step is to adapt the same planted-coordinate instance to the unknown-link case, which this paper leaves open, since the hard part is locating the planted coordinate regardless of whether $f$ is known.","A testable practical consequence: on design matrices with approximately uniform Lewis weights, the number of labels needed for a $(1+\\epsilon)$ fit should be essentially independent of $n$, scaling only with $d$ and $\\epsilon$; if experiments instead show a polynomial dependence on $n$, the metric-entropy estimate in Theorem D.1 is the first place to look."],"forward_implications":["For every constant $p\\ge 1$, fitting an unknown 1-Lipschitz nonlinearity to $b$ costs at most $\\widetilde O(d^{1\\vee p/2}/\\epsilon^{p\\vee 2})$ coordinate queries, roughly the same as a known-link model up to polylog factors.","For $p>2$ in large dimension, the $\\epsilon^{-p}$ dependence of the query count is unavoidable: the new lower bound matches the known-link upper bound up to logs, so that problem is essentially settled.","Because the algorithm is non-adaptive, all query indices can be chosen before seeing any labels, which makes the bound applicable to batch data-collection settings.","The analysis permits the link class to be any subset of $\\operatorname{Lip}_1$; restricting $f$ with extra structure does not increase the query count.","Combined with earlier lower bounds for $p\\le 2$, the paper completes a near-tight description of active $\\ell_p$ single-index regression in the known-link case across all $p\\ge 1$."],"supporting_citations":[{"why":"Supplies the active-regression template, the known-link upper bound, the bootstrapping argument, and the $\\pi_2(T)$ entropy estimate that this paper extends to unknown links.","marker":"[8]"},{"why":"Provides the earlier $p=2$ unknown-link constant-factor result and the symmetrization-and-chaining approach over the link function that is generalized here.","marker":"[4]"},{"why":"Establishes $\\ell_p$ Lewis-weight row sampling, the sampling distribution on which the algorithm builds.","marker":"[3]"},{"why":"Supplies the standard metric entropy bound for Lipschitz functions in the sup norm used in Lemma D.2.","marker":"[11]"},{"why":"Provides the chaining and Dudley integral bound for subgaussian processes used to control the Rademacher process.","marker":"[12]"},{"why":"Supplies the binomial moment bound used in the $p=1$ truncation argument.","marker":"[1]"}],"fun_headline_variants":["Unknown links? Active ℓ_p regression still hits (1+ε)","Non-adaptive queries crack unknown-link ℓ_p regression","Tight bounds for active ℓ_p regression with unknown links","Nearly tight query bounds for ℓ_p single-index with unknown link","Active regression: unknown link no barrier for any p ≥ 1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper bound rests on the claim that covering 1-Lipschitz functions under a weighted maximum of sup-norms costs no more, up to a log factor, than covering them under the ordinary uniform norm on $[-1,1]$—and the proof only demonstrates this for single functions, not for the differences of two functions that a covering argument requires.","fun_headline_variants_meta":{"raw":{"variants":["Unknown links? Active ℓ_p regression still hits (1+ε)","Non-adaptive queries crack unknown-link ℓ_p regression","Tight bounds for active ℓ_p regression with unknown links","Nearly tight query bounds for ℓ_p single-index with unknown link","Active regression: unknown link no barrier for any p ≥ 1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001293,"raw_usage":{"total_tokens":5370,"prompt_tokens":1128,"completion_tokens":4242,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":744,"completion_tokens_details":{"reasoning_tokens":4153}},"tokens_in":744,"tokens_out":4242,"duration_ms":26672,"temperature":1.0,"reasoning_tokens":4153,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:10:07.560390+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Work out the covering-number inequality in Theorem D.1 for the two-interval case $M_1=1$, $M_2=10^4$, weights $\\lambda_1=\\lambda_2=1/2$, and $\\epsilon=10^{-3}$: compute the true covering number of $\\operatorname{Lip}_1$ under $\\|f\\|=\\max\\{\\tfrac12\\|f\\|_{L_\\infty([-1,1])},\\tfrac12\\|f\\|_{L_\\infty([-10^4,10^4])}\\}$ and compare it with $N(\\operatorname{Lip}_1,\\|\\cdot\\|_{L_\\infty([-1,1])},\\epsilon/(C M\\ln\\kappa))$. If the measured covering number exceeds the predicted bound by more than a constant factor, the entropy step behind Theorem 3.2 collapses; a finite-net calculation on a grid is enough to decide this.","supporting_citations":[{"cited_title":"Near-optimal active regression of single-index models","cited_arxiv_id":null,"evidence_quote":"Supplies the active-regression template, the known-link upper bound, the bootstrapping argument, and the $\\pi_2(T)$ entropy estimate that this paper extends to unknown links."},{"cited_title":"Gajjar, W.M","cited_arxiv_id":null,"evidence_quote":"Provides the earlier $p=2$ unknown-link constant-factor result and the symmetrization-and-chaining approach over the link function that is generalized here."},{"cited_title":"Cohen and Richard Peng","cited_arxiv_id":null,"evidence_quote":"Establishes $\\ell_p$ Lewis-weight row sampling, the sampling distribution on which the algorithm builds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard metric entropy bound for Lipschitz functions in the sup norm used in Lemma D.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the binomial moment bound used in the $p=1$ truncation argument."}],"review_version":2}