The Gain from Ordering in Online Learning
Authors: Vasilis Kontonis
Mingchen Ma
Christos Tzamos
Venue: NeurIPS 2023 poster (2023)
Keywords: Online Learning
Self-directed Learning
Hardness of Approximation
TL;DR: We study the effect of ordering the examples in fixed-design online learning and present novel approximation algorithms and hardness results.

Abstract: We study fixed-design online learning where the learner is allowed to choose the order of the datapoints in order to minimize their regret (aka self-directed online learning).  We focus on the fundamental task of online linear regression: the learner is given a dataset $X$ with $n$ examples in $d$ dimensions and at step $t$  they select a point $x_t \in X$, predict a value $\widetilde y_t$,  and suffer loss $(\widetilde y_t - w^\ast \cdot x_t)^2$.  The goal is to design algorithms that order the examples and achieve better 
regret  than random- or worst-order online algorithms.

For an arbitrary dataset $X$, we show that, under the Exponential Time Hypothesis, no efficient algorithm can approximate the optimal (best-order)  regret  within a factor of $d^{1/\poly(\log \log d)}$.


We then show that, for structured datasets, we can bypass the above hardness result and achieve nearly optimal regret. When the examples of $X$ are drawn i.i.d.\ from the uniform distribution on the sphere, we present an algorithm based on the greedy heuristic of  selecting ``easiest'' examples first that achieves a $\log d$-approximation of the optimal regret.

The Gain of Ordering in Online Learning
Vasilis Kontonis UT Austin vasilis@cs. wtw.usteeee.o.o edu
Mingchen Ma
Christos Tzamos UW-Madiion tzamos@visc. edu
UW-Madison mingchen@cs.c wisc.
Abstract
We study fixed-design online learning where the learner is allowed to choose the order of the datapoints order minimize their regret (aka self-directed online learning). We focus on the fundamental task of online linear regression: the learner is given a dataset X with n examples in d dimensions and step they select a point 2, E X, predict value Y. and suffer loss (Yr. w" 2,, The goal is to design algorithms that order the examples and achieve better regret than random- worst-order online algorithms.
For arbitrary dataset X, show that, under the Exponential Time Hypothesis, no efficient algorithm can approximate the optimal (best-order) regret within a factor of (l/poly(loglog
We then show that, for structured datasets, we can bypass the above hardness result and achieve nearly optimal regret. When the examples of X are drawn i.i.d. from the uniform distribution on the sphere, we present an algorithm based on the greedy heuristic of selecting "easiest" examples first that achieves a log d-approximation of the optimal regret.
Introduction
In online learning [Rob51, Han57, B 54, CBL06] the learner receives an example and outputs a prediction about its label. The true label of the example is then revealed and the learner suffers loss depending on the "distance" of their prediction from the true label. The goal is to minimize the total loss over all learning rounds given the knowledge of the correct labels of previous rounds. Under worst-case assumptions, where an adversary controls the sequence examples and labels presented to the learner, wide range of algorithms based exponential reweighting [Vov900, LW94, FS97, Vov95, CBL06] and online convex optimization [Haz16, Ora19] have been developed.
Beyond Worst-Case Online Learning A less adversarial setting is fixed-design (aka transductive) online learning first considered in [BDKM97] and subsequently studied [KK05, CBS13, WHGS22). In fixed-design online learning the pool of potential examples that the learner is going to face during the learning phase is fixed in advance and known to the learner. There are three main variants fixed- design online learning considered in the literature (see, [BDKM97J): the worst or adversarial order setting, i.e., when an adversary controls the order of examples presented to the learner, the random order, i.e., when the examples are presented the learner in random order, and the best-order or self-directed setting [GS94], where the learner can choose the next example to predict its label every round. Ordering examples during learning is common in practice: learning, designing the order of examples when training model is known as curriculum learning (BLCW09, HW19, WCZ21], where the focus is on finding ways to rank the training examples from "easy" to "hard", well as using the right pacing function for introducing more difficult data. Another application is direct marketing [LL.9, NL11], one common business intelligence task, which is process of identifying likely buyers to market products accordingly. In particular, an agent must study customers' characteristics and needs, and select customers to market their products, For example,
the context deep-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

streaming service or social media platform may want to learn the content preferences of customers without making too many bad recommendations. In this upplication, the platform chooses the order in which to present the content (from a pool of available videos) in order to minimize the "regret" (and keep the user engaged). Finally, other non-adverserial online learning variants assume that the order of examples is chosen by a teacher who knows the ground-truth and presents the examples to help the learner [GM93, Mat97, DSZI0, MSSZ22] or make regularity assumptions about the dataset of examples [RS13, JRSS15].
Self-Directed Learning and Gain from Ordering In this work, we focus on the best-order or self-directed version of fixed-design online learning. We first formally define the self-directed online prediction model [GS94] and random- and worst-order variants that we consider in this work.
Definition 1.1 Delff-Diectted Online Learning [GS94]). Let f E C be unknown target concept
from some concept class C of functions from E. R and let X = (x(1) ....., x(n)] be a subset of N points in Rd. The learner has access to the full set of (unlabeled) points X.
Until the labels of all examples of X have been predicted:
* The learning algorithm picks a point x E X and makes prediction 2 E RR about its label.
. TTe true label (x) of x: is revealed and the learner suffers loss (z f(x)))
We say that the learner suffers loss (or regret) to label X if. with probability at least 99%, holds that the total loss suffered by learner over all rounds is at most L. In what follows, given self-directed learner Aselt we shall denote by L(A f) f) its total loss L.
In this work, we investigate whether power of ordering to improve the regret compared to the worst- and random- order settings.
design efficient self-directed algorithms that exploit the
Remark 1.2 (Random-order and Worst-order Online Learning). We shall refer the setting where the example during the training phase is picked uniformly at random (without replacement) from the unlabeled data X random-order learning. Moreover, we shall refer the setting where the next example is chosen by an adversary as worst-order learning.
Before we continue, we remark that we will also consider "average-case" (Bayesian) settings where the target concept f is sampled from some prior distribution F' over concepts.
Remark 1.3 (Average and Worst-Case Targets). In Definition 1.1, we will also consider the case is drawn from some distribution over targets F, in which case the total cost defined to be the average cost over F, i.e. L(Arelt, X, F)) = FF L(Aself ,X,f). In the worst case selting we will simply write L(AAsell X) = sac L(Asell X)..
where the ground-truth,
To formalize the notion of how much self diffedireceed learners "improve over worst or random settings" compact way, we introduce the "Gain from Ordering" (or simply gain) that is defined be the ratio between the minimum possible total loss of an algorithm that works in the random-order setting and that of an algorithm that can order the examples.
Definition 1.4 (Gain from Ordering). Let f E C be a target concept. Let X (x("))...,a")))
be dataset of points in Rd. We define the Gain from Ordering of a self-directed learner Awelf
G(Asell ., min Arandom LrAnnnoom A .X.F)
L(Aseli F,
Moreover, we denote by G*, = max A G(Asell X, F) the maximum possible Gain from Ordering. Similarly, we define the Gain from Ordering in the worst-case (where the target f is chosen adversarially, see Remark 1.3) by setting ((A .X) = min grandom C(A Arndom .X) and
G" (X) maer ((Ate X).
We remark that in the above definition, we do not compare against worst-order algorithms as they always perform worse than the best random-order algorithm, and therefore, results readily generalize when considering the Gain from Ordering with respect to worst-order algorithms.
Whether ordering the examples can improve the total loss suffered by the learner was first studied in the context of online classification, i.e., when the predictions of the algorithm and the ground truth labels are binary 2, fx) e {+1). For the class of one- one-dimensional thrchsolds over the real line, in

---

[GS94] it was shown that, in the best-order setting, one mistake suffices. On the other hand in the random- and worst-order settings it is known [Lit88, Lit89] that the total loss (or equivalently the number of mistakes) is (log n), where is the size of the dataset. Therefore, for thresholds on the real-line the Gain from Ordering is known to be O(log n). Positive results on the Gain from Ordering exist for other concept classes as well (e.g., for monotone monomials and axis-aligned rectangles) but there are also known concepts where ordering the examples does not help, see [GS94, BDEK95].
Online Linear Regression In this paper, we focus on perhaps the most fundamental problem in online learning, namely online linear regression. An unknown target vector w* E R is picked by an adversary (or sampled from some prior distribution, see Remark 1.3). The true label of an example z corresponds to f(x) = w- x. In the adversarial/worst-orkde setting there are numerous results studying online linear regression going back to the seminal work of Widrow and Hoff [WH60, LLW91, KW97, CBLW96, By197. AW01, Vov01, OCCB15]. In this setting, the optimal regret is well-understood and tight (even with respect to constant factors) upper and lower bounds exist [AW01, Vov0I, CBL06). The self-directed setting much less understood both information- theoretically, i.e., what is the best possible Gain from Ordering, and computationally, i.e., whether there exist efficient self-directed algorithms that can achieve the optimal Gain from Ordering. In this work, we aim to make progress in this direction and ask the following fundamental question.
there an efficient, self-directed learning algorithm for linear regression that achieves (upproximately) optimal Gain from Ordering?
1.1 Our Results and Techniques
Our first result is an impossibility result showing that for unstructured datasets it is computationally intractable to compute an ordering that approximates the optimal Gain from Ordering under the Exponential Time Hypothesis (ETH). More precisely, we show that, even for the "casier" version of the problem where the target vector is drawn uniformly at random from the unit sphere, efficient self-directed learner can achieve better than d' ppooly(log log d) approxxmmaiionn of the optimal Gain from Ordering.
Theorem 1.5 (Hardness of Approximation for the Optimal Gain from Ordering). Let X be an arbitrary set of unit-norm examples and denote by S the uniform distribution over the unit sphere. Under the Exponential Time Hypothesis (ETH), there is no polynomial time self-directed learner Aself such that ([Aself X, xx,4)== 2 d- log log d g* S where e 0 is some universal constant.
log
Our hardness result follows by reduction to the Densest k- k-Subgraph (DkS) problem (see Defi- nition 3.1) that was shown in [Man17] to be ETH-hard to approximate. To go from our learning problem to the combinatorial DkS problem we perform a sequence of approximation preserving reductions. At high-level, we first show that selecting the best order for online linear regression is equivalent an offline geometric problem where we need to sort the examples that the sum of the distances of every example from the subspace spanned by the previous examples in the ordering is minimized, see Definition 3.3). We then show that this problem can be further reduced to a specific edge packing problem on graphs (see Definition 3.7) by only worsening the achieved approximation guarantee by a factor of 2. Finally, we show that any a-approximate algorithm for the k-packing problem yields an O(a²) -appproiiii algorithm for the Densest k-Subgraph problem. For more details, we refer to Section 3.
As our hardness result suggests, without any assumption over the structure of the data, there is no hope design an efficient self-directed learner with "good" approximation guarantee - especially in high-dimensional settings, i.e., when d is large. This motivates us to study self-directed learning over structured datasets. We focus the fundamental setting where the dataset X is i.i.d. drawn uniformly from the unit sphere, Std In this case, we design an algorithm based on a greedy heuristic that picks the example that is "most similar" to the examples already seen achieves a log d-approximation of the optimal Gain from Ordering.
Theorem 1.6 (Efficient Self-Directed Learner under Spherical Data). Let X be set of examples drawn ii.d. from Sd. There exists an efficient self-directed learner A such that, with probability at least 99%, it holds G(A, X, 2 Q(1/ log d) G S,).) Moreover, it holds that G(A, X, X, Z min(S(d)), 2d).
3

---

We remark that, apart from presenting an efficient algorithm for approximating the Gain of Ordering, Theorem 1.6, gives the first information -ethrooticthhoticccco bound for the optimal gain under spherical data, showing that (Xx, (*)) " is roughly n²/d, At a high level, the fact that the optimal gain increases slower as the dimension increases is explained by the fact that, n samples from the uniform distribution on the sphere will be almost orthogonal (unless is very large). Therefore, observing the labels of a subset of them reveals little information about the remaining points. See Section 4 for more details.
Apart from showing that, under structured datasets, singnificantly improved approximation guarantees can be achieved our upper bound of Theorem 1.6 serves as a formalization of the popular greedy heuristic of picking the "easiest examples first" used in curriculum learning (BBICW09) for linear regression. In particular, assuming that we have already observed the labels of the points x(1), ,...,, x(.)
we pick the example that is closest to the subspace spanned by _())..... .!".......!! ..... (*)), see Algorithm 1.
As an extension, we also study the self-directed ReLU regression problem, where the concept class is C = [Relu(w" .x) w² E ] ReLU regression is a very popular non-convex optimization task that has recently received sigmificant attention both in online and offline settings, [KS09, Sol17, GKKT17, GKK, DGK 20, DKKZ20, DKZ20, FCG20, DKTZ22, DKR23J. due to the fact that ReLU is very common activation in deep learning models. In Section we present an efficient algorithm that achieves Gain of Ordering roughly min(d, n²/d/ log d + log n/ log d), see Theorem 5.1, assuming a "warm-start" labeled example. We observe that, even though ReLU regression is typically a harder task than linear regression, the Gain of Ordering that we achieve is larger (by term of logn/ log d) than that of linear regression. At high-level this interesting phenomenon has to do with the the ReLU being constant on a large region of the space: a fact that the self-directed learner can exploit to improve its gain. It is an interesting direction for future research to further investigate the properties of the activation and the dataset that allow for improved gains by self directed learners.
1.2 Related Work
Related to the setting of self-directed learning is active learning [CAL94], where the learner has access to a large pool of unlabeled examples and chooses the "most informative" to ask for their labels. The goal is to find a classifier with good generalization while minimizing the number of label queries. There is a long line of research on active linear classification in the distribution-speciicc setting (e.g.. under the uniform distribution on the unit sphere) [DKM05, Hanl1, BU16). We remark that our goal of minimizing the number of mistakes is orthogonal to that of active learning: at high-level, our algorithms pick the examples for which the current hypothesis is most confident ("casiest examples") while in active learning one typically asks for the labels of the "hardest examples", e.g., those with the smallest margin with respect to the current guess (see, e.g.. [ABHU15, ABHZ16, ZSA20)..
In deep learning, stochastic gradient descent typically trains models by considering the examples in random order. In the influential work of [BLCW09] the authors proposed curriculum learning: training machine learning models in "meaningful order" from easy examples to harder ones. There is long line of research (see the surveys [HW199 WCZ21, SIRS22] and references therein) giving empirical evidence that curriculum learning provides significant benefits in convergence speed and generalization over training with random order. Our results provide theoretical evidence that ordering the examples from easier to harder significantly reduces the mistakes made by the learner.
There has been a long line of work studying online linear regression. We first review the results in the realizable setting, which means y(z) w" xr. In this case, the problem is also called the adaptive filtering problem by [K [K66) Online gradient descent was shown to be a minimax optimal method by [KW, CBLW96]. These works show if ||,r||| S B and ||w0|| || < W. then online gradient descent achieves a regret bound O A matching lower bound Q D(22)) was given by [CBLW96] using a dataset that contains only one example. In the adversarial setting, online gradient descent and exponentiated gradient were studied by [CBLW96, KW97]. Given the knowledge of B, by suitable tuning the learning rate, the two algorithms achieve regret bound O(L(w*)), )), which grows linearly with T in the worst case. Furthermore, if the algorithms know an error bound E for L(w") and a bound W for ||w*]] |]. then these algorithms can achieve a regret bound O E), which is O( ((VT) in the worst case. These regret bounds cannot be further improved for such types of algorithms. On the other hand, assuming y(x) S Y and ||ا|||| x B for any & E X, [Vov01, AWO1] obtained a regret bound of O (Iw= 112 + d (og(TX//))) using a so called online nonlinear ridge regression method.

---

A matching lower bound of Q[[[== 11² + dog T') were given by [CL06, Vovo1]. Recently better lower bound of D[dY? log T' were given by [BKM 15, GGHS 19]. Another interesting setting is the stochastic setting studied by [OMP21], where y(æ:) w" x + g. is zero-mean sub-gaussian noise with variance o². In particular, such a setting, the label y can be unbounded. Ouhamma et al. showed that the online (nonlinear) ridge regression with high probability has regret bound of Odda log T' log log T).
Notation and Preliminaries
In this section, we introduce the notations we will use in the paper. Let X C R be the set of n examples Denote by w E Fd the target vector that labels each æ E X by y(z) = w- z. Let A be self-directed learner. For i E [n], we use random vector ( E denote the example in X that is selected by A in the i-th round. We denote by Lg be subspace spanned by examples 2 ,..., ..)) and L the subspace that is orthogonal to L, For every E R" and for every subspace L S R we denote by vr, = projz (v), the projection of onto I.. Furthermore, we will use 5 to denote the unit sphere in _2 and use Sd to denote the uniform distribution over Std
Optimal Gain from Ordering under Arbitrary Data is Hard
In this section, we show that self-directed linear regression, in general, is hard to approximate, even when X S 5d and w" is drawn uniformly from S
In the rest of this section, we will give high-level overview of the proof of Theorem 1.5. The full proof of results in this section can be found in Appendix A. The key idea is that if we have a good efficient self-directed learner, then can obtain efficient algorithm that approximately solves the k-densest subgraph problem (DISS), which has been shown hard to approximate by [Man17].
Definition 3.1 (Densest k- k-Subgraph Problem (DkS)), Ler G (V, E) be an undirected graph with vertices and m edges, and let k E [n]. The goal is to find subset of k vertices S such that the edge density p(S) == | (15)) is maximized, where E(S) denotes the of all edges among the vertices in S. We define opt to be the maximum density over all possible subsets of l vertices. Given G and k; a-approximate algorithu for DKS problem outputs subset of k. vertices S such that (p((S) 2 opt in polynomial time.
The Sequential Spanning Problem (SSP) To begin with, observe that every self-directed learner has two parts, selecting examples and making predictions. The first observation, which is stated Lemma 3.2, is that with a prior distribution of w", it is easy to obtain a Bayesian optimal prediction each round.
Lemma 3.2. Let (x. (n)) C Rd be a set of examples and w" be a target vector drawn uniformly from Sa that labels y = w x(0 for each x(1) E X. Given given any set of labeled examples (xx1), ())), ......... (z (e(i-1).((-11)) (() denote by L.-1 the subspace spanned by (1)), ..... "i..,,((--1)) (i-1) and wt the projection of w² onto L,-1. Let A be self-directed learner, denote
by g be the prediction of Afor the next example 10(), then we have Ew-
(()() - (0)) | ww.,, .) 2 Egg- (wi)) =0)) wi..... Furthermore, the inequality holds for equality if g(0) = wi_., (.)..
With the Bayesian optimal prediction, the problem becomes how to select good ordering. We show in Proposition 3.4, the problem can be equivalent to formulate as the following Sequential Spanning Problem.
Definition 3.3 (k-SSqqeentil Spanning Problem (k-SSP)). Let X (x.))..... (m)) Ie be set of m points with unit norm and let k E N. Consider an ordered sequence a of points of X, ie.. =ftt) ((()) ..... x and define Lij to be the sub-space spanned by the first j-elements of o i.e., Lj- (ttn )...)(()))) span(z(o(1) ... x(o(5)) and Vo 0. Define the following cost,
called spanning cost,
k C(a,k) =
Σ
Ilpoii (ot1)) 1.
i=1
5

---

We define opt to be the minimum cost over all sequences of k-elements of X. Given X and k, an a-approximate algorithm for k-SSP Problem outputs an ordered sequence of points from X so that C(aa,) k) S opt in polynomial time.
We shall refer the special case of the problem where k m simply as the Sequential Spanning Problem.
Proposition 3.4 (From SSP to Self-Directed Learning). Let X = (x!l1) f..1))...,,. x(m)) E R.d be set of examples. For every self-directed linear regression algorithm A over X, with expected learning loss C(A, S we can use to get randomized algorithm A' for SSP over X with expected cost (a, m)) S )"A, Moreover, given a randomized algorithm A' for SSP over X, we can get a self-directed linear regression algorithm A over X. with expected learning loss ((A.S*)= E(((o, m))/d. In particular, the construction can be done efficiently.
With the intuition above, we only need to show it is ETH-hard to approximate the SSP. The key technical result we obtain is the following proposition.
Proposition 3.5 (From D to SSP). For every function a(d, m.) RR Rt - Itt, if there is an ad,, m) -mp-apopxximate algorithm for the SSP, then there is a 64a² (n", n -approxximate algorithm for the DKS problem.
As a direct corollary of Proposition 3.5, we obtain the computational hardness of SSP.
Corollary 3.6 (ETH-hardness of SSP). Assuming the Exponential Time Hypothesis (ETH) is true, then there is no algorithm that outputs an d²/ log log --approximate solution to the SSP in poly m) time, where e 0 is a universal constant.
Proof of Corollary 3.6. By Corollary 1.3 in [M if the Exponential Time Hypothesis (ETH) is true, then there is no polynomial time //ol log "-approximate algorithm for k-densest subgraph problem. By Proposition 3.5, there is a polynomial time d log log d d-approximate algorithm for SSP, we can obtain an efficient 1/ log log" a approximate algorithm for k-densest subgraph problem. Thus, if ETH true it is hard to approximate SSP within di/poly log log factor in polynomial time.
In the rest of the section, we introduce the high-level of the proof of Proposition 3.5 by breaking down into two steps.
From E-Edge Packing to SSP In the first step, introduce an intermediate problem called k-Edge Packing. We want to show if we can approximate SSP efficiently then we can approximate k-Edge Packing efficiently.
Definition 3.7 (k-Edge Packing). Let - EV, be an undirected graph with vertices and m edges, and let kt E [n]. The goal is to find subset of k edges S such that the number of vertices covered by S, VVS)) is minimized, where VSS) denoles the set of endpoints of edges in S. We define opt to be the minimum number of vertices covered by any possible subsets of k edges. Given and k. a-approximate algorithm for the k-edge packing problem outputs subset of k edges S such that V(S)= & copt in polynomial time.
The key idea in this step is to show Lemma 3.8, if we can approximate k-SSP efficiently, then can approximate k-edge packing efficiently.
Lemma 3.8. For every function a R+ R+ Rt, if there is an a(d, a(d,m) mapappooxiate algorithm for k-SSP problem, then there is a 20(n, m)-apprxximate algorithm for k-edge packing problem
To build connection between geometric problem and combinatorial problem, we have the following construction. Given a graph G = (V, F.) with n vertice and m edges, we will map every edge (u, v) to sparse n-dimensional vector Tue such that the only non-zero entries are F, I, = -1. 1. In this way, we obtain dataset X as the input of A. the approximate algorithm for K-SSP. Intuitively, if we select & edges in G that are disjoint, then no matter how to order the corresponding vectors of these k edges, the spanning cost is (kk). But if we select & edges that form a clique, the corresponding vectors span a subspace of dimension O D(Vk), so it is easy to order these vectors to get a very small spanning cost. With such an intuition, the key structure result we use here is that if solution to the k-SSP problem has a sufficiently small cost, then the corresponding edges to these k

---

vectors must be sufficiently connected to each other and thus cover a sufficiently small number of vertices.
However, now we are only able to approximate the k-edge packing problem with an algorithm that approximately solves the k-SSP problem. To finish this step, should also be able to algorithm for SSP as a subroutine to solve the k-SSP problem. We show this is possible in Lemma 3.9.
Lemma 3.9. Assume that an algorithm for SSP in d dimensions exists that finds an a(d, m)- approximate solution in poly m) time for some function : RR x R - Rt. Then an algorithm that finds a 4m(m(d= + m.), m(d d + m))-approximate solution for k-SSP for every value of l in poly(d, m) time exists.
The intuition here is that if the dataset is in general position (every of examples are linearly independent) then SSP is actually d-SSP. Given any dataset X with m points, we are able to map X a dataset X' in f(k, d, m) > d dimension that is in the general position. Such a map done by making multiple copies for each example, lifting them to high dimension and adding tiny structured noise each of them. We will show that such a transformation well preserves the information in the original dataset that if we run A over X', we can extract good approximate solution to the original k-SSP from the first [k; d, m) terms of the output solution.
From D&S to k-Edge Packing So far we have shown how to use an algorithm for SSP to solve the k-edge packing problem. Our final step to show Lemma 10, which implies that if we can approximately solve the k-edge packing problem then we can also solve the k densest subgraph problem.
Lemma 3.10 (k-edge packing and DiS). For a > 0, if there is an a-approximate algorithu for k-edge packing problem, then there is a² aa-aproximmate algorithm for DkS problem.
Notice that k-edge packing is seeking k edges that cover few vertices possible, which can be thought as a dual problem of DKS. we are able to find the largest number f(k) such that s f(k) edges cover most l vertices, then these fkk edges induce the densest subgraph with k k-vertices. The idea behind Lemma 3.10 that we can approximately find such f(k) using an approximate algorithm for k-edge packing and thus approximately find the k-densest subgraph.
With the above three lemmas, we can prove Proposition 3.5.
Proof of Proposition 3.5 Assume we have an a'd, mapproxxmiae algorithm for SSP problem, then by Lemma 3.9, we get an efficient 4a((d + m)m, (d+ (d))mm))alggo) allgorihhm for k-SSP problem. By Lemma 3.8, we get an efficient 8a((m (o0(m++m) +nnnnmmm problem. Since (m + n)mm S n always holds, we get an efficient 8a(n2, apprroxiiee algorithm for k-edge packing problem. By Lemma 3.10, this gives us an efficient 64a2(n2), 1,, ,,²) aapproxxiie algorithm for k-densest subgraph problem.
algorithm for k-edge packing
Ollog ()-lpg))-Appoxxiiii AAAppooximatioon for Spherical Data
Theorem 1.5, suggests that without any assumption on the structure of the data, it is hard to obtain an efficient self-directed learners that approximates the best possible improvement over learning in random order. This motivates In this section, we consider perhaps the most natural setting, where the dataset X is drawn i.i.d. from gd. Our main result in this section shows a simple greedy heuristic, Algorithm 1, which selects the "easiest" example in each round, and has nearly (i.e., off by a log dlfactor) optimal gain of ordering.
study the learning problem over datasets with natural structures.
We first bound the Gain of Ordering achieved by the greedy heuristic described in Algorithm 1.
Proposition 4.1. Let X be set of 2 poly(d) examples drawn i..dd from Sd and let A denote Algorithm 1, then over the randomness of the dataset X, in expectation, (,A,X, < 0(1dd 2//d)
7

---

Algorithm 1 SSLIEDDRECTDDLLEEARRRRRSSSOOO
Randomly partition X into d subsets XI..... Xa such that X; contains O(n/ (d i)2) examples.
for i 1........4 dd do
Set - =
x.i-1)). ,...,,,(-111),,
Find (( E -; consistent with (x(11) (,())) (..,,,.... (x(1-1), (001-1,,,(001)) 11(-11).
Select (0) argmin projj.... (z)
Predict g(0) = w(() xX00 and receive (
Label all unlabeled examples in X using (d)).
We start with some intuition for Algorithm 1. Since the observed labels y( are consistent with w", after selecting examples z("),.... (0),, our guess w(() at step coincides with the projection wf, of "t onto the subspace L, spanned by these examples. If we choose any (+++1) and predict wł, (z+1),,
then we will pay ? 7w,, 2 (w "T (2 Since we make a random partition of
the data in advance, we are able to show that in expectation G/( w L.
(+ 1/(d- i).
This suggests the cost we pay in each round is proportional to (1+1)
and we should choose the example that is closest L, greedily. Our key technical lemma shows that in the + 1-th round, for a greedily chosen example and a randomly chosen example, the expected ratio of the loss is O(n ((n22/(d-)),
We next show that the optimal Gain from Ordering can only be O(log d) times larger than that of Algorithm 1.
Proposition 4.2 (Bounding the Optimal Gain). Let X C S be a set of > poly(d) examples drawn i.i.d. uniformly from Std. For every 8 e (3/n, 1), with probability least 99%, G* (*(, Q(1/d+ + ön (24228)/d)
Recall that in Section 3, we showed that if w ~ Sd, then the expected learning cost is proportional to the optimal spanning cost of sequence of examples. This implies analyzing the best Iearner is equivalent to analyzing the sequence of examples in X with the smallest spanning cost. The key of our proof is show that the distribution of Sd is very concentrated and unless the size of X is very large there no sequence of examples whose spanning cost is much smaller than the average spanning cost.
As a direct corollary, we are able to show Algorithm has a gaining that at most 0(1/ log dX)*(XX (X, which is exponential improvement of the hardness of approximation obtained by Theorem 1.5.
Proof of Theorem 1.6 By Proposition 4.1 and Proposition 4.2, we know that with probability at least 99%, ((A, X, -x, < 1/dd+ 1/d and G (X,,s4)- 2 1/d + -n-222+) Here we ignore the hidden constant within the bound obtained from Proposition 4.1 and Proposition 4.2 because it will only add some multiplicative constant factor in our final result. It remains to tune the parameter
show that 1/d+n 17d4-n-(2-2277 (2+2377 is at most Ollog d). To do this, we write gd/2 and we consider different
ranges for s. We consider the following two cases.
< 2/d 2(1/d 8n- (2+25)/d). which implies Case If 2 then we have we have 1/d n -2dd 2/d
C(A,X,3' 8d (X,))"(X,
Case 2: If
d, then -2/d > 1/d and 1/d 8n 22+26 > 8n 8n- (2+28)/d This implies I/d-on (212677 < n6/d 308. We set 5 1/ log and we obtain that 1 = /// log log O(log)) s) < O(log d). This implies that G(A,X,8 $4) 2 2(1 log (X)""(X(""")
2/d
1/d+n 2/4
Remark 4.3. We remark that although the stutement of Proposition 4.1 and Proposition 4.2 are about the average performance of the algorithmm, the same results also hold under the worst-case setting because, with dataset from spherical distribution, the learning cost of Areadom under
8

---

these two settings are asymptotically the same in expectation. A detailed discussion about this and the proof of Proposition 4.1 and Proposition 4.2 are deferred to Appendix B.
Remark 4,4, Although according to Theorem 1.6, Algorithm approximates the optimal gaining within (log d) factor, when S s for some constant that doesn't 't depend on d or n. d Algorithm I approximates the optimal gaining within constant factor and thus is nearly optimal.
Self-Directed ReLU Regression
Finally, we study the problem of self-directed ReLU regression, which shares similar spirit the one of self-directed linear regression. According to Proposition 4.1, given a dataset X that is drawn from 3 we are able to design an efficient learner with gaining ( X) 2 min (d)2/)) if each x is labeled by y(z) = w æ. In fact, the bound of min(() ((n can also be obtained by the following Algorithm 2, when each x: is labeled by a ReLU function Relu(w" xx). However, an interesting phenomenon
found is that if we give Algorithm 2 some reference example (zx y)) as a warm start such that ((z(1)) w²) Oo < 2/2, then
able improve the gaining to min(S)(d) ((1//d/ log d + lo log d)), which is huge improvement when the dimension of the problem is large.
Algorithm 2 SELFFDIRCCEEDRELLUGGGEESSSSS
Let (z:(0), ()) be pair of reference example such that ((x!'),'''' - 0o S 4/2.
(Assume (x) (0) ) (0, 0) if there is no such a warm start)
Randomly partition X into d subsets X1...., Xa such that X; contains n//d examples.
for i 1,...,dd d. do
Set L1-1 = span
x(i-1)), where 206 is example that has been selected with positive
label for j E {0, .0....,. 1}.
Find (+) E Li-1 consistent with (zr(0), (,(0),,(")),,. ,,(")),..., ( (x((-11) ,y((-1)
Keep selecting
X; such that w+)) x E argmin (() x' and predict Relu(w()) xx)
until see some (1)( (1)) such that ())) > O.
Label all unlabeled examples in X using (d+11)
Theorem 5.1. Let X S Rd be a set of n 2 poly(d) examples drawn i.i.d. from St. Let G(A, X) be the gain from ordering of Algorithm for the self directed ReLU regression problem over X. Then
min tan" 9, log d min(O tan 9n log d (
O
log
if
Tndlog > exp(g) (
ndn
n
((A,))-'
O
log d'
if if S And logl S exp(
(og()))
n2/a
if and andlog d < 1.
ndn
The main difference between ReLU regression and linear regression is that in ReLU regression, with good warm start, are able to start from the region that is labeled 0 by the target seek the decision boundary. Before we see positive example, we pay nothing. The first time we see a positive example æ, we pay (w* xz) The key technical lemma, Lemma 5.2 shows that we keep selecting the most "negative" example with respect to our current guess, the first positive example we see must have a very small margin with respect to w², In this way, Algorithm 2 learns w" with a very small cost. We refer to Appendix C for more details and proofs.
Lemma 5.2 (Geometry Technical Lemma). Let w* E Sd be target vector and let S be arbitrary vector such that 0 = ((w", w) < T/2. Denote by = {x E Std w < O, w x 0}. For every a, E (0, 1), denote by K. ==:=a (x C w x asin 0) and Ka,b == fx w.wx sin 8 w x < -b f). Let be a point uniformly drawn from Sd There is some absolute constant
>> 1 such that if a/b 2 then Pr (x E Ka. x E K.) < 2exp
d 3 (b2 + 2ab cos 8))
6 Conclusion, Limitations, and Broader Impact
In this work, we study the self-directed learning problem for linear regression. Our work presents novel results both computational and information-theoreti Our first result shows that approxi-

---

mating the optimal self- delfedireeeed regret within a / log logd factor is ETH-hard under arbitrary datasets. Our second result yields novel characterization of the Gain of Ordering for data that are uniformly distributed on the sphere and gives an efficient approximation algorithm that bypasses the aforementioned hardness result and achieves close to optimal regret by exploiting the structure of the data. A limitation of our work is that our algorithms can currently handle linear (or ReLU regression). Moreover, our presented results assume that the labels are realizable even in this fundamental setting, nothing was known prior to work. Generalizing our results to other concept classes and investigating the effect of adding noise to the labels are natural questions for future investigation. Designing robust self-directed learning algorithms for broader concept classes under broader distributional assumptions are interesting direction for future work.
7 Acknowledgements
This work was supported by the NSF Award CCF-2144298 (CAREER).
References
[ABHUI5] P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings The 28 Conference on Learning Theory, COLT 2015, pages 167-190, 2015.
[ABHZ16] P. Awasthi, M. Balcan, N. Haghtalab, and H. Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152-192, 2016.
[AW01] Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43:211-25 246, 2001.
[B+ IB+5A) 54] D. Blackwell et al. Controlled random walks. In Proceedings of the international congress of mathematicians, volume 3, pages 336-338, 1954.
[BDEK95] S. Ben-David, N. Eiron, and Kushilevitz. On self-directed learning. In Proceedings of the eighth annual conference on Computational learning theory, pages 136-143, 1995.
[BDKM97] S. Ben-David, E. Kushilevitz, and Y. Mansour. Online learning versus offline learning. Machine Learning, 29:45-63, 63, 1997.
[BKM 15] Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth. Minimax fixed-design linear regression. In Conference on Learning Theory, pages 226- 239. PMLR, 2015.
[BLCW09] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pages 41-48, 2009.
[BU16] M. Balcan and R. Urner. Active learning-modern learning theory., 2016.
[By197] Tom Bylander. Worst-case absolute loss bounds for linear learning algorithms. In AAAI/AAI,, pages 485-490, 1997.
[CAL94] D. Cohn, I.. Atlas, and R. Ladner. Improving generalization with active learning. Machine learning, 15:201-221, 1994.
[CBL06] N. Cesa- Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[CBLW96] Nicolo Cesa-Bianchi, Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Tronsactions Neural Networks, 73))6644-619, 1996.
10

---

[CBS13] Nicolò Cesa-Bianchi and Ohad Shamir. Efficient transductive online learning via randomized rounding. Empirical Inference, page 177, 177. 2013.
[CL06] Nicolò Cesa-Bianchee and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[DGK I. Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Ap- proximation schemes for ReLU regression. In Conference on Learning Theory, COLT, volume 125 of Proceedings of Machine Learning Research, pages 1452-1485. PMLR, 2020.
[DKKZ20] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and SQ lower bounds for pac learning one-hidden-layer ReLU networks. In Conference on Learning Theory, COLT, pages 1514-1539. PMLR, 2020.
[DKM05] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In Learning Theory: 18th Annual Conference Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings 18, pages 249-263. Springer, 2005.
[DKR23] I. Diakonikolas, D. M. Kane, and Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. CoRR, abs/2302.06512, 2023.
[DKT722] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning a Single Neuron with Adversarial Label Noise via Gradient Descent. COLT. arXiv, June 2022.
[DKT723] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Self-directed linear classification, In The Thirty Sixth Annual Conference on Learning Theory, pages 2919-2947. PMLR, 2023.
[DKZ20] I. Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[DSZ10] T. Doliwa, H. Simon, and S. Zilles. Recursive teaching dimension, learning complexity, and maximum classes. In Algorithmic Learning Theory: 21st International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings 21, pages 209-223. Springer, 2010.
[FCG20] S. Frei, Y. Cao, and Q. Gu. Agnostic learning of single neuron with gradient descent. Advances in Neural Information Processing Systems, NeurIPS, 2020.
[FS97] Y. Freund and R. Schapire. A an application to boosting. Journal of Computer and System Sciences, 19-1199, 1997.
generalization of on-line learning and
[GGHS19] Pierre Gaillard, Sébastien Gerchinovitz, Malo Huard, and Gilles Stoltz. Uniform regret bounds over (Rt for the sequential linear regression problem with the square loss. In Algorithmic Learning Theory, pages 404-432. PMLR, 2019.
[GKK] S. Goel, S. Karmalkar, and A. R. Klivans. Time/accuracy tradeoffs for learning relu with respect to gaussian marginals. In Advances in Neural Information Processing Sys- tems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019.
[GKKT17] S. Goel, V. Kanade, A. R. Klivans, and J. Thaler. Reliably learning the relu in polynomial time. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 1004-1042, 2017.
[GM93] S. Goldman and D. Mathias. Teaching a smart learner. In Proceedings of the sixth annual conference on computational learning theory, pages 67-76, 1993.
11

---

[GS94] S. A Goldman and R. H Sloan. The power of self-directed learning, Machine Learning. 14:271-294, 1994.
[Han57] J. Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
[Hanl1] S. Hanneke. Rates of convergence in active learning. Ann. Statist., 39(1):333-36) February 2011.
[Haz16] E. Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[HW19] G. Hacohen and D. Weinshall. On the power of curriculum learning in training deep networks. In International Conference on Machine Learning, pages 2019.
PMLR,
[JRSS15] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398 406. PMLR, 2015.
[KK05] Sham Kakade and Adam T Kalai. From batch transductive online learning. Advances in Neural Information Processing Systems, 18, 2005.
[KS09] A. T. Kalai and R. Sastry. The isotron algorithm: High- digensiimenioonl isotonic regression. In COLT. Citeseer, 2009.
[KW97] Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(():1-63, 1997.
[KWH06] Jyrki Kivinen, Manfred K Warmuth, and Babak Hassibi. The p-norm generalization of the Ims algorithm for adaptive filtering. IEEE Transactions on Signal Processing. 54(55:1182-1795 2006.
[Lit88] N. Littlestone. Learning quickly when irrelevant attributes abound: new linear- threshold algorithm. Machine Learning, 2(4):285-318, 1988.
[Lit89] N. Littlestone. From online to batch learning. In Proceedings of the Second Annual Workshop on Computational Learning Theory, pages 269-284, 1989.
[LL98] Charles X Ling and Chenghui Li. Data mining for direct marketing: Problems and solutions. In Kdd, volume 98, pages 73-79, 1998.
[LLW91]] Nicholas Litrlestone, Philip M Long, and Manfred K Warmuth. On-line learning of linear functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 465 1991.
[LW94] N. Littlestone and M. Warmuth. The weighted majority algorithm. Information and Computation, (88(2)21122211 February 1994.
[Man17] Pasin Manurangsi. Alooos-polynomial ratio eth-hardness of approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 954-961, 2017.
[Mat97] D. Mathias. A model interactive teaching. journal of computer and system sciences, 54(3):477551, 1997.
[MSSZ22] F. Mansouri, H. Simon, A. Singla, and S. Zilles. On batch teaching with sample complexity bounded by ved. In Advances in Neural Information Processing Systems, 2022.
[NL11] E. Ni and C. Ling. Direct marketing with fewer mistakes. In Advanced Data Mining and Applications: 7th International Conference, ADMA 2011, Beijing, China, December 17-19, 2011, Proceedings, Part I pages 256-269. Springer, 2011.
12

---

[OCCB15] Francesco Orabona, Koby Crammer, and Nicolo Cesa-Bianche Bianchi. A generalized online mirror descent with applications to classification and regression. Machine Learning. 99:411 19:411-433, 2015.
[OMP21] Reda Ouhamma, Odmbric-Ambrym Maillard, and Vianney Perchet. Stochastic online linear regression: the forward algorithm to replace ridge. Advances in Neural Information Processing Systems, 34:24430-24433 2021.
[Ora19] F. Orabona. A modern introduction online learning, 2019.
[Rob51] H. Robbins. Asymptotically subminimax solutions of compound statistical decision problems. In Proceedings of the second Berkeley symposium on mathematical statistics and probability, volume 2. pages 131-149. University of California Press, 1951.
[RS13] Rakhlin and K. Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pages 993-1019, PMLR, 2013.
[SIRS22] P. Soviany, R. lonescu, P. Rota, and N. Sebe. Curriculum learning: A survey. Interna- tional Journal of Computer Vision, 13066):556-1165, 2022.
[Sol17] M. Soltanolkotabi. Learning relus via gradient descent. Advances in neural information processing systems, 30, 2017.
[Vov90] V. Vovk. Aggregating strategies. In Annual Workshop on Computational Learning Theory: Proceedings of the third annual workshop on Computational learning theory, 1990. Association for Computing Machinery, Inc, 1990.
[Vov95] V. Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
[Vov01] Volodya Vovk. Competitive on-line statistics. International Statistical Review, 69(2):213- 248, 2001.
[WCZ21] X. Wang, Y. Chen, and W. Zhu. A survey on curriculum learning. IEEE Transactions Putlern Analysis and Machine Intelligence, 44(0))4555-4576 2021.
[WH60] Bernard Widrow and Marcian E Hoff. Adaptive switching circuits. Technical report, Stanford Univ Ca Stanford Electronics Labs, 1960.
[WHGS22) Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojeiech Szpankowski. Sequential vs. fixed design regrets in online learning. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 438-443. IEBE, 2022.
[ZSA20] C. Zhang, J. Shen, and P. Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Advances in Neural Information Processing Systems, NeurlPS, 2020.
13


Reviews:
[{"review_id": "vdv7fnpDVP", "reviewer": "Reviewer_eLsL", "summary": "The paper considers online (realizable) linear regression, in a setting where the learner may choose the order of datapoints (=self directed learning) with the goal to minimize her regret. Roughly, the gain from ordering of a self directed learner $\\mathcal A$ is defined as the ratio between the best performance given random order samples, and the performance of $\\mathcal A$. The paper proves that:\n1. Under the exponential time hypothesis (ETH), no efficient algorithm can approximate the optimal gain to within a factor of $d^{1/\\log\\log^c d}$ for some constant $c$. This holds in particular in the case that the ground truth is uniform over the unit sphere.\n2. Assuming that the datapoints are drawn uniformly over the unit sphere, as well as the ground truth hypothesis vector, a certain greedy algorithm (Algorithm 1) provides a $\\log d$-approximation to the optimal gain.\n", "questions": "### Minor comments\n- Lines 62-63 are repeated inside Remark 1.3\n- Line 84: \"one mistake suffices\" - suffices for what?\n- Theorem 1.5: \"Let X be an arbitrary set...\"; There exists sets (e.g., singletone X) for which it is easy to approximate the optimal gain. I assume the claim should refer the (non) existence of an algorithm that works for arbitrary sets. \n- When using 99% in the theorem statements it is unclear what is the dependence on high probability factor.\n- Notation for the datapoints is inconsistent sometimes, for example in Definition 3.3, first $x_i$ then $x^{(\\sigma(i))}$\n- In Algorithm 1, I think $L_{i-1}$ in the selection of $x^{(i)}$ should be $L_{i-1}^\\perp$.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well written, the proofs are non trivial, and from a purely theoretical perspective the question studied seems interesting,\n", "weaknesses": "The motivation for studying regret of a self directed learner is not entirely clear to me. Curriculum learning sounds like a good motivation for sample complexity or convergence rate, but not regret. In which truly online setting would the learner have access to the order of datapoints?\nTo me this is really the main weakness, I do not understand the motivation of this question in the context of machine learning problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n## Reviewer eLsL\n\n>The motivation for studying the regret of a self-directed learner is not entirely clear to me. Curriculum learning sounds like a good motivation for sample complexity or convergence rate, but not regret. In which truly online setting would the learner have access to the order of data points? To me this is really the main weakness, I do not understand the motivation of this question in the context of machine learning problems.\n\nWe thank the reviewer for carefully reading our manuscript and providing insightful feedback. Self-directed learning is a fundamental online learning model that studies if the ability to reorder examples can help a learner make better predictions. The study of self-directed learning can be traced back to the 1900s e.g. [1,2,3] and even very recently there is still surprising progress made in this direction e.g. [4], which shows in the problem of online linear classification if the learner has the power of reordering then the number of mistakes made by the learner to learn the target linear threshold function is significantly smaller than that in the setting where the order is chosen by an adversary. Our work extends the classification setting studied in the literature to the more general regression setting.\n\nIn practice, there are also many direct applications of this learning model. A direct application is directed marketing [5,6], one of the common and crucial business intelligence tasks, which is a process of identifying likely buyers to market products accordingly. In direct marketing, an agent must study customers’ characteristics and needs, and select customers to market its products to minimize its market loss. As a more concrete example, a streaming service or social media platform may want to learn the content preferences of customers without making too many bad recommendations. In this application, the platform chooses the order in which to present the content (from a pool of available videos) in order to minimize the “regret” (and keep the user engaged).  We will include a more detailed discussion on motivation in our revised manuscript.\n\n\n[1] Ben-David S, Kushilevitz E, Mansour Y. Online learning versus offline learning[J]. Machine Learning, 1997, 29: 45-63.\n\n[2] Goldman S A, Sloan R H. The power of self-directed learning[J]. Machine Learning, 1994, 14: 271-294.\n\n[3] Ben-David S, Eiron N. Self-directed learning and its relation to the VC-dimension and to teacher-directed learning[J]. Machine Learning, 1998, 33: 87-104.\n\n[4] Diakonikolas I, Kontonis V, Tzamos C, et al. Self-Directed Linear Classification[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 2919-2947.\n\n[5] Ling, Charles X., and Chenghui Li. \"Data mining for direct marketing: Problems and solutions.\" Kdd. Vol. 98. 1998.\n\n[6] Ni, Eileen A., and Charles X. Ling. \"Direct marketing with fewer mistakes.\" Advanced Data Mining and Applications: 7th International Conference, ADMA 2011, Beijing, China, December 17-19, 2011, Proceedings, Part I 7. Springer Berlin Heidelberg, 2011.\n\nMinor Comments\nWe thank the reviewer for pointing out typos and making suggestions for improving our manuscript. Here are answers to some of the minor comments.\n- Line 84 => one mistake suffices to learn the one dimension threshold function.\n- We agree with the reviewer and will restate Theorem 1.5 so that it is more clear.\n- The randomness for spherical data only comes from the fact that the points of the dataset $X$ are drawn i.i.d. from the uniform distribution on the unit sphere. \n\n\n"}, {"review_id": "2XIl8oEkfu", "reviewer": "Reviewer_Kpn9", "summary": "The paper focuses on the setting of \"self-directed online learning\", where the online learner has access to the entire set of unlabeled points $X = \\{x_1,\\ldots,x_n\\}$ and has to choose the point in some order $x_{\\sigma(1)},\\ldots,x_{\\sigma(n)}$ such that at time $t$, the learner has to predict the label $y^\\prime_{\\sigma(t)}$ for $x_{\\sigma(t)}$, then observes the true label $y_{\\sigma(t)}$ and suffers loss $\\ell(y_{\\sigma(t)}, y^\\prime_{\\sigma(t)})$.\n\nIn the paper, the \"gain from ordering\" of a self-directed algorithm is defined w.r.t random order learning (as the ratio of the total losses of the best random order algorithm and the self-directed algorithm), where the learning algorithm picks the points according to a random permutation $\\sigma$ of $[n]$.The labels for the points in $X$ will of course come from some $f$ belonging to a concept class $\\mathcal{C}$ and the paper considers the gain from ordering both in expectation for a random labeling $f \\sim F \\in \\Delta(\\mathcal{C})$ (average case) and also when the worst possible labelng $f \\in \\mathcal{C}$ is chosen by an adversary.\n\n* The paper shows that assuming the ETH (Exponential Time Hypothesis; 3SAT cannot be solved in subexponential time), no polynomial time self-directed learning algorithm can achieve even a $d^{1/{\\rm polyloglog}(d)}$ approximation of the optimal gain from ordering when $X$ is an arbitrary subset of points in $\\mathbb{R}^d$, even when the concept-class is linear ($f(x) = w \\cdot x$) and the target vector is sampled uniformly from $\\mathbb{S}^d$.\n* When $X$ is also sampled uniformly from $\\mathbb{S}^d$ (spherical data), the paper proposes and analyzes an efficient greedy self-directed learner that achieves a $\\log d$ approximation of the optimal gain and also shows that the gain from ordering for this algorithm is at least $\\min(\\Omega(d),\\Omega(n^{2/d}))$.\n* For the ReLU linear regression problem (labeling is $f(x) = \\mathrm{Relu}(w \\cdot x)$ for some $w \\in \\mathbb{R}^d$) with spherical data, the paper presents an efficient self-directed learner that achieves a gain of $\\min(\\Omega(d), \\Omega(n^{2/d}/ log d + log n/ log d))$ with some non-trivial assumptions.", "questions": "* Could the authors comment on the applicability of the algorithms proposed under the spherical data assumption, even in quasi-practical scenarios (assuming very well-behaved datasets, preprocessing etc)?\n   * Are there any theoretical justifications for this assumption being a useful approximation for more general cases?\n   * Have the algorithms been evaluated on simulated data?", "limitations": "None (w.r.t negative social impact)", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The ETH-hardness result for approximating the optimal gain from ordering is very interesting from a technical perspective (relies on a sequence of reductions showing that approximating optimal gain from ordering is at least as hard as approximating the densest $k$-subgraph problem for some appropriate choice of approximation ratios).\n* The reduction reveals a very interesting equivalence between optimizing the gain from ordering and choosing an ordering that optimizes the sequential spanning cost of the data points --- which is the sum of the squares of the $\\ell_2$-norms of the projections of the points taken in some order, where the $i$-th point is projected to the orthogonal complement of the span of the previous $(i-1)$ points.\n* The efficient self-directed algorithm for linear regression for spherical data very intuitively exploits the above equivalence, which may be of independent interest.", "weaknesses": "* The ETH-hardness result requires a lot of technical machinery which is mostly relegated to the supplementary material. The proof sketches provided in the main paper are not very informative when considered \"on their own\".\n* The spherical data assumption used to design efficient algorithms for self-directed linear regression and ReLU linear regression is an interesting enough starting point theoretically, but may not be very useful in a lot of practical scenarios. Even considering random (even i.i.d) data, less-restrictive distributional assumptions would be needed.\n* No experimental results or even code are provided for the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Reviewer Kpn9\n\n> The ETH-hardness result requires a lot of technical machinery which is mostly relegated to the supplementary material. The proof sketches provided in the main paper are not very informative when considered \"on their own\"\n\nWe thank the reviewer for pointing out this shortcoming. The proof of the hardness result is complicated and due to the space limitations, we are only able to break down the proofs into several pieces and present the key technical lemmas in the main body of the paper. We will modify the proof sketches in the main body and add a more detailed overview in the next revision of this work.\n\n> The spherical data assumption used to design efficient algorithms for self-directed linear regression and ReLU linear regression is an interesting enough starting point theoretically, but may not be very useful in a lot of practical scenarios. Even considering random (even i.i.d) data, less-restrictive distributional assumptions would be needed. Could the authors comment on the applicability of the algorithms proposed under the spherical data assumption, even in quasi-practical scenarios (assuming very well-behaved datasets, preprocessing etc)? Are there any theoretical justifications for this assumption being a useful approximation for more general cases?\n\nThis is a good point. Our hardness result shows that if we consider a very general dataset, even if we know the target is drawn uniformly from a sphere, it is computationally hard to compute an order of examples that approximates the optimal order very well. That is why the assumption of the structure of the dataset is necessary to get a non-trivial approximation result. In the distribution-dependent setting, uniform distribution over a sphere (or standard Gaussian) is perhaps the most standard assumption [1,2,3]. \nOur negative result shows that for arbitrary datasets it is computationally impossible to obtain (approximately) optimal orderings while our positive results show that a simple greedy heuristic is almost optimal for spherical data.  It is a very interesting direction for future work to investigate whether it is possible to obtain efficient ordering algorithms for broader (but non worst-case) structured distributions. \n\nFurthermore, our greedy algorithm for linear regression can still be applied to more general (non uniform on the sphere) datasets.  In fact, we implemented our method and in our experiments (see next question) we empirically observed that our greedy heuristic can outperform the random order for datasets that are far from being uniform on the sphere.\n\n[1] Dasgupta S, Kalai A T, Monteleoni C. Analysis of perceptron-based active learning[C]//International conference on computational learning theory. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005: 249-263.\n\n[2] Diakonikolas I, Kane D M, Kontonis V, et al. Learning general halfspaces with general massart noise under the Gaussian distribution[C]//Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022: 874-885.\n\n[3] Yan S, Zhang C. Revisiting perceptron: Efficient and label-optimal learning of halfspaces[J]. Advances in Neural Information Processing Systems, 2017, 30.\n\n> No experimental results or even code are provided for the proposed algorithms. Have the algorithms been evaluated on simulated data?\n\nEven though our primary goal in this work is to establish a theoretical understanding of this problem, we agree with the reviewer that implementing our method and evaluating it empirically is a nice addition to our manuscript. We implemented our greedy algorithm (see Algorithm 1) and tested it using datasets drawn uniformly on the unit sphere spherical dataset and also data generated by mixtures of spherical data (similar to Gaussian mixtures).  We observe that our simple greedy method is computationally efficient (and can be implemented with a few lines of code) and also consistently outperforms the random-order method (see attached figures). We also implemented our algorithm for ReLU regression (Algorithm 2) over a spherical dataset. We see our algorithm achieves a much smaller regret than that of a random order. Furthermore, we notice that if our algorithm is given a suitable initialization, then it has an even much better performance. More comprehensive empirical evaluation on the gain of ordering in regression (on non-synthetic data) is an interesting question for future work.\n\nWe state the details of our experiments here. The first set of experiments is to evaluate the performance of Algorithm 1 over a spherical dataset. For a single experiment, we sample $20d$ examples and a target vector $w$ uniformly from the unit sphere in $R^d$. We label the dataset with an order computed by Algorithm 1 and a random order, then we compute the total regret respectively. We perform the experiment for $d=5,10,\\dots,75$, for each $d$, we repeat the experiment 30 times and compute the average regret. The result of this set of experiments is shown in the first attached figure.\n\nThe second set of experiments is to evaluate the performance of Algorithm 2 over the spherical dataset. The data generation process is the same as the one in the first set of experiments. However, in this set of experiments, we will compare three different settings. 1. ReLU regression with a random order. 2. Algorithm 2 without an initialization. 3. Algorithm 2 with initialization $(v,v\\cdot w)$, where $v=sgn(w)$.\n\nThe third set of experiments is to evaluate the performance of Algorithm 1 over more general datasets. The setting of the experiments is similar to the first set of experiments. However, the dataset is generated as follows. For each $i \\in [d]$, we generate 20 examples $e_i+0.05\\epsilon$, where $e_i$ is the $i$th standard basis vector and $\\epsilon$ is a vector uniformly drawn from the unit sphere. Finally, we normalize every example so that each of them has a unit norm. The result of this experiment is shown in the third attached figure.\n\n"}, {"review_id": "gXB8XrZogI", "reviewer": "Reviewer_N13f", "summary": "The paper considers an online regression problem and attempted to achieve the optimal gain of ordering with efficient algorithms. For general concept class, the optimal gain of ordering is $O(n^{2/d})$, where $n$ is the number of data, $d$ is the dimension of the data.\n\nThe paper first show there is not polynomial algorithms exists to achieve optimal gain of ordering if the data label is generated arbitrarily. However, if data label is uniformly generated from a unit sphere, a $\\log d$-algorithm, which picks the order of the examples based on its difficulty. When concept class is chosen to be ReLu, the optimal gain of ordering is $O( \\min(d,  n^{2/d} / \\log d + \\log n / \\log d) ) $, ", "questions": "no", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "not capable of evaluating", "weaknesses": "no ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work."}, {"review_id": "VfdG1jU2bJ", "reviewer": "Reviewer_5ur6", "summary": "This paper studies the problem of self-directed online learning, where a set of examples (i.e., features) is provided in advance, and the learner has the autonomy to determine the order of the examples with the aim of minimizing their regret. The primary focus is on realizable linear regression and ReLU regression under square loss, assessing the ratio between the best achievable regret with random order and the achievable regret with a self-directed order (termed as the 'Gain').\n\nThe main contribution of the paper aims to highlight the discrepancy between the efficiently achievable Gain and the optimal information-theoretical Gain. The key findings are as follows:\n\n1. If the optimal weight $w^*$ is sampled uniformly from the unit sphere, and the example set is chosen adversarially, then no polynomial time algorithm achieves the Gain of order $d^{-1/\\log\\log^c d}$ times the optimal information-theoretical Gain, assuming the Exponential Time Hypothesis (ETH).\n2. If $w^*$ is adversarial but the example set $X$ is sampled uniformly from the unit sphere, then a computationally efficient algorithm exists that achieves the Gain of order $1/\\log d$ times the optimal information-theoretical Gain.\n3. Absolute lower bounds for computationally efficient Gains are also established for the Linear and ReLU regression.\n\n*After the rebuttal: In light of the responses provided by the authors and my improved understanding of the impact of this work, I have decided to adjust my rating to \"accept.\"*", "questions": "I have a few questions for the authors:\n- Currently, the paper only considers the realizable case. Is it possible to extend the methodology to the unrealizable case (i.e., when the labels $y$ are adversarially given)?\n- Is there a known result that demonstrates the distinction between random order and worst-case order in the fixed design online setup?", "limitations": "No issue with negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of this paper lies in its unique presentation of a hardness result on the efficiently achievable Gain in the context of self-directed online learning. As far as I am aware, this is the first of its kind in this scenario. The reduction used in the proof is interesting and could potentially be useful in obtaining hardness results for other learning theoretical problems. In addition, the paper employs interesting geometric concepts to establish the efficiently achievable Gain in cases of random examples.", "weaknesses": "The primary limitation of this paper is its overall significance. While the results are intriguing from a theoretical computer science perspective, I'm not entirely convinced of their importance from a learning theoretical standpoint:\n\n1. The significance of an impossibility result in self-directed online learning is unclear, considering that we already have efficient algorithms for linear regression, even in the adversarial case.\n2. The results are somewhat challenging to fully appreciate given that the Gain is already a ratio, and the presented results are essentially a ratio of a ratio.\n3. In Section 4, it would be clearer to state the results for the worst-case $w^*$ directly, rather than including it as a remark.\n\nNevertheless, despite these points, I believe this paper still holds interest for the NeurIPS community due to its presentation of a set of intriguing technical results. This is the primary reason for my \"weak accept\" recommendation.\n\nAdditionally, I noticed a couple of typographical errors:\n- Line 202: A period is missing at the end of the sentence.\n- Line 211: \"Given\" is repeated.\n- Footnote of page 15 (in appendix)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Reviewer 5ur6\n\nWe thank the reviewer for carefully reading our manuscript and providing insightful feedback. We answer the reviewer's question in the rest of the rebuttal.\n\n> The significance of an impossibility result in self-directed online learning is unclear, considering that we already have efficient algorithms for linear regression, even in the adversarial case.\n\nThe significance of self-directed online learning is that: (i) it is a natural and well-motivated learning model (see also our response to reviewer eLsL) and (ii) it can potentially lead to much lower regret bounds than standard random or worst order learning.  The fact that efficient worst-order algorithms that achieve “low” (e.g., sublinear) regret exist does not mean that we shouldn’t try and make this regret even smaller by re-ordering the examples (self-directed learning).  As we discuss in the introduction of our manuscript, for $n$ examples on the real line that are classified by a linear threshold function, in worst-order  online learning $\\Omega(\\log n)$ mistakes are necessary. In contrast, a self-directed learner only makes one mistake.\nOur negative result shows that achieving the optimal gain from ordering (which can be very large) for arbitrary datasets is computationally intractable. In other words, even if for some dataset the (information-theoretic) optimal gain from ordering is large it is computationally intractable to find the optimal ordering of its points to achieve it.  Starting already from our work, our impossibility result motivates the study of the distribution-specific setting where structural assumptions about the distribution that generates the examples are made.\n\n\n> The results are somewhat challenging to fully appreciate given that the Gain is already a ratio, and the presented results are essentially a ratio of a ratio.\n\nIn our paper, the notion of Gain is used to compare the order selected by the learner and random order. The gain itself can be seen as an absolute improvement of a self-directed learner over an online (random) learner. In our paper, we also have results that bound the Gain itself (see e.g., Proposition 4.1). However, simply considering the absolute improvement is not very meaningful from a theoretical perspective, because we have to compare the performance of a self-directed learner with the best one. For this reason, we need to introduce the term of approximate ratio, which compares a self-directed learner with the best self-directed learner. This is why our main result is presented as a ratio of ratio.  We will include this clarification in our revised manuscript.\n\n\n\n>Currently, the paper only considers the realizable case. Is it possible to extend the methodology to the unrealizable case (i.e., when the labels y  are adversarially given)?\n\nPrior to our work, nothing was known about the self-directed linear regression problem. We initiate its study focusing on the most fundamental setting of realizable linear regression. As our impossibility result reveals, even this (seemingly) vanilla setup is surprisingly difficult to fully understand.\nStudying settings where the predictions are noisy (by some adversary or at random) is a very interesting question that we plan to investigate in the future.  Currently we believe that our results could be generalized assuming mean-zero additive noise but we believe that the investigation of the effect of noise in the labels is beyond the scope of this work.\n\n\n\n> Is there a known result that demonstrates the distinction between random order and worst-case order in the fixed design online setup\n\nThis is a good question. Since this is the first work on self-directed linear regression, to the best of our knowledge there is no previous result showing the distinction between a random order and the worst order. However, there is an example showing such a distinction. Assuming there are $d+m$ examples in $R^d$. The first $d$ examples are the $d$ basis vectors and the last m examples are $e_1+\\epsilon_i$, where $\\epsilon_i$ is a tiny noise. In this case, the worst order would be picking $e_1,e_2,\\dots,e_d$, while as m increases, a random order is likely to pick examples around $e_1$. So there will be a clear separation between the worst order and the random order. We will add a section in the appendix to explain this in detail in the next revision of our paper."}]

Author rebuttal:
We want to thank all reviewers for taking the time to read our manuscript carefully and for providing constructive and insightful feedback. We are very encouraged by the positive comments of the reviewers on the **novelty of the ETH hardness result** (Reviewers eLsL,Kpn9, 5ur6), **interesting and potentially useful techniques for proving the hardness result**(Reviewers Kpn9, 5ur6), **geometric intuitiveness of the self-directed learning algorithms** (Reviewers Kpn9, 5ur6), **the writing quality and the clarity of the presentation of the ideas** (Reviewer eLsL).

We attach a pdf file here that contains a numerical experiment that we did and provide detailed responses to each reviewer separately. We look forward to engaging in further discussion with the reviewers, answering questions, and discussing improvements. 

Meta-review: The paper examines online linear regression, where a learner can order data points to minimize regret. The paper proves that, under the exponential time hypothesis (ETH), no algorithm can efficiently approximate optimal gain A greedy algorithm provides an approximation to optimal gain assuming uniform data and ground truth. Reviewers found the paper theoretically interesting but questioned the motivation. The author provided a convincing argument in favor, citing historical and recent advancements, and they also offer examples like directed marketing and content recommendation systems.
Decision: Accept (poster)