Interactive Learning of Single-Index Models via Stochastic Gradient Descent
Authors: Nived Rajaraman
Yanjun Han
Venue: ICLR 2026 Poster (2026)
Keywords: single-index model
stochastic gradient descent
nonlinear bandit
Primary area: learning theory
TL;DR: We show that SGD, applied to single-index models (ridge bandits), naturally transitions from a burn-in to a learning phase. With the right step-size schedule, SGD achieves near-optimal regret across both phases for a wide range of link functions.

Abstract: Stochastic gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization, renowned for its empirical successes. Recent theoretical advances have provided a deep understanding of how SGD enables feature learning in high-dimensional nonlinear models, most notably the *single-index model* with i.i.d. data. In this work, we study the sequential learning problem for single-index models, also known as generalized linear bandits or ridge bandits, where SGD is a simple and natural solution, yet its learning dynamics remain largely unexplored. We show that, similar to the optimal interactive learner, SGD undergoes a distinct "burn-in" phase before entering the "learning" phase in this setting. Moreover, with an appropriately chosen learning rate schedule, a single SGD procedure simultaneously achieves near-optimal (or best-known) sample complexity and regret guarantees across both phases, for a broad class of link functions. Our results demonstrate that SGD remains highly competitive for learning single-index models under adaptive data.

INTERACTIVE LEARNING OF SINGLE-INDEX MODELS VIA STOCHASTIC GRADIENT DESCENT
Nived Rajaraman Microsoft Research
Yanjun Han
New York University
nra ja jaramaant aman@mmi wrwsoft.oooooooooooooo
sanjunhan@nyu.edu
ABSTRACT
Stochastic gradient descent (SGD) is a comeertone algorithm for high- dimensional optimization, renowned for its empirical successes. Recent theo- retical advances have provided a deep understanding of how SGD enables fea- ture learning in high-dimensional nonlinear models, most notably the single-index model with i.i.d. data. In this work, we study the sequential learning problem for single-index models, also known generalized linear bandits or ridge ban- dits, where SGD is simple and natural solution, yet its learning dynamics remain largely unexplored. We show that, similar to the optimal interactive learner, SGD undergoes a distinct "burn-in" phase before entering the "learning" phase in this setting. Moreover, with an appropriately chosen learning rate schedule, a sin- gle SGD procedure simultaneously achieves near-optimal (or best-known) sample complexity and regret guarantees across both phases, for a broad class of link func- tions. Our results demonstrate that SGD remains highly competitive for learning single-index models under adaptive data.
INTRODUCTION
Stochastic gradient descent (SGD) and its many variants have achieved remarkable empirical suc- cess in solving high-dimensional optimization problems in machine learning. Recent theoretical advances have provided rigorous analyses of SGD in high-dimensional, non-convex settings for range of statistical and machine learning tasks, such as tensor decomposition (Ge et al. 2015). PCA
(Wang et al., 2017), phase retrieval (Chen et al., 2019 Tan & Vershynin 2023), to name few. A particularly intriguing setting is that of single-index models (Dudeja & Hsu 2018 Ben Arous et al.
2021 (and generalizations
multi-index models (Abbe et al. 2022] 2023 Damian al. 2022 Arnaboldi et al.) 2023 Bietti et al. 2025)) with Gaussian data. In this framework, each observation
(Ie, 31) consists of a Gaussian feature xt (N(0, Ia) and noisy outcome
yt = f((0",((0))) xx1) +
IR : unit sphere in Rd, and E, denotes the unobserved noise. With a learning rate 7) > 0 and a random initialization 0, Unif( ) the SGD update for learning single-index models is given by
where
R is known link function, 0* E gd-1 is unknown parameter vector on the
O2+1/2
O241/2 = 02 (.00m((((()) ((((0() - 31 (1),, (I (I- -,07 Jar, Oc+1 = 100+1/211
(1)
Here, the first update is a descent step of the population loss + LE (f((0, x)) y)² at 0 O.. whose spherical gradien is estimated based on the current sample (Iz, y1) It is well known (cf. e.g. (Ben Arous al. (02T)) that the evolution of SGD this context exhibits two distinct phases: an initial "search" phase, during which the correlation (0,, 0*) gradually improves from 1/22/ to ((11,, followed by "descent" phase in which the iterates 0 converge rapidly to the global optimum ,", driving (0, 8*) arbitrarily close to 1.
RReaal that spherical gradient a function f gd-1 - defined as V DJ the Fuclidean gradient, and 37 the derivative in the radial direction.
01 oF 0r
where D

---

Beyond statistical learning, single-index models have found applications in interactive decision- making problems, including bandits and reinforcement learning, where the reward a nonlinear function of the action. An example is manipulation with object interaction, which represents one of the largest open problems in robotics (Billard & Kragic 2019) and requires designing good se- quential decision rules that can deal with sparse and non- inarr reward functions and continuous action spaces (Zhu et al. 2019). This setting is known as the generalized linear bandit or ridge bandit in the bandit literature, where the mean reward satisfies [ir:]ae] = =(((0, ax)) with a known link function f. Classical results (Filippi et al. 2010; Russo & Van Roy, 2014) show that when 0 < 9 S (x) S C2 everywhere, both the optimal regret and the optimal learner are essentially
((000)))))
the same in the linear bandit case (where ((x) = x). Recent studies (Lattimore & Hao 2021
Huang et al. 2021 Rajaraman et al. 2024) have considered challenging settings where [((x) could
be small around x = 0. This line of work yields two main insights:
While the final "learning" phase has the same regret as linear bandits, there could be a long "burn-in" period until the learner can identify some action a with (0*,") .u)) = Q(1);
2.
New exploration algorithms are necessary during this burn-in period, as classical methods such as UCB are provably suboptimal for minimizing the initial exploration cost.
In response to the second point, this line of research has proposed various exploration strategies for the burn-in phase that are often tailored to the specific link function f and rely on noisy gradient estimates via zeroth-order optimization. In contrast, SGD offers natural and straightforward alter- native, as its intrinsic "search" and "descent" phases align well with the "burn-in" and "learning" phases encountered in interactive decision decision-making.
This paper is devoted to a systematic study of SGD for learning single-index models, including the aforementioned challenging setting where fa(x:) could be small around x: 0, within interactive secision-making settings. In these scenarios, the actions ae are no longer Gaussian, prompting us to adopt the following exploration strategy:
0+ V o70, + 0.74,
Z4 ~ Unif (faest-1:0 0a)
(2)
where an additional hyperparameter o, E [0, 1] governs the exploration-exploitation tradeoff. After playing the action 0₂ and observing the reward rt, we update the parameter 0, via the same SGD as Equation T
02+1/2
12+1/2 = 0, -)((((((;;)a)) - rz) ((0r, (I 0.0, )oz, 0.t1
(3)
||0,+1/21|
By simple algebra, the stochastic gradient in Equation 33) is also an unbiased estimator of the popu- lation (spherical) gradient of 0 - JE (f((8. a)) - r)² at f = 9r, with the distribution of a given by Equation (2) and the reward r = s[(0' a)) + Our main result will establish that, for broad class of link functions, this SGD procedure, with appropriately chosen hyperparameters (7,, or), achieves near-optimal performance in both the burn-in and learning phases.
Notation. For E Rd, let ||a||] be its & norm. For y E Rd, let (x, v) be their inner product. Let gd-1 be the unit sphere in Rd. Throughout this paper we will use 0* E gá to denote the true parameter, 6g denote the current estimate, and m, = (8* (1) E [-1, to denote the correlation. The standard asymptotic notations o, O Ωt etc. are used throughout the paper, and we also use Ô, Q etc. to denote the respective meanings with hidden poly-logarithmic factors.
1.1 MAIN RESULTS
First we give a formal formulation of the single-index model in the interactive setting. Let 0* e E be an unknown parameter vector, and AA = gd-1 be the action space. Upon choosing an action a, E A. the learner receives a reward r; =((00, ,,))) for a known link function f [-1,1]]- and an unobserved noise e, which is assumed to be zero-mean and I-subGaussian.
Remark 1. The scaling considered here differs crucially from the prior study on learning single- index models under non-inter intiittrreetive environments (such as (Dudeja & Hsu 2018 Ben Arous et al. 2027) with Gaussian or i.i.d. features). In the non-interactive setting, it is usually assumed that Fe (0, Ia), so that |2:|] x Vd. In the interactive setting, we stick to the convention that actions
2

---

belong the unit Ey ball. in line with settings considered in the bandit literature (Filippi et al. 2010 Russo Van Roy 2014; Rajaraman et al. 2024). As a consequence, sample complexity com- parisons between the interactive and non-interactive settings must be made with care. We discuss this in more detail in Section 5 and compare with results established for online SGD with Gaussian features (Ben Arous et al. 202 after normalizing for the difference in scaling.
Throughout the paper we make the following mild assumptions on the link function f. Assumption 1. The following conditions hold for the link function f:
1. (monotonicity) f f [[-1.]] + [-1,1] 1] is non non-decreasing. with ll - 1;
2. (locally linear near x 1)0 < 71 S fx) S 72 for all E [1 - Yo, 11, with absolute constants Yoo 71, 72 > O. Without loss of generality we assume that "to I 0.1.
In Assumption the monotonicity condition is taken from (Rajaraman al., 2024) to ensure that reward maximization is aligned with parameter estimation, where improving the alignment (0", at) directly increases the learner's reward. In addition, when comes to SGD, we will show in Sec- tion 5 that the population loss associated with the SGD dynamics in Equation (3) is decreasing in the correlation my (#*,6) only if f is increasing. Without monotonicity, there also exists a counterexample where the SGD can never make meaningful progress (cf. Proposition [ Similar to (Rajaraman et al., 2024), this condition can be generalized to ʃ being even and non-decreasing on [0, I], which covers. for example, f(z) |x|| for all p > 0. The second condition in Assumption [ is very mild, satisfied by many natural functions, and ensures that the problem locally resembles a linear bandit near the global optimum a 8*. Finally, not exclude the nontrivial scenario where fz(x) is very small when x = O.
emphasize that this local linearity does
Our first result is the SGD dynamics in the learning phase, under Assumption 1
Theorem 1 (Learning Phase). E,t E, > 0. Under Assumption | let (at, 02)121 be given by the SGD
evolution in Equation 2 and Equation 3 with an initialization O2 such that (0,, 0*) 2 70/4
1. (Pure exploration) By choosing
ē A (.) and of = 0(1), it holds that my 2 1 - E with probability least 8f, with T Ō
2. (Regret minimization) By choosing 7). 0 1/2 2) and of E Jz A1), with probability at least 1 8T holds that (1(1- (m.)) Ö(d/T).
Both upper bounds in Theorem are near-optimal and match the lower bounds Ω d" and ((dvT) for the respective tasks, shown in Theorem 1.7 of (Rajaraman et al. 2024). In other words, SGD with proper learing rate and exploration schedules achieves an optimal learning performance in the learning phase, given a "warm start" 02 with (0,,0') 2 - -o/2. 2.. To search for this "warm start" through the burn-in phase, we additionally make one of the following assumptions.
Assumption 2. There is an absolute constant co > 0 such that f((x) 2 co for all x E [0,
Assumption 3. The link link function f is convex on [0, 1].
Specifically, (assuupptoon[aanna cover two different regimes of generalized linear bandits: Assump- tion 2 corresponds to the classical "linear bandit" regime studied in (Filippi et al. 2010: Russo & Van Roy 2014), and Assumption 3 covers the case with a long burn-in period where f'(x) small
at the beginming, e.g. in (Lattimore & Hao 2021 Huang et al. 2021). We will discuss the challenges in dropping the convexity assumption for the SGD analysis in Section 5
Under Assumption 2 or our next result characterizes the SGD dynamics in the burn-in phase.
Theorem 2 (Burn-in Phase), Let â > O, and Assumption i hold. Let (or, 0z)ez1 be given by the SGD evolution in Equation 2 and Equation 33, with an initialization 02 such that (01, 00) 2 v
1. Under Assumption by choosing Th:
( and o =(1), it holds that myr 2 1-70/4 / with probability at least -T, where T (
2. Under Assumption 3 by choosing an appropriate learning rate schedule (cf. Lemma 8 and
of = O(1), it holds that mrr 2 1 - 7 with probability at least 1 - 8T, where
11-004
T T= (
(INOVV f'(m)z F'(m)zam) dm)
m
3

---

Corre on
1.0
Condution
1.0
0.9
0.8
0.
0.7
0.6
0.5
0.4
0.3
0.2
50009
20000 30203 40000
70000 #0020
(a) Evolution of m. (0', 02) averaged across 100 runs. The shaded region plots one standard deviation.
(b) A single trajectory of (0" 0z).
Figure 1: Correlation m, (0.. 8*) plotted function of t in d = 20 dimensions, for the cubic link f(x) = x² We run interactive SGD with a constant learning rate 7) = 0.002 for all t, using an exploration schedule with a, 0.5 until m, reaches 0.7 and
0.2 thereafter.
Note that for bility. A simple hypothesis testing subroutine in (Rajaraman et al.) [024 Lemma 3.1) could further certify using (((f(1/Vd) f(0)) -) samples. Therefore, combining Theorem the following corollary on the overall complexity of SGD.
Unif the condition (0",01) 2 1/vd d is fulfilled with constant proba-
and have
Corollary (Overall sample complexity and regret). Under Assumption | and Assumptioo 2 or the SGD evolution in Equation (2) and Equation (3) with proper (M), 0z)211 and a hypothesis testing subroutine for initialization satisfies the following:
1. (Pure exploration) For E O, mr 2 with probability least 8T, where
T = 0 J
1-70/4 m
d² =
dm +
f'(m)a 1/228)
2. (Regret minimization) For 8 > 0, with probability at least 1 - 8T, the regret satisfies
T
S f. J'(m)z dm + dvT)))
11000/2
- f(m))) Ō min [T de
Under Assumption Corollary yields an overall sample complexity bound Ō /E) and a regret bound Omin (T, d dvT)). both of which are known to be near-optimal, e.g., in the case of linear bandits (Lattimore Szepesvári, 2020 Wagenmaker et al. (022). Under Assumption 3 the upper bounds in Corollary also match the best known guarantees in (Rajaraman et al. 2024). using different algorithm based on successive hypothesis testing. In the special case f f(x)) x. with odd
2 3. SGD achieves a regret bound ([min[T.cm d" + dvTT), which is near-optimal (Huang et al, 2021 Rajaraman et al.) (224)). By contrast, many other approaches, including all -on-intereettve algorithms (in particular, non-interactive SGD) and UCB-based methods, provably incur a larger burn-in cost of ((d++)) (Rajaraman et al. 2024). Therefore, it is striking that SGD attains optimal performance even the burn-in phase, while simultaneously staying optimal in the learning phase. Taken together, these results highlight SGD natural, efficient, and highly competitive algorithm with near-optimal statistical guarantees for learning single-index models in the interactive setting. As numerical example, Figure illustraates the evolution of m, obtained by SGD with constant learning rate for the cubic link f(z) = x², shown either as an average over 100 runs (left panel) or single trajectory (right panel). We observe that, despite the non-convex loss landscape and potentially non- monooonto progress, SGD consistently delivers strong performance during both the burn-in and learning phases.
1.2 RELATED WORK
Single-index models. tures has long history. The approximation and statistical aspects well understood in (Barron
Analyzing feature learning in non-linear functions of www-dimensional fea-
4

---

2002 Bach 2017); by contrast, the computational aspects remain more challenging, and positive
results typically require additional assumptions on the link function and/or the data distribution. Fo- cusing on the link function f. rich line of work (Kalai & Sastry [0009] (Shalev-Shwarte
al. [010)]
Kakade et al. 2011; Soltanolkotabi] 2017; Frei et al.. 2020; Yehudaí & Ohad [020] Wuj (uu22002))) has exploited its monotonicity invertibility to obtain efficient learning guarantees under broad distri- butional assumptions. At the other end of the spectrum, the seminal works (Dudeja & Hsu 2018
Ben Arous al., 2021) developed a harmonic-analysis framework for studying SGD under Gaus- sian data, sparking extensive follow-up research (Abbe et al.
2022 Bietti et al. 2022 Damian et al.,
2022 Ben Arous et al. 2022 Abbe et al. 2023 Zweig et al. 2023 Damian et al. 2024 Ben Arous
et al.
2024 Bietti et al. 2025
representative finding for the single-index model is that the sample complexity of SGD gov- erned by the information exponent of the link function, i.e., the index of its first non-zero Hermite coefficient. In the interactive setting, however, where the data distribution is no longer i.i.d., the information exponent ceases to be an informative measure of SGD's performance. We defer more discussions to Section 5
The most canonical examples of generalized linear bandits are linear bandits (Dani et al. [208)] Rusmevichientong & Tsitsiklis 2010 Chu et al. 2011) and ridge bandits with 0 < < [f(()) S o everywhere. In both cases, the minimax regret is ((dvT) (Filippi al., 2010 Abbasi- Yadkori et al. 2011; Russo & Van Roy. 2014), attained by algorithms such as LIB and information-direeted sampling. For more challenging convex link functions, the special cases f(r x² and f(x) = x" with p 2 2 were analyzed in (Lattimore
Generalized linear bandits.
Hao 2021 Huang et al.] 2021), using either successive searching algorithms or noisy power methods. These results were substantially generalized by (Rajaraman et al. 2024), which identified the existence of general burn-in period and established tight upper and lower bounds on the optimal burn-in cost via differential equations. In particular, their upper bound strengthens Corollary | in the absence of convexity, using refined algorithm of (Lattimore & Hao 2021) during the burn-in phase and an ETC (explore-then -commm) algorithm in the learning phase. By contrast, we show that a single, much simpler SGD algorithm achieves the same upper bound for convex f.
A related line of work (Fan et al. 2023 Kang et al. 2025) studied the single-index model with an unknown link function. where the central idea is to estimate the score function. Their resulting algorithms are of the ETC type, and the regret guarantees rely on a positive lower bound for f".
Gradient descent in online learning and bandits. Gradient and mirror descent are classical al- gorithms in online settings (including online learning and online convex optimization BisncBi & Lugosi 2006 Hazan et al. 2016: Orabona 2019)), ), as well in bandit problems with gradient es- timation, such as EXP3 for ad adversarial multi-armed bandits and FTRL for adversarial linear bandits (Lattimore & Szepesvári 2020). A distinct feature of our work is that our SGD remains a first-order method even in this bandit problem, in contrast to the zeroth-order stochastic optimization usually used for single-index models such as (Huang et al. 202T). Moreover, the SGD dynamics for single- index models demand a more fine-grained analysis than that required by standard online learning guarantees. Further details are provided in Section 5
1.3 ORGANIZATION
The rest of this paper is organized as follows. In Section 2 we present a general analysis of the SGD update, including bounds on the mean drift, stochastic term, and normalization error. In Section 3 and 4 we analyze the learning and burn-in phases, respectively. Additional discussion is provided
in Section[5] and detailed proofs are deferred to the appendix.
2 ANALYSIS OF THE SGD UPDATE
To establish our main results Theorem and we first understand the properties of each SGD update in Equation (2) and Equation 3 At each time step (, the improvement on the correlation from m, := (8*, 0.) to m4+1 == (6*, (e+1) consists of three parts:
1. Drift: the mean improvement (/ m, of the descent step in Equation 3 where mz+1/2 (0', (0+1122), and F, denotes all historic observations up to the end of time I.
5

---

2. Martingale difference: the stochastic temn 1/+1/2 1 with zero mean.
3. Normalization error: the difference M 1/41/22 due to the normalization step in Equa- tion (3)
We will present generic lemmas to bound each of the above terms in this section, and use them to analyze the learning and burn-in phases in the next two sections. We start from the drift.
Lemma (Drift). Let d 2 3. The following identity holds for the drift:
E 1 m4
f (V1- mł) - E [p (V1- ham.m.../----. (1 0:/1-max) mxx
x2) Fr
d d-2
where follows the one-dimensional marginal of the uniform distribution over Sd-2, In particular, m > 0,
under Assumption
1/2 1
my
Cdr
of (1 (f mm under Assumption
for universal constant Cdr
0.
The next result concerns the subexponential concentration property of the martingale difference. Lemma 2 (Martingale difference). The V W1-Orlicz norm (i.e., the subexponential norm) of the mar- tingale difference has the following upper bound, conditioned on Fi:
M B/mu+1/2 Filllv S. Coo / --mi m mor I (VI-
where Cse > 0 is a universal constant.
Based on Lemma we proceed consider the (discounted) sum of martingale differences. For to 2 0 and 3 > 0, let
S4o.8 = Σ ga-to (m,+1/2 Blm,+ 1/2 FFl)
be a martingale adapted to (Fi and V. = Ex go( K3 be proxy for its predictable quadratic variation. The following result a self-normalized concentration inequality for such pro- cesses established in (Whitehouse et al. (2233] Theorem 3.1):
Lemma 3 (Sum of martingale differences). Let n S (Cse72) and of S To for all 2 1, and
0. For 8 > 0, holds that
+ log (Vrtoul v1) and gi to <2 F 5
3 to | 2 Cmry // log
for some universal constant Cmt > O.
Note that when B E [0, 1], the condition 3t < 2 vacuous. For 3 1, this condition results in smaller range of t [to, to + log, 2]. Finally, we bound the normalization error m441 1/41/2- Lemma 4 (Normalization error). With probability at least 1 - ô, it holds that
M++1 2 M2+1/2 Cam 1o (J' o) log( (og))
for some universal constant Cum 0. addition, if m4+1/2 0, then with probability 8,
m++1/22 2 m4+1 2 m441/2 (1-Cmm of (8 ( o))) 1lgg))))))))
log(1/0))
3 ANALYSIS OF THE LEARNING PHASE
In this section we analyze the SGD dynamics the learning phase, given a "warm start" 0, with mi 00, 2 1 70/4.

---

3.1 PURE EXPLORATION
The crux of the proof of Theorem lies in the following lemma, which shows that starting from
correlation my 2 1 - e, SGD will improve it to 1 e/2 after (dd /E) steps.
Lemma (Local improvement for pure exploration). Suppose my 2 1 for some & S 70/4. Let
c :: log" log/(d/=)) (d/=õ), and for s 2 set
CE
=²= 70:
M/ =
di
where > is small absolute constant. Then for A == Cd/n and a large absolute constant C independent of c, we have m++A 2 1 E/2 with probability at least 1 - Ad.
We call the time interval t A] an "epoch", and choose the learning rate based on the epoch. Lemma SouumaaShorr shows that, as long as the correlation is large at the beginning of an epoch, then it must be improved
linear rate the end of the epoch. Therefore, by induction and geometric series calculation, it is clear that the learning rate schedule given by Lemma corresponds to Ø(1 A }), and Lemma gives overall sample complexity Ō(d²) for pure exploration.
In the sequel we prove Lemma 5 We first show that by induction on that with probability at least 1 A6/3, m, 2 1 2s for all [t, A]. The base case / is ensured by the assumption my 2 &. For the inductive step, suppose M.,,..., Ma-1 2 28. Then
(E(m,-1/222)
m.) + (m,41/2 - Elm,+1/21 + (m,+1 - 1/21
20 by Lemma 0
=:A-
=:B,
Thanks to the inductive hypothesis, K, On for all r E [1, 8 - 1] in Lemma 2 so Lemma
(with to t, 3 1) gives EE= / A, O log( ) O log( +
with prob- by choosing > 0 small enough. Similarly, Σ:=1 |, O log( ()
ability
8 by Lemma and choosing c > 0 small enough. This implies that m, 2 m, { > 1 2E with probability 1 3. completing the induction.
Odd log( +
)) < & with probability
Conditioned on the event m, 2 2= for all E [t. + A), we distinguish into two regimes in this epoch. Let To 2 / be the stopping time when m, > e/4 for the first time.
Regime I: < 8 To- In this regime m, E [1- 2c, e/4]. We show that To S t + with probability A6/3. To ++ A, using the same high-probability bounds, we have
444-1
m++ m
(E/m,- F.] m.)
with probability 1-/6 By Lemma with 1 1-m = (ss and VI- - 2 1-70 for s < To. the total drift is ( [E= R(C2). Therefore, for large absolute constant C 0. we would have M++ 2 - E/4, a contradiction to the assumption To t A.
Regime I1: induction starting from s = To shows that, with probability 1 A,/3, m, 2 mı, E/4 holds for all E [To t + A]. In particular, choosing t + A gives the desired result m44 e/2.
To. As shown above, this regime is non-empty with high probability. The same
An illustration of the above proof technique is displayed in Figure 2 shown in Appendix
3.2 REGRET MINIMIZATION
The proof of Theorem T for regret minimization follows similarly from the following lemma. Lemma (Local improvement for regret minimization), Suppose m, 2 1 - s for some e S 70/4.
Let 1 = log" (d/s0), > small absolute constant, and for 8 2 6, set
o2 e.
T/s = di'
Then for = Cd/(nE) and a large absolute constant C > independent of c, with probability at least 1 2d, have (0', ,aa) 2 48 for all E A} and m4+ & e/2.
7

---

The main distinction in Lemma 6 the choice of smaller o² encourage exploitation for small the total regret in the epoch is
regret: using the local linearity assumption in Assumption |
++ -(( - 1(10 ((,"",)))))))) S (A+ 4 Ō
dc
with probability Ad.
In addition, the duration of each epoch becomes longer, with a correspondence & == O d A 1).
This correspondence gives the learning rate and exploration schedule in Theorem [ as well as the (dvVT) regret bound. The proof of Lemma 6 is deferred to the appendix.
ANALYSIS OF THE BURN-IN PHASE
The analysis of the SGD dynamics in the burn-in phase relies similar induction ideas, with more complicated tradeoff among the three components in the correlation improvement m m7.
4.1 LINK FUNCTION WITH DERIVATIVE LOWER BOUND
We first investigate the simpler scenario in Assumption i.c., f'(x) 2 co for all [0, 1]. In this case, Theorem 2 is a direct consequence of the following lemma:
Lemma (Burn-in phase under Assumption
2p. Suppose mi 2 Va
Let L: == log (d/8), and set
= := di of =²= ==
where c. > 0 is a universal constant. Then for T == Cd/n and a large absolute constant C > independent of c, we have mT 2 1 70/ with probability at least TT.
In the sequel we present the proof of Lemma 7 m 2 70/8} and splits into two regimes.
Again we consider the stopping time To min(t
Regime I: S To. If To > T, we prove by induction that my with probability at least 1-1 T5, for some absolute constant c' independent of The base case t = is our assumption. Now suppose this lower bound holds for mı. m4-1. then by Lemma] and with probability at least 8 for each = =,....,
2vd + c1 d
1
s(t=1) 1) for all E [1,
4-
1f/ma+1/a/FF]- m.) (ms.1 m,+1/2) Ω (2) O 12 log 2 2) S (
by our choice of y/ Here we have critically used the condition m, = 211) ) for < To when
applying Lemma [ and the inductive hypothesis to ensure m. > 0. By Lemma 2 and with
probability 1 - . the sum of martingale difference is at most O [ log( 0 log f < for e >>> 0 small enough. Therefore, 2vd
Σ
1
n(t ntt- 1)
110-11
m, 2 m1
+
2vd
d
2vd
with > large enough shows the opposite result my 2 1 70/8, implying that the event Tú > T only occurs with probability at most T5/2.
completing the induction step. Now choosing
Regime II: To stsT. Under the high-rrobbiility event To T and starting from To.
(B(me41/22/FF) - m.) + (M441/2 - E(me+1/2/Fi) + (m++ - m4+1/2)
WT - --TT
T=
by Lemma
miA.
By Lemma
and 3
Σ
A,l = O log( (+)) = O ()) < with probability Σı=
1- T6/2, for (dn log( ())
small enough. In addition, Lemma gives ETz B, O(T log( {))
2o with probability - T6/2, again for > 0 small enough. Therefore, at the end of this regime, mr > mT, 20/8 2 1 70/4 with probability 78, as desired.
T6
8

---

4.2 CONVEX LINK FUNCTION
When f is convex in Assumption 3 we establish the following lemma.
Lemma 8 (Local improvement for convex link function). For I d let my == (1 To)² k/dd, and my := (1 7o/4)/k/o Suppose that my 2 my at the beginning of the k-th epoch. Let := (d/0)))) (d/o), and for 2 t, set
7 7 = (m
0 =0= := 7o.
edma
where c 0 is a small absolute constant. Then for A Cd( my) /nn (mx)) and a large absolute constant C' >> 0 independent of c, we have m++A 2 m with probability at least - Ad.
Since m1 2 l/d
my. recursive application of Lemma 8 for k 1.....d d - leads to mt 2 1 - 7o/ with probability at least T8, with (recall that 70 S 0.1) 70/4
T= log" (9)
My (m++1 mz)
rdæ
f'm )2
f'(x)²
20/
This completes the proof of Theorem details to the appendix.
The proof of Lemma is more involved, and we defer the
5 DISCUSSION
Comparison with other descent algorithms. Our SGD update in Equation 3 is an online gra- dient descent applied to the loss (0) := (rr - f0, aa))), with a, chosen according Equa- tion (2). A typical guarantee in online learning takes the form (e.g., via the sequential Rademacher complexity (Rakhlin et al. 2015))
T Σ (f((0),a))) ((10),)))) Ö(d).
which is known online regression oracle (Foster& & Rakhlin 2020 Foster et al. 2021). How- ever, this oracle guarantee alone does not yield the optimal regret of O, in single-index models; see Theorem 1.5 of (Rajaraman et al. 2024) for general negative result. This motivates to move beyond standard online learning guarantees and directly analyze the SGD dynamics.
A different descent algorithm for single-index models is also in (Huang al. 2021). using zeroth- order stochastic optimization to approximate the gradient and implement a noisy power method. In contrast, SGD is zeroth-order method: rather than performing gradient descent the link function 0 + f(( 0)) where only a zeroth-order oracle is available, we apply gradient descent the population loss 0 11 f(10, a)) for which an unbiased gradient estimator exists for every 0. This change of objective makes SGD natural yet novel solution to nonlinear ridge bandits.
Necessity monotonicity. Throughout this paper we assume that the link function / is mono- tone, assumption that is not needed in the non-interactive setting (see, e.g., (Ben Arous et al., 202TT). This condition, however, turns out to be essentially necessary for SGD to succeed under our exploration strategy equation 2 Indeed, when o; SGD is performed on the population loss
E (ra f((0,, az))) E (F((00, ((((0";a))) ,a))) - f((0,, az)))) + Var(r:)
E (f(VI-o7) - f 1f((---i11 02 ,,, + t (100,zi)) + Var(r,)
(1(VI-07) (f (V11- 0.))) Var(r:),
where the last approximation uses that (0* Zz) is typically of order Ö(1/Vd) and thus often neg- ligible. Recall that for SGD to succeed at the population level, the population loss must decrease with the alignment (0*, 0,) (stated as Assumption A in (Ben Arous al. 2021)). Treating Var(re)

---

constant, this requires f to be increasing [0, v1 a²] in the interactive setting (assuming (0) > 0). Hence, whenever a bounded away from 1, a monotonicity assumption on f is indis- pensable in the interactive setting. By contrast, when sary: in this case Equation (2) reduces to pure exploration, and the problem essentially collapses to the non-interactive setting. However, this would eliminate the statistical benefits of interaction.
the monotonicity condition is unneces-
We also provide an explicit counterexample to formally support the above intuition.
Proposition 1. Consider the SGD dynamics in Equation (3) applied to the link function
if m S 0
f(m) = - m
if0 < m _ 3
if < < 1
with any initialization m, (8",0,) S 0.1, any exploration schedule or S 0.1, and any learning rate S 15g(TT5) for some small absolute constant c > 0. Then P(max.e(7] my S 0.2) 2 1 1-8. 8.
Note that the above link function f violates the monotonicity condition: it first decreases and then increases on [0, 1]. By choosing 8 = T Proposition shows that with any practical initialization, any exploration schedule that does not essentially correspond to con-interactive exploration, and any learning rate that is not too large to escape the local optima, with high probability the resulting SGD cannot achieve an alignment better than small constant (say 0.2).
Comparison with information exponent. In the non-interactive case with a ~ NO0 Ia), known that the information exponent of f determines the sample complexity of SGD. In the interactive case, however, the monotonicity of f ensures that the information exponent is always 1. Indeed, for the first Hermite polynomial H1 [z) x, Chebyshev's sum inequality yields
(2)=) 2 (zz (0 [H1 [Z)] =,
with equality iff f = is constant. Morcover, the sample complexity predicted by the information exponent is no longer tight. For instance, when f(z) = x" with an odd 2 3, the sample complexity of SGD with ~ (0, Ia/ d) is O(d++1) (see remark below), which is strictly worse than the (dP) guarantee obtained by our interactive SGD. These observations show that the information exponent ceases to be an informative measure for SGD in the interactive case, for the actions de are no longer Gaussian.
Remark 2. For [(xx) x² with odd 2 3, the population square loss has information exponent equal to 1. Let 61 be the coefficient of the linear term (0",0) 0.) in
Ex-N10.1a [F(((0 xX) f((0,
then C1 -2uu with un (f) being the first Hermite coefficient of f. When scale down the input features into X Ia/Ad/ we effectively change F(x) (z/ (d), so e₁ becomes d-Pcy Therefore, the SNR effectively worsens by a factor of d.
Dropping the convexity assumption. The convexity assumption in Assumption 3 is not required in the statistical complexity framework developed for ridge bandits in (Rajaraman et al. 2024) Relying only on the monotonicity of they establish the upper bound
Ō(2² Lu
1/2
d(z2)
Juya max
Va SuSz f(())2
on the sample complexity of finding an action a, with (0*,ar) 2 1/2. In comparison, under our con- vexity assumption the denominator simplifies to f (z)² There two main obstacles to recovering this sharper bound. First, our analysis in Lemma 4 requires a conservative choice of the learning rate 7/. which in turn depends having lower bound for f f'(m.) at the current correlation m,- Obtaining such a bound is challenging without further conditions on f- In this paper we handle this by using f'(m.)
in the generalized linear case, and f'(m:) I' (mm,) in the convex case, where < my is known. Second, achieving the factor max, 1 /V ("())² requires careful tuning of o, target the maximizer of f', which in turn relies knowledge of the current correlation m,- In (Rajaraman et al. 2024), this is accomplished by running a separate hypothesis test. However, such an additional testing step is not compatible with the dynamics of SGD.
10

---

REFERENCES
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-stairease property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pp. 4782-4888 PMLR, 2022.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-saddee dynamics. In The Thirty Sixth Annual Conference on Learn- ing Theory, pp. 2552-2623. PMLR, 2023.
Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, and Bruno Loureiro. From digh-dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1199-1227. PMLR, 2023.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Ma- chine Learning Research, 18(19): 2017.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory. 39(3):930- 9450,9995.000 2002.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensiona. inference. Journal of Machine Learning Research, 22 (106):1-51, 2021.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling. Advances in neural information processing systems, 15:25349-253661 2022.
Gérard Ben Arous, Cédric Gerbelot, and Vanessa Piccolo. High-dimensional optimization for multi- spiked tensor pea. arXiv preprint arXiv:2408.0644 2024.
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances neural information processing systems, 35:9768-9788. 2022.
Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien On learning gaussian multi-index models with gradient flow part i: General properties and two-timescale learning. Communications on Pure and Applied Mathematics, 2025.
Aude Billard and Danica Kragic. Trends and challenges in robot manipulation. Science, 364(6446); e4at8414, 2019.
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176:5-37, 2019.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings. 2011.
Alex Damian, Loucas Pillaud- -ivien, Jason Lee, and Joan Bruna. Computationallstaaisnnn gaps in gaussian single-indes models. In The Thirty Seventh Anmual Conference on Learning Theory, pp- 1262-1262. PMLR, 2024.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can lear representations with gradient descent. Conference on Learning Theory, pp. 5413-5452. PMLR, 2022.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. Conference Learning Theory, pp. 355-366, 2008.

---

Rishabh Dudeja and Daniel Hsu. Learning single-indes index models in gaussian space. In Conference On Learning Theory, pp. 1887-1930. PMLR, 2018.
Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in over- parameterized single index model. Journal of the American Statistical Association, 118(544): 2315-2328, 2023.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International conference on machine learning. pp. 3199-3210 PMLR, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13887 2021.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5428, 2020.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference learning theory, pp. 797-842. PMLR, 2015.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
Baihe Huang, Kaixuan Huang, Sham Kakade, Jason D Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient-based algorithms for non-concave bandit optimization. Advances in Neural Information Processing Systems, 34:29101-2911 2021.
Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of general- ized linear and single index models with isotonic regression. Advances Neural Information Processing Systems, 24, 2011.
Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, volume 1, pp. 9, 2009.
Yue Kang, Mingshuo Liu, Bongsoo Yi, Jing Lyu, Zhi Zhang, Doudou Zhou, and Yao Li. Single index bandits: Generalized linear contextual bandits with unknown reward functions. arXiv preprint arXiv:2506.1277 2025.
Tor Lattimore and Botao Hao. Bandit phase retrieval. Advances in Neural Information Processing Systems, 8801-1881, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv: arXiv:1912.13 1912. 2019.
Nived Rajaraman, Yanjun Han, Jiantao Jiao, and Kannan Ramchandran. Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52()):2557-2582, 2024.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complex- ities. J. Mach. Learn. Res., 16(1):155-186, 2015.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395-411 2010.
Mathematics of
Daniel Russo and Benjamin Van Roy. Learning to optimize via inforrmation-directed sampling. Advances in neural information processing systems, 27, 2014.
Shai Shalev- Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaccs with the zero-one loss. arXiv preprint arXiv: 1005.3681, 2010.
12

---

Mahdi Soltanolkotabi. Learning relus via gradient descent. Advances in neural information pro- cessing systems, 30, 2017.
Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. Journal of Machine Learning Research, 24(58):
1-47, 2023.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free RL is no harder than reward-aware RL in linear Markov decision processes. In International Conference on Machine Learning, pp. 12430-22455 PMLR, 2022.
Chuang Wang, Jonathan Mattingly, and Yue M Lu. Scaling limit: Exact and tractable analysis of online learning algorithms with applications to regularized regression and pea. arXiv preprint arXiv:1712.04332. 2017.
Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas. Time-uniform self-normalized con- centration for vector-valued processes. arXiv preprint arXiv:2310.09100, 2023.
Lei Wu. Learning a single neuron for non-monotonic activation functions. In International confer- artificial intelligence and statistics, pp. 4178 -499. PMLR, 2022.
Gilad Yehudai and Shamir Ohad. Learning single neuron with gradient methods. In Conference on Learning Theory, pp. 3756-3786. PMLR, 2020.
Henry Zhu, Abhishek Gupta, Aravind Rajeswaran, Sergey Levine, and Vikash Kumar. Dexterous manipulation with deep reinforcement learning: Efficient, general, and low-cost. 2019 Inter- national Conference Robotics and Automation (ICRA), pp. 3651-3657. IEEE, 2019.
Aaron Zweig, Loucas Iilaud-Vivien, and Joan Bruna. On single-index models beyond gaussian data. Advances in Neural Information Processing Systems, 36: 10200-1022, 2023.
13

---

A PICTORIAL ILLUSTRATION OF LEMMA
5
1-2
1-2c 2c
To 1 &
Figure 2: An example behavior of SGD for pure exploration in the learning phase (cf. Lemma 5 For appropriately chosen learning rates, if the correlation hits my 2 1 E at time t, the SGD dynamics will enjoy the following behaviors with high probability: (i) the trajectory will never degrade too significantly, satisfying m, 2 2x for all < S + A; (fi) at some time = To [t, + A). m, improves to least 3: and (iit) thereafter, my may decrease, but will never fall below 1
for all To
B PROOFS OF MAIN LEMMAS
B. PROOF OF COROLLARY 1
By Theorem and it remains to show that both the initialization cost ((f(L/VV) - and the burn-in cost (d²) under Assumption 2 are dominated by the integral.
For the initialization cost, we have
1
4d
S())22
((
- [(
(2va ///v f ((m))dm)
(b)
3/Ve
J f((m2 dm,
1/va
4d 2vd
1/leva) f'(m)z dm s 16d2
where (a) follows from the monotonicity of S. and (b) applies Jensen's inequality.
For the burn-in cost ((d) under Assumption] 2 we simply note that f'(x) I 72 when & E [1-70.1] by Assumption
1 that
10/4
dm 2 d² 370 1 ((dd)) f'(m)2
d
1-70
72
These complete the proof.
B.2 PROOF OF LEMMA 1
Observe that
E(0:41/2 E 10. 11 [[f((ar, 0,)) (((ar,0)) NN) 0,))] F.
0, n [[(f((ar, (a)) s((ar, 0 (²))){((( (())) 0.))] Z.FF..
v1 - of 0. + Z. in Equation 22.. Since Z, 1 0, almost surely, (ar, 0c)
Recall that de
VI of. Taking an inner product with 0* on both sides.
E E/m,+1/2|FF m, morl (V1 of)
of (0,, 0r) (Z) (Z,, (Z,,0)) [F]
14

---

Since Ze ~ Unif(f E 8d-1
1 0,)), the random variable (1 11-mm))1122 (Zz the one-dimensional marginal of a uniform random vector on gd- 2; denote by X a random variable following this distribution. Consequently, for
(Z, 8*) is distributed as
g(z) j (f (0,, + oiy 1 m2x
an application of the spherical Stein's 's lemma (cf. Lemma 10 gives
1/m4+1/2 Fel m
noo o' (111(((1111 03 V m E (I]]
[(V( 07 m² E (X) [r]
d-2
noo (1- d-2 l' )(- m,)-B (1)
- [r (VI- m. + 1 1 (1 - x2) Fr
(1-x3)
This is the desired identity. For the other inequalities, under Assumption 2 and m, 2 0, for
h(x) = 5' (Vi- (0,,0) + - 1- 2 0,
have
(I - x3]] (11(()(11XXX)) x3)1 20]
d = 2(1)
2 co - x 2 0)] = co 2(d - 1)
for d 3. Under Assumption 3| and me 2 0, we then write
(1xx)(1-33)) 2
0)]
2 f'(v - 0f B[(1
- x2)1(X 2 0)
B.3 PROOF OF LEMMA
By definition,
M m. (no,(f((ar; + No f((a,, (1)) 0.)) (Z,,8")
Define new random variables:
(11) maa,((((a 0*)) I( (()))) (Ze, 0*),
{(2) = Mo.NNef ((a,, 0.)) (Z,, 0*),
such that m4-1/22 m, (12) g(2), We will show that each of these random variables is subex- ponential with bounded -rllic norm.
For (()), note that [f(((r,))) 0))) s(la,, 0,)) S 2ll and (ar. = VI of In addition.
(2,, 0*) d V 11-min /I-m,x, m2X,
where X follows the one-dimensional mariina of uniform random vector on dd-2, By Lemma |1 it holds that ||, < [N(00, d = 0(d-1/2). Therefore,
O(IE(")) - (n m
1g |
Vd
where (a) follows from
/Vershynn 2018 Remark 2.8.8).
15

---

For {(2), note that || R2 1 by the I-subGaussian assumption the noise. Therefore, by
independence of Ze and No. Vershynin 2018 Lemma 2.8.6) gives
||. & non noof ) 12, 1") =0 [nonf of m
vd
Finally, the triangle inequality the v norn gives
M++1/2 1/ $ |I. + 1| =0 [mors 0. / m
Vd
B.4
PROOF OF LEMMA
For notational simplicity write S Sto.9. By Lemma 2
log ([(eep(A(SS S.)) Cg2((- K?X?, for all | S C Kr
Here C > 0s a universal constant. show that K; S 1 almost surely. fact, ('v11 5 by Assumption when of Yo, and
Ke S Csell:72 $
by the choice of nı- Consequently, for Vj = C s== -
L-1 (2(0-10) K3 Amax == 20 and
X
(AA)
A [0, Amax):
A/ Ammx
holds that
Ejexp(AS+41 (AA exp(AS (A)VV), A [0, Am 2.
Therefore, the conditions of Lemma 9 are fulfilled, and the claimed upper tail of S, follows from choosing w = Replacing S, by SS, in the above analysis gives the lower tail of S..
B.5
PROOF OF LEMMA
Since Ze, the iterate 0.41/2 in Equation 3 satisfies
||0+1/2|| of
re)2.
Therefore, ||0+11/2| 2 1, it is clear that
m/+1/2
m4+1/2
(10041/2ll-1)
m4+1 1/21
m241/22
11,+1/2||
1
2 1441/2
2 1
( of ( rr)
for x 2 0, and ( S 1. The first statement now follows from the sub-Gaussian concentration of r,, which implies (f((0,, ax)) r2) 0(log(18)) with probability least 1 5.
using
For the second statement, m4+1 S m4+1/2 follows from |0++1/2l| > 1. The other direction follows from the same high-probability upper bound of ||0+1/2l| 1, and the simple inequality I+e for r 2 0.
B.6 PROOF OF LEMMA 6
As we showed in the proof Lemma 5 we will show by induction on s that with probability at least
1 A5/3, m, 2 my & for all 1, A). The base case is ensured by the assumption
16

---

my For the inductive step, the induction hypothesis implies that my...... M 25.
Then
my my
Σ
(B(m,-1/2 mr) + (Mx+1/2 1lmr+1/2/FFl) + (mr+1 m2+1/22
20 by Lemma !
=:A,
=:B,
Thanks to the inductive hypothesis, K, = (1)) for all r E [t,s 1] in Lemma (with to = t, = 1) gives
so Lemma
-41=
A log ) OVT log
0
with probability
6. by choosing > 0 small enough. Similarly,
B,l O log( ) Odn log(
with probability 1 by Lemma 4 and choosing c > small enough. This implies that m, 2
- with probability
8 3. completing the induction.
Conditioned on the event m, 2 28 for all E [t, I. A), we distinguish into two regimes in this s/4 for the first time.
epoch. Let To t be the stopping time where m.
Regime I: S 8 < To. In this regime m, E 2s, - e/4]. We show that To S L A with probability 1 - A6/3. 3. If To > 1+ A, using the same high-probability bounds, we have
m++A m
E FF] m.) 4
with probability 1-16/3. By Lemma with 1-m3 M)=) and /I- o Y for < To. the total drift is . (0($)=²) ((C').. Therefore, for a large absolute constant C' > 0, we would have m++ e/2, contradiction to the assumption To A.
Regime II: s 2 To. As shown above, this regime is non-empty with high probability. The same induction starting from s To shows that, with probability 1 A8/3, m, 2 mı, E/4 holds for all E [To, / A]. In particular, choosing L + A gives the desired result mi+ 2 8/2.
Finally, to lower bound (0',as .xx) during this epoch, we simply note that
(0", aa) /I 1 orm, + 0, (0", Za)
v1 o?m, + og (f* m.g, Za)
2 1 ofm, 0 1 m20
I 0 0. /1 m
Under the good event m, 2 m.
35 by V we have a,)) 2 1 - 4e, as desired.
/
B.7
PROOF OF LEMMA g
Let
44A
8 = Cnm
1202002 2
2
(4)
with C'm given in Lemma 4 (1/2, 1). In addition, let
By the choice of 17, when the constant 0 is small enough, we have
{s { 2 t: m. (1 (1- 70
To min
(S)
be the stopping time when the correlation m, first hits a given threshold. Unlike the other proofs, the event To + A no longer occurs with high probability, and proof will diseuss both cases.
17

---

Case I: To ++ A. Define the following event:
Eg E,:= {mmm, m.
To en 2nl' (s-
(6)
where d' > 0 is small absolute constant (to be chosen later) independent of We will prove by
induction that
8 P((U)_))) (To > 1+ (+))) S 10 1)/2 all & = L, + 1,...
The base case follows from the assumption m4 my, that P(E For the inductive step, suppose that Equation 7 holds for s 1. Since P)AUB) = P(A) + (P B), it suffices to prove that
6 2
P ( (To 1+ (+) S
(8)
To this end, we introduce some additional events. First, applying Lemma Equation
3 with to and ,
<
gives
P(E,,1) = P Mr+1/2 - ELm,+
d 9)
6
I CuV d
log
2
(9)
gr-t
4A
for some absolute constant C To see Equation
9 note that
8- = exp (0((1 3)4 exp (o
1/ log d / ) exp 0
cC
= 1 + 9e(1)
(10)
id
d
so that the condition B- < 2 holds for small >> 0, and Σ --((r-t) O ( - 0(A).
In addition, let E,22 be the good event that the lower bound in Lemma 1oamma4hollde hholds for m,+1, with 6/ in place of 6.
Note that &, n n (To > + A} implies that
My 2 Bm,+1/2
3 (m,41/2 1/2
Bim [F] m, + m.)
nf (m))
2 3 My+1/2 Elm,+1/2/ c1
d + +my
where > 0 is an absolute constant, and the last step invokes Lemmal uses m, I 1 111 since r S l To, and
m, /1
70
70 d
2 (1
70)2
V m,
by Equation
6 and the definitions of my, my- Summing over = l,..., 1, the event n (E
Ex22 n (To + A} implics that
M,+1/2 Blm,+1/2/Fil
nI" (m)))) grtl
m g
m+
+ +
gr-t
d
In view of Equation and Equation
10 a further intersection with E.-1 implies that
0c(1)
A
88) (o) c'n' (s
m,
m -Cay
log
d
d
oo(1)
cC'
+ d'f((mme)) (s (s-t)
1
O
To
d'n (m²) +
m0
d (s t)
d
for e > small enough; this precisely the event E,, other words, we have shown that
33 n (E; E n E,2) n (To -}= =
(1I)
18

---

By Equation 11 have
P n (1
*t++
(E n (To > + A})
By Equation and the union bound, the first probability at most 4. For the second probability, the n ( > ++ A} implies mr+1/2 2 0, which is the prerequisite of Lemma Therefore, the conditional probability of &r,2 is at least
same program above shows that (
1 a and by a union bound the second probability is at most 6 This proves Equation 8 and completes the induction.
4'
Finally, note that & implies that
70 c'ns' (m))
M4+4
2 mi
70 cCC(e4t mp 2 m++1+
by choosing C large enough. Therefore, Equation with 1 A implies that
A6 P([m++ m n (To ++ S 2
(12)
Case II: To St+ A.
We apply our usual program to this case: if To S t + A, then
44--1
Σ
[ (E|m++1/2 m.) + (ma+1/2 - Blm 1/2 [Fl) + (mş+1 m
M++
20 by Lemma
=:A,
=:B.
By Lemma with probability least
A4 4
++
Σ
A, 0
(m/
log (3)) 0 (a)
0
d
To
By Lemma with probability at least
1
A6 T
B&l ( 1 log
d) ( 0
(c0
cC
==
Therefore, conditioned on To < L. + A, with probability at least 1
A6 2
M++a (1
70
k / o (
(2e
1
70
k
ā
4
for a small enough constant c > 0. In other words,
A6
P([m++ m (To 51+
(13)
2
Finally, a combination of Equation and Equation 13 gives P(M++A mb+1) S A6, which is the desired result.
B.8 PROOF OF PROPOSITION
Let To be the first time 2 such that m, 2 0.1. To T, the target claim max,er my < 0.2 clearly true. Hence in the sequel we condition the event To T. In addition, by Gaussian tail bounds, we have m |rx O( ((vlog(T/8)) with probability at least - 5/4. By Equation (3 we then have a deterministic inequality
mT. 1//-1/2 I MT-11 + S0m-iVlog(T//0 S mT,11 1 + 0.05 < 0.15,
19

---

by assumption of ?/ [7g] for sufficiently small constant > 0, and the definition of To that - I 0.1. By Lemma this implies that mtp 0.15.
In the sequel, we start from meTo E [0.1, 0.15], and for notational simplicity we redefine mr, to be our starting point, i.e. To 1. Next we consider the time interval [I] with
C1
T = min 2
d
log 2
(T
e
for some absolute constant c be chosen later. We prove the following claims.
Claim I: [TX) m, 2 0.2 with probability at least 1 - ((4T))) To prove this claim, we first show that when my S 0.2, then
E E S m.
(14)
Indeed, by Lemmaly I
Elm{+1/2|F4 m4
d-2 f (VI- (1 - mē² E { (VI- m, 10/1-m33 (1 (1- x23 x3)
nio 2
Since o, S 0.11, m S 0.2, and | almost surely, we have
V1- of m + a m m4 + 02 S 0.3 3
of) Since ('mm s for all m s 1/3 in our construction, and f'(v o?? > 0, we obtain Equa- tion 14
Next, without loss generality we assume that my 2 0 for all E [Ti], since negative m, only makes the target claim simpler. For every t e [Ti].
m. mi
(E(m,+1/21F.) - m,) + (mr+1/2 - 1/22+1/2(FF)) + (m,+1 - m/+1/2)
by Equation
<0 Lemma
By Lemma 3 with B 1, we get
1-1
of d
Σ Ar < C Clog
with probability at least - (47)), for some absolute constant C >>
By the definition of Ti, we
obtain |E=]| A,l < 0.05 for sufficiently small > O. Therefore, S mı + 0.05 < 0.2 with probability least 1 6/(4T", and an induction on with union bound gives the target claim.
Claim II: min.e(T,) my < 0.1 with probability at least 1- ((4T). In the sequel, we condition on the good event Claim I. Let T2 be the first time such that m, S 0.1; note that is possible to have T2 > Ti even T2 co. We first show that if m, 2 0.1, then
m, _em.oo d
Eim4+1/2
(15)
for some absolute constant 02 > 0. Indeed, for o, $ 0.1, m E [0.1, and X S 1, we have
0 < 00.99m, v0.99a, I v1- of me + 01 1 mxX S m. + σ < 3
Since f'mm - for all [0, 1/3] in our construction, Equation 15 follows from Lemma Next, for every < min (T,, Ti we write m1
m:
E [Bmm,11/2/F11 m,) + (mr+1/2 B,m, 1/2 1/2 + (m,+1 M,+1/2)
5- on by Equation
=:A-
< by Lomma
20

---

Similar to Claim I, have hand, the total drift is
A,l I 0.05 with probability at least 5/(4T). On the other |E== 1--1
Σ (2/m,+1/2/FFl1 m.) -
T1
T _
(a) c2 log (T/5)
T1-1
1/ : _
2
(b)
C102
od
2c
where (a) uses the upper bound of nh. and (b) uses the definition of T₁. By choosing enough, the total drift can be made smaller than -0.1, so that if T2 > Ti, then my, S my - 0.1 +
small
0.05 S 0.1, which in turn means that T2 S Ti, a contradiction. Therefore, with probability least 1 - (4T), we have T2 S T1, or equivalently min
0.1.
Finally, it is clear that repeated application of Claim I and Il implies Proposition [T starting from the first time To with nn, 2 0.1, the above claims show that with high probability, future alignment my will fall below 0.1 before rises above 0.2. Once m, falls below 0.1, we repeat the entire process again and wait for the next time it falls below 0.1. Since the failure probability at each step of the analysis is at most 8 /T, union bound gives the total failure probability of
C AUXILIARY RESULTS
Below we state self normalzzdl concentration inequality for martingales (Whitehouse al., 2023 Theorem 3.1) adapted to our setting.
Definition (CGF-like function). A function 1/> [0, Ammox) Rzo is suid to be CGF-like if it is (a) twice contiuoouly-diffeenntddd on its domain, (b) strictly convex, (c) satisfies 1/(0) = v/ (0) = 0,
and (d) vz (0) > O.
Definition 2 (Sub-u)). Let tb 10, Amax) + Rzo be CGF-like function. Let { {Se1220 and {Ve be respectively R-valued and IR RRzo-valued processsss adapted to some filtration {Fi)120. We say that {Se, ViJ is ub if for every X [0, Amax),
Ma == exp (AS: (A)VG) < L2
where Jt20 a non-negative supermartingale adapted {Fi)220-
The following result is corollary of (Whitehouse et (1 + k)² for k 2 1.
2023 Theorem 3.1) with the choice h(k)
Lemma 9 (Self- normaazzd concentration inequality). Suppose (St, Vil is real-valued sub-a)
process for : [0, Amax) + Rzo satisfying
X
(AA)
1- A/Amax
on its domain. Let 8 (0,1) 1) denote the error probability. Define the function E: R2o - Rzo by
ts (v) = 2 log (1 + log (ew V 1)) + log
then there exists universal constant C such that,
Pr P= C (a (V - la (V:)) (oa) s 8.
Proof. By simple algebra, the convex conjugate oi of 1 satisfies (1+)- 2 > u. The rest follows from (Whitehouse et al. 2023, Theorem 3.1).
Lemma 10 (Spherical Stein's Lemma). Suppose Z ~ Unif(Sd-1) and consider a fixed a E Idd and let X (a, Z). For any bounded function f.
1 d d -
E[xf(X)
21

---

Proof. The density of X is given by
d-1
2 (1 x22)
Pa(x)
1(1x] S 1).
Beta
d-1
21 2
Consequently,
2 2(1 x²) 4
[[Xf(x)] = xf(x).
dr
Beta 21
k-1
(a)
2
(x)
2
dx
d
Beta 2 2
k-1
2 2 x2) d-1
d / f'(x)(1 - =x²)
da
Beta
21 2921
k-1
d-1 E (1) -xx]]
where (a) follows from integration by parts.
Lemma 11. Suppose X (N, I/d) and X' ~ Unif(S For any fixed a E R., (o, X)² dominates (a, x in the convex order. Namely, for every convex g : -> R
Eig((a, s Elg( ()²])
Proof. Observe that X follows the same distribution as NX', where N and X' are independent, and N is scaled chi-squared random variable such that E[ = 1. Therefore,
E[g( (a:, x)3] E[o(NV (a, X
E[E[o(N (a,
[[, X
22


Reviews:
[{"review_id": "xxOsSxRW6b", "reviewer": "Reviewer_zDB6", "summary": "This paper considers interactive SGD for single-index bandit problems where the reward is a potentially non-linear function of the dot-product between the current and optimal actions. The paper analyses both a burn-in phase to get a constant dot-product, and a learning phase which starts from a warm-start initialization and achieves a $\\tilde{O}(d^2/\\varepsilon)$ sample-complexity and $\\tilde{O}(d\\sqrt{T})$ regret.", "questions": "* I think it would be very useful if the schedule of $\\sigma_t$ could be presented more explicitly for regret minimization in Corollary 1.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "While there is now a rich literature for learning single-index models in the supervised setting, I believe the literature on online/bandit settings is more sparse. Therefore, the problem that this paper wants to tackle is novel and of importance to the community. Also, the paper is explicit about its assumptions and it is generally easy to read and follow.", "weaknesses": "My main concerns are the following:\n* In the pure exploration case $\\sigma_t = 1$, this algorithm is the same as one-pass SGD studied by Ben Arous et al., 2021. However, the sample complexity seems to be worse. Due to the monotonicity of $f$ (hence information exponent 1), the sample complexity of (pure exploration) SGD would scale linearly with $d$ (at least in the noiseless setting, but I believe it should be able to tolerate $O(1)$ i.i.d. noise as well). However, the bound of Theorem 1 (SGD with warm-start initialization) scales with $O(d^2)$ and that of Corollary 1 can be as large as $O(d^p)$ for $f(x) = x^p$. It might be plausible that to get sub-linear regret, one should ultimately settle for a worse sample complexity, but if that's the case it should be better highlighted.\n\n* The argument of Section 5 only shows that $f$ needs to be monotone around $m \\approx 1$, and one can drive $m$ towards $1$ by pure exploration. This accommodates higher order Hermite polynomials, e.g. $H\\_2,H\\_6,...$. It would be interesting to know the effect of high information exponent in such cases.", "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": "BMhtJ6ciAO", "reviewer": "Reviewer_Veb4", "summary": "In this paper, the author study the time/sample complexity of learning single-index models when the learner is allowed \nto query a specific, instead of random, point. They show that a simple SGD-type algorithm can achieve the best-known \nbounds on this problem, under the assumption that (1) the target function is monotone and has a nonzero derivative \nat $0$, or (2) the target function is convex. \nAt each step, the algorithm queries the reward/target value at a perturbed version of the current weight and update the \nweight using the (spherical) SGD. The size of the perturbation controls the exploration-exploitation trade-off: \nIn the burn-in stage ($1/\\sqrt{d}$ to constant correlation) and the exploration stage (constant correlation to $1 - o(1)$\ncorrelation), larger perturbations are used, and in the final exploitation stage (minimizing the regret in the $1 - o(1)$\ncorrelation regime), a small perturbation is used.", "questions": "* See the 2nd point of the weakness section. In particular, how do your bounds depend on the size of the label noise?\n  Can they recover/improve over the usual IE bounds when there are no label noises or the label noise is small?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Overall, this is a well-written paper and is easy-to-follow. In addition, it is short (19 pages), which is a nice and \n  rare thing for a theory paper to have.\n* It is somewhat surprising that how being able to choose the position of the query greatly simplifies the analysis and \n  improves the bounds (when the label noise is large). They choose the next query position $a_t$ to be a weighted average \n  of the current weight $\\theta_t$ and a noise that is *orthogonal* to the current weight. This makes the \n  $f( \\theta_t \\cdot a_t )$ part deterministic. Together with the monotonicity/convexity assumption, the analysis \n  becomes much cleaner than the usual analysis.", "weaknesses": "This is a neat paper that does everything the authors claim to achieve, so I do not think there is any major weakness,\nthough one could complain that the setting is too easy. Nevertheless, the following are a few complaints I have. \n\n* As someone who is more familiar with IE/Gaussian single-index models, I found the $\\tilde{O}(d^2)$ bounds really \n  confusing until I realized that the scaling is different, as the non-interactive bounds are $\\tilde{O}(d)$. It \n  might be better to point this out early on, instead of putting the discussion in the Related Work section and \n  Section 5.\n* The comparison with the information exponent results is not entirely fair, as the discrepancy comes mainly from the \n  label noises $\\epsilon_t$. Without the label noise (i.e., we have access to $f(\\theta^*, a)$), the IE bounds are \n  invariant under rescaling. It seems that being able to choosing the query point does not lead to improvements in \n  the no-label-noise setting. Moreover, if the link function is $f(x)=x^{2q}$ for some positive integer $q$ (the convex \n  setting), the IE is $2$, so the IE bound is $\\tilde{O}(d)$, while Theorem 2(2) depends on $1/f'(1/\\sqrt{d})$, which \n  can be large when $q$ is large.", "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": "Ttd4YPsVtL", "reviewer": "Reviewer_6gnD", "summary": "This paper studies a variation of Single Index Models where the features are 'interactive' meaning they depend on the current state of the parameter vector in a specific way and hence the data is not iid. The required sample complexity to learn the unknown parameter vector under SGD is studied. This paper proves sample complexity bounds on estimating the unknown parameter vector to arbitrary precision for a class of link functions which according to other recent works is tight up to poly-logarithmic factors. Additionally for the same set up the authors prove regret bounds. \n\nI think the results shown in this paper are interesting and begin to contribute to filling in the picture of SGD and Single Index Models with different features, however, I think the results are somewhat marginal as there seem to be other very closely related questions regarding sample complexity of these models which are not quite flushed out here. Please see the sections on weaknesses and my questions below. If my concerns can be addressed and I can be convinced that the story is more complete than I currently suspect it to be I would be happy to increase my scores. Currently I think this is a good start to a paper but needs a bit more flushing out to be complete.", "questions": "Do you suspect that there is a similar notion of information exponent for single index models with 'interactive features'? With Gaussian data the sample complexity is of course strongly dependant on the information exponent and can vary widely. Here, only one case is presented: i.e. you can solve the problem with quadratic complexity for the given class of functions. Do you suspect that it is possible to solve the problem for a more general class of link functions given larger sample complexity? Or that outside of the given class you cannot solve the problem? Simulations may be informative as well to answer these questions.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper proves novel results for understanding the training dynamics and sample complexity of SGD for Single Index Models with interactive features. The results are novel and demonstrate the value of SGD in this setting. The paper does a good job at explaining their results and the outlines of the proofs which are often otherwise hidden in the appendix.", "weaknesses": "The assumptions feel rather restrictive, particularly monotonicity of the link function. There is discussion of the 'necessity' of the monotonicity assumption, however there is not nearly enough detail to convince me that the assumption is necessary. If the assumption is truly necessary for the results it would be nice to have a rigorous negative result such as a counter example demonstrating that a lack of monotonicity will indeed break the conclusion of the proof.\n\nThe relationship of the information exponent in the Gaussian iid feature case is discussed and how the concept does not directly apply to the non-interactive setting. However the information exponent in general relates to the taylor expansion of the population loss and specifically for single index models with iid gaussian data this concept reduces to checking the Hermite coefficients of the link function. It is unsurprising that when the data is not gaussian the Hermite coefficients are no longer important. What would be nice is to consider the original notion of information exponent applied specifically to this problem. For example it is not clear to me that the assumptions (monotonicity and either bounded derivative from below or convexity) do not somehow still just imply information exponent 1 but under a more appropriate definition.", "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)