Near-optimal Active Regression of Single-Index Models
Authors: Yi Li
Wai Ming Tai
Venue: ICLR 2025 Poster (2025)
Keywords: Lewis weights
Active regression
Query complexity
Primary area: learning theory
TL;DR: We provide a near-optimal query complexity for the active regression of single-index models.

Abstract: The active regression problem of the single-index model is to solve $\min_x \lVert f(Ax)-b\rVert_p$, where $A$ is fully accessible and $b$ can only be accessed via entry queries, with the goal of minimizing the number of queries to the entries of $b$.
When $f$ is Lipschitz, previous results only obtain constant-factor approximations. This work presents the first algorithm that provides a $(1+\varepsilon)$-approximation solution by querying $\tilde{O}(d^{\frac{p}{2}\vee 1}/\varepsilon^{p\vee 2})$ entries of $b$. This query complexity is also shown to be optimal up to logarithmic factors for $p\in [1,2]$ and the $\varepsilon$-dependence of $1/\varepsilon^p$ is shown to be optimal for $p>2$.

Published as a conference paper at ICLR 2025
NEAR-OPTIMAL ACTIVE REGRESSION OF SINGLE- INDEX MODELS
Li
School Physical and Mathematical Sciences and College of Computing and Data Science Nanyang Technological University yili@ntu. edu. .g
Wai Ming Tai Independent Researcher ta i wa mi 200 20mmmmmaa0000000mmmmmmmmmmm com
ABSTRACT
The active regression problem of the single-index model is solve min ((Ax)) b/ln- where A is fully accessible and b can only be accessed via entry queries, with the goal of minimizing the number of queries to the entries of b. When f is Lipschitz, previous results only obtain constant-facto approxima- tions. This work presents the first algorithm that provides (1 (1+22 appprroximmii solution by querying (d /EPV2) entries of b. This query complexity also shown to be optimal up to logarithmic factors for E [1, and the e-dependence 1/e" shown to be optimal for > 2.
INTRODUCTION
Active regression, an extension of the classical regression model, has gained increasing attention in recent years. In its most basic form, active regression aims solve minger= ||Ar - bll, (p Z 1), where the matrix A E Raad represents n data points in Rd and the vector b E IR" represents the corresponding labels. However, since label access can be expensive, the challenge to minimize the number of entries of that are accessed while still solving the regression problem approximately. typical guarantee of the approximate solution is to find å Rt such that
|| A bllp S (1 + +)]l - bllp.
where x² is the optimal solution to the regression problem, i.e., xt = arg min |Ax bllp-
Research on this problem often focuses on randomized algorithms with constant failure probability, i.e. the entries of b are sampled randomly (but typically not uniformly) and the output å satisfies the error guarantee above with probability at least large constant. When showed sampling O(d/e) entries of suffices, and when p 1, Parulekar et al. (2021) ) showed an optimal query complexity of ((d/s²). The case of general p was later settled by Musco et al.
2, Chen & Price (2019)
2022), who showed query complexity of Ö(d/e) for p (1, and Ó(dr/2 /gp for p 2. Their proof was later refined by Yasuda (022)).
A more general form of the regression problem is the single- index model, which, in our context, asks to solve
min 2
[fxx) 61lp:
where f: f(u) = (f(w)),... f(u,)), )), i.e., applying f entrywise. This formulation arises naturally in neural networks and has received significant recent attention (see, e.g., (Diakonikolas et al.) 2020 Gajjar al. 2223a; Huang et al.) 2024) and the references therein). A neural network can be viewed the composition network backbone and a linear prediction layer z Rd with an activation function f. where typical choice of f is the ReLU function. The network's prediction is given by f(Ar),
a nonlinear function and, for u E IR"" we abuse the notation slightly to denote

---

Published as a conference paper at ICLR 2025
where the matrix A is the feature matrix generated by the network backbone from the dataset. The goal is to learn the linear prediction layer z, which corresponds to solving the regression problem.
In this paper, we consider to be general L-Lipschitz function. It is tempting to expect an analo- gous guarantec as (1) for the canonical active regression problem, i.c. to find ă E R such that
I| b|l S (1 +)][((())))) bllp
where x² arg minyerd ([xx)) bllp- However, Gajjar al. (2023a) showed that achieving this guarantee with a poly(d) query complexity is impossible even when J 18 a ReLU function and is constant. Hence, we can only expect weaker guarantce. The single-index regression problem was studied for 2 in the same paper (Gajjar et al. 2023a),, which showed that sampling Odd entries suffices find an ă E Rd such that
(A b112 < C(Ii(AA*) - b12 +
11:)
(2)
where x² arg min p. Huang et al. (2024) obtained
ce (Axx) bll2 is the minimizer and C' is absolute constant. For general
||
- bll < ( - -1]
(3)
for some constant C(p) depending only on p. using O(d/E*) samples when 1 < 2 and ( (ce)2/ee)) samples when p > 2. For = 2, Gajjar et al. (2023b) also independently ob- tained (ddes*) samples and, with additional co-authors, further improved the query complexity to (d/=²) in Gajjar et al. 2024).
The main drawback of the existing results for the single-index model, compared the basic form of active regression, is that (2 and B only achieve constant-factor approximations, whereas ①
achieves guarantee of (1 appppoxximati The goal of this paper is obtain a (1 + E)- approximation for the single-index model.
Note that all existing results assume access to an oracle solver the regression problem of the form arg min (A'xx) - D' Ilp its regularized variant, which may not be convex programme and where the objective function may be non-differentiable due f. this work, we retain the assumption of having such an oracle solver.
1.1 PROBLEM DEFINITION
Now we define our problem formally. For 2 0, let Lip, denote the set L-Lipschitz functions f such that /()) = 0, i.e.
Lip,, == {
f(0) = 0 and - f(y)] - L |a yl for all x y e R.).
Suppose we are given a function f E Lip a matrix A E Raxd and a query access to the entries of an unknown n-dimensional vector b R Define
OPT
min (Ax) #ERd
bll and x² .ER*:
arg min ||
That is, if there are multiple minimizers x", we choose an arbitrary one that minimizes ||Ax As noted in (Gajjar et al.) 2024), there is loss of generality in assuming ((0) O because one can shift both [(x) and by ((0). For an error parameter O, our goal find an & e IRd such that
(| b1B < (1 + s)OPT + C=||
where C is some constant that depends only L and while the number of queries to the entries of is minimized. Therefore, we would like to ask:
What is the minimum number (in terms of d and E) of queries to the entries of b needed in order achieve this goal?
We will solve this problem in this paper.
2

---

Published as a conference paper at ICLR 2025
1.2 OUR RESULTS
We first present the main result of this paper that querying Odd/s² poly log lo entries of is sufficient for a (1 + -paappoxximttion when 1 S S 2 and 2(d//2/e" poly log n) entries when > 2. Our result achieves the same query complexity (up to logarithmic factors) for the constant-factor approximation algorithm in (Gajjar et al. 2024) when =
Theorem 1. There is a randomized algorithm, when given A E R E R", f E Lip and an arbitrary sufficient small & > O, with probability at least 0.9, makes Odd / poly log(d/s) (d/=))
queries to the entries of and returns an &t E E& such that
II((A)) - bll S OPT + e(OPT - Aa
(4)
The hidden constant in the bound on number of queries depends p only.
Recall that in the canonical active regression problem, i.. fxx) z. the query complexity is (d/E) when 1 < p S 2 and 6(P//3 /-=-)) when p > (Musco et al. 2022). We can show that accom- modating general f pushes up the e-dependence to T/E² and T/E", respectively. In particular, for 1 p & 2, we show a lower bound of M(d/=") queries, which suggests that our upper bound is tight up logarithmic factors. The following are formal statements on our lower bound.
Theorem 2. Suppose that p > 1, > 0 is sufficiently small and Z (d d) e Any randomized algorithm that, given E Raxdd a query access to the entries of an unknown b E R" and f E Lip outputs d-dimensional vector such that (4) holds with probability at least 4/5 must make (2(d/= queries to the entries of
Theorem 3. Suppose that p > 2, E > is sufficiently small and n Z d/E". Any randomized algorithm that, given A R=xd query access the entries of unknown b E R" and f Lip outputs a d-dimensional vector such that (4) holds with probability at least 4/5 must make (2(d/e)) queries to the entries of b.
2 PROOF OVERVIEW
In this section, we will provide a proof overview of our theorems. The full proof for the upper bound can be found in Appendix B and the full proofs for the lower bounds in Appendix C
2.1
UPPER BOUND
General Observations We follow the usual "sample-and-solve" paradigm as in many previous active regression algorithms (Chen & Price. 2019 Musco et al. 2022, Gajjar et al. 2023a Chen 2022 Huang et al.) 2024). Querying entries of b can be viewed multiplying b with sampling matrix S. which is a diagonal matrix with sparse diagonal entries; the nonzero entries in Sb correspond to the queried entries of b. Hence, we would like to minimize the number of nonzero diagonal entries in S. The same sampling matrix S is also applied to f(Az), leading to natural attempt at solving the optimization problem min [|S([
b) I| However, we preview that this optimization problem is not the one we seek and we will provide more explanation on how to modify it.
The natural question is how to design the sampling matrix S. In all previous work, S is row- sampling matrix with respect to Lewis weights; see the statement of Lemma 6 In this paper, we adopt the same approach. This means that (i) (unbiased estimator) Se| and (ii) (subspace embedding) when S has sufficiently many nonzero rows, ||Ar||, all æ E Rdd Note that the query complexity for active regression is usually higher than necessary for subspace embedding alone.
| | for each R"
||xl|, for
We will present the construction of the sampling matrix and the full algorithm in Section 3
Formulating the Concentration Bounds Let å arg min (n - b)Il Although BJ((((Ax)) b) (Ax) bllg for each x Rd, it is unclear what ((()(
bi is since & depends S. To address this, we instead argue that the sampling error
3

---

Published as a conference paper at ICLR 2025
[[)(f((z) bb
[[f(A) - bllp is small for all T. where T is "small" bounded do- main containing Σ. Here, the small size of T is critical for a small error bound since con- trols the number of points in T at which the enror needs be small when applying Dudley's 's integral, a classical extension of the net argument. To further reduce the variance, we choose [|((f(x=)) b)ll3 (1f((x=)) bllB reference point and argue that the difference
Err(x) = ((I)(((A))) bbl IIf(Ar) - bllp) (I]((f(Ax)) 6)11 - If -(ll)-- (5)
uniformly small over T. Note that the reference point can be any 2 E Rdd This approach has been employed by Yasuda (2024) for the canonical active regression (i.e. f(x) z). However, for general Lipschitz functions key challenge is to identify an appropriate domain T, which we shall discuss below.
for
Regularized Regression As previously noted, the optimization problem min (Axz) b is not the one we are seeking. It turns out that there is a fundamental challenge argue that & arg min ( (Ax) b)l satisfies the desired guarantee (4 In the canonical active regression, one can show that
|A(2 - x ele S ||Az" - -b1p.
(6)
This suggests that for T "small" bounded region. Unfortunately, for Lipschitz function f. it is not clear how to obtain an analogy to 66 and thus bounded region 7 containing é. Hence, we still seek bound on the norm | to keep T bounded and ideally small. For constant-factor approximations, previous work Gajjaar et al. 2023a Huang et al. 2024) restrict the domain in the regression problem and solve min [[ (Az) 6) for some "small" T, but this leads to poor e-dependence of 1/e* in
fo E Rd ||A(x 21p S ||Az* bllp }. which
query complexity.
To improve the e-dependence, can consider regularized regression problem b)ll
min [((((Ax) ZER
||
where 7 0 is regularization parameter. This approach, demonstrated by Gajjar et al. (2024), improves the e-dependence for constant- factor approximations when p = 2. and will therefore be adopted in this paper. To ease the notation, assume that the Lipschitz constant L from now
An important question is how to choose the regularization parameter т. Recall that we want the sampling error Err(x:) (defined in (5)) to be small, ideally close to 0, when &. Then
Il (A b OPT (I((A)) bl [If - blß < [) b)ll [|S(f(Ax*) b) + error terms
S r || error terms,
where the last inequality follows from the optimality of é. The desired guarantee (4) has an additive error =|| =||AAz Il.. indicating that should be set smaller than e. On the other hand, the main purpose of regularization is to bound || By the optimality of & and rearranging the terms, we have
| S ! (IS(F(A=)) - b)ll ((((()))) - b)(l?)
+ ||Ar"")! Ip.
This suggests that should be set as large as possible for better bound on || Therefore, we set 7 = and the optimization problem becomes
[S(((x)) - b)lb + s- Ax ZERd
min
Bounding the Error To avoid overloading our notation, we focus on S p S A similar argument works for 2 2. Recall that our intention is to bound
sup Err(a:), TET
4

---

Published as a conference paper at ICLR 2025
where Er)( is the sampling error defined in 5 The first issue need to resolve is defining the domain T. By the optimality of ø in ( and rearranging the terms, we have
||A$|| -
[|([(Ax=) b)1b [[((((a)) b)]l3] + -||Ax")) 1|
(8)
14
||((f(Ax)) - b))1 || ||
24
OPT + || by Markov inequality.
(9)
Hence, we can set
1 OPT + || and T= (= Rd || R).
Then & E T. Now, while we omit the details, we obtain the following concentration bound in (T)) by following the standard technique of upper bounding the supremum of a stochastic process using Dudley's integral, which has been the central tool in the work on subspace embeddings (Bourgain ct al. 1989; Ledoux Talagrand, 1991 Cohen & Peng 2015) and previous work on active regres- sion (Msco et al. 2022, Chen et al. 2022 | Huang et al. 2024 In short, when the number of queries m. we can obtain that with probability at least 0
V
dd poly(((o n, log 6-1 R.
sup Err(x) S 2ET
(10)
We preview here that this concentration bound will yield weaker result, but it serves to illustrate the key idea and will guide us in refining the analysis later.
Suppose that m & poly log n. By plugging m and R into (10 we have with constant probability,
sup Err(x) & e(OPT + =|| 1[)). xET
Since & T. we have
(AAA) blli - OPT S [[(f(A)) - - b)( + <OPTT + E [A)
K =x * 1 + =OPTT + =||Ax* Il)) by the optimality of in
2 (OPT + ||Ar" ||))
(11)
which achieves the desired guarantee by rescaling ef
Attempt to Improve The reason we previously set m 24 poly log n is because R OPT +
||Ax [| and we need the square root term in 110 be e2 so that the overall error is most e (OPT+ and bound the radius of the domain in (6), this large R is the main reason why extra factors of are needed.
||Ax" [[z). Indeed, when we compare to the canonical case of f(x)
[Ax() b)l in Err(æ:) also appears in 8 means that we can plug the bound Err(x) into (8 and improve the radius R.
Notice that the term [[S(f(Ax) I)
This
For example, let
2 poly log Here, the exponent 3 can be replaced by any value strictly larger than 2 and we simply choose this number for demonstration purposes. By plugging m and R into (TO), we have with constant probability
sup Err(1)) sup(())((((A)) - b) 1| ||((f(A=)) - b)} (l)((z)) bll IIf(Ar) blD TET
sET
<
OPT + + ||Ai" +
(12)
Since & T. by plugging
12 into (8) and a similar calculation that in (. we have
| p
OPT + ||Ax I| which is smaller than R.
If we set
R' OPT + ||x' and T (x E Rd ||Aa|| & R'
5

---

Published as a conference paper at ICLR 2025
then 2 T', By plugging m, R' and T into (10 we have with constant probability,
sup ZET
Err(x)
x sOPT +
This is an improved error bound compared to that in [I that
12 It follows from & E T and a similar calculation
II((A)) b1p OPT
OPT X s(OPT + |1)))
which achieves the guarantee (4) Therefore, we have successfully improved the query complexity d from d poly log to 2 poly log Although this bootstrapping idea of reusing the enror guarantee to g 7 has appeared in previous work (Musco et al. 2022 Yasuda 2024), we emphasize that there is fundamental difference in the detailed analysis for general Lipschitz functions f, due to
the lack of convexity ( - -----
Further Improvement Recall that we are targeting query complexity of 2 poly log n. One may d poly log n in the above argument not helpful. To address immediately check that setting m ~ 2z
this issue, we refine the analysis of (TOp and improve the bound follows. Recall that R = OPT + ||Ax I| such that ||A P S R. If we further restrict the domain I and set it to be
T = E 5 R and 11f(Ax) f(Ax f(Ax0)l( FF
for some F 2 OPT
then (10) can be improved to
d poly((og n, log 8-1)
sup Err(#) $ =ET
VR..
(13)
m
Note that, by the Lipschitz condition and the fact that Ax S R. we have
(lf(Ax) - f(Ax S || Ar 1 R
and hence one can set = R. That means (13) is always no worse than 10 need show that & T, i.e. find a suitable F such that [ fAAx*
To apply
13
wc
F.
In the proof of a constant-factor approximation by Gajjar et al. (024), a key step is
I|AAi) f(Ax") " S OPT + +
when 2. A straightforward modification extends it to general which means that we can set F OPT + Ax|
Now, we pick m = poly log n. By plugging m. R and F into 13 we have
sup Er)(x) Se =ET
(OPT + +eIlAx*1B) OPT
||Ar (
6
(14)
Following the same argument before and plugging it into S we have
| -
OPT ||
which allows refine further the radius R and thus the domain T. leading better bound || | Iterate this process and apply (13) log log times, we shall arrive at the bound
Er)(#) = (())(((())) - 1 [IS(S(Ax))))))) b) ) (IIS(A)) bll (Is(A=)) bIB S e (OPT + | (1:).
Finally, we follow a calculation similar to that in to achieve the desired guarantee The caveat here is that repeatedly applying the concentration bound (13) in the iterative process causes the failure probability to accumulate. We resolve this by setting 1/ log (og(1/s) in (13) keeping
log(1/ /8) most log n. Hence, the query complexity remains (d/s²) poly log

---

Published as a conference paper at ICLR 2025
Dependence Although have achieved the query complexity of - poly log n, it may not be desirable when n is large and we seek to further remove the dependence on n. The poly log n factor arises from estimating covering number when bounding Dudley's 's integral. Indeed, by using a simple net argument with a sampling matrix of poly(d/e) non-zero rows, the solution guarantee can still be achieved. While the dependence on d and e are both worse, the query complexity is independent of n. To take the advantage of this trade-off, a standard approach involves using two query matrices S and S, where 5 has the suboptimal number of nonzero rows, and then solving the following new regularized problem
arg
b)) = Arlp.
ZER4
We need pay close attention the fact that we are not simply using 5 A as the input matrix A in the original statement because of the function ʃ.
To bound the error, natural attempt to use the concentration bounds and show that
(f(A)) b1l - [Ixx) bllb
s (f(())))) - b) - [] b)ll + error terms -ISS ([(Ax))=b))
(15)
$ ||SS (f(A)) (f( b)ll
+ error terms
(16)
and then we use the optimality of to complete the proof. However, we remind the readers that, to apply the concentration bounds, it is important to check that the relevant points x², f are in the
domain of interest for the corresponding bounds. It turns out that we can obtain (15) but arguing
(T6) is the main obstacle because of that. While will omit the detail, note that we need
proxy point x to circumvent this obstacle when using the concentration bound for S. The proxy point x is defined
argg
+)
ZERd
and this proxy point allows us to show that & lies within the domain of interest. We can then modify the above argument by continuing from (5)
(f(A)) b) 1/ 1| II (f(Ax") b)
< {[))(((A))) 1)|s [|5(()(
b)ll + + =
< ||SS (J(A)) b)1 118S (J(Ax)) b)]l : + terms
and use the optimality of f to finish the proof.
2.2 LOWER BOUND
General Observations As in the previous results (Musco et al. 2022: Yasuda 2024), via Yao's minimax theorem, the proof of the lower bounds is reduced to distinguishing between two distribu- tions (which are called hard instance). Specifically, we construct two "hard-to-dissinguihh" distri- butions the vector b, and it requires certain number of queries to the entries of b to distinguish between these distributions with constant probability. The reduction is using an approximation solution f to determine from which distribution is drawn. We construct
hard instances for
1 1 p < 2 and 2 separately. These instances are inspired by those in (Musco et al.) [002]] Yasuda 2024) but are more complex, as are showing higher lower bound. For the purpose of exposition, we assume d = 1, in which case the matrix A degenerates to a vector E R². We shall then extend the result to the general d.
Hard Instance for 1 < 2 We pair up the entries (say 2i 1 and 26). Let
2
u = and =
3
Let Do (resp. D1) be the distribution on E 2m2n that, for all i 1= 1,..., n, each pair
b2g-1]
= { with probability 1 + E (resp. - =)
bzi =10 with probability 2 (resp. + e).
7

---

Published as a conference paper at ICLR 2025
2.50
/|
x2
Z20
Figure 1: (left) Plot of the locus =()-=x), where the red (resp. blue) part corresponds to S (resp. 0): (middle) [[[ e is the point the red part that closest and v in the ly-distance; (right) f[[ ) ) is the point on the blue part that closest to u and v in the Ey-distance
By the standard informatiin--teerrtiic lower bounds, one needs to query (2 entries of to distin- guish Do and Dj.
To reduce this problem to our problem, we set
i S -6
- x -4 15-45553 if < x
[ax-1
[-1]
f(x)
and
for i I..... n.
02i
Let be the number of u's in b. The objective function becomes
[s(a x) - bl = k [[[([=)) u + (n k) [[((==)) -
The takeaway of this construction is can view f(1 11]=x) in Figure [ Suppose is drawn from Do- It implies that l = 2 + En and hence n < k. One view each component as the b, distance between the locus and locus passes through u and v. When x = -6, we have [[[ -x = u and so
locus in R² as varies, illustrated
v. As seen in Figure [ the
OPT S 0 (n k) |Iu = = 2" (n- k) ~ 20- - 22).
On the other hand, Figure I also suggests that, when 0, we have
(a x) - bl l 2 k. ||u
-u--elo - + (n - k) 2 2 2 20 1 + 25).
Suppose we have solution a such that
Ilf(a - i) - b1β < + c + c. I|a x²1 13
< (1+c. k) + c ||a x 10I - 2s) c 6º 2n
2 e1+c.e).
2" 221-n((111) - ((=)) for sufficiently small
22--nn + 2s)
which implies that < O. Similarly, suppose b is drawn from D1, one can show the symmetric result. We can declare is drawn from Do if f and Dj otherwise. This concludes our reduction.
Hard Instance for 2 We start with the all-one vector b 2 Then, we pick random index from {i...., 2n) uniformly and update b;. < bt- + 1/E. Our question is to determine whether 5" S or i* > n, and it follows from straightforward probability calculation that 22n)) queries to the entries of b are required. Recall that we are targeting a query complexity of ((1/cP) and hence set 1/sP.
To reduce this problem to our problem, we set
0 i < 0
if 1,..., 7
f(x)
x ff0$<5
and
a,
if = 2n.
1 if <
8

---

Published as a conference paper at ICLR 2025
Algorithm Generating Sampling Matrix GSM(K) kn.
Input: n integers .y...., knn 2 O; sampling rate < 1
S f an n x diagonal matrix, initialized a zero matrix 2: for I, l,...., do
3: if h; then
4: Generate binomial random variable N, Bin(k,,
5: Su 4 ak.
6: Return
Suppose that 1 I n. If = 1, we have the following. For i 1,..., and i * i", we have f(a 2)1 f(1) = bj. Recall that bi- =1 1/s. Hence. we have 2==lf(a (()x bil"'
1/8" = n.. For i = n + 1...., 2n, we have f(a x); = f(-1) = 0 and therefore we have
Dim+1iffe 2) - b,l" = Lient1 1 = Namely, we have
OPT S [a
bll 2n.
On the other hand, it is easy check that, when x < 0, have
15 x) - blp 2 Σ (is x); - 1,1 2 n 1+ 1
( 1+==+++++ 2 2n(1 +
Suppose we have a solution & such that
[I i) - b11 s (1+ 8)0TT + s||a->*||}
< (1 2n + e P
< 2m +)) for sufficiently small
0
which implies & >> 0. Similarly, suppose that i* 2 n + 1, one can show the symmetric result. We can declare 1* S # > 0 and > n otherwise. This concludes our reduction.
Extension to d instances of d = and reduce this new problem to the regression. The formal construction as follows. Let ((1/e((()))) eevv2). We have dm-diimesional vector b, which can be partitioned into d blocks of mi-dimensional vectors, with each block drawn from either Da or D2 (the hard instances introduced earlier depending p). By straightforward probability calculation, it can be shown that (2dm) queries to the entries of are needed to correctly answer, with constant probability, which distribution each block of m-dimensional vector is drawn from, for least 2d/3 blocks.
We consider the problem of solving multiple independent copies of hard
To reduce it to our problem, let A be dm-by-d block-diagonal matrix, partitioned into da blocks of m-dimensional vectors. Each diagonal block is the vector a which we constructed earlier. The function f remains the same as before. Suppose we have a solution 2 satisfying 4 By the inde- pendence between blocks in b and the block-diagonal structure of A, we can argue that 4 can be decomposed into the sum of the objective functions for each independent block and declare that each block drawn from Do or Dj based on the same criteria as in the case of = 1. By the standard counting techniques, at least 2d/3 of the d answers are correct and this completes the reduction. Hence, we achieve the query complexity of d/eev2.
We point out that for the canonical case of fz) and p 2 2. the previous result of Yasuda (2024) gives stronger lower bound, in terms of d, of (2dp/2 /er-)) Unfortunately, it is still not clear how to apply the techniques in our setting.
3 ALGORITHM
To complement the proof overview Section 2.1 we present our full algorithm in Algorithm 2 and explain the explicit implementation.
first constructs a sampling matrix S (line ! to line of Algorithm 2 and applies it to A, (A(-))
and b. This sampling matrix S is generated using Algorithm 1 When applying S to A, in step

---

Published as a conference paper at ICLR 2025
Algorithm 2 Algorithm for Active Learning without Dependence
Input:
matrix A E Rnxd
query access the entries of the vector E R function f Lip an error parameter e
two sampling rates < a² <
1: Compute the Lewis weights of A, denoted by wi (A)...., Wx)())
2: for I,..., do
3: k -- [1)
4: 5 + GSM(A)
k a) from Algorithm
5: m < number of nonzero rows in S
6: Compute the Lewis weights of 5 A, denoted by (5 ,),
7: for 1,...,.... n do
8: k; + (
9: S GSM(M) n 0x) from Algorithm
10: Solve the minimization problem & := arg min |S8 S +
Return the vector è Rd
of Algorithm ! it is equivalent to splitting the rows of A such that all rows have uniformly bounded Lewis weights of (d/n). To achieve this, it needs the Lewis weights of A and they can be computed as in (Cohen & Peng 2015) for < 4 and as in (Fazel et a (022) for 2 4. Afterwards, we sample each row with the same probability a This row-splitting approach has been used the proofs of Cohen & Peng (2015); Yasuda (2024) and in the algorithms in (Gajjar et al. 2023b 2024). Details of this row-splitting technique can be found in Appendix B.I
We set the sampling rate a poly(d/e)/m) This effectively reduces the dimension from n, the number rows of A, to m ~ a n = poly(d/s), the number of non-zero rows of S A. Therefore, it removes the dependence on in bound.
then constructs the main sampling matrix (line line 9 of Algorithm 2 with the sampling rate a v / (() poly log(m), whereby avoiding dependence on as previously discussed, and applies to S A, S [(A())) and S*b. That means that the number of non-zero entries of S is, with high probability, most 2am ~ (EVI/(EPV3) poly log(d (og(d)s) which is the query complexity we are looking for. Note that also generated using Algorithm and hence satisfies the property of uniformly bounded Lewis weights through the previously mentioned row-splitiigg techniques. Finally, the algorithm outputs the optimal solution & of the regularized problem
min S5 f(Ax) - bS + S Ar
FER
and that completes our full algorithm.
4 CONCLUSION
In this paper, we consider the active regression problem of the single-index model, which asks to solve min, Il (Az) (Az)-bllp> with being Lipschitz function, A fully accessible and only accessible via entry queries. The goal is to minimize the number of queries to the entries of é while achieving an accurate solution to the regression problem. Previous work on single-index model has only achieved constant-factor approximations (Gajjar et al. 2023a b. Huang et al. 2024 Gajjar et al.) (024). In this paper, achieve (1 + appprooximnaionn with (d v1 /EPV2) queries and show that this query complexity is tight for < p < 2 up to logarithmic factors. Furthermore, we prove that the 1/e" dependence is tight for p > and we leave the full tightness of d2/2 as an open problem for future work.
ACKNOWLEDGEMENTS
Y. Li was supported in part by Singapore Ministry of Education AcRF Tier grant MOE- T2EP20122-0001 and Tier I grant RG75/21. W. M. Tai was supported by Singapore Ministry of
10

---

Published as a conference paper at ICLR 2025
Education AcRF Tier 2 grant MOE-T2EP20122- when he was affiliated with Nanyang Tech- nological University, where most part of this work was done.
REFERENCES
Shiri Artstein, Vitali Milman, and Stanislaw J. Szarek. Duality of metric entropy. Annals of Mathe- matics, 159(3)1313-1338, 2004.
Jean Bourgain, Joram Lindenstrauss, and Vitali Milman. Approximation of zonoids by zonotopes. Acta Mathematica, 162(():73-141, 1989.
Cheng Chen, Yi Li, and Yiming Sun. Online active regression. In Proceedings of the 39th Interna- tional Conference on Machine Learning, pp. 3320-3338 PMLR, 2022.
Xue Chen and Eric Price. Active regression via linear- sample sparsification. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty- Conference on Learning Theory, vol- 99 of Proceedings of Machine Learning Research, pp. 663-695. PMLR, 25-28 Jun 2019. URL htttts:://pposeeee
ngs. ml www.sresssvv. v95 p9t/che//nnnccc chen 9a. html
Michael B Cohen and Richard Peng. Tpp row sampling by Lewis weights. Proceedings of the 47th annual ACM symposium on Theory of computing, pp. 183-192, 2015.
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Jacob Abernethy and Shivani Agarwal (eds.), Pro- ceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 1452 1485. PMLR, 09-12 12 Jul 2020. URL http:: ptttps://proceeding
mlr www.ppeessvllll /ttps////////aaakoooooooooo
html
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing lewis weights to high precision. In Proceedings of the 33rd Annual ACM-SIAM Symposium Discrete Algorithms (SODA 2022), pp. 2722-2742, 2022. doi: 10.1137/1.978 1711999777111177711177
Aarshvi Gajjar, Christopher Musco, and Chinmay Hegde. Active learning for single neuron models with Lipschitz non-linearities. In International Conference Artificial Intelligence and Statis- tics, pp. 4101-4113. PMLR, 2023a.
Aarshvi Gajjar, Xingyu Xu, Christopher Musco, and Chinmay Hegde. Improved bounds for agnostic active learning of single index models. In NeurlPS 2023 Workshop on Adaptive Experimental Design and Active Learning in the Real World, 2023b.
Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, and Yi Li. Agnostic active learning of single index models with linear sample complexity. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 1715-1754. PMLR, 30 Jun-03 Jul 2024.
Sheng-Jun Huang, Yi Li, Yiming Sun, and Ying-Peng Tang. One-shot active learning based on lewis weight sampling for multiple deep models. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https:://pperree
net.
E. Kiltz and V. Vaikuntanathan. Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part II. Lecture Notes Computer Science. Springer Nature Switzerland, 2022. ISBN 9783031223655.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
Cameron Musco, Christopher Musco, David P Woodruff, and Taisuke Yasuda. Active linear gression for L, norms and beyond. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 744-753. IEFE, 2022.

---

Published as a conference paper at ICLR 2025
Aditya Parulekar, Advait Parulekar, and Eric Price. L1 regression with lewis weights subsampling. In Mary Wootters and Laura Sanità (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2021), volume 207 of Leibniz International Proceedings in Informatics (LJPPccs) pp. 19:1-49:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl Leibniz--Zentrum für Informatik. ISBN 978-3-95977-207755 L.PIS.AAPROX//AANOOMM..... .9, document 42.0/230110 311/30//IPPCC www.OXPPPPP... RAOOO//AADOOOOOOOO 2021.
doi: 10.4230/ http:/ppp...gggioeeeeeeeeeeeiaia
Michel Talagrand. Embedding subspaces of L1 into g.. Proceedings of the American Mathematical
Sociery, 108(2):363-36)) 1990.
Michel Talagrand. Embedding subspaces of Tp in Cx. In Lindenstrauss and V. Milman (eds.), Geometric Aspects of Functional Analysis, pp. 311-326, Basel, 1995. Birkhäuser Basel.
Roman Vershynin. High-Dimensional Probubility: An Introduction with Applications in Data Sci- ence, volume 47. Cambridge University Press, 2018.
Przemystaw Wojtaszezyk. Banach Spaces for Analysts. Cambridge Studies in Advanced Mathemat- ics. Cambridge University Press, 1991.
Taisuke Yasuda. Algorithms for Matrix Approxination: Sketching, Sampling, and Sparse Optimiza- tion. PhD thesis, Carnegie Mellon University, 2024.
A PRELIMINARIES
Notation For distribution D, write X 'D to denote random variable X drawn from D and 3.D to denote the distribution of the scaled random variable B.X,, where ~ D. For any 0 S p S and positive integer n. we use Ber(p) denote the Bernoulli distribution with expected value p and Bin (n, p) to denote the Binomial distribution with n trials and success probability p for each trial. That if X Ber(p) then
with probability x x
with probability 1-p
and if X pi then X can expressed as Ei= X, where XI,..., Xn are i.i.d. Ber(p) variables.
For matrix A, we use A,, to denote its i-th row and A. its i-th column. For A An E R, we use diag(A,.... .............................. )n to denote a diagonal matrix whose diagonal entries are Ai...., An.
a normed space (X, || II), the unit ball B(X) is defined as ( = { E X |||||| 11). When X is clear from the context, may omit the space and write only B for the unit ball. When X is the column space of a matrix A, we also write the unit ball as (A)). If the norm has subscript |I-I shall include the subscript of the is the column space of A). In R", the standard fn-norm and the weighted fp-norm, denoted by II-11p and I|-Ilar,p are defined as ||0|||
and denote the associated unit ball by Bn (or Bn (A) if X
(E (x.l))2/p and ||>|| w.y (Ei= W//x,/P)//P, respectively,
where w R. and w; > for i [m].
We shall use C, C1, C2 .... e, c1, c2, to denote absolute constants. We also write max(a. b} and min b) as a b and a A b, respectively. We use 0,Ω, θ and S, Z, interchangeably.
Lewis Weights We now define important concept regarding matrices, which have played criti- cal roles in the construction of space-efficient subspace embeddings. Definition 4 (c,- Lewis weights). Let A E gaxd and p 2 For each E [n], the ey LewLs weight of A for the i-th row is defined to be w; that satisfies
wi (x(A) = (a, (A w A)taa)
where o; is the i-th row of (as a column vector), W = diag WT.... wr and denotes the pseudoinverse.
12

---

Published as a conference paper at ICLR 2025
When the matrix A is clear in context, will simply write (x(A) w, Adopting that 0 oo O, we have (A) = if a; = 0. The following are a few important properties of Lewis weights; see, e.g., (Wojtazzzyyk 1991) for proof.
Lemma (Properties of Lewis weights), Suppose that A E B=
xd has full column rank and Lewis weights w1,..., Wn. Let W [lag(ww,..... Wn. The following properties hold.
(a) Ex 2,::=:6 = d;
(b) There exists a matrix U E Raxd such that
(i) the column space of U is the same as that of A;
(ii) W; = |1,,,112 112
(iii) W - has orthonormal columns;
(c) It holds for all vectors u. in the column space of A that [WZ 22l12 S d²= zेत
- 11lll
(d) It holds for all vectors in the column space of A that |u,] S då aùo w: ||ullp
Suppose that A E Raxd and E (0, 1). We say matrix S E R is an Ep -ubsppaec embedding matrix for A with distortion + if (1 + +1) I ||S S (1 [1+E)]] Axlpp- The prevailing method to construct l, -subspace embedding matrices to sample the rows of A according to its Lewis weights.
Subspace Embeddings
Lemma 6. Suppose that A Raxd has Lewis weights wi.-..; Wn. Let Pt E [0, 1] satisfy that 2 (Bwz) A and S E RRax be a diagonal matrix with independent diagonal entries Ss ~ Pi 1/p Ber(pi). Then with probability at least 0.99, S is an ep-suspacce embedding matrix for A with distortion 1 + if
22 log (log log e),
1<p<2
3 2ZP
log
p p= 1.2
d2
(log d)² log
p 2.
The results for E [1, 2] are due Cohen & Peng 2015)) ). based on carlier work of Talagrand 1990)
1995). The result for p can be found in (asudda [024] Huang et al. 2024). which improves upon the previous bound B (de/2-1/E5 (log d) log( (1/e) in (Bourgain al. 1989 Cohen & Peng 2015).
Covering Numbers and Dudley's Integral Suppose that T is a pseudometric space endowed with a pseudometric d. The diameter of T, denoted by Diam d), is defined as Diam(T", d) == suP p(t, s).
Given r > an r-covering of dT is subset X C T such that for every & T, there exists E X such that d(t, < r. The covering number (T, d,r) is the minimum number K such that there exists an r-covering of cardinality K.
The covering numbers are intrinsically related to subgaussian process on the space T' that conforms the pseudometric d. This relationship is captured by the well-known Dudley's integral.
Lemma 7 (Dudley's 's integral Vershynin| (2018).. Let X, be zero-mean stochastic process that is subgaussian w.r.t. a pseudo-metric on the indexing set T. Then holds that
Pr sup X x (f (f NT, sdde + Diam(T))} < 2 2exp(=xx= LEET
where C' is an absolute constant. As consequence,
sC' ce [V.0 Vlog (TT,d +VEDiaa(TT)
E
sup |X
x.i) [X.
J.TTT
where C and C" are absolute constants.
Note that when r > Diam(T, (d),, the covering number WT,, d, = and thus the integrand becomes O. Hence, Dudley's integral is in fact taken over the finite interval [o, Diam(T, d)].
The following covering numbers related to I| will be useful our analysis. These are not novel
results though include a proof in Appendix B for completeness.
13

---

Published as a conference paper at ICLR 2025
Lemma 8. Suppose that A E Raxd has full column rank and W is diagonal matrix whose diagonal entries are the Lewis weights of A. holds that
dlog t logl qd
9 -=p21
log N (B (W 1/8 A), 1ll
1 1 p and q >
2.
Lower Bound The following two lemmata, Lemma and Lemma 10 are needed in the proof of our lower bounds for p S 2 and p 2 2, respectively. Lemma is a classical result, whose proof can be found, for example, in (Kiltz & Valkuntanathan 2022 p?I.).
Lemma 9. Let be positive integer. Suppose we have m-dimensional vector whose entries are i.i.d. samples all drawn from either Ber( vmm) or Ber( - +m) It requires (1mm) queries to distinguish Ber( +
Vmn and Ber( 7 with probability at least 3/5.
Lemma 10.
Let m be a positive integer. Suppose that x E IR2m a random vector in which all but one of the entries are the same and the distinct entry Iz- is located at a uniformly random position it E [2m]] Any deterministic algorithm that determines with probability at least 3/5 whether i" lies within (1....,m) {m + 1,...,211. must read (m entries of
Proof. Let be the set of indices the algorithm reads and A(Q, i*) be the output of the algorithm.
Note that, if & Q, then A(Q, i*) does not depend on i* and we write it A(Q).
Now, let & be the event A(Q, i+) being the correct set and I be the event of i" being chosen among these queries. Then, we have
Pr(E) = Pr(E Pr() + Pr(E []) Pr(Z).
Note that
Pr(E (2) 1 Pr(Z) 2m
and Pr(Z)
4
2m
where q = IQ)-
Now, evaluate Pr(E Σ). Let 91 (resp. 42) be the size of the set Q {l...., m} (resp. Q n
(m + 1, ..... 2m }), so @1 92 g. Given the event I, recall that we have A(Q, A(Q). If A()) {1,... ..... m), the event of & I is equivalent to the event that i' belongs (1..... m] but is not queried, thus we have
m 91
17 92
Pr(E I))
2m q
2m q
Similarly, if ((Q) {m + 1, 2m}. we have
Pr(E [T) = 2m
m7 92
m 91
2m
Hence, we have
Pr(E Σ) S max
m 92 91 }.
2m q 2m
Namely, we have
Pr(E) <
q
max
171
Q2
m Q1
](1
g
2m
2m -
2m
2m
q
Q1 1
Q2
+ max
{
2m
2
2m 2
2m
+ maxt
91
Q2
}.
2m
2m
If q S 7, it implies max(gn, 22) m and hence Pr(E) <
14

---

Published as a conference paper at ICLR 2025
Algorithm 3 Algorithm for Active Learning
Input: matrix A E Rnxd
query access the entries of the vector E R function f Lip an error parameter e sampling rate <1
1: Compute the Lewis weights WI.... Wy of A
2: for = L...., do
3: + m.
4: S + GSM(k ..... Knn a) from Algorithm
5: Solve the minimization problem & :- arg min (S{(a)) Sbilž + +111Ax|E
6: Return the vector è E Rd
The next lemma extends the previous two lemmata to multiple instances of the problem considered therein.
Lemma 11. Let d and m be positive integers. Suppose that Do and Dr are two distributions in Tn and distinguishing whether a vector is drawn from Do or Dj with probability at least 3/5 requires querying 3m entries of the vector for some constant B > O. Consider dm-dimensiooal random vector consisting of d blocks, each of which is an m-dimensional vector drawn from either Do or Dj. Every deterministic algorithm that correctly distinguishes, with probability at least 2/3, the distributions in 2d/3 instances requires (dmm) entry queries to this tin-dimensional random vector.
9 8 dm queries in total. Then there exist 1n Proof. Suppose that an algorithm makes fewer than 1o blocks, each of which makes fewer than 3m queries. Therefore, each of these blocks will make an error in distinguishing the distributions with probability at least 2/5. By a Chernoff bound, with probability at least 1/3, at least d' = Iо @(vd) instances make an error. It means that d' d/3 and arrive contradiction against the assumption on the correctness of the algorithm.
9
B UPPER BOUND
In this section, first obtain query complexity with poly log factors with the algorithm pre- sented in Algorithm 3 (see Theorem [2) and then remove the dependence on n in Appendix B.4
B. EQUIVALENT STATEMENT
We shall first reduce the problem to the case where A has uniformly bounded Lewis weights, before proving in the next section that the output of Algorithm with a suitable a satisfies (20p with probability 0.99.
We start with the following observation. Let k; be D000: for í 1, 1...., n which is the same term also defined in Algorithm Hence, we rewrite
(Ax) b13 DIU(As) - ki
6).1
(f(Ax)-b)
I(((Ax) b):
Now, suppose that we duplicate the i-th term, ((f(Ax)-0) b)slP, IlP,A k; times and assign a weight of 1/k each duplicate term. Formally, let
n'' Σi= ks.
A' be an n by- matrix in which AJ.- = A,, if i-1 Ka <jS Ei= has
D' be n/-dimensional vector in which B', by if Σi=l 1 k <j S Ei= hig
A be n'-by-n' diagonal matrix in which A5 k, - if x hi < 5 Ei
kas
15

---

Published as a conference paper at ICLR 2025
In other words, have
((A))-bil) Σ - - IE
Note that we still have
OPT
min zER
AAf(A2)) 1bIE and x²
arg min ZER (M1A'')-A8133-00
|AA''1
(17)
On the other hand, in Algorithm
recall that N₂ ~ Bin a) for = I,... n, it can be rewritten
as
N Σ Niji
where Ni. Ni.; are i.idd Ber(a)) variables. In other words, we have
[[S((r)) - Sb1l Σ ((U(())))) - b)dl No K
-(([Ax)) b)sl".
Let S be an n' n'-by-n' diagonal matrix in which S/ if j Eizt ka + 3' for j
No.
..... ks. Then
[Sf(Ax) - Sbli Σ S (f(A')) B') (S'AS(A'))))) S'ARIE
Also, it is easy check that
| ||AA'
We still have
à = arg minl| - A/
(18)
wERd
The advantage of introducing the diagonal matrix A is to bound the Lewis weights. Formally, have the following observation. By the definition of Lewis weights, the j-th Lewis weight of AA' is if = -a=1 Ka + 1,........... Eds1 No for j = 1,... n²', Recall that k2 n-w. and we have
W.'s and n'
1) 2n.
Therefore, generalize statement to be the following, Let A' be r'-by-d matrix, E Lip be an n'' n'ddimensional vector, A an arbitrary n'-by-n' positive diagonal matrix such that the Lewis weights of AA'' is most 2d x/ Define OPT and x² in (17). Furthermore, let S' be an n' by--n diagonal random matrix in which the diagonal entries are i.i.d. a # Ber(a:) variables, i.e.
a
with probability with probability 1
S
0
and define in 18). Our goal show, for a suitable a, we have correspondence to
||A((A3)) AB 13 < + e)PT T
16

---

Published as a conference paper at ICLR 2025
B.2 CORRECTNESS
We would like to prove that the output of A satisfies f with probability 0.99. In view of Appendix B.I, we can replace A with AA, where the Lewis weights of AA are uniformly bounded by 2d/r n. The desired error guarantee is therefore
[|Af(А)) - & S (1 = + L'e||Arr Ip.
(19)
By replacing (x) with (x)) and with b/ L, we henceforce assume that and the error guarantee becomes
Af(()) Ab|l < (1 [1+:))PTT+ +
(20)
We shall first prove a weaker version of Theorem
| with query complexity containing log factors
and then show how to remove the log n factors in Appendix B.4 The weaker version of Theorem is stated formally below.
Theorem 12. Let A E Raxd, I E b R", f E Lip E E (0.1) be sufficiently small and A be n X diagonal matrix satisfying that A& > 0 and wx(AA) S d/n for all i. There is randomized algorithm which, with probability at least 0.9, makes (d / poly log n)) queries the entries of b and returns an & E I satisfying
(A() - b) < (1 + =)]AAA(AAS - b) +
The hidden constant the bound on number of queries depends on p only.
Note that we introduce vector I E 1 If we take 2 = x², Theorem 12 becomes Theorem except that the query complexity contains log factors. The reason we introduce E is because when we remove the log factors in Appendix B.4 we reuse the theorem using different ž. Now, to prove Theorem 12] we first provide a concentration bound Lemma 13
Lemma 13. Let A E Ra / f Lip,, E (0, 1) be sufficiently small and be an n x n diagonal matrix satisfying that Aü > O and wx(AA) E d/n for all i E [n]. Also, let S be n-by-n random diagonal matrix which the diagonal entries are i.idd a Ber(a) variables where d ngrvz
-poly logn. i T E Rdd satisfy
$ arg min| |nin|||SA ((A(([(s))))))))))))))) b) + +1I ZER
and
[IA[(A)) b)| (IA - b)|B <(((AA(((A)))) D)I + +
then, with probability least 0.9.
KIISA(F(Aa) - - [[SA(f(AT) - - -)] (AA-IAA((A))--- - b)]
S (E-()A((AA)) b)|b + ||A
We show how Lemma 13 can be used prove Theorem 12 The proof of Lemma 13 will be presented in Appendix B.3
Proof of Theurem 12
We shall apply Lemma 13 with ø = x² to prove Theorem First, we verify Clearly, the output & of Algorithm 3 satisfies
the conditions in Lemma 13
i arg min Mnin||SA(((AA))
6) + =||AA>
ZERd
and, by the optimality of x², we also have
[A([(Ax)) - 1)T ((A[())(((A)))))))) b) O.
Recall that |[A([(A)*) b)l1 = OPT. By Lemma 13
with probability at least 0.9, we have
SA(((E)) - -b)1g [|SA(f(Ar)) b) (IA((((A)) - bb) OPT) E (OPT + ||AA**1 113),
17

---

Published as a conference paper at ICLR 2025
which implies that
[AAf((A)) - b)1l OPT
< [AA( b) (ISA( - b]1I + (OPT + ||AAx |p))
$ e |AAx"| 11 + (OPT + ||Ax)")))) by the optimality of f
E (OPT + ||Ax ||:)
This completes the proof of Theorem 12
B.3 CONCENTRATION BOUNDS
B.3.1 PROOF LEMMA 1
To prove Lemma 13 we rely on the following concentration bound provided in Lemma 14 and provide the proof in Appendix B.3.2
Lemma 14. Let A E TRaxd f Lip 6 E (0.1) be sufficiently small and A be an n x n diagonal matrix satisfying that Au 0 and w/ (AAA) d/n for all [ni]. Additionally, suppose that Rd
and V E I are fixed vectors, 0 S a S 1, R is any value that R 2 | F is any value that F2V V |A(f(AE) and T is any subset Rd that {z} C CT ( Rd ||AAr| R}.
Let S be an n-by-n random diagonal matrix in which the diagonal entries are i..dd o Ber(() variables. When conditioned on the event that
u)) V and sup [SA(f(Ax) ((AT((AAA)((AA)))) f(A))) S zET
it holds with probability least 1 8 that
sup (I]SA(((Az) =ET
->> [SA(f(AT) - - S)IEE [A([(A)) -NN -
d1v4 eV -R++" RT. r.
1 g ) log de log sd + vlog log
SC.
on
where C is an absolute constant and
r (d Rd (d4 ((m)) p' R
when 1 / when p 2.
(21)
R
With Lemma 14, we immediately have the following two corollaries.
Corollary 15. A E Raxd, E Lip,, E Raxx, E Rd, a E (0, RE R2, T Rdd and S E Raxn be as defined in Lemma and satisfy the same constraints. Additionally, suppose that 2 d4vll /n. When conditioned on the event that ||SAAz| & ||AAx for all E Rd., it holds that
with probability at least
sup [|pp|((A(AAA)) - f(AE))I [IA(f(Ax)= f(AE)) =ET
d
R. (log&t d log ā (1105
S..
(am) IVp
where C' is an absolute constant.
Proof. In Lemma 14 we take = f(Ar) and to be constant. Note that V = [[SA(((A))
B 0. For any T, we take F 2n R then
< ||SA(Ar Ax))
by the Lipschitz condition by the assumption of ||SAAr < ||A by x, T
- ||A(Ax - Ar)
< 2
and hence the result follows by Lemma 14
18

---

Published as a conference paper at ICLR 2025
Corollary 16. Let A E Raxd, LipI, (0, 1.A E BOX", E R E (0,1), R.R.FE - Rd and S E Rux" be as defined in Lemma 14 and satisfy the same constraints. Additionally,
suppose that Z at ne
and Z eR. When conditioned on the event that
[[SA(((A) - b & [IA(((A)) -b and sup [[A(((Ax) f(AE))(l 2 F, ZET
it holds with probability at least 1 - 8 that
(lss(()(((((A)) - 1b |S - ((I((AAA))))))((((((AA))))) - - -IA(f((AE) -b) b)]] rET
SCT.
(1og& dy
log n2 Ed
log
1
where C is an absolute constant and T is as defined in 27
Proof. In Lemma 14. we take v = Note that we have = [A(f(AA)
bb -
and hence the result
follows, noticing that the last term in the error bound of Lemma 14 is the dominating term. n
Now, ready complete the proof of Lemma
Without loss of generality, we can assume that n Z d5V1/EPV2 We rely on Corollary 16 in this proof. To apply the corollary, we need to pick suitable subset T so that the output T. The set will be defined through suitable bounds for and F and the main part of the proof will focus on obtaining these bounds.
Proof of Lemma 13
Before doing so, we present some useful incqualities. First, by Markov inequality, with probability at least 0.99, we have
SA(f(AF) - b)lb < (00])A(((A)) b)
(22)
We condition on this event in the remainder of the proof. By the optimality of i, we have [SA(f(A)) b| + =||AA& < [[SA(((A)) - b)ll + =|
(23)
implies that, by 22 and (3).
100 A(f(AE)) 6) + |
| SA(f(AA) b]1 + |AAE <
(24)
-o
Throughout the remainder of the proof, we assume that
d
1 log log( 1/e)
nevve poly log n and
so that the error term in Corollary can can be upper bounded
r loglylogn n+ + Ilog(1/6)) (o/()) S SEFOR
where 3 = A and 0 = (1 - ))) v J. Note that 3 + = 1.
Bounding F' in Corollary 16
We would like to first use Corollary 15 and let
T- {I 1dd || S Ro }.
Now, check the conditions. Our choice of satisfies that > poly log n, thus, by Lemma 66] S a constant-distortion subspace embedding for AA with probability at least 0.99,
i.e. ||SAAz & 2| AAxll for all x E IRd. Recall that
100
Ro
[A(((F))
b)lb + |AA
19

---

Published as a conference paper at ICLR 2025
Hence, by Corollary
13
with our choice of a and R Ro, it holds with probability 0.99 that
- (As) =
sup
[|A[[(x)) [( - CieRo:
(25)
where C1 is constant that depends only on Below we shall use C2 Cs,... to denote constants that depend only on p. Conditioning on the event 25 follows that
|A(F(A)) ( {( < - - f(A))>Iı + Cielo
S 2" (ISA(F(AB) b][b3 [[A(f(AZ) - b)|B) + CLERO
(1)
S 2" (ISA(F(AZ) b][;; - = [[SA(((A)) - b)[{) + CiER
2" (21ISA(f (AF) b)]l + + AA ((]) Ci
(B)
100 [|(f(()) - b)1l + |AAE| p)
$ 2" (2 100 1 - =||AΛΣI;) + CIE(
I (C((AA((AEE) - + + =
for some large constant C22
(26)
where (A) is due to (23). the optimality of i, and (B) to 22 the Markov inequality for [[A(f(AT) b) by. and the definition of Ro.
Define Fo to be the RHS of (26 i.e.
Fo C2(IAA[(AZ)) b) +
We preview that the set T we use in Corollary 16 contains the element x satisfying the inequality
[|(f(Ax) - f (A - Fo
Hence, (26 suggests that is in the domain of interest and hence Fo is the bound will use in Corollary 16
Bounding R in Corollary 16 Now, we would like to use Corollary [6 Recall that
100
R
[(f(AE)
1 + ||
We can apply Corollary 16 with Rg but it will give weaker result. However, we shall still use this weaker result and improve the bounds iteratively. Specifically, we shall define R2 based on R ensuring that R2 & Ro and that each Rg has the form of X, (AA) b)lB + Y|||AA for some Y, 2 (for example, Xo 100 and Yo = 1). Furthermore, let
T, =
|| < R. and [|A(f(Ak) f(AT) F
so that T, S. To. More specifically, we shall use T; to estimate an upper bound of ||A. and define Ri+1 based on the upper bound, ensuring that F E T.. This guarantees that T. satisfies the subset condition in Corollary I6 We shall also verify other conditions of Corollary [6
It is clear that R2 < Ry S 1 Fo- By 22). we have [[SA(](AØ) - b)llg S [IAS(Aa)) b)l and, by 25 and the fact that T, S T- we have
sup [ISA zET;
(( < sup (|((((x)) (a00))(((A))) f(AF)) CieRo $ Fo-
ZET:
We invoke Corollary 16 with our choice of a. R R2 and F = Fo. Hence, with probability 1 - 8.
sup [I]SA(f(Ar) - 1| [[SA(f(A)) - b)]l)) - (IAA(((A)) - 6) 11 -IA(((A))))) - b)]1() ZET:
< C3 ER Fo for some constant Cg.
(27)
To use 27
we would like to argue that the solution à E T, For To. we have
||A <
Ry
by 24 and [|A(f(A)) - f {A by 26
and hence à E To. From now on, suppose that å T; and we will argue that T
20

---

Published as a conference paper at ICLR 2025
We continue to bound (27 Assume that KY,Xx; 2 for some K 2 1. then we can upper bound
Rd F8 as follows.
Rº P (XIIIAU((A)) b)l + X|JAAEI)) 3 C2 (IIA((AA)) b1 + =1)
- C2 (X.IIA(((AZ) - + XX]AAEIB)) (IAUFCAE) b)1 X; || AA
KY,
C2 - X; (X.IIA(((A)) b)1 *YY]AAAFE)) note that B -+0=1 =1
(28)
Thus,
|
(ISA(J(AF) 1I11 -165-11300 -IA(/((A) b)TE)) ||А
(IA(((AA)) - 6013--111 (AAA((((E)))) - + =R 13) + |
by (7
From our assumption, we have
[[A()(A)) 6) -A]
<=([AA([ b) +=||AAZ||
$ SER Fe by the definition of Fb and Fo 2 R4
In other words, we have
for some constant C4 ||AA$| - C4 (R. 13)) + ||A=I|
C2
s C4
X; (XiIIA(((A)) b)Ib KY, KY, ||
s X X4+1||A(fAA) 6)1B3 |AAEIE
(29)
where
X = -CCCX! and Y = 1+ C.CKY,
X²
Define R2+1 to be the minimum of Rg and the expression in (2)) i.e.
Ri+1 Ro A (X++1 (Af) b) + Y | |AA
We immediately have à E T.+1, which needed to iterate the argument.
Let Xo 100/s and Yo 1. By induction, one can show that
100 (1-0y*
1-
X; C5
for C5 = C.C. Then Co < X; < 1000 /e for some constant Co for all i S r, thus Y:+1 S
1 + CrY, & CgY, ( for some constants C7 and Cg. When ~ip log log(1 /e), have
X, S Co and Y, < Ca(Ca) = poly log
We shall also verify that KY,X,, 2 E for some E. Indeed, Y/X, 2 1/(100C)/") /E) 2 E/K for
K 100c
Iterating the argument above r times. The total failure probability is at most 8r + 0.03 = 0.1 since that
8 1/r. It then follows from 27 with
[[A(f(*)) - b) 1E [A()(AA) b
< [[SA(((A)) b)l - -allg-1SSAP (I b)1B
C3 ERR S =| + Cs FR by the optimality of #
S =||AΛE 1 + ((X))I)A(((())
b) + Y-IIAAa)g) by 288
poly log !) ||A
$ [[ b) +
Rescaling poly log 1 to proves the claimed result of the theorem.
21

---

Published as a conference paper at ICLR 2025
B.3.2 PROOF OF LEMMA 14
In this section, we will prove Lemma 14 Recall that an arbitrary fixed vector in R2 is an arbitrary fixed vector in R", V = [[A([(A)) - v) Ip. R 2 | F 2 V and [
R ||AAT 1 - R Also, would like to bound the following expression
sup|(]SAA[[A>>)) I) [[S(S((A)) =)]l (IA(S((x)) 1) (IA(((A)) .)|
xET
which can be written as
Sup ZET
( ()AA)( -); (U)(E)) -)),))
(30)
We shall bound
30 from above by, up constant factor,
divE
EV + an R+T. poly log n + V log 8)
(31)
with probability 1 1-0 6. Recall that, as defined in (1
(d/(am)) R F
when 1 1 p S 2
r
(d# (am)) (z
when p > 2.
d' R from Lemma 19
We preview that the first term <V comes from Lemma 18 the second term
and the third term r (poly log n + Vlgg })) from Dudley's 's integral (Lemma useful lemma.
We first present
|| let T be set that {a} T S {x Rd ||Az s R}. }. Also, let wi,.... Wn be the Lewis weights of AA. It holds for all x E T and E [n] that
Lemma 17. For any R 2
[Aa([(Ax) - ((AT)) S 2d vvv wi R².
Proof. Note that [A=(((Ax) - f(AT))1 & |An(Ax A
by the Lipschitz condition
s d tे. wi ||AAT - AAøIp
by Lemma d)
Since x, F are both in T, we have
AA - AAT S |AAx|p + ||AAø||p S 2n
The desired result follows.
Define the set G of "good" indices to be
d zto w R²d
G== d=1
1-ite i [
[As([(AT)= v)al S
(32)
We shall first take care of the terms with "bad" indices in 30 i.e. the indices not in G, and hence obtain the first term eV in (3T). We highlight that only the property of the nonnegativity of the diagonal entries of S is used in Lemma
Lemma 18. For any R > || and > let be a set that (a) CTC(C E IR ||Ad|E S
R) } and G be the set defined in (32. Suppose that an n-by-n diagonal matrix with nonnegative diagonal entries and
[[SAf((AE) - - UI
where V [[A(S(A)) u)) Then, we have
SS) - u)(P)) SEV.
sup T
Gg
22

---

Published as a conference paper at ICLR 2025
Proof. To ease the notations, let
Ux == f(Ax)
for all R and
A = As for [n].
Note that by the triangle inequality,
ESs - (I) w)sl ((uz - -)) S >E (S + 1)>p w)/lP 1(ux u)
RgG
ieG
Furthermore, by the inequality ||a|0 66/0| S pla bl |a|0-1 + 16|0_1/. we have
X w)al" - I(ux v)slp S p/>,(u>> uz)il ||A:(u= r).l" + Dasuu u)(p
For any & G and T, by Lemma 17 and the definition of G, we have
1 ug)a 2s As u)el
(ar(u, - v).l & (Ar(uz - ux)aal (u - -) $ (1 (r - -))a
follows that
22|1(1 - w):l? 1(uz o){(" Selssux= v)dlp.
which implies that
Σ
(S 1))((((us, u):lp 1uuz (luz-rii1) r):1²)
sup TET
kEG
n SSh ()) Se. V, u) SE S -1)
iGG
where we used the assumption of the lemma the last step.
Now, we also define the set of indices whose term has a high Lewis weight within G. Let
sPd
J J:= iEG W;
(33)
n²
We now take care of the terms with low Lewis weights in (30p. i.e. the indices i & J, and hence
obtain the second term d'Y in 31p. We highlight that only the property of the diagonal entries an
of S being in [0, L is used in Lemma 19
Lemma 19. For any R > ||A and e > let T be a that (a) CT E |AAx S
R } and J be the set defined in (33). Suppose S is n-by-n diagonal matrix whose entries satisfy
0 < SR < 1 for any a > 0. Then, we have
1 an
sup T
Σ (S ()(((((()))))))))))))) o),P I(f(A)) w)(P)) S
R.
EEGUJ
Proof. To ease notations, let
Uy = f(Ax) for all x e Rdd and A = Ai
for i [n].
Note that by the triangle inequality,
Σ Sh () u))1 1(u2 v){l') KEGUJ
Σ
(S.. + +1) -),," -1((= Pl.
iEGUJ
23

---

Published as a conference paper at ICLR 2025
Since i G, by Lemma 17 we have
1 - xेत wi Ro.
(u v):ll S Aeeuu - us)el + Pur - 1))1 S (2 +
which, together with & J. implies that
11,(uz u)/l d
d
w.R S
n²a R.
Recall that we assume S - a Therefore,
sup #ET
Σ IEG
(S% 1) (I(uz v),1 1(ug w){lP)
S Σ
_
d
S
dive
R.
n
an
VEGW
With Lemma 18 and Lemma 19 we only need to take care of the indices J. Namely the set of indices i such that
d प w R
edd d
(f())) v)d
and
We
E
n²
Now, we would like to bound the following expression
Σ 1)A (((((x) -) -)f
sup ZET
LEJ
We consider bounding its L-th moment and then apply Markov's inequality for some é to be deter- mined later. To that end, consider
+
= sup ZET
CS -() - w))1P)
By the standard symmerization trick, we have
OsO's S 2'
sup JET IEJ
Σ &
(34)
where & is |Jl-dimensional vector whose entries independent Rademacher random variable, ie. each & is uniform on 13.
Next, condition S. Recall that S is either a 0, let I C J be the set of indices such that S 1, For any Rd we define 2g to be the n--iienniinaa vector whose i-th entry is
a
(zx); == (fr(((Ar) - v) (f u
(35)
Also, we define a pseudometric be
pla, x') = [1(2x:) 1- - (zw)) for any x, e Bd
Σ (IAn)((Aa)) - (Aal--))(((Ar))) o))p)) 1/2
Recall that (-), means shrink the vector by only retaining the entries whose index is in I. Now, in order to upper bound the right-hand side of (34). we seek to upper bound
Eg supl aET
(Er, (zw)r))
Since F E T, the t-moment of the supremum can be upper bounded using Dudley's integral (Lemma 7 as
(1,
Diami(Ts))
supl (Er, (sn))il) $ See GeT
VlogN(T, (TT.p. mjar) + (Ve (VEDiammTT p1)
Eg
(36)
24

---

Published as a conference paper at ICLR 2025
Recall that (VT, is the covering number of T w.r.t p and that
We will prove in Appendix B.3.4
pp)
Vlo.NiT,P,, ,,, S a llgg d 1o10 n
and
Diam Sa. a.
(37)
Ed
where
dd RF IM frf
r
an Taking expectation over S, it follows from
(36) and (37 that
EsOg S (C'T)é
(log d log n
+ vē
Ed
Take f = log(1/8). By Markov inequality, it holds with probability 1 5 that
g5 sup
Σ &
S. (I(u -) I(ux v):P))
- r- log dv log ed
71 /l10
+ Vlo log
=ET VEJ
Note that is the third term in (31) Combining Lemmas 18 and
19 proves Lemma
14
B.3.3 DIAMETER ESTIMATES
In order to bound Dudley's integral in 37 we need to bound the covering number (T,, p, r). To this end, we shall bound the metric, p. and the diameter Diam p). The proof imitates the proofs in carlier works, c.g., Ledoux & Talagrand (1991); Huang al. (2024); Gajjar et al. (2024), on subspace embeddings and active regression problems.
Lemma 20. Let A Bx
R R", f E Lip A E RTx", [0. 1] and S E Rxx" be as defined in Lemma 14 and satisfy the same constraints. Suppose that 0 I a S 1, R 2 ||AA]] and
F 2 (AT) - w) Let T be set that {f} CT ||Am|| < R.. If is subset of J such that
((A)((A))o))) S a -
r) and sup](A(f(Az))
sET
then, for any x, x' E T and q = log( (.)) we have
,lx,2') K. (1Iw- 2
1/1 d -vp
200 - AA(( x0)1 [A1
and
Diam (T,P) p) S -d=-zvo 15p KR
where W ddaggw (1 ...., wa and
VadF/n K
for S p S 2: (ap-1 ddddd/1/// /n)2/p for porp? 2.
Proof. As in the proof of Lemma 18 we let u2 f(Ax) and X; As simplify the notation. We further define semi-norms ||u|],, max4e1 |u,] and || (Eer |n //p
For i E 7 and x' E T, we have
((zx): (z )al < || - w).l |Ar( - P)
p/ uv >ıl (Iv(u,, v).l-- + [s-(uz- -)
where the first inequality is due the definition 335 and the second the fact that [|a|l-166 S
bl ||a|=-1 + +bbp 1bp--11 It follows that
p(z, x'2 < Σ p² pll )el (1 - u)1 + 1is(us - p))
iEr
2 Σ
Muluu u (14o - 20-2 + 1ee - 20)))--2)
(38)
1E1
25

---

Published as a conference paper at ICLR 2025
When 1 S 2, we further bound (38) by
Li - )x (1>i(ux - v))( 2)) + |Ar(uzz - 2)
VEl
Smax
- -
- u Σ -
(1>cus - 20 + ao (uzz - 0),120-2)
'EI
iE!
We can then proceed as
Σ
Ac(uz - -x:); P- (1>:(ux - u))120- Aee(ugr 10 u0)
IE1
< X2((2z - -ue) 2 max - 10110-2,1(uu, 2)
iET
2-p
2p-2
(u - we))PP)
Σ X max 1 u)vl 1(ve m)
3m=2
S (| Uer) "|ppp' [)) ||A u)
For the ep-norms in the preceding line, we remind the readers that they have been restricted to the indices in I and do not refer to the f--norm of the entire vector.
Since us - u = (ug v) + (ue - uz). by our assumptions,
||A(uz u>ll?, I 2 [P-1(1 - 1) 19, + +1AA ug) p
a |A(uz - -b + a
aa. F.
(39)
Similarly,
||A(uz - 11 S |A(u - U]|I + || - v)lle S (at))
It follows that
x1 & |AAuu ( (aF) 2-8 x (aF)
2
I oF |A(uz u. Ml.
(40)
When p 2, we use the fact that |2,| 12/12022 || 2 for vector 2 and so we can proceed from
38
as
Σ (rruus - uz) (12r(1) - 0))120-2 Dulum - 20))
>> ||A(uz ux 117 -)),1lAa) v)llf.3 + 1oo v), u)A - 1)117,33)
IET
-||A(u, uz 117,00 (IA(U)) - w) |A(u, - w)llf-2 3+ + ||A( II - -
SaF- |IA(u - uz (II(uu= - v) 1/ + ||A(uz - v)1
by 39
SaF- ||(uu - u (IA(uu= - u) 11p + ||A( w)
Since
- & 1|A(u - uz)p - ||A(u= uills S (aF)
have
x'xx''² S (aF)2-² 7. ||Auz - us.)
(41)
Combining (40) and yields
pl 2') S (1 +1V+ |A(ur 20.1 and our next task upper bound [|A( u ),,
(42)
26

---

Published as a conference paper at ICLR 2025
Recall that wa 2d/n, we have by the Lipschitz condition and Lemma d))
11: - uo (A(Ax Az')aa - w dd IVE |AA I')1le
(43)
d के. | - x')lp
Plugging this result into (42 immediately leads to
(xx x') S K d zdp ||A( x1)1g
(44)
Alternatively,
d
(Ax - Ax))el
w
d
|Ai(Ar A A
ed
wi
since we
72
wpp
n²
d
|| 3/4 AAA(3 - -2)
recall that ||0|| w.
wi lay 19) 1/9
and thus
plx,²') S K. -.Ilw--AGe - 23
(45)
as claimed.
Finally, we bound Diam(T', p). By the definition of and (44), we have that ||A((z - 21)1 R. The claimed upper bound on Diam(T, p) follows immediately.
0
B.3.4 BOUNDING DUDLEY'S INTEGRAL
In this section, we will prove 37p. i.c.
(T,
VlogN(TT,,, (,T,, Sa r poly logn,
where I' is as defined in
To further simplify the notation, let
P A1 3
0= 0=
v
1-1v p
1
2' 7 DV2
2
Note that
log.V(T.ppr) S (lg (p(AA), Kd | AA(-) r)
by Lemma
1
=lggAV(B((AA), I AA(-)
R
Kdtt
log Log.N(Bw.p E), 11-1l Red
since 7/00 =
K
where colspace(W- and endowed with norms 11-1l for p 2 1.
Now, we shall split the integral domain into two parts [0, A] and [A, Diam for some & & be determined later (note that & p:3). Note that when S we have
(r/ ( ( 1.
27

---

Published as a conference paper at ICLR 2025
By Lemma 8 Case 1, we have (letting X 2/(KR(
Lo Vog.N(T. ((r.p
log log.N(Bu.pp (ll.pl. Rid K
}d)dr
u. (F), (F) KK) )
x V Vdlog Rd
% log ds
Vd. Kd. R
1
S Vd. Kdd 2log
X
d' K
S AAVilog A
(46)
To handle the integral over [Λ, Diam(T, p)], we bound
log.N(T.p.r) s log. Bp(A A), KIIW AA)
by Lemma 20
=log.V (B)A.V( W (AA()
)))))
R
= =log.N F.),
11- -lw.q
K
where colspace ( and endowed with norms || ml for g 2 1. We further divide the estimates into two cases. For E [1, 2). we invoke Lemma 8 Case 2 and obtain that
(T,)
(Tam(T.p)
1
/logN(TT.pp) $
log. Log.N(Buu (Bw, (E), (E); I1-1lwm
)
dr
R
K
Diam(T.P) 1
$ Rd K
log(
log
-dr
Ed
s R² K log n
Diam (T, ,)
log log
(47)
Ed
For 2, invoke Lemma
8 Case and obtain that
Diam(T.pp
Diam(T, .))
Vlg CoggNTT.pPra drr x
log log (Buu,p(E), (E), Illl
)dr
Ri K
Diam(Tipp)
d d 1/4
log n
R K
dr
Ed
d
log n Ed
Rd K log
Diam(T,p)
(48)
Combining 47 and 48 yields
Diam(T,o)
(o, S Sd log n
//lodloy
Diam(T.p)
(49)
ed
X
Recall that by Lemma 20
d where K (aF)
Diam (T,p) S d KR.
71
28

---

Published as a conference paper at ICLR 2025
Combining (46) and (49) and taking À (d" R ) (gd K), we have
Diam(T.p)
d' K
d' KKRP KR
log. p,r S Avdlog
+ + R K V
log
Vlog dlog
Ed
X
X d' K log d log ed
= =a =a. log d log ed.
B.4 REMOVING THE DEPENDENCE ON
In this section, reduce the log factors in Theorem 12 log(d/E) factors, thereby proving Theorem | This is achieved by first applying a sampling matrix S to reduce the dimension of the regression problem from poly(d/e) before invoking Algorithm B Algorithm 2 for the full algorithm. The sampling matrix 5 uses a larger sampling rate a which allows for controlling the error in Lemma 14 via Bernstein's s inequality with simple net argument instead of the chaining argument or Dudley's 's integral and thus avoiding the log factor from entropy estimates.
Recall that, in Appendix B.I uniformly. We will include the matrix A in our proof and abuse the notations by dropping the prime mark as indicated in Appendix [..]
we introduce the matrix A to ensure that the Lewis weights bounded
The following is a weaker version of Lemma 14 for reducing n to poly(d/e)
Lemma 21. Let A E Ruxd v. E R", f E Lip & > O, A E R a E [0, S E R Rx and
R R be defined in Lemma 14 and satisfy the same constraints. Suppose that 0 S such that on Z (d' /spt2) (og+)) log(1/e) and R Z ||AAr* (IA[[(AA" - u) Lei T
Rdd | ||AA> S R}. When conditioned on x E
[|SA(((E=)) - u>]1 S R,
holds with probability at least 0.99 that
sup zET
s(p((()A(((AA)) - -)1 [SA(f(Az") o)|[)) - (IA(f(Ax)- w)lB -[A(((AA(A))) w) e)
CCER,
(50)
where C is an absolute constant.
Proof. Recall that the error bound in Lemma 14 consists of three terms. By the same proofs in Lemmas 18 and 19] the first two terms remain the same, both of which are now bounded by CeR under our assumptions. The rest of the proof is devoted to deriving similar bound for the third term. Recall that we need to upper bound
sup Σ (tw)) IEJ
where is as defined in (35) and {&:} are independent Rademacher variables. We shall use net argument here.
Fix an T. Let W, (zx)) then EW; 0 and
W < (zx)dl
(A(F(Ax) - o)p ( - w)Pl
(Aa(f(Ax*) 2n "0-'(IAa(((AA)) [(Ax*)) ((A")))p((Aa((AAe)) o){l) IAa(J(Ax*) - u)
1
3 (IAr(Ax - -A -AA(((Ax*) - u))P))
29

---

Published as a conference paper at ICLR 2025
Now use (43) for the first term in the brackets and the definition of G in We proceed as
32 for the second term.
W - = ( = d (a8-ivooJAA(== x' 2D n
d
11v0 -
x
d V1
R.
72
anEr
A
Next bound
E(EieJ W??).
E
W?
Σ
ES (2+) $ 3 -(>))
Σ (2x)al
iEJ
SEJ
SEU
Note that
Σ iEJ
(22) & |A(f(Ax) - 1) [IA(f(x=)) E>ll
2 (1A(S 1(Ax))) +
(|A(S(A=*) - -)) -IA(S(A==)- u))1
2/ $ IAA(E - 2')1 (2 +DJIA(((AE" - -)
||Ax |AAx 1 -
27 R.
Hence
E Σ
W? S.75A.1 R.
2EJ
It follows from Bernstein's 's inequality that
12
Pr
Σ
W.
2 RR
S 2exp
A R - A nR
KEJ
(dd 772 R
< exx
A
< exp
CCd
provided that
d log 1 R/(ane") 7 d Rlog / (ans")
p> 2 1 1 <2
1 2 d A
or
( an
1
log 17
(51)
2722
To summarize, we have shown that when (5I). for each fixed x E that with probability at least 1 - 8 (where 8 = exp(-Cd log(1/n)) holds
Σ NEJ
S SR
To obtain upper bound for the supremum over E T, employ standard net argument. Let N T be an (nR* --net I such that | < (3/n)d. By a union bound, we have with probability at least 1 - N 2 0.99 that
sup Σ (..,())); ZEN KEJ
$ R.
For an AAx E T, there exists AAy N such that ||A((z - v)l1p I nRt. Thus
sup x
Σ (z)))
< sup
Σ St
+ sup
Σ
St,Cilz zy); S + sup
Se - zy)i
NEJ
yENV
KEJ
zET' NEJ
=ET
KE.
30

---

Published as a conference paper at ICLR 2025
We bound the enror term by Hölder's inequality
Σ
zy)e
VEJ
Σ (z Zn)ial
VEJ
Σ SullA u)dP (Aa(u, -))1''
SEJ
(u -uy)i (IAri(Re - -2)( |An(uy 1)(lp-1)
iEJ
(( Sg -aaaauu==e)) -w>ip)
1-2 1-3
S As: w)ss(' 1-3
Σ AA AW)iP))
Σ
iEJ
- ||SA((= - )) v) 1)| -
-))1B-11
Using the the subspace embedding property of S.
||SA(( S)lle 21IAA(2 -1)lp S 2n
and
[SA(f(Az) -))l
[[SA(((A)) - -(A (SA((()))))))))))))-)))))>)))))- -
< ||AA(x--05 x0) -
|AA( - =11) +|SA(((A="") 11
R R!-
Hence,
ShEEl2z 2n)s 2 nR.
sup xET
iEJ
Therefore,
Σ Sh nR KEJ
and the claimed result follows from setting 7)
To prove that the output & of Algorithm 2
satisfies 20 let x E Rd be
= arg min
| A(f(()) - b) 1 AA
zER
where A is the matrix ensuring the Lewis weights of AA are uniformly bounded. Note that we set the regularized parameter to be e² instead of e. We highlight that this x is for the purpose of analysis and we do not actually compute it in the algorithm. From now on, we set
d
5v1)+1
poly log m and a n(e4)p+2 log(1/s)
mevv2
where is the number of nonzero rows in S A which is the same the m defined in Algorithm 2
(
Note that our choice of a implics that
log(1/e) poly(d, 2). We preview that when use Lemma 21 we aim for the error of Ce" R in 50 Combining with the regularized parameter
e4y
e?, we set 4 in a Recall that our goal is to simply reduce n to poly(!) and thus these choices of
the exponents of E may not be optimized. Nonetheless, they are sufficient to achieve our objective.
We begin with using Lemma 13 with ă = x and S A as the matrix ensuring the Lewis weights of S AA are uniformly bounded. We now verify the conditions in Lemma 13 By Appendix D the
31

---

Published as a conference paper at ICLR 2025
Lewis weights of AA are uniformly bounded by ((d/m) with probability at least 0.99. Clearly, the output of Algorithm 2
satisfies
c arg min|| Aain||ssA([[(AA))) A(f(Ax) - b)ll + E ( ^xx
=ER*
and, by the optimality of x", we have
||5 (([(A=)) b)l A({(A))))))))))))) b)1b S ||
(52)
We need to upper bound ||А 13. By the optimality of àt we have
\(((A)) - b) E||5º AAæl| - ||SS A(S(A))) - b]]l =
which implies
1
15 A - I|SS A(J(A=)) I|
(53)
Since 5 is an fp-subspace embedding matrix for AA with constant distortion with probability 0.99 because of our choice of a and we condition on it from now on, we have
2
|I - 1 AA
(54)
Also, by Markov inequality, with probability at least 0.99, we have
|SS A(f(A=)) - b) - 100 A(f(Ax)) - b)
(55)
Plugging (44 and
55 into 53)
we have
|Ai
S A(S(Ax))) b)lB + 1|5 AAx
and when we further plug this into
(52) we have
||S A(f(A²))
b) 18 - 1 - 6)1
X 2 1
11:)
= (11S ((x()xx)) -)
+|p+ AAT
which completes the condition verification for Lemma
13
By Lemma 13 with probability 0.99, we have
I(I A({(A)) - 1) - ||S5 A(((x²)) - b)1B) ((AA)))) - -)I - - A(((4>)) - bb]1
S S 1-SSS(SSAA(L A(S(A=)) - b) + |55 11P))
By rearranging the terms, we have
- A(F(E)))
- A()(()))))())))))))))))))))))))) b)1 $ <|SS5
b) ||SS b)|,++ - ([(=)))( -)] 1S AAxx
Se SE-115AAA2
+ II (I5" bb) + 1|S AAx by the optimality of &
S (IIS* -))B) AAx
(56)
Now, we would like use Lemma 21 with LOPT + ||AA= || for Æ and hence we need to verify & E T. By the optimality of I. we have
||S5 ((f( b) + = AA < A(f(x=)) - b)l = AA="|
which implies
1 ||S <
(57)
g
Recall that we condition that 5 is an -usssace embedding matrix for AA with constant distor- tion. We have
| < A and ||SAAx=1 13 s 2|
(58)
2
32

---

Published as a conference paper at ICLR 2025
Also, by Markov inequality, with probability 0.99, we have
|SS A(f(Ar)) - b)lb - 100))A(f(Arr) - -]1 1000PT.
(59)
Plugging 58 and
59
into
58
we have
|A
OPT + ||Ar"11 l|g which implies & T.
E By Lemma 21 with our choice of a., with probability 0.99, we have
A( A (AA) b) |S b)]{)) (IIA(f(A)) - 8)1 -IA(f(A=')) b)|p))]
-5t - OPT + ||Ax= [p))
S (OPT + ||Axx"I;))
(60)
By the optimality of x", we have
-115 A( - b]1 -15'AA(((()=)) - + +
which implies
|| A(f(Aa) b)1b - A(f=A(((A=")) - b)11
$ |(5 - b)1b - A(S(==))))) b]1 =1AAA==11
Se. (E.(115A((AA
b)|b 115 (1') + 6 AAxx= || by (6))
By rearranging the terms in (60). we have |A(S(A)) -b |A(A(Ax)) bb Se (115 It means that we need to upper bound the terms A(f(Ax)) - b)lه and || AA=
b) + 115 AA ||8 + OPT + ||Ax*1I²)
(61)
For
I|se A(f(Ar)) b)p. we have
||S A(f(A))))
6) < A[ - =" by the optimality of x
S 1000PT + +=AIAA==*11
(62)
IP, where the last inequality holds with probability 0.99 by Markov inequality. For ||S AAx have
AA= IPP & |AAc"|| recall that S is an Ep subspace embedding.
To further bound the term
|AAx o ,,, we have
| IB
A(f - b)lb + |A by the optimality of x
100
OPT + |AAr IB
by Markov inequality with probability 0.99.
Note that this bound is not enough finish our proof. However, it implies that x E T where T is the set defined in Lemma 21 with Rt = 100 OPT + ||AA= IIg. By Lemma 21 with our choice of a", with probability 0.99, we have
((f(s))((A>))) - u) I| - ||5 A(f(==)) 1) (IAA(((A=)) 2) -IAA(((A=*)) - x)]3
1000
S Set.
OPT + ||Ax* (1))
8² E (OPT + ||AA 1B).
Then, have
||AA
[|5'A(((Ax)) -01 -11S:--1SSA(AAAAA A(F(E))) - -b)1z) + ||AA=*Ig
by the optimality of x
2A
[|((f(A)) DB [Ax)) - -u)1B + E ||AA** 113)
+ -|AAAx" "I3
OPT +
||Ax 1 by the optimality of x
(63)
Plugging
(62)
and 633 into 61. we have
[A(()))) b) OPT S (OPT + ||AAx*
This completes the proof for the query complexity without dependence on n. The overall failure probability is most 0.1 1 in the above argument.
33

---

Published as a conference paper at ICLR 2025
C LOWER BOUND
C.1 CASE OF E [1,2]
By Yao's minimax theorem, suffices to show the following theorem.
Theorem 22. Suppose that p 2 1, > O is sufficiently small and Zp (dlogd)/e' There exist a deterministic function f Lip,, a deterministic matrix A E Raxd and a distribution over E IR such that the following holds: every deterministic algorithm that outputs & E R which with probability at least 4/5 over the randomness of b satisfies 20) must make 9 ((d/e²) queries to the entries of b.
We remark that the lower bound holds for all p 1. and is tight up to logarithmic factors for p E 21. To prove Theorem 22 we reduce Problem 23 below to our problem.
Problem 23. Suppose that
1, d a positive integer. m (log de/ and 2md. Let
3
2
and
3
Let Do be the distribution on the -immeiiinn vector D' such that, for i = 1,...,
U2s -
u
with probability with probability 1
+E
U2
and Dj be the distribution on the (2m) (om))ddimesional vector such that, for i = I,..., m,
with probability 1 -
b2
with probability 5 +
Let b be the n-dimensional random vector formed by concatenating i.i.d. random vectors ((2), .....b....... where each b(0) is drawn from Do with probability 1/2 and from D₃ with probability 1/2.
Given a query access the entries of b, we would like to, with probability at least 2/3, correctly identify whether (99) drawn from Do D2 for least 2d/3 indices
By Lemma 9 and Lemma 11 any deterministic algorithm that solves this problem requires Q (dd//2) queries to the entries of 6.
Now, we construct the reduction. Let f be the function
if S -6
f(x)=
x
i < x < -4 44 < 50
1
if < a
Let a be the dimessiiaal vector such that
022-1
[
for i 1,...,m
a22
and A be the block -iack-di matrix whose diagonal blocks the E 2m
Given a deterministic algorithm A that takes f, A, E and a query access to the entries as inputs and returns & Rd satisfying (20), claim that & can be used to solve Problem 23 This claim is
proved in Lemma 24
Lemma 24. Let f. A, b be as specified above. There exists K(p), a constant only depending on p such that given an & E Rd satisfying
C @OPT+ || K
(Af(
-bl 51+
we can, with probability at least 99/ 99/100 (over the randomness of b), identify whether ((5) is drawn from Do Dr for least 2d/3 indices i.
34

---

Published as a conference paper at ICLR 2025
We need the next lemma, whose proof is postponed to Appendix C33 Lemma 25. Let be a -imeemmies vector in which
to prove Lemma 24
b/ = -uo urrr U, i 1= m.
22
Then
(a) it holds for x S 0 that [[(rr) - -V1,, > II5(-6u) VIp and
(b) it holds for x 2 0 that [f(ar) - 1' z [ff - b'l
Now we are ready to prove Lemma 24
Proof of Lemma 24 To prove the statement, we first give a bound for OPT. We have
OPT = min (fin)) - b1p Σ min ffxf))))x)))))))))))))))) 669) l| by the structure of A
(64)
.Elk"
2vER
and hence we can look at each term min,, eR (ax;)) - bllg individually. By Lemma 25 we have
min [[(())) 2,88
b1 min (llf(- 1 (l - b09))) (p)
(65)
For i = I....,dd. d, let h; be the number of occurrences of u [ in 6(0) Recall that (log /Ea.
By choosing the hidden constant to be large enough, we have by a Chernoff bound that for every i s.....d,, d, with probability least 1
100d
- + (1- - (1+
m
+ (1 + 3)
if ((0) is drawn from Do
4/ E
2
(66)
2 (1 3mmm] if (() is drawn from D₁
where 3 > is constant to be determined. Taking union bound, with probability at least 99/ 99/100, every i satisfies this condition. We condition on this event below.
Note that
[6a) (600 11 2(m k,) and [If(-6a) 100 2k:
By 66 if (00 is drawn from Do, we have
2(1 + 3)em < [f( - b0 S m 2(1 - 8m
[l((-aa) - 61 1B 2 m + 2(1 - 3m.
Similarly, if (() is drawn from D1, we have
[f((a) - b00 | 2 2(1 8)mm
m - 2 3m < Ilf( - 610 | S m 2(1 3)mm.
By plugging them into (65) and 64 have
OPT < d (m 2(1 - 3)mm)
Now, suppose that solution d satisfies
OPT + 8.
I - bib < (1 +
1 Ax
K
K
(1 (1+ + K
d(m -2(1-2211- - 3)em) 2md 62
Cp K
< md
2((1 ((1-8)-9
emd
md
(2 333)mm,
35

---

Published as a conference paper at ICLR 2025
provided that K Cp/B. Here Cp is constant that depends only on p.
We declare ((0) is drawn from Do if 2 O and from D1 otherwise. Suppose that our declaration is
wrong on & indices, then by Lemma 25
(I((A)) b1b 2 8 (m + 2(1 3)mm) + (d - E) (m 1 221 + 9)em)
md 2(1 + 3)mmd + 4g9m.
Therefore,
md - 2(1 + 3)mmd + 4atm & md - (2 - --33)mm
which implies that
8 { 5 4 Bd.
We can conclude that we have used an approximate solution & deduce the distribution of 6(5) for at least (1 - 53/4)e indices of = 1....,d. d. Choosing 3 = 4/15 and K = 4Cp completes the proof of Lemma 24
To finish the proof of Theorem 22 by Lemma 24 with probability 1/100 1/5 > 2/3, we can correctly identify whether bo) is drawn from Do D, for at least 2d/3 indices i, i.e. we solve Problem 23 Hence, we conclude that A must make (d(/=²) queries to the entries of b.
C.2 CASE OF 2 2
By Yao's minimax theorem, suffices to show the following theorem.
Theorem 26. Suppose that p 2 1, E O is sufficiently small and n Zp d/e². There exist deterministic function I E Lip,, a deterministic matrix A E Raxd and a distribution over b E H" such that the following holds: every deterministic algorithm that outputs RR which with probability at least 2/3 over the randomness of b satisfies (20) must make ((d/=") queries to the entries b.
We remark that the lower bound holds for all 2 1. To prove Theorem 26 we reduce Problem 27 below to our problem.
Problem 27. Suppose that O < & < 1, d is a positive integer, m - = 1/82 and n = 2mn. Let be the 2m-dimensional vector whose entries are all 1, i.e. u [1,,....,1] distribution on {v + (1/E) E (1/E) e and D1 be the uniform distribution on {u + (1/E) "e+t1...,,'
Do be the uniform
(1/E) e2m] where Ei...., 62m are the canonical basis vectors in 2m Let b be the n-dimensional random vector formed by concatenating i.i.d. random vectors 6(1), ...., b(d), where each (()) is drawn from Do with probability 1/2 and from D2 with probability 1/2, i.e. each ( is an all one vector with value 1/s planted at a uniformly random entry.
Given a query access to the entries of b, we would like to, with probability at least 2/3, correctly identify whether (99) drawn from Do or Di for least 2d/3 indices
By Lemma and Lemma any deterministic algorithm that solves this problem requires ((d/e²) queries to the entries of b.
Now, we construct the reduction. Let f be the function
0
if x < 0
f(x)
if < x x
1
if
Let be the 2m-dimensional vector such that
1 for i 1, ....,
0
for i m 1,... 2m
and A be the n x block-diagonal matrix whose diagonal blocks are the same a E 2
Given deterministic algorithm A that takes f. A, and query access to the entries of b inputs and returns â e Rd satisfying 20 we claim that & can be used to solve Problem 27 This claim is proved in Lemma 28
36

---

Published as a conference paper at ICLR 2025
Lemma 28. Let f, A, b be specified above. There exists K, a constant, such that given i R satisfying
IIf(A)) bll S (1+
OOPT+ |1
K
we can identify whether (6) drawn from Do or D at least 2d/3 indices i.
We need the next lemma, whose proof is postponed to Appendix
Lemma 29. Let 1' be 2m-dimensional vector in which all entries are except one of them is Then
(a) it holds for x S 0 that [f b 2 llf(-a)) Bl and
(b) it holds for 2 0 that [f(xx) bl llf(a) b' b'1lp:
Now we are ready to prove Lemma 28
Proof of Lemma 28
To prove the statement, we first give a bound for OPT. We have
OPT
min [(Ax) - b11B Σ min [(x;;) b0
(67)
=ER*
z,ER
and hence we can look at each term min min blg individually. By Lemma 29 we have
minllf(ax;) 10 min min(ll5(-o)) 1e IIf(a)) -b))
(68)
2.ER
Recall that m 6.. For i = I,....d.. d, if 6(0) is drawn from Do. we have
1 - + mm 11 (2 E)m
(I - 11 m + 8D 2m and I1((-a) - 60 (1 +
and, if ((0) is drawn from D,. we have
Ilf(-a) - 1 m+
2m
and
[l.((a) b10 (1 p m 12 (2+ mm
EP
By plugging them into (68) and
667,
we have
OPT < 2dm.
Now, suppose that solution & satisfies
E IIf(At) - b1b $ (1 + OPP +
Axxx1|
K
K
$ (1 + K
(2dm)
+
E
2dm
K
4edm
< 2dm +
K
We declare that ((0) is drawn from D, if and from D₃ otherwise. Suppose that our declaration
is wrong on É indices, then by Lemma 28
(IS(A)) blly < ((2 e)m + (d - ()(mm) 2dm + elm.
Therefore,
4sdm
2dm + sbm
2dm
K
which implies, when = 12, that
d
l <
3
completing the proof of Lemma 28
To finish the proof of Theorem 26 by Lemma 28 with probability 2/3, can correctly identify whether 5(0 is drawn from D, Dj for least 2d/3 indices i.e. we solve Problem 27 Hence, conclude that A must make 2 ((d/eP) queries to the entries of b.
37

---

Published as a conference paper at ICLR 2025
C.3
OMITTED PROOFS
Proof of Lemma 25
Suppose that d' contains A: occurrences of a -= [2] and 0 = k/m. Then
[[((a)) - B'llz 0() + (1 - ()())))))
where
g(x) -
f() --
and Mxx) = [-()))))))
f(x)
- 2
3
It suffices to show that both h(x) and g(x) attain a local minimum at = 66 when r S 0 and at x when I 2 0.
Now, we view the 2-dimensional vectors as points in RR2 For any E R. let ((x) be the point (f(x), [(=z)). Also, let 7 C R be the locus ((x) = [(()), i.e. 7 = ((x)) x E R.
It has a positive branch y- (((x)) x 2 0) and a negative branch 7 = (((x) x 2 0).
We first consider x I O. Note that ((-6) = (2,3) is on Y and x = -6 is the only value such that ((x) For g(z), consider the smallest ep-ball centered at (3. 2) that touches (2, 3) on its boundary. It is not difficult verify that this lp bp-ball does not intersect y at any other point. (Figure provides geometric intuition.)
3). Hence, we immediately have that l(x)) 0 attains a local minimum at x -66
Since y and y symmetric about I, can show the symmetric result for 2 0.
47-6)
4(-6)
(2:3)
61-47
c06)
x)
<100
CE1)
C00
Figure 2: Illustration of the locus 7 (left), the minimizers when x S 0 (middle) and the minimizer
when r 2 0 (right)
Proof of Lemma 29
We would like to show that the function [If(ax) attains local minimum
at = - when < 0 and at 1 when 2 0. Note that, by the construction of f. f(x) = f(1) = for all x
and f(x) = f(-1)())))) = 0 for all æ S Therefore, we now restrict our domain to be æ E [-1, 1].
Suppose that the index of the entry whose value is + is in {1....,m} m). Then
(a(r)) - di (1 f(x))* + (m 1)(1 [()))) + m(1 - f(-x))p
Note that we drop the absolute value sign because f(x) < 1 on TR. When -1 - S 0, we have
[lf(ax) - - (1 + )p (m 1) + m(1 2)
2 (1 + -) + (m 1).
where the equality holds if -1. When 0 < x < 1, have
(ax)) - 6' 111 (1
x> (m 1)(1 2;)² m
+
38

---

Published as a conference paper at ICLR 2025
where the equality holds if x = 1.
Similarly, we can prove the same result when the index of the entry whose value is 1 + in {m + 2m.).
D LEWIS WEIGHTS OF Row- NOW-SAMPLED MATRIX
In this section, we shall show the following theorem.
Theorem 30. Suppose that A E Raxd has uniformly bounded Lewis weights w,(A) & d/n. Let S be an n diagonal matrix in which the diagonal elements are i.i.d. a-1/p Ber (x) for some sampling rale a E (0, 1). When on Zp d log d when p < 4 or on Zp de log d when 2 4, it holds with probability al least 0.99 that w. (S S d m. where is the number of nonzero rows of S.
This theorem is similar to (Chen et al. 2022 Lemma A.3), where the sampling rates are proportional to Lewis weights and no assumptions on the bounds of w;(A) were made. Our proof is also similar.
Proof. Let Wi...., w/n denote the Lewis weights of A and suppose that S = diag J. We first show that with probability at least 0.995,
Σ 2
1-2 aaa!
Wi - (a,a))(a,,))
3 Σ 3
2 w
aqa
Here, the 3 sign denotes semi-positive definiteness. We prove this claim by the matrix Bernstein inequality. Notice that
Σ Wc 1 (oxa))(oraa)
E Σ
a Wy
a.a
where & are i.d.d Bar(a) variables. Let M Σ, w.
"a,a df M and X, (d(())T ww; 1-3 T(() then EX; = 0 and, by the definition of Lewis weights, ||a|11
2
1- L w.
2/p We bound w
1 w v
d
|
w S
a
a
an
Also,
Σ
E
5 a
1
Σ
w
2(1 3
||
Σ wi . w; > aa((a))
1-2
a
d
2/
Σ w1 "a((a))
an
2
d
|
an
d an
follows from matrix Bernstein inequality that
{
Σ X, 2 < 2dexp
amns)
Pr
-c d
< 0.005,
provided that an 2 n 2d d. This shows that
n)T Σ w. d((()) I1+1)I,
which is equivalent claim.
39

---

Published as a conference paper at ICLR 2025
When o; > 0,
-1
(oza;) T
Σ
W
1-3
(ora:)
$
0 4
2 T
Σ
1-3
agaz
1
0
1
Wi
1
a
and, similarly,
(osas)
(
(o:a,) 2 1+n
1 Wi
We take be constant depending on p for and 1/ V/(C)vd) for p > 4. It then follows from (Cohen & Peng 2015 Lemmas 5.3 and 5,4) that (S S wy (A)/a 2 d/(an), where i' is the index of the corresponding row in A.
By a Chernoff bound, with probability at least 0.995, m S an. The result then follows.
E ENTROPY ESTIMATES
In this section we provide proof of Lemma 8 for completeness. The proof is decomposed into the following three lemmata, Lemma Lemma 32 and Lemma [3]
Lemma 31. Suppose that Raxd has full column rank and W is diagonal matrix whose diagonal entries are the Lewis weights of A. It holds for p 2 1 that
log.N((w..p www/p//) 1l: t) S d log
Proof. This is standard result following from standard volume argument, which we reproduce below for completeness. Suppose that E. is the column space of W-1/p A and is endowed with norms I|-Ilar,p: Using the notation simplification defined in Appendix A we denote by Bw.p the unit ball of E w.r.t ll-lla..g i.c. Bud (w A)p Consider a maximal t-separation set N C. Bg.p. then the balls + B...p. (a E N) are contained in (1 + Bu,,, and are nearly disjoint (intersection has zero volume). Hence EPEN vol(x + & Bw.p)) I vol((1 + Bu,p)) that is, |N] vol( I vol((1 + Bw,p) leading to |N < (1 + 2/t)d, It easy to check that N is t-covering of (Bw.p. I1-Ila..) and it implies (BB.,, (W 1/P Il 1l.p t) S [N| s (1 + 2/t)d.
Lemma 32. Suppose that A gaxd has full column rank and W is diagonal matrix whose diagonal entries are the Lewis weights of A. When S S 2 and > 2, it holds that
log (W 1/p 1), I1l S 9vlogd (W-
1
Suppose that E is the column space of W-1/P A and endowed with norms II and an inner product (,, )w. We first have
Proof.
log (B o7 1) S log (Bw,ps I1.1llm. A) log.V 11 4
40

---

Published as a conference paper at ICLR 2025
Recall that Bu.p (W-1/PA) and Bu Bu.:(W-11/n) (l)))A)..
For the second term, we can
apply Lemma 33 directly and obtain that
log.V (Bu:2 1.l.:1 4) d2/49.
12
= 82
Next we deal with the first term.
We first consider the case 1 < p 2. Let be the conjugate index of and r 2 p' to be determined. Define [0, by
1
1 1- 0
p
2
For 2, y 2, by Hölder's inequality,
| vllar.p'' S 1| vllu. 1|:0 - yllurr S
22-
yll
This implies that
Bu.:2, 11-2., (2) 1/0
2 2/0
N (Bu,2, (1-p)))))p)))))) s log N/
rd2//
where the last inequality follows from Lemma
33
Since
1 p'
2
2
1 -
1
0
p'
-2
2
p
r
follows that
log.V BB. I1-luar.pp 1) x
2
rd/
Choose = p' V (logd),
2l
log.V (Bn (1u.22:l-llugrr. 2
2
2-p
By duality (Artstein et al. 2004),
2v
2
I-p
log V( 11-
2) S
Therefore,
2
2p
X
log.N (B 1o I1-lba.gg t) S
Ll
t2
Optimizing X yields that
12/221-p/2
log.((nnng I1-Ilm..g: 1) S
+
v log d
g
1P
This completes the proof for < S 2.
When p = Maurey's empirical method gives that (using the fact that, by Lemma 5),), 11-1 S [H in E)
log.N(B..1. 2m S log d
X2
and thus
log (B t) log d x2
X2 delg.
Optimizing À yields that
log.N(B...) I1:ll (B, t) S V log d/a
41

---

Published as a conference paper at ICLR 2025
Lemma 33. Suppose that A Raxd has full column rank and W is diagonal matrix whose diagonal entries are the Lewis weights of A. When p, q 2 2, holds that
d
log log.N(B (W-1/PA) w.g t)
g
Proof. Suppose that E is the column space of W-1/p A and is endowed with norms Il- and an inner product (, :w By Lemma b), there exist u1..... Ud E I2" such that
(Us uv) O, |luille, and Σ
1 for any i, I....,n..
Recall that Bu Bu ( (W-1/PA) and Bu.2 Bu Bw First, observe, by Lemma 5 that Bu.p C dd/2-1/9. B, thus
log (B (1=Il s log.N (Bu Il 01/2-1/1
and it suffices show that
qd
log.N' (Bw.2. (1-.lww
12
Let q' be the conjugate index of q, i.c. 1 g =
By dual Sudakov minorization,
log.N N (Bm22. 1l-laa
1 x 12
EgnNON sup ze Bun
Σ
gruli
By duality again.
E(.. sup se Bund
Σ
gels;
1g
Σ J:ul
m
10
Then,
1/0
geu:
W
Uis
wmg
1/9
5
BynN((..aa)
Wi
giulis
1=1
1=1
d
10
<
W
E
~
((O. 1g
1/9
n Σ
d
< (Eg
wy
since
Σ
" = 1
f=1
1=1
2 //.
42


Reviews:
[{"review_id": "Cier4yXb5D", "reviewer": "Reviewer_qzE3", "summary": "This paper presents and algorithm to provide an epsilon approximate solution to the active regression problem. They show that their number of query points is minimax optimal.", "questions": "Q1 - Following the impossibility result of Gajjar et al., how does your result compare?\n\nQ2 - Why are the probabilities different in Theorem 1,2,3.\n\nQ3 - In addition to the constant probability ones, do you have a high probability results, where the number of queries is a function of that probability?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1 - The paper is generally well written.\n\nS2 - The technical claims in the paper are generally well explained.\n\nS3 - The idea is interesting.", "weaknesses": "W1 - Literature review is a bit lacking.\n\nW2 - No numerical experiments.\n\nW3 - The presentation can be improved by first introducing the algorithm. In the current version, the algorithm is somewhat built up during the upper bound proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hAWEgQEbtE", "reviewer": "Reviewer_82LY", "summary": "In summary, this paper studies the single-index (label efficient) active regression problem of $\\min_{x} \\|f(Ax)-b\\|_p$, where $b$ is sampled as efficiently as possible. It contributes a $(1+\\epsilon)$-approximation, replacing the constant-factor approximations in the literature, with near optimal query complexities.", "questions": "**Questions:**\n- Line 148: why is this approximate?\n- Line 163: what is the relation between $\\overline{x}$ and $x^*$?\n- Line 172: what is this approximate inequality defined as?\n- Line 197: is this inequality exact?\n- Line 215: again, what is this inexact inequality?\n- Line 220: how do you conclude $\\hat{x} \\in T$?\n- Line 299: how do you apply (13) repeatedly, AM-GM inequality? Don't the regularization terms also accumulate?\n- Line 397: is the second line an inequality?\n- Line 423: how is the last inequality obtained?\n\n**Major Suggestions:**\n- There are too many approximative parts in the analysis, which hardens the verifiability. The writing should be improved to ease digestion.\n- Line 68: improvement from [2023b] to [2024] is unclearly worded.\n- Line 191: error terms need to be expanded and explained more clearly.\n- Line 278: need more intuition into (10) and (13).\n- Line 461: this multi-dimentional extension could be better explained, feels a bit rushed.\n\n**Minor Suggestions:**\n- Line 16: V1, V2? better write these (and similar ones) as $\\max, \\min$ initially to ease reading.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Originality:**\nIt presents novel findings from theoretical and algorithmic perspectives.\n\n**Quality:**\nThe approach is well motivated, including being well-placed in the literature.\n\n**Clarity:**\nThe general approach is observable.\n\n**Significance:**\nRegarding potential value and impact, the paper has the goal of better addressing a known application/problem, namely single-index active regression, with new theoretical findings of improved query complexities.", "weaknesses": "The submission is not sufficiently clear, with many occasions of ambiguous wording. \nIt seems technically correct but hard to gauge at various times. \nThe experimental analysis is missing, hence not rigorous or reproducible. \n\nThe paper does not sufficiently support the claims. A key issue is that the analysis accompanying the theoretical results of query complexities includes many approximations, the significance of which are mostly omitted without necessary explanations, resulting in a somewhat lacking scientific rigor.\n\nThe paper could bring new knowledge of sufficient value to the community. However, it needs to be revised to better present its soundness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A8n6jBL2LJ", "reviewer": "Reviewer_rYLj", "summary": "The paper considers the problem of active regression where the objective is to solve the problems of the $\\min \\|f(Ax) - b\\|_p^p \\|$ where $f$ is an unknown Lipschitz function, $A$ is a known matrix. The learner aims to solve the minimization problem by querying only a fraction of elements of $b$. The problem has been well studied for $f(x) = x$. For the case of general $f$, existing results only obtain a constant factor approximation. In this work, the authors obtain a $(1 + \\varepsilon)$ approximate solution with general $f$ with a new algorithm and analysis.", "questions": "Can the authors elaborate why the techniques in Yasuda (2024) do not carry forward to the case of $p > 2$. As far as I understand, the hard instance needs to be updated where $1/\\varepsilon$ is replaced by $d/\\varepsilon$ and the analysis should work out. I am trying to understand what does not work out with this choice.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think this is an interesting paper overall. While the problem appears to be simple, there is quite of bit of machinery involved in establishing the results and designing the algorithm. I believe there are several novel aspects in the algorithm design and analysis that might be useful in general for future studies in this direction.", "weaknesses": "I don't see any glaring weakness in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6dgK6SikCS", "reviewer": "Reviewer_kECa", "summary": "This paper studies the problem of learning single-index models in the active learning setting, where given a dataset $(A,b)$ and an activation function $f$, the goal is to output some $\\hat{x}$ by querying the entries of $b$ such that $||f(A\\hat{x})-b||_p$ is close to $opt$, the error of the best $x \\in R^d$. Previous works that study this problem give several upper bounds for the query complexity for different $p$, but can only approximate $opt$ within a constant factor of $C$. In this work, the authors develop active learning algorithms for this problem with different $p$. For $p \\in [1,2]$, the query complexity of the algorithms is $\\tilde{O}(d/\\epsilon^2)$, which matches the lower bound provided by this paper. For $p>2$, the query complexity is $\\tilde{O}(d^{p/2}/\\epsilon^p)$. In this regime, the paper also gives a lower bound of $\\tilde{\\Omega}(d/\\epsilon^p)$.", "questions": "1. I would like to suggest the authors improve the presentation and move some related background from the appendix to the main body of the paper. \n\n2. There have been papers such as [DKR23] that show that even if the data is sampled from a Gaussian and the activation function $f$ is a ReLU, it is computationally hard to achieve $opt+\\epsilon$. Can you help explain the relation between these hardness results and the results in this paper? Given the hardness result, why it is still motivated to design algorithms that learns a $(1+\\epsilon)$-approximate solution?\n\n\n\n\n>Diakonikolas, Ilias, Daniel Kane, and Lisheng Ren. \"Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals.\" International Conference on Machine Learning. PMLR, 2023.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Learning single-index models and active learning are both central problems in learning theory. Compared to active learning for classification problems, active learning for regression problems is much less understood. This paper gives a nearly optimal query complexity for the corresponding $l_p$ regression problem for a wide range of $p$. The algorithm builds on a similar sample and learn frameworks used by previous works but uses several solid and new ideas to analyze and improve the error guarantee and the query complexity. The results and new techniques would be of interest to ML and theory communities.", "weaknesses": "I think one main weakness of the paper is its presentation. The paper itself is very technical and involves deep mathematical tools such as  Lewis weights that are frequently used for other problems such as subspace embedding. As a person who does not work on these problems and is not familiar with these tools, I found sometimes it hard to go over the paper as the related background is not clearly provided in the main body. Furthermore, I feel that to fully understand the techniques, the paper requires the reader to be familiar with the line of the previous work. For example, in line 219-line 226\n>we obtain the following concentration bound .... which has been the central tool in the work on subspace embeddings... In short, when the number of queries is m...\n\nThese statements are confusing for a reader who is not familiar with the technique and related literature. It is hard to get an intuition of how to relate the query complexity with the previous error analysis.\n\n2. Another weakness I found is the computational complexity of the problem. I think to implement the algorithm in the paper, one has to solve a sub-optimization problem, which I believe has a super-polynomial time complexity with respect to the error parameter $\\epsilon$. In fact, there have been works that show that agnostic learning single index model is usually computationally hard. (see my questions below) Given these hardness results, I am not sure whether it is still motivated to pursue $(1+\\epsilon)$-approximation, such a strong guarantee. I think adding some numerical simulations for the algorithm would be helpful to show the algorithm is useful and it is still reasonable goal to achieve $(1+\\epsilon)$-approximation for some reasonable choice of $\\epsilon$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)