REVIEW 3 major objections 5 minor 16 references
Active Regression for Single-Index Models with Unknown Link Functions
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read 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$.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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$.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section B, Eqs. (15)-(17)] 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.
- [Appendix D, Theorem D.1] 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.
- [Algorithm 2, line 6] 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.
minor comments (5)
- [Appendix D, proof of Theorem D.1] 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 E, proof of Lemma E.1] 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 B, Eq. (15)] 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.
- [Theorem 3.1] 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 F, bootstrapping step] 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.
Circularity Check
No significant circularity: the new upper bound is supported by an independently proved covering lemma and the new lower bound by a new hard instance; self-citations are supporting ingredients, not the target claim.
full rationale
The paper's central claims do not reduce, by construction, to their inputs or to a self-citation chain. The upper bound's new load-bearing ingredient is Theorem D.1, a covering-number estimate for Lip1 under weighted sup-norms, and the proof of that theorem is given in Appendix D rather than assumed or imported. The technique overview explicitly identifies this entropy estimate as the main new challenge: 'controlling the π1(T) component is new to this work and constitutes the main technical challenge.' The algorithm is inherited from prior work, but the proof of the (1+ε) guarantee for unknown link functions requires the new entropy bound, the new process bound in Lemma E.1, and a bootstrapping argument in Theorem F.1; these are not obtained by assuming the theorem being proved. Lemma C.3 is cited from the authors' prior paper [8], but that result concerns the projection π2(T) for the known-link setting and is used as an ingredient inside a larger argument; its statement does not include the unknown-link (1+ε) target result. Under the stated rules, that citation is real evidence and does not raise the circularity score. The lower bound is also new: it uses a ReLU link, a spherical-code hard instance, and the short-list argument of Lemma H.2, with the final query bound obtained by balancing two explicit conditions rather than by renaming a known quantity. The paper does not fit any parameter to b and then predict a related quantity; the algorithm optimizes over all of Lip1 and all x against a sketched objective with a regularizer, and the guarantee is relative to the true optimum. The reader's flagged weakness in Theorem D.1 is a possible gap in justification of a metric mapping property, and the symmetrization algebra concern in Eq. (16) is a correctness matter; neither is a circularity, since no load-bearing step is equivalent to its own input by definition. The paper also openly states a limitation: 'We leave open the question of whether the log n factors can be removed,' which is an honest boundary of the result, not a circular justification. Overall, no circular step meeting the quoted-evidence threshold was found.
Assumptions & free parameters
assumptions (6)
- standard math Lewis weight properties (sum of weights = d, row norm characterization, subspace embedding inequalities) as established in Li-Tai [8, Lemma A.1].
- standard math Existence of a spherical code u_1,...,u_N on S^{d-2} with pairwise coherence ≤τ and log N ≲ τ^2 d.
- standard math Dudley's integral inequality for subgaussian processes, and the truncated variant for p=1.
- standard math Talagrand's entropy bound ln N(Lip1, ||·||_{L∞([-1,1])}, ε) ≲ 1/ε.
- standard math Yao's minimax theorem to reduce randomized lower bound to deterministic under a hard input distribution.
- domain assumption The sketched optimization problem in Algorithm 2, Step 6, is solved exactly, ignoring computational tractability.
Cite this review
Pith. "Pith review of Active Regression for Single-Index Models with Unknown Link Functions." pith.science (2026). https://pith.science/paper/TGZMFK2U
@misc{pith2026260801287,
author = {Pith},
title = {Pith review of: Active Regression for Single-Index Models with Unknown Link Functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/TGZMFK2U}},
note = {Machine review of arXiv:2608.01287}
}
abstract
This paper studies active regression for single-index models under general $\ell_p$-loss with an unknown $1$-Lipschitz link function $f$, formulated as $\min_{f,x} \|f(Ax)-b\|_p^p$ with full access to $A$ but coordinate-query access to $b$. Prior work established upper bounds for known link functions for all $p\geq 1$ and for unknown link functions only in the $p=2$ case, together with lower bounds for $p\leq 2$. This work addresses the more challenging setting of unknown link functions and general $p \geq 1$. A non-adaptive sampling algorithm is presented that achieves a $(1+\epsilon)$-approximation using $O(d^{p/2\vee 1}/\epsilon^{p\vee 2}\operatorname{poly}\log(n/\epsilon))$ queries. Nearly tight lower bounds are also established for $p>2$. These results close much of the remaining gap in active $\ell_p$-regression for single-index models.
Reference graph
Works this paper leans on
-
[1]
Thomas D. Ahle. Sharp and simple bounds for the raw moments of the binomial and poisson distributions.Statistics & Probability Letters, 182:109306, 2022
work page 2022
-
[2]
On computing approximate Lewis weights
Simon Apers, Sander Gribling, and Aaron Sidford. On computing approximate Lewis weights. arXiv:2404.02881 [cs.DS], 2024
arXiv 2024
-
[3]
Michael B. Cohen and Richard Peng. lp row sampling by Lewis weights. InProceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 183–192, New York, NY, USA, 2015. ACM
work page 2015
-
[4]
A. Gajjar, W.M. Tai, X. Xu, C. Hegde, Y. Li, and C. Musco. Agnostic active learning of single index models with linear sample complexity.Conference on Learning Theory, 196:1–40, 2024
work page 2024
-
[5]
Active learning for single neuron models with lipschitz non-linearities, 2023
Aarshvi Gajjar, Chinmay Hegde, and Christopher Musco. Active learning for single neuron models with lipschitz non-linearities, 2023
work page 2023
-
[6]
One-shot active learning based on Lewis weight sampling for multiple deep models
Sheng-Jun Huang, Yi Li, Yiming Sun, and Ying-Peng Tang. One-shot active learning based on Lewis weight sampling for multiple deep models. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024
work page 2024
-
[7]
Springer, 1991
Michel Ledoux and Michel Talagrand.Probability in Banach Spaces: Isoperimetry and Processes. Springer, 1991
1991
-
[8]
Near-optimal active regression of single-index models
Yi Li and Wai Ming Tai. Near-optimal active regression of single-index models. In Proceedings of ICLR 2025, 2025
work page 2025
Show all 16 references
-
[9]
Woodruff, and Taisuke Yasuda
Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear regression for ℓp norms and beyond. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 744–753, 2022
2022
-
[10]
L1 Regression with Lewis Weights Subsampling
Aditya Parulekar, Advait Parulekar, and Eric Price. L1 Regression with Lewis Weights Subsampling. In Mary Wootters and Laura Sanit` a, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 ofLeibniz Int...
2021
-
[11]
Michel Talagrand.Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, volume 60 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Springer Nature Switzerland, Cham, Switzerland, second edition, 2021. 10
2021
-
[12]
Cambridge Series in Statistical and Probabilistic Mathematics
Roman Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
2018
-
[13]
Woodruff
David P. Woodruff. Sketching as a tool for numerical linear algebra.Foundations and Trends in Theoretical Computer Science, 10(1-2):1–157, 2014
2014
-
[14]
PhD thesis, Carnegie Mellon University, 2024
Taisuke Yasuda.Algorithms for Matrix Approximation: Sketching, Sampling, and Sparse Optimization. PhD thesis, Carnegie Mellon University, 2024. A Additional Preliminaries Covering Number and Dudley’s Integral.Suppose that ( X,d ) is a pseudometric space. The ϵ-covering number ...
2024
-
[15]
Bounding F in Corollary E.3.Let T−1 ={(f,x )∈Lip 1×R d :∥ΛAx∥p p≤R 0}, where R0 = 100 ϵ ∥Λ( ¯f(A¯x)−b)∥p p +∥ΛA¯x∥p p
It is obvious thatθ+β= 1. Bounding F in Corollary E.3.Let T−1 ={(f,x )∈Lip 1×R d :∥ΛAx∥p p≤R 0}, where R0 = 100 ϵ ∥Λ( ¯f(A¯x)−b)∥p p +∥ΛA¯x∥p p. By Corollary E.2 with our choice of α and R =R0, it holds with probability at least 0 .99 that sup (f,x)∈T−1 |∥SΛ(f(Ax)− ¯f(A¯x))∥p ...
-
[16]
Whenr∼ p ln ln 1 ϵ , Xr≤C 9 andY r≤C 4(C8)r−1 = poly ln 1 ϵ
Then C6≤X i≤ 100 ϵ for some constant C6 for all i≤r , thus Yi+1≤ 1 +C7Yi≤ C8Yi for some constantsC 7 andC 8. Whenr∼ p ln ln 1 ϵ , Xr≤C 9 andY r≤C 4(C8)r−1 = poly ln 1 ϵ . We shall also verify that KYi Xi ≥ϵfor smallϵ. Indeed, Yi Xi ≥ 1 (100Cθ 5) ϵ ≥ ϵ K forK= 100C θ 5. We iter...
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.