Online Learning of Neural Networks
Authors: Amit Daniely
Idan Mehalel
Elchanan Mossel
Venue: NeurIPS 2025 poster ()
Keywords: Online learning
Neural networks
Deep learning
Primary area: theory

Abstract: We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball in $\mathbb{R}^d$ to a finite label set $\mathcal{Y} = \{1, \ldots, Y \}$.
First, we characterize a margin condition that is sufficient and in some cases necessary for online learnability of a neural network: Every neuron in the first hidden layer classifies all instances with some margin $\gamma$ bounded away from zero. Quantitatively, we prove that for any net, the optimal mistake bound is at most approximately $\mathtt{TS}(d,\gamma)$, which is the $(d,\gamma)$-totally-separable-packing number, a more restricted variation of the standard $(d,\gamma)$-packing number. We complement this result by constructing a net on which any learner makes $\mathtt{TS}(d,\gamma)$ many mistakes. We also give a quantitative lower bound of approximately $\mathtt{TS}(d,\gamma) \geq \max\{1/(\gamma \sqrt{d})^d, d\}$ when $\gamma \geq 1/2$, implying that for some nets and input sequences every learner will err for $\exp(d)$ many times, and that a dimension-free mistake bound is almost always impossible.
To remedy this inevitable dependence on $d$, it is natural to seek additional natural restrictions to be placed on the network, so that the dependence on $d$ is removed. We study two such restrictions. The first is the multi-index model, in which the function computed by the net depends only on $s \ll d$ orthonormal directions. We prove a mistake bound of approximately $(1.5/\gamma)^{s + 2}$ in this model.
The second is the extended margin assumption. In this setting, we assume that all neurons (in all layers) in the network classify every ingoing input from previous layer with margin $\gamma$ bounded away from zero. In this model, we prove a mistake bound of approximately  $(\log Y)/ \gamma^{O(L)}$, where L is the depth of the network.

Online Learning of Neural Networks
Amit Daniely
Idan Mehalel
Elchanan Mossel
The Hebre University
The Hebrew University
MIT
amit. dan.ely@mailll....m....mmmmmm wtw.:mmmmmil.........m.. oc....
edanmehalel@@aail com
elmos @ mit.edu
Abstract
We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball R to a finite label set y {1, ..... Y}. First, characterize margin condition that is sufficient and in some cases necessary for online Icarnability of a neural network: Every neu- ron in the first hidden layer classifies all instances with some margin y bounded away from zero. Quantitatively, we prove that for any net, the optimal mistake bound is at most approximately TS(d, 7), which is the (ottt))tly---pparrda packing number, a more restricted variation of the standard (d, 7-pacckng number. We complement this result by constructing net which any learner makes TS(d, 7) many mistakes. We also give a quantitative lower bound of approxi- mately TS(d, 7) 2 max(L/(rvv)) d} when < 1/2, implying that for some nets and input sequences every learner will err for exp(d) many times, and that a dimension-free free mistake bound is almost always impossible. To remedy this inevitable dependence on d, it natural seek additional natural restrictions to be placed on the network, so that the dependence on d is removed. We study two such restrictions. The first the multi-index model, which the function computed by the net depends only on k & d orthonormal directions. We prove mistake bound approximately (1.5/>) k+2 this model. The second is the extended margin assumption. In this setting, assume that all neurons (in all layers) in the network classify every ingoing input from previous layer with margin 7 bounded away from zero. In this model, we prove a mistake bound of approximately (log OLL) where L is the depth of the network.
Introduction
We study online learning of feedforward neural networks with sign activation functions that implement functions from the unit ball in Rd, denoted by B(R"), to the label set ) {l,..., Y) where Y 2 2.
In more detail, we consider the following setting. An adversary Adv and a learner Lrn rivals in a repeated game played for some unbounded number of rounds T. In each round t, Adv sends an instance e (RRd) Lrn, and Lrn sends back a prediction 9c e y. Lrn then receives the true label ye E y from Adv, and suffers the loss 1 + ye]. The goals of Lrn and Adv are opposite: Lrn's goal is to minimize the mistake bound Eieryy 1 F Vrl, and Adv's goal is maximize it.
Our results and analysis focus the realizable setting, where there exists unknown target function t*: ((Rd) + y implementable by some neural network, such that y, = h +'(x,) in every round I. In this setting, we denote the mistake bound of Lrn on sequence of instances S = æ1, 22. AT by M(Lrn, 5) = E.e [T) 1 * 4" (xxx)) As we explain in the sequel, the agnostic case in which the adversary is allowed to respond with + x (xxx) is handled by the agnostie-to-realzzable reduction
We focus deterministic learners.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of [Hanneke et al. 2023a to obtain a regrer bound of Ô (VMT) where M is the mistake bound guaranteed when realizability is enforced, and T is the number of rounds.
To the best of our knowledge, the task of online learning neural networks was not extensively explored in the literature However, we do believe that this is an important task for a variety of reasons:
1. Many learning tasks are not well captured by an i..d. assumption and fit well as an online learning model. This includes weather prediction, financial prediction, ad click prediction etc. Given the prominent role of neural networks in various learning and prediction tasks, it is natural to study online learning algorithms for neural networks.
2. The online learning setting adversarial, difficult, and general. Therefore, online learning mistake bounds often have implications in other settings of learning. A non-exhaustive list of examples include PAC-Iearning (by using online-to-batch conversions) [Littlesonee
1989 private learning [Alon et al. 2022a), and transductive learning [Hanneke et al. 2023b 2024].
3. This is a natural task, and as our work shows, standard and natural learning techniques reveal connections between online learning of neural networks to a known geometric quantity known as the snally-separable packinng number (see Section 2.1 1 and to the widely practically applied paradigm of pruning neural networks [Blalock et al. 2020 Cheng et al.
2024]
(see Section 3.3).
4. Some learning tasks related to transformers use an autoregressive learning model, which is closely linked with online learning: The recent work (Joshi et al. 22255 shows that learning with reasonable sample complexity in an autoregressive model is impossible for some PAC-learnable function classes. However, all online learnable classes are also learnable in the autoregressive model. Our work suggests that under certain assumptions on the target network and the input, autoregressive learning of neural networks could be possible with reasonable sample complexity.
As mentioned, we focus our study on neural networks with sign activation functions. While this activation function is not used in practical applications of neural networks, there number of good reasons for studying online learning with this activation:
It is simple and classic. The sign function is simple and classic, and many classic theoretical analyzes use sign as the activation function. For example, such expressivity results can be found in (Shalev-Shwartz and Ben-David 20144), and sample complexity bounds may be found in [Anthony and Bartlett 2009). Furthermore, online algorithms for neural networks with sign activation function can be seen as generalizations of the classic perceptron algorithm [Rosenblatt 1958 for the multi- layer case.
It is used in binarized neural networks. The sign activation function is widely used in binarized neural networks (BNNs) [Hubara et al. 2016), such networks are restricted to having binary activations and weights. The study of BNNs is motivated by the need to deploy deep learning paradigms on low-power devices, such as mobile phones, industrial sensors, and medical equipment, where computational and energy resources are limited. Such devices often lack the infrastructure required to train standard neural networks, which typically rely on powerful hardware. Moreover, the learning tasks these devices perform are often online in nature: they make real-time predictions based on continuous stream of incoming data.
It implies results for other activation fuucction. Beyond the motivations discussed above, we argue that our results extend, to some extent, more common activation functions. Consider the following very simple classification network: a single input neuron and a single output neuron. In this setting, the target function is $: [-1,
[+1]. The output neuron computes real value r E [-1, 1] based on the input, and the final prediction is given by sign(r). Even in this minimal setting, learner can be forced to make an unbounded number of mistakes unless additional assumptions are made. A standard assumption is that the prediction margin is bounded away from zero. That is, Irl 2 7 for all values computed by the output neuron, for some 7 > 0. Under
Sooe related work we did find is mentioned and compared to in Section 3.1

---

this margin assumption, the sign function can be replaced by any activation function that agrees with sign whenever |r] 2 7; including smooth activation functions, that are more commonly used in practice. The assumptions
make throughout the paper are of a similar nature to the margin assumption described above, and analogous arguments can be used extend our results other activation functions. For example, see Section 3.1 where compare some of our results to results of |Rkkliin et al. 2015), who considered more general activation functions.
Main results
The following sections assume some familiarity with standard definitions from online and neural network learning. For completeness of the main body of the paper, we provide the formal setting that consider in the following paragraph. For other relevant definitions, the reader may refer to Section A which introduces all the necessary background in a self-contained manner.
Online learning is repeated game between a learner and an adversary. The learner's goal is to classify with minimal error a stream of instances ,1, X. Each round of the game proceeds as follows.
The adversary picks an instance 2t X, and sends it to the learner.
(ii) The learner predicts value ÿt V.
(iii) The adversary picks y/ y and reveals it to the learner. The learner suffers the loss [ + (x,)]-
We focus on the realizable case, where there exists an unknown target function h: X y taken from known concept class H. such that y = hxx)) for all E [T]. In this work, H is a class of functions implementable by neural networks of some architecture. In the following subsections, describe the results proved in this work.
2.1 Characterization
We prove that the optimal mistake bound of learning a sequence of instances S = ..... .T E X labeled by a target network V with input dimension is nearly characterized by the (d, 71 (N+ S))- sotally-separable packing number (or TS-packing number, for short), denoted by TS(d, (d, (N* S)).
where " : 7 (W",, is defined as the minimal distance between a neuron in first hidden layer of * to an instance in S. By "nearly characterized" we mean that there is upper bound quantitatively controlled by (d, 71) for all d* S, and that lower bound of TS(d, 7/) ) attained for some networks N and sequences S.
For any d, c, TS(d, c) is the maximal size T of subset {ai,..., FT) C B(R))) such that for any two distinct points w4, Tj there exists hyperplane (w, B(Rd) [-1, 1, 1] satisfying:
1. (w, b) linearly separates from Tz.-
2. For all E [T]. the Euclidean distance between (w, b) and 2g is at least e.
We prove the following bounds. Theorem 2.1. There exists a learner Lrn such that for any target network No with input dimension and realizable input sequence S:
M) Ō TS(d
TS(d. (1)
7
Furthermore, for any learner Lrn, and for any ε > 0, d 2 1/e2, there exists network with input dimension and realizable input sequence S such that 71 2 8 and
M(Lrn, S) ((TS(d, e) 1/e2).
The upper bound is proved under the assumption that 7 is known the learner in advance. This also the case in the next two upper bounds, stated in the following two subsections (with Yi replaced
AAssuming all neurons" weight vectors in the first hidden layer of N normalized to have unit nommm

---

by the relevant margin definition appearing in the statement). In Section 2.4 we discuss how this assumption may be removed by variation of the doubling trick [Cesa- CesscBiiacch et al. 1997]. in the cost of polynomial degradation in the mistake bound.
We prove Theorem 2.1 in Section C Note that the difference between the upper and lower bounds is roughly quadratic in the worst case. Furthermore, the bounds on TS(d, e) given in Theorem G.1 imply that when 71 is sufficiently small, TS(d, 711) is much larger than 1/72. giving tighter bounds in this case. When is large, the dependence on 1/7i in the upper bound could be more significant, but this is not catastrophic, as 1 1/7i relatively small in this case.
Note that the mistake bound demonstrates no dependence on the size of the label set y, which is common in multiclass online learning (Daniely al., [0155 Bränzei and Peres 2019 Hanneke et al. 2023a]. On the other hand, as stated in Theorem G.1 TS(d, e) is exponential in for small e, and even for 1/2 it is at least linear in d. This implies that to obtain dimension-fres mistake bounds, we must further restrict the network and input sequence. We describe two such restricted settings we have been studying, as well as the derived results, in the following two sections.
2.2 Improved bound in the multi-index setting
In the multi-indee model, we assume that the target function h B(Rd) + y calculated by the target network is restricted in the following way. There exist k < d many unknown orthonormal signals s(1), g..).,,()))))))))
((k) E Idd and a function o= ((R²) - 3 such that for every E B(Rd), we have o (x((x) 6- ((s(1), 1)),.))... ....... . (s()),z)) x.). In simple words, while the domain of 4* is B(R"), the value of 4 (z) ) not arbitrary but depends only on an unknown k-dimensional projection of
The motivation of studying this setting lies in the following conjectured phenomenon: There are natural learning tasks with seemingly high-dimensional input, that in fact hides a low-dimensional structure explaining their behavior [Goldt et al. 2020). This conjectured phenomenon might partly explain why deep learning mechanisms do well some high-dimensional learning tasks, with low sample complexity that does not match the high-dimensional input. Consequently, this model has gained significant interest in the community, and is extensively studied in the past few years, especially in the context of stochastic optimization Arous et al.) 2021 Ba et al., 2022 Bietti et al. [222] 2023
Damian et al. 2024 Dandi et al. 2024 2025].
Lee et al. 2024 Amaboldi
al. 2024] Cornacchia et al.
We study online learning of neural networks in this so-called multi-inder model. We prove that g..,, (bk) are unknown and k < d, it turns out that the upper bound of with with k replacing d, assuming a multi-index model.
even though the signals g(1) ,...,
Theorem holdd
Theorem 2.2. In the multi-inder model with k many unknown signals, there exists learner Lrn such that for any target network with input dimension and realizable input sequence S:
(s(, (okkm)))
M(Lrn, = S)
We prove Theorem 2.2 in Section D Theorem G. implies TS(K, m) < (1.5/m)* Therefore, if is, say, some universal constant, then Theorem implies a guaranteed mistake bound of only poly(1/71).
The proof idea of Theorem 2.2 that while the (d, --S--acinn number of the domain of 4* does not change, the labeling of large packings made by x* cannot be too complicated, and in fact behaves as if the labeling was made by a function with the domain (RR.).
2.3 Improved bound with large margin everywhere
is natural to study the mistake bound as a function of y := ((N* S). which is the minimal margin over all neurons and all input instances. In more detail, for every neuron and any input instance the neuron classifies the input coming from the previous layer, and this classification also has the same natural definition of margin in the first layer. The minimal margin y is the minimal margin observed in all neurons and input instances. When is large, a significantly better mistake bound than of Theorem 2.1 can be proved.
'The lower bound trivially holds.

---

Theorem 2.3. There exists learner Lrn, such that for any d E for any target network with input dimension d, and for any realizable input sequence S:
M(Lrn, Ö log )
( gAL+2
where I. is the depth of the network.
We prove Theorem 2.3 in Section E A lower bound of Q[min (1/72, /d)) dd} for some networks and input sequences is easily implied by the well-known lower bound for online linear classification. Therefore, when L is small, the bound of Theorem 2.3 is fairly good.
To illustrate the significance of this result over the worst-case characterization (Theorem 2.1 let's consider prototypical case of network with single hidden layer and one output neuron. In such network, the difference between the set of neurons in the first layer considered in Theorem 2. and the entire set of neurons is only the output neuron. However, the bound of Theorem 2.3 in this case depends only polynomially on 1/7, and does not depend on the input dimension. Thus, it suffices
that the margin in the output neuron is not extremely small for the bound of Theorem 2.3 to be much better than the bound of Theorem 2
Determining whether the exponential dependence on L is necessary remains open. The proof of Theorem 2.3 uses a method to significantly reduce (when 7 is large) the number of neurons in the target network, which is, to the best of our knowledge, novel. Our method relies on the celebrated uniform convergence theorem /Vapnik and Chervonenkis, 1971]. See Section 4.4 for more details.
2.4 Adaptive learning
Suppose that a learner has a mistake bound of 1/72 guaranteed by one of the theorems presented above, where y is the relevant definition of margin and b is the relevant exponent. We note here that the algorithms used to prove the upper bounds described so far assume that 7 are known and given in advance. In Section we show how to remove this assumption, in the price of some polynomial degradation in the mistake bound. We stress that a standard doubling trick (which usually causes only constant degradation in the mistake bound) is insufficient here, since there are unknown parameters.
As by-product, not assuming knowledge of 7, in fact allows us to not even know which of Theorem 2.2 or Theorem 2.3 guarantees a better mistake bound, and still achieve it, up to polynomial factors.
Theorem 2.4. For some target network N and imput sequence S, let M1, M2 be the mistake bounds guaranteed by the non-adaptive algorithmss providing the mistake bounds of Theorem (he and Theorem 2.3 respectively. Then, there exists an algorithm, that without any prior knowledge on N or S enjoys mistake bound of M(Lrn, S) = (M,
This result is obtained by simply executing multiclass version of the Weighted Majority algorithm of [Littlestone and Warmuth, 1994) (described in Section A.3.T] on the adaptive version (described
in Section FF of the algorithms providing the mistake bounds of Theorem 2.2 and Theorem 2.3 as experts.
2.5 Agnostic learning
Our results and amalysis focus on the realizable case, but can be adopted to the agnostic setting, where the adversary allowed "lie" and provide responses not perfectly matching to the target network. A different, and perhaps more common point of view on agnostic learning is that the adversary never lies, but the true labels do not match any target function. Since the expressivity of neural networks is very strong, we adopt the first point of view which is somewhat more natural in our context. That is, we assume that there exists a target network producing the labels, but the adversary changes the correct label to different label in some of the rounds. The identity and number of rounds in which Adv tampers with the data is unknown. Our goal is to minimize the learner's 's regret, defined as
T
Reg(Lrn, 5) = M(Lmn, S)
1 1 (are) + yc
5

---

for any (not necessarily realizable) input sequence S. The expectation is taken over Lrn's 's randomness. In contrast to the realizable case, in the agnostic case we must allow the learner randomize its predictions in order to achieve (T)) regret [Cover] 1965). The following regret bound is obtained by applying the conostic-to-realizane
reduction of [Hanneke et al.] [023a].
Proposition 2.5. There exists a learner Lrn, such that for any (not necessarity realizable) inpur sequence S of length T 2 2M that has a guaranteed mistake bound M by a learner Lrn' in the realizable case (withoul any labels being altered by the adversary):
Reg(Lrn, S) - (VMT))
The proof of the proposition is given by closely following the proof of Theorem of [Hanneke et al. 2023a], and just replacing the Littlestone dimension with M.
3 Related work
We overview and compare to previous work generally related to online learning of neural networks in Section 3.T Our results, especially Theorem 2. and Theorem 2.2 are strongly related to the TS- TS-packing number. Finding bounds the TS- TS-packing number is geometric problem which is interesting on its own right. We overview some known results related to it in Section 3.2 Our bounds also rely on the possibility to identify small set of "important" neurons in the target net, and then use only on those neurons when learning the target function. This technique reminds us of the known "pruning" methodology which is extensively studied in the literature. We overview related work on pruning in Section 3.3
3.1 Previous work on online learning of neural networks
2017 an online learning algorithm for neural networks is proposed, and tested experimentally. hhoretical analysis of regret bounds for randomized neural networks was performed
In (Shhoo et al.
by [Chen et al. 2023 Wang et al. 2024].
Most related to our work, the work of [Rakhlin al. 2013 gave regret bounds for online learning of neural networks when the activation is Lipschitz and the loss function is convex and Lipschitz (by joining Theorem 8 and Proposition 15 in [Rakhlin et al. 2015)- Although this is still quite different from our setting, which assumes sign activation and the 0/1 loss (which is usually used in classification problems), we may compare their regret bound to the bound obtained in this work under the extended margin assumption. Specifically, if the depth of the network is L, the output is
binary, and margin of y is assumed for all neurons, regret bound of ò (VT///00) is obtained
by joining Theorem 2.3 and Proposition
2.5
The regret bound of [Rakhlin et al. 2015 in this
where C₃ is the Lipschitz constant of the loss function, d O(L)
setting is Ô Ci d
B
the input dimension and B is an upper bound on the 1-norm of the weight vectors. To see this, note that the actual bound given by [Rakhlin et al.) 2015 Theorem 8 and Proposition 15] is OCCeVTlog d(B ((L))) where C₂ is the Lipschitz constant of the activation. but the margin assumption allows us to replace sign with Ca-Lipschtiz function for some C. 2 1/7. Although the result of |Rakhlin et al. 2015) applies a more general setting, our bound has few advantages:
1. It does not depend the input dimension nor the 1-norm of the weight vectors, which could a priori depend on the network's 's width.
2. It is given by an explicit algorithm rather than minimax analysis.
3. It applies to the non- con-ccovex 0/1 loss function. An analogue result for linear classifiers was proved in (Ben-David et al. 2009 Section 5].
4. It is given by an agnostic-tts -tessticctooooee cencc-to--raazzze realizabee reduction (Proposition 2.5 Therefore, it is finite (independent of T) in the realizable case (Theorem 2.3
3.2 Related geometrie results
The bounds in Theorem 2.1 and Theorem 2.2 are given in terms of the TS TS-packing number. The investigation of totally separable packing problems in geometry literature dates back to the 40's

---

[ooomman and Goodman 1945 Hadwiger 1947 and the totally-separabee notion is due to Erdós. who has made some conjectures with respect to those problems, according [Goodman and Goodman T945] The works (Töth and Tóth 1973 Kertész, 1988) proved bounds on the density of TS-TTSpaa TS-packing of circles (2-dimensional balls) and balls (3-dimensional balls), respectively. The packings considered in those works are very similar to our TS- -S-paccings, with the main difference being that we are more interested in high dimensions, as this is the typical case when dealing with neural networks. The interested reader may refer to the recent thorough survey separability in discrete geometry [Bezdek] and Längi 2024] for more information.
3.3 Neural networks pruning
Pruning is popular practical paradigm used to reduce the number of computation elements in neural network, which is useful in practice for a variety of reasons, such as reducing infrastructure costs. There is extremely vast literature on the pruning paradigm: more than three thousand papers just between 2020 and 2024, according to [Cheng et al. 2024]. We refer the interested reader to the surveys [Blalock et 2020 Cheng et al. 2024 for more information and references.
The pruning method in our work is a bit different from standard, practically used pruning techniques. In standard pruning, the net is pruned and then trained again as is recover its precision (this is sometimes called "fine-tuning"). In this work, we identify a (desirably small) subset of the neurons that is necessary to compute the target function calculated by the network, and then learn the target function, possibly without relying on the actual architecture the original network.
4 Overview of proof techniques
In this section, we informally describe the main ideas used to prove our results. We start by describing general approach that is common to quite few of the proofs in this paper. A similar approach was also taken in Khalife et al. 2024]. We think of a neural network as a pipeline with two stations:
The first station, implemented by the first hidden layer, partitions the unit ball 2 many regions (which some of them might be empty), where l is the number of neurons in the first hidden layer, denoted with C. Each region specified by a region-specifying vector r := ,(() E {=1)f. That is, the region of point ((Rd)) is specified by r if for every i E [e] it holds that r; = sign( (u, 2) + b:), where (uz, by) is the i'th neuron of L.
2. The second station uses all other layers implement some function f: {=1]f V.
For any point x E B(RR), we denote the region-specifying vector of by r(x). The function $* calculated by the target network is thus the composition f r. That is, (x) f(r(x)) for all x E (TRd).
The above point of view is at the heart of the high-level strategy used to prove the mistake bounds in this paper:
1. Learn the partition of (RRd) to regions.
2. Learn the label of every region.
To implement this strategy, we first describe a meta-learner that uses a multiclass version of the Weighted Majority algorithm of (Littlestone and Warmuth 1994). which has good guarantees executed with an appropriate expert class. Then, we provide specific expert classes to run the meta-learner with, for the sake of obtaining the stated mistake bounds.
Naively, the number of mistakes made when learning the partition of ((TRd)) into regions might depend on f. Since l might be very large, this could be significant bottleneck of the mistake bound. Therefore, a main idea in most of the bounds is to reduce the number of neurons in the net such that only neurons which are required to properly partition ((Rd)) regions are considered.
Section organization. In Section 4.1 we overview our meta-learner for learning neural networks online. This algorithm the main framework used to prove the mistake bounds this paper. In Section 4.2
we describe how to use the meta-learner in order to prove the upper bound of Theorem 2.1
7

---

and we also include a brief explanation of the lower bound. In Section 4.3 we explain how to improve the upper bound of Theorem 2.1 the multi-index model, and in Section 4.4 we explain how to improve it when an extended margin assumption holds.
4.1 The Meta-learner
The meta-learnr executes a multiclass version the weighted majority (WM) algorithm of [Littlestone and Warmuth, 1994]. This algorithm aggregates predictions of a class & of experts, unified prediction strategy with a mistake bound that depends logarithmically on the size of the class, and linearly on the mistake bound of a best expert. In our case, each expert from implements some partition of B (RR)) to regions and a labeling function labeling those regions. To obtain good bounds, we need to make sure that:
1. & is not too large.
2. At least one expert does not make too many mistakes.
In nutshell, we are able to make sure that both items hold in the instances of the meta-learner we use, by:
1. Showing that there are not too many possible partitions of the input sequence C B(Rd)) to different regions in ((R)).
2. Making sure that every possible partition of the input sequence S C B(R)) regions is implemented by some expert E, and that the labeling function of an expert with the correct partition to regions is accurate enough well.
The first item enables & to be reasonably small, and the second item is necessary so that at least one expert E. will perform well in the task of predicting the labels of We use three different instances of the meta-learner, for three different setups: general (Theorem) 2.1). multi-index (Theorem 2.2). and everywhere-marge (Theorem
4.2
Quantitative general characterization
4.2.1 Upper bound
we show that the optimal mistake bound for every target net A with input dimension d, and for every input sequence S,, is much larger than TS(d, 71). In order to prove this bound, the fact that in any partition of B(Rd) to regions implemented by V at most TS(d, 71) regions actually contain points from S, otherwise induces a (d, - which is larger also prove that there
In Theorem 2.
than TS(d, 7/),, and this is contradiction. Armed with this argument, exists an important set of neurons G size at most (S, 71). This allows us to construct a good enough expert class & to execute the meta- letane with.
4.2.2 Lower bound
The lower bound follows from the "two stations" point of view explained in the beginning of the section. We take a (d, c..S--SSpackinn of size (s, E) as the input sequence S, and show that for every {0, llllbbiging of S there exists network ^ realizing it, such that 71 e. The neurons in the first hidden layer of * are the hyperplanes induced by the TS TS-packing S. The second hidden layer consists of neurons determining which regions induced by the first hidden layer are labeled and which are labeled 1. This implies a lower bound of (S(d, 7)).
4.3 The multi-index model
The proof of the mistake bound for the multi-index model (Theorem 2.2 follows the same lines of the proof of the upper bound in the general characterization result. The main difference that since hh in fact depends only on k & orthonormal directions, the arguments outlined for the general case actually hold with replacing d. We show that if this not the case, we can construct (k,, (1) -TS TT-ppacking of size larger than TS( Y1), which is of course contradiction.

---

4.4 Large margin everywhere
Let us focus on the case where the target net has single hidden layer and calculates binary function x*: B(R") + {=1}. In this case, the extended margin ry is the minimal margin over all neurons in the hidden layer and in the single output neuron. Recall that the margin of neuron (v, b) is minges (v, x) + b). where is the input that (v, b) receives from the previous layer when the input to the network is x. If y is large, significantly better mistake bound can be proved, compared the case where ?1 (the minimal margin in the hidden layer) is large but the minimal margin of the output neuron small. Below, briefly explain what makes such improvemnt possible. We use known terms and results from VC-theory. The unfamiliar reader may refer to Section A for a formal background, before reading the next paragraph.
In this section, we explain the proof technique of Theorem 2.3
For simplicity, in the following paragraph we assume that all neurons in L are homogeneous (have bias 6 0). For every S. define function hg L + {=1}, given by h₂ sign (x, v)) for every v E C. Note that (z, w) 2 y for all E S, v E C. Using the mistake bound the known Perceptron algorithm (Rosenblati 1958 Novikoff 1962) and the online learnability characterization of [Littlestone] 1988). this implies that the VC-dimension of the class H = {h x E S} is at most 1/72. Therefore, may the celebrated uniform convergence theorem of [Vapnik and Chervonenkis) 1971] to obtain a small "representing set" of & with respect to any distribution D of our choice. It remains to choose D in a way that communicates the result of the output neuron for any E S. using only the neurons in the representing set. We show that this is possible with a representing set of size only ((1/7²) by choosing the probabilities of D to be proportional to the weights in the weight vector of the output neuron.
To extend this result to general networks, we first extend the result to a network of arbitrary depth that calcultes single output neuron, by applying the explanation above from the output neuron backwards, up to the first hidden layer. This is where the exponential dependence on the network's s depth in Theorem 2.3 comes from. To handle any label set V, we use the same idea every of the log | output neurons separately. This where the logarithmic dependence on [ in Theorem 2.3 comes from.
Open questions and future work
5.1 Open questions
Quantitative gaps in mistake bounds. There are some quantitative gaps in the mistake bounds
that it will be nice to remove.
In Theorem 2.1 there is multiplicative gap of approximately min(1/>7 TS(d, between the upper and lower bound. Can we find the correct optimal mistake bound?
Theorem 2.3 exhibits an exponential dependence on the depth of the target net. Is this dependence inevitable? For example, Khalife et al.) [2024] show how reduce the number hidden layers in network with sign activations to only two. Perhaps this idea could be used to improve the exponential dependence on the network's 's depth.
Better adaptive algorithm. Our adaptive algorithm Adap (Figure 4) has polynomially worse mistake bound than the non-adaptive Iearner given to it as input. This is in contrast with other online learning problems, where adaptiveness costs only a constant factor, or even less than that et al. 1997, Filmus et al., 2023] 2024 Chase and Mehalel] [024]. Does a better adaptive algorithm exist for online learning neural networks? More broadly, given an online learner
with mistake bound a² on the input sequence S, that requires knowledge of both and 6, is there an
adaptive version of Lrn with mistake bound ((a²) that does not require the knowledge of neither nor b?
5.2 Future work
Better bounds on the TS-packing number. We prove (Theorem 2.1 that the optimal mistake bound of learning input sequence S realizable by a neural network N with input dimension

---

d is controlled by TS(d, (W However, we are not aware of any bounds on TS e) for high dimension d, except for trivial upper bound given by an upper bound on the standard packing number, and relatively straightforward lower bound we prove in Theorem G.1 Besides having clear application mistake bound analysis for neural networks, finding tighter bounds on TS(d, <) an interesting problem in its own right. A similar problem was pointed out also in a recent survey on the topic [Bezdek and Lángi 2024). a somewhat different direction, would also interesting to understand if there are efficient methods to approximate TS(d, e) for given d,
Computationally efficient learning. Our meta-learner described Section juses a set of more than d experts that need to be queried and updated in every round, where is the size of the set of "important" neurons in the target net. Even in the most optimistic settings of Section D and
Section E. it holds that g 2 1/7, which means that more than 1/7
experts maintained by the meta-learner. If y is small, this very inefficient terms of computation. Can we achieve good mistake bounds with computationally efficient algorithms?
Study of other activation functions. This work studies the sign activation function, which is basic and natural. However, modern neural networks often other activations, such as ReLU or its variations. It will be interesting to study similar questions in the presence of more popular activations such ReL.U. We do not how extend our analysis to the ReLUU activation, which might require a fundamentally different approach from the one taken in this work.
Acknowledgments
The research described in this paper was funded by the European Research Council (ERC) under the European Union's 's Horizon 2022 research and innovation program (grant agreement No. 101041711) 1), the Israel Science Foundation (grant number 2258/19), and the Simons Foundation (as part of the Collaboration on the Mathematical and Scientific Foundations of Deep Learning).
EM acknowledges the support of the Theoretical Foundations of Deep Learning (NSF DMS-2031883), the Vannevar Bush Faculty Fellowship ONR-N00014-20-12222 and the Simons Investigator Award in mathematics.
References
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. ACM Journal of the ACM (JACM), 69(4):134, 2022a.
Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 558- IEEE, 2022b.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. fiteorttialooudatioonn university press, 2009.
cambridge
Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iu- vant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.1 14459, 2024.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high- -igh-dimensional inference. Journal of Machine Learning Research, 22 (106):1-51, 2021.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptoties of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37946, 2022.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwarzz. Agnostic online learning. In COLT, 2009.
Károly Bezdek and 7solt Lángi.
separability in discrete geometry. arXiv preprint
arXiv:2407.20169 2024.
10

---

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-999 -9783, 2022.
Alberto Bietti, Joan Bruna, and Loucas Pillaud-Viin Vivien. On learning gaussian with gradient flow. arXiv preprint TrXiv:2310.19791 2023.
models
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2: 2:129-146, 2020.
Simina Brânzei and Yuval Peres. Online learning with an almost perfect expert. Proceedings of the National Academy of Sciences, 116(13):5949-55 2019.
Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
Zachary Chase and Idan Mchalel. Deterministic apple tasting. arXiv preprint arXiv:2410.10404, 2024.
Xinyi Chen, Edgar Minasyan, Jason D Lee, and Elad Hazan. Regret guarantees for online deep control. In Learning for Dynamics and Control Conference, pages 1032-1045. PMLR, 2023.
Hongrong Cheng, Miao Zhang, and Javen Qinfeng Shi. A survey on deep neural network pruning: Taxonomy, comparison, analysis, and recommendations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Elisabetta Comnacchia, Dan Mikulincer, and Elchanan Mossel. Low-dimensional functions efficiently learnable under randomly biased distributions. arXiv preprint urXiv:2502.06443, 2025.
Cover. Behavior of sequential predictors of binary sequences. In Proc. of the 4th Prague Conference Information Theory, Statistical Decision Functions and Random Processes, pages 263-272. Publishing House of the Czechoslovak Academy of Sciences, 1965.
Alex Damian, Loucas Pillaud- Vivien, Jason D Lee, and Joan Bruna. Computationall-tttistti gaps in gaussian single-index models. arXiv preprint arXiv:2403.00 05529, 2024.
Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala.
The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXiv:2402.033220 2024.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Mach. Learn. Res., 16(1):2377-2404, 2015.
Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized littlestone dimension. In COLT, volume 195 of Proceedings of Machine Learning Research, pages 773-836. PMLR, 2023.
Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Bandit-feedback online multiclass classification: Variants and tradeoffs. arXiv preprini arXiv:2402.07453, 2024.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10 (4):041044, 2020.
AW Goodman and RE Goodman. A circle covering theorem. The American Mathematical Monthly, 52(9):494 498, 1945.
H Hadwiger. Nonseparable convex systems. The American Mathematical Monthly, 54(1OP1): 583-585, 1947.
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. The Thirty Sixth Annual Conference on Learning Theory, pages 5682-5696. PMLR, 2023a.
11

---

Steve Hanneke, Shay Moran, and Jonathan Shafer. A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36: 19559999999, 2023b.
Steve Hanneke, Vinod Raman, Amirreza Shaeiri, and Unique Subedi. Multiclass transductive online learning. arXiv preprint arXiv:2411.01634 2024.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Eaniv,, and Yoshua Bengio. Binarized neural networks. Advances in neural information processing systems, 29, 2016.
Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. arXiv preprint arXhv:2503.07932, 2025.
Gábor Kertész. On totally separable packings of equal balls. Acta Mathematica Hungarica, 51(3-4): 363-364, 1988.
Sammy Khalife, Hongyu Cheng, and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. Mathematical Programming, 206(1):333-33 2024.
Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoreiicc limit. Advances in Neural Information Processing Systems, 16-58766, 2024.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning. 2(4):285-318, 1988.
Nick Littlestone. From on-line to batch learning. In Proceedings of the Second Annual Workshop on Computational Learning Theory (COLT 1989), pages 269-2844 San Francisco. CA, USA. 1989. Morgan Kaufmann Publishers Inc. doi: 10.5555/93335.99336 URL https://dl. acm. org/
doi/10 000555555533333 00133335.933655.. 93365
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261 1994.
A. B. J. Novikoff. On convergence proofs for perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pages 615-622. Polytechnic Institute of Brooklyn, 1962.
Philipp Petersen and Jakob Zech. arXiv:2407.18384, 2024.
Mathematical theory of deep learning. arXiv preprint
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexi- tics. J. Mach. Learn. Res., 16(1):155-186. 2015.
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Doyen Sahoo, Quang Pham, Jing Lu, and Steven CH Hoi. Online deep learning: Learning deep neural networks on the fly. arXiv preprint 17X1v:1711.03705, 2017.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Fejes Tóth and L Fejes Tóth. On totally separable domains. Acta Mathematica Hungarica, 24 (1-2):229-23)) 232, 1973.
Vladimir N. Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications, 16(2):264 280, 1971.
Junda Wang, Minghui Hu, Ning Li, Abdulaziz AI-Ali, and Ponnuthurai Nagaratnam Suganthan. Incremental online learning of randomized neural network with forward regularization. arXiv preprint XrXiv:24/2. 2024.
Yihong Wu and Yingxiang Yang. Lecture 14: Packing, covering, and consequences on minimax risk, 2016.
12

---

NeurIPS Paper Checklist
limit.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims proved in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Each result applies to the specified setting for which it is proved.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Complete proof' of all results are included in the paper (either in the main text or appendix).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Theory paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pips.cc//uullc//guu Sotpe///ggideeeeeCeuuuuubbibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Theory paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Theory paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurda: /ttpaarrpp..ccooooffeeeeeeee///s for what should or should not be described.
19

---

Appendix Table of Contents
Definitions and technical background
21
A.I
Standard Notation
A.2
Concept classes
21
A.3
VC-theory and Uniform Convergence
21
Neural networks
A.5
Online learning
22
meta online learner for neural networks
23
Meta mistake hound
24
A
quantitative characterization of online learning neural networks
26
Upper bound of Thheorm
26
Lower bound of Theorem
29
D
The multi-index model
30
Learning with large margin everywhere
31
E.1
Margin-based pruning with single hidden layer and two labels
32
Margin-bascr Pruming the general case
33
Learning algorithm with margin everywhere
34
Adapting to the correct parameters
34
Bounds on the TS-packing number
36
20

---

A Definitions and technical background
A.1 Standard Notation
We use [n] = (l....,77) We define the sign function for all E IR as sign(z) = 1 if x 2 0 and sign(z;) = -1 otherwise. For a natural d, let (R*) be the ball of radius r in Rd centered at the origin. Denote ((IR2) : Bi (R.). The euclidean distance between 21, 22 R is dist(x), 22). The &2 norm of is || The unit vector in direction i E [d] is denoted by ei. Matrices are denoted by bold capital letters like W, and vectors by bold lowercase letters like w. The entries denoted by subscript indices such (u, v)
wi..... Wa for of dimension d. W., is the value in row and column j of the matrix W. For two vectors u, v of dimension d, their dot product is
Eie(d] u.y.-
A.2 Concept classes
Let X' be (possibly infinite) domain, and Y be finite label set. A pair (I. v) E X x y is called an example, and an element æ E is called an instance. A function h: X' -+ y is called a hypothesis or concept. A hypothesis class, concept class, is a non-empty set H. C yxx A labeled input sequence of examples {(r,, y=))²= said to be realizable by H there exists h(zz)) = V/ for all 1 < i < T. We say that such h is consistent with the labeled input sequence, or realizes it. An unlabeled sequence of instances S = 21...., Ir is called an imput sequence. An input sequence S = 21.............................. Fy and function h H naturally defines the realizable labeled input sequence (I1, ((z1))........ (xr. h(rT)).
H. such that
The concept classes we will consider in this paper will usually (but not always) be all functions computable by some neural network, as formally defined in Section A.4
A.3 VC-theory and Uniform Convergence
In the proof of Theorem 2.3] we use VC-theory, and specifically the fact that VC-classes enjoy the uniform convergence property.
y/t = [=1, and let H. c yd be a concept class. A set ø1...., Jd E X is shattered by H. if for all y....., Vd V. there exists h H such that f(x)) y4 for all i [d]. The VC-dimension of H. denoted by VC(H), is defined as the maximal size of a shattered set. there is no such maximal If VCHH) oc, say that H. is VC-class.
size, then VC(H)
Let D be a probability distribution over X. For any h E H. and for any sample S = Z1.... F'm of instances from X, define
(h) [h((), (s(h)= E M(x) +1] (x E S: h(x) 11]
S
We will use the uniform convergence theorem of (Vapnik and Chervonenkis 1971]. Theorem A.1 (Uniform convergence (Vapnik and Chervonenkis 1971)). We have
Pr sup (QD()) Qs(h)) cf s 8(em/ VC(H) -me /32
Smmi soo D LEE
where the notation S Ti,... I' D indicates that the sample S = Z1,.. Em is drawn i.i.d from D.
A.4 Neural networks
Let us formally define a neural network. We mostly follow the notation of [Petersen and Zech 2024 as described below. Let N, .i.......+ E N. We denote also do and dous di In this paper, a neural network with the architecture do....,d1+ is function & B(Rdo) + ( such that there exist weight matrices (4) Rdcc1 and bias vectors (()) E TRde+1 for all E {O...., L). for which the following holds. Let x = x, and (()) = sign () b(e-1)) for E E [L + 1]. where the sign function is applied separately for each row. That is, (0) sign( (ann((W(e (e-1,,))) (e--1) + b.) where (e-11,6) denotes the i'th row of ((-1), Then,
x
21

---

((x) = (I.+11 for all I E RR. For technical reasons, it will be convenient to assume that the sign function generating x is normalized (multiplicatively) by 1/vde. For simplicity of notation, we will also usually assume (unless stated otherwise) that all bias vectors are the all-O vector. Whenever this is assumed, it is clear that the arguments apply also when this is not the case.
Each row ((,))) in (()) is called a neuron. In many cases, we will fix & and consider the rows of ((.)) as a sequence of separate neurons denoted by u1,. Wde+1 We relate to those as the neurons in the (E + 1) hidden layer. We further assume that for every neuron w: ||w/|| 1. We use the notation N' := A (V((())
W(() to refer to the neural network itself, as an ordered
collection of weight matrices used to calculate the appropriate function & as described above.
A.5
Online learning
Online learning is a repeated game between a learner and an adversary. The learner's goal is to classify with minimal error a stream of instances T1, ,1,...,5f Jr E X. Each round of the game proceeds as follows.
(i) The adversary picks an instance 2, E X, and sends it to the learner.
(ii) The learner predicts a value dr E V.
(iii) The adversary picks y E y and reveals it to the learner. The learner suffers the loss 1 [ū +
hxx)))
We focus on the realizable case, where there exists an unknown target function h: X + y/ taken from known concept class H. such that yr hxx,) for all E [T]. In this work, y {=1]ddm
and H H(d, dows) is the class of all functions + ((Rd) - Y implementable by neural network * with architecture satisfying d = dout and do = d. We may also relate to y as the set [Y] = [200 where each y E 3' has binary representation in [=1]dout
We model learners as functions Lrn: (X' x )) X y. The input of the learner has two parts:
a feedback sequence F E (X' x y)", and the current instance x E X. The feedback sequence is naturally constructed throughout the game: in the end of every round the learner appends (xt, ye) to the feedback sequence. The prediction of Lrn round + is then given by F is the feedback sequence gathered by the learner in rounds 1,..., L,
where
Given a learning rule Lrn and a labeled input sequence of examples S = (x1 B1),.,.,.. (DT, we denote the number of mistakes that Lrn makes on S by
T
M(Lrn; S) = Σ
1 10e + yrl.
This quantity called the mistake bound of Lrn on Our goal is to design learners who minimize M(Lmn; 5) for every imput sequence S.
is worth noting that fixing S beforehand usually linked with an oblivious adversary setting, in which the adversary cannot pick the examples on the fly. However, when the learner is deterministic, the adversary can simulate the entire game on its own, since we assume that the learning algorithm is known to all. Thus, oblivious and adaptive adversaries are in fact equivalent, and we will refer to the adversary as being either adaptive or oblivious, depending on whichever more convenient in the given context.
All of our algoritms are conservative. Those are algorithms that change their working hypothesis only when making a mistake. Therefore, rounds where the algorithm makes a correct prediction may be ignored, and we assume that the number of rounds T is exactly the number of mistakes. However, it is understood that the number of rounds may in fact be unbounded.
'In traditional ouline learning, one often requires a uniform bound A on M(Lm;; S) that applies to all realizable sequences This is not possible when learning neural networks, even for the simplest single-layer perceptron with input dimension 1. The interested reader may refer to [Alon et al. 2022b for a unified theory handling with such cases.
22

---

WM(E)
Input: set of experts [F...... F Initialize: Set w() (E) for all E E
for / / 1,...,
1. Receive expert predictions Ei(l) E for all E [n].
2. Predict
Σ w (E,)
max yEY VE(m):B.(==v
3. Receive yt-
4. If yv De: w (1(+1) ( (Fa) for all i E [n).
5. yt * U:: set w((+1)(E,)) = w (E:)/2 for all so that E,(t) + ye. and (((+1) - (B:) for other i [m].
Figure I: The multiclass weighted majority algorithm.
A.5.1 Multiclass weighted majority
The algorithms present known binary weighted majority (WM) algorithm Littlestone and Warmuth 1994]. To the best of knowledge, this simple extension does not appear in the literature, for completeness, and it is described in Figure [ The WM algorithm is executed with a family = (E), (..,..., E.,) of many experts. Similarly the standard online learning setting presented in Section A.5 the setting in which WM is executed is a repeated game between a learner and an adversary, where in the beginning of each round every expert Eg gives its prediction Et(() y The learner's goal is to make as few as possible prediction mistakes compared to L, the minimal number of mistakes made by a single expert.
conservative, straightforward multiclass extension of the well-
include it here
The multiclass extension of the weighted majority algorithm has the same mistake bound as the standard binary version of the algorithm.
Proposition A.2. WM(E) makes most 3(L + n) many mistakes where L is the number of mistakes made by an expert with a minimal number of mistakes, and n = 11).
Proof. For y E let
W y
( (E.), and W(O Σ w(0. (E)
Σ
DEY
In simple words, w is the sum of weights of all experts predicting y in round f, and ( the sum of weights of all experts in round By the prediction rule, in any round have w(() W,/2. Indeed, by definition of ÿr we have wilt) < w(t). Therefore w>(t) > W./2 then we have w:( + w((0 > W., which a contradiction. Therefore, it holds that W w > W(0 So by the update rule, we have W((++) < W, W/( /2 S _ 2w()), On the other hand, in every round we have ((t)= 2 1/24. Therefore, since (1)) n, for any number of mistakes we have: 1/2 < WTT) < n (3/4).. Solving this inequality for T gives the stated upper bound.
B A meta online learner for neural networks
In this section, we describe meta-learner for online learning neural networks, used to prove upper bounds. Generally speaking, the meta-learner's main theme is to execute WM(E) on an appropriate class of experts E.
23

---

Neuronp
Input: p E {0.1)7 Initialize: A d-ary all-O vector w.
for / 1,..., T:
Compute dr
2. If P:
(a) If De 0, update
Tt. It.
(b) De 2 0, update
3. Return ÿt-
Figure 2: A perceptron with updates given by the "manual" vector p.
Let : B(R4) + y/ be the target function, calculated by some neural network A called the target net. Fix the input sequence S = T1,..... .......................... E BRR)). For any neuron (e,i) in N let (w.. (S) min (W()).) x(())) (0:
This quantity is called the margin of (e,i) with respect S. We assume w.l.o.g that for all l, (e,)) is maximum margin classifier for S. That is, there is other hyperplane W such that (W(S) > (e. (5), and both have the same sign on every input from previous layer, for all x E S. In this section, will only care about the margin of the neurons in the first hidden layer. Namely, denote
YNV S)
min (w(),)) (S). [d]
When the identity of * S (or both) is clear, we may omit them from the notation.
We may now describe the meta-learner in detail. As mentioned, the main idea of the learner is to execute WM(E), where is chosen to be sufficiently "good". What makes a class of experts & "good""? In nutshell:
1. The set & should not be too large.
2. least one expert in & will not make too many mistakes.
If we have both guarantees with good enough numeric values, Proposition A.2 implies good mistake bound.
How can we satisfy both guarantees? Each expert in the class & is an algorithm of type Expert La described in Fi which, as suggested by its notation, parametrized by a sequence of algorithms G. and a function LG. The algorithms in G are instances of the algorithm Neuron, described in Figure 2 who simulate a neuron, where each instance of it is parametrized by different vector 1 JT, where 7 is the mistake bound of the meta-learner when executed with È (or, simply the number of rounds in the game, WM conservative). The binary vector p functions as "manual" for Neuronp. telling which hyperplane it should converge to. This idea is inspired by the technique of [Ben-David et al. 2009
The function LG is a labeling function from the set of regions in B(Rd) induced by intersections of halfspaces defined by the neurons G, to V. The idea is therefore to use to partition ( to different regions, and then identify the correct label for every region. In order to satisfy the first guarantee above, we will have to show that the "correct" labeling function Lg can be defined for relatively small G.
B.1 Meta mistake bound
We would now analyze meta mistake bound to used in our instances of the meta algorithm. We first define some additional notation, formalizing the idea of partitioning B(Rd) to regions based

---

Expert
Input: A sequence G (P1, ......... PPg) of g many vectors in {0, 10; A labeling function La: {=1}8 +y. for t = T::
1. Construct r E {=1}0 such that for all é:
Ti = sign (qt, 12)),
where qi the hyperplane maintained by Ne
2. Send (r(r) to the meta-algorithm as the expert's prediction.
3. Retrieve y/ from the meta-algorithm.
4. p; = 0 for every neuron E G, update Lr(r) =
Figure 3: An expert parametrized by sequence of neurons.
on G. For sequence G (w1, .... Wgg of hyperplanes, we can partition the unit ball to set of distinct regions (where some of them may be empty) by region-specifying vectors of the form {+1}%, where the i'th is the sign of the i'th hyperplane. For region-specifying vector (GG) for G, we denote the region of (G) by R(r(G)), which is the set of all æ E ((Rd) agreeing with the signs defined by (G)), If the identity of the sequence of hyperplanes G is clear, we omit the (G) superscript. Note that for any two distinct region-specifying disjoint as they lie in different sides of at least one hyperplane. We use the notation r(z) for the region-spoer segiion-pecifying vector of x. That is, for all [g], we have sign( (w; 2)) rz().. We may also abbreviate R(x)= == R(r(z)). Another useful notation is S(r) == R(r)
vectors, their appropriate regions are
Fix the input sequence S and l == ' (W*, S). G' = (wi..... Wgy be sequence of neurons taken from the first hidden layer of the target net, such that there exists function f: {+1)² - y, satisfying that for every E S it holds that f(r(x) x (I:). Note that taking the entire first hidden layer must satisfy this condition, and the challenge is to find smaller sequences satisfying it. For an expert E' == Expert denote the number of mistakes it makes the input sequence S by M(E) = (E) + M2(E), where (E) is the number of mistakes in which the E S misclassified by E' satisfies (x) * (G') That is, this is the type of mistakes that occur is not correctly identified by E. We call those mistakes of the first type. The
because the region mistakes of the second type counted in (E) are all other mistakes. Namely, for an misclassified because of mistake of the second type, holds that (z) is, the mistake is caused by a local incorrect choice of La. We now define the type of expert classes that we use, accompanied with two propositions showing why they are "good".
(('' but Lo # f(x). That
Definition B.1. For a number of neurons and number of rounds T, an expert class of experts of type Experta, is (g. -reeepessnt if for every collection P of size of vectors p {0, 1) with at most 1/7/ many 1's, there exists an expert Expertg,ta such that the vectors of G precisely those of P.
Proposition B.2. For all g, T larger than universal constant, there exists (g. reeppeseeetnn class & such that
|1 99)²
Proof. We choose who satisfies the requirements of Definition B. of minimal size: Let P C {0. 1)TH be the set of all {0, 1v-ulueed vectors with at most 1/92 many 1's, and let & = {G c P |G] = g), where here C P denotes collection taken from P (possibly with repetitions), arbitrarily ordered sequence. Let E (Expert E G} where LG is some labeling function. Then:
(<1/1))
+9 < (T1/18 + +9)²
[3| <
required.
25

---

Proposition B.3. Let g be the size of G", let T be the number of rounds, and let & be a (g. T)
representing class. Then there exists Expert E such that:
Mi (Expertt.. 9/h
Furthermore, in every round in which Expert makes mistake, the mistake is of the first type if and only if there exists p E G such that pt
1.
Consider execution of the known perceptron algorithm of [Rosenblati 1958 the labeled input sequence S(w,) = (21, sign (1ng z1 ))).........................)) (2r. sign( (un,, zT))), , for some wy E G By the perceptron's s mistake bound guarantee Novikoff 1962]. will make at most 1/72 many mistakes. Therefore, there exists vector p E 10, with at most 1//2 many 1's, such that Pt and only if the perceptron algorithm errs on round t when executed on the input sequence S(w,). Therefore, for that p. algorithm Neuron, classifies S(w,) correctly everywhere except for rounds t with P: = 1. Thus, there exists an expert Expertc, such that = (Pi..... Pg) is a sequence of vectors in 1)7 satisfying the following: There exists a permutation p: [g] + [g]. such that for any [gl. sign( ((p()))))) -())()))))))))))))))))))))))))) = (gj.( for all E [T] except for at most 1/72, where ęj is the hyperplane maintained by Neuronp,: The role of the permutation p is simply to match between the indices G and the indices of G. By summing over all neurons, the total number of rounds where (x;) & (((())) (x+) ) most g/vl. where the superscript p(G*) means that the region specifying vector's 's entries are according to the order induced by the permutation p. The same discussion implies also the "furthremore" part of the lemma.
Proof.
if
C quantitative characterization of online learning neural networks
In this section, we describe instance of our meta-learne that has mistake bound close to optimal, when no special assumptions on the target network are assumed. Unfortunately, while this mistake bound is close optimal, it might be very large. In the following sections, natural restrictions on the input sequence and/or the target function, and obtain better mistake bounds. We first introduce geometric definition that will play important role in the proved bounds.
will place further
Definition C.1. A (d, c)-totally-separae
packing, or (d, points 21.....27 2T E (RR") satisfying the following. For all distinct i, [Z'] there exists hyperplane w E Idd such that:
for short, is a set of distinct
1. | = 1.
2. sign((w, .x)) sig
3. miniepr (ww Ir:I] 2
For simplicity, we did not mention that in the formal definition, but any hyperplane allowed to have non-zero bias. The (d, toottalll--spparaalll packing number, or (d, S-TTS-pacckng number, for short, denoted as TS e) is the maximal number T such that there exist distinct 21..... .T which form a - --ppkkking.
.T E B(Rd)
In simple words TS(d, e) is the maximal number of disjoint d-dimensional e-balls that can be packed in Bi+e (TR.) such that the interiors of every two balls are separated by hyperplane that does not intersect with any of the interiors of other balls. We may now prove Theorem 2.1
C.1 Upper bound of Theorem 2.1
Theorem C.2. There exists a learner Lrn such that for any target function 4* computed by a target net N*, and any realizable input sequence S:
M(Lrn, S) - ÖTSS(,,
The following lemma is central in the proof of Theorem C.2
Lemma C.3. There exists subsequence G (wI,.... wg) of the neurons in the first hidden layer N such that:
26

---

1. 9 ž S TS(d, 7). where Z = (r(()) E {+1} : S(r) + 0}.
2. There exists a function f: {+1}² - ) satisfying that for every x E S it holds that f(r(x)) = 46 (z).
Before prove lemma C.3 prove auxiliary lemma. We say that r, r' E {+1]
j-neighbors if ri r - 7 j. Let g be the minimal number for which the conditions in Lemma C.3 holds. Note that g well-defined, since in the worst case it is the size of the entire collection of neurons in the first hidden layer of
Lemma C.4. For every j E [gl there exist j-neighbors r, r' E {+1]9 so that:
1. Both S(r) and S(r') are non-emply.
2. f(r) f(r').
Proof. Suppose that for some j [g). for all j-neighbors r, r,r' E {+139 one of the following conditions holds:
1. At least one of
is empty.
2. -(r)= - f(r').
Then, we show that we may remove w; from G and define a new function fl: {+1]s-1 + y instead of f (as defined Lemma C.3 as follows. For r E {=1] let r r') E
(=1]s-1 be the vector which is identical to r without the j'th entry. Let E (#139 such that S(r) * 0. Define ('(r)(()) = -(r). By assumption, either that S(r') = or that s(r') = s(r), where r' the j-neighbor of and therefore using the value of f(r) for the vector r r/} does not violate the requirements from f. We now only consider region- specifying vectors of length g - 1, and for all
region-specifying
we have (( (x)) th (x)). This contradicts the minimality of g.
We note that in this section we do not need the second item of Lemma C.4 but it will be useful in the following section, when proving improved bound for the multi-index model. Let 2 be as defined in Lemma C.4, and denote Z = |2]. In order to prove Lemma C.3 we will lower and upper bound Z, starting with the lower bound.
Lemma C.5. We have Z 2 g +
Proof. By Lemma C.4 for every E [g] there exists an unordered pair of region-speciflinn vectors
Pj = (T(.+)) (.. -G.-)} where the j'th entry of r()++) is +1, the j'th entry of r(j--) is 1, both agree all other entries and both are in Z. Therefore, suffices to show that [U] > g + 1 Denote the distinct objects of U by
where U = U P3 -.... {ui...., J.
We define an undirected graph Q with the set of vertices being U [uI,.... ... Um) and the set of edges PI...., Pg. First, note that Q is simple graph. Indeed, by definition of Q. for any j. we have TG.+) # -(j.-) and therefore Q contains no self-loops. Furthermore, for all i. E [g]. P. * P, and therefore Q contains no parallel edges. We now argue that Q contains no cycles and therefore is forest. To show that fact, we argue that for any two different vertices u, u such that there exists a simple path of l edges connecting them, we have Ham(u, v) ht where Ham(u, u, v) is the hamming distance between u, U. Let P....... Ps.. be the edges of the path. Since Q is simple and the path is simple, all iι, ....... in are distinct. Therefore, precisely the bits of indices i.,..., ig are flipped between u and v. We now use that claim to prove that Q contains no (simple) cycles. Suppose that U1 U2,... ... ... Ug, U1 is simple cycle of length & > 3. Then, the path u2,.... .... Uk in is simple path
of length - 1, and thus Ham(ug, u1) = k - 1. On the other hand, that path u1, U2 is a simple path of length and thus Ham(ug, u1) = 1. It holds that 1 + k for all k 3, and thus have reached a contradiction.
To conclude, Q is forest with y many edges. It is well-known that the number of vertices in forest with g many edges is at least g + 1, proving the stated bound. As side note, the bound holds as equality in the case where Q is tree.
27

---

Lemma C.6. We have Z I TS(d, 71).
Proof. It suffices to construct a (d, "i Denote 2 "ri.....2.. We define the set P (21,...... { where for all E [Z], 2; E S(r;) is chosen arbitrarily from the (non-empty) set (r;)). The set P is well-defined by definition of 2. size Z. It is clear that |P| = and all points P are in (RR), since every instance taken from different region in B( To prove all other conditions, let j E [Z] distinct. So 24 E S(r:), Iy E S(ry). Therefore, there exists an index that rg. rJ disagree on, which means that sign( (Wk- x;)) -iign( ( In addition, |/ = by definition of the target net, and minser (1k,,;; 2 m since P PCC and by the definition of n1.
of size Z. We construct such packing as follows.
Let us show that
7/1 -dSpaa-isg
Proof of Lemma
C.3
Immediate from the jointing Lemma C.3
and and Lemma C.6
C.6
We use minimal size (g, repprssennn class as defined Definition B.1 with TSd,, 71) and LG = 1 for all G.
Lemma C.7. There exists expert E & who makes most 2TS(d, (1)(/ n//h many mistakes.
Proof. By Lemma C.3 and Proposition B.3 there exists expert E Expert such that Mi (F(F) S (S m)/n1-
We now bound M2(E), Let be a round in which makes a mistake of the second type. By the "furthermore" part of Proposition B.3 we may assume that Pt = 0 for all p E G. By definition of By definition of mistake of the second type, we have (G) (xx) - (v((")) (xxe) (where (p(G") is defined as in Proposition B.3). which means that f(r(C) (z, = yı. for f defined in Lemma C.3 Therefore, for any other round such that (Iv) = (zz) and E does not make mistake of the first type, E will predict for He, which is correct. Therefore, E will make at most Z | mistakes of the second type, one for each region such that S(r) + Therefore, M2(E) (d,, 7)) by Lemma C.3 The total number of mistakes made by E is thus at most
Expertc,,.c in such rounds Expert updates (o(r
(1(F) + M2(F) (s, Ts(d, s 2Ts m)/
(1)
That completes the proof.
Lemma C.8. We have
M(WM(E), max(16 Ts(d, m)/7 lo)((s(d.)))//))).co C}.
where C' is a universal constant.
Proof. First, by Proposition B.2 we have
|3] < (T'/7²
TS(d, 7 m(ddn))
By Lemma C.7 there exists expert who makes most 2TS (d, many mistkaes. By the mistake bound of WM(E) in Proposition A.2 we have:
2T. 7
TS(d, m) o
T
log T TS(d, log Tog
For any T > 15 TS(d,
rs)d,7))/ ///
log(TS(d, 71) / the above inequality is contradiction if
(Sdd, 71 //7 is larger than a universal constant. Othrewise, the above inequality is contradiction for any 7' larger than universal constant. This proves the stated bound.
Proof of Theorem
C Immediate from Lemma C.8
28

---

C.2 Lower bound of Theorem 2.1
The idea is similar to universality and expressivity results for neural networks (see, e.g.. [Shalev- Shwartz and Ben-David 2014)). Concretely, the lower bound relies showing that every binary function on a (d, ( -'S-packing can be expressed without violating the minimal ?1 margin constraint in the first hidden layer the target net.
Theorem C.9. For any learner Lrn, and for any : > 0, 2 1/s², there exists network with input dimension d and realizable input sequence S such that 71 2 and
M(Lrn, S) (( +/2)).
Proof. The dependence on 1/e² is implied by the known lower bound showing that the Perceptron algorithm is optimal.
Let us concentrate in the dependence on TS(d, e). Let Z1...., be a maximal (d, T)--piiccki,n For simplicity of notation, we prove the lower bound for the case where all induced separating hyperplanes for #1,...., IT are homogeneous, and the same argument works when this is not the case. The adversary uses S 21....,. FT as the input sequence of instances, and forces a mistake on the learner in every round. It remains to show that for every binary labeling V1...., UT E {=1} of S there
exists network V of input dimension d who realizes it with 71 2 Let G = (w (w ..... (9)) be a sequence of separating hyperplanes induced by the TS-packing be binary labeling of S. We construct net V with two hidden layers as follows. The first hidden layer consists of all hyperplanes in G. The second hidden layer is constructed as follows. Let
and let y/, yf,,... E {+1}
f: {+} - {+1] be a binary function such that for every 22 E S. f (rr((()))) ye- The neurons in the second hidden layer are all r E { such that f(r) 1, multiplicatively normalized by single output neuron with all 1/vg, and with an added bias of 2g The output layer consists
weights being 1/vds (recall that d2 is the width of the second hidden layer). The bias of the output neuron is 1/d2.
for all E S, where o' is the function computed by N*. Let xi E and let us calculate o (xx). First note that the input for second hidden layer is precisely / r(xx). Now, for every neuron (g(r), 2n 1) in the second hidden layer
Clearly, " 2 c. remains to show that (*xxx)
added for some r E {=1] the first hidden layer, we have
sign ( ((())
1 r(xe)) Vg
1 2g
[ r= r=)(; = 1-1 r r
1+
Therefore, if y/ O, then the output every neuron in the second hidden layer is -1/ Vdz and therefore the output neuron will get the value
sign (-db
1 d2
(- 1 = d2
+
sign
ddz
dd2
Otherwise, if = 1, then the output of every neuron in the second hidden layer is -1 -1/VTz, except for the neuron with weights q(r(z)) which exists by the definition of the network. Therefore the output neuron will get the value
sign - ((d2
+1
d2 = sign
= 1,
v JTz
dd2
Vola
VT2
d2
completeing the proof.
Applying the lower bound on (Sdd, c) from Theorem G.1 to the lower bound on the mistake bound proved above shows that the mistake bound can be exponential in d small 7ı, and linear in d even for constant 71 This inevitable dependence on d requires further assumptions on the target net and the input sequence in order to get dimension-fres mistake bounds. We study such assumptions the next sections.
29

---

D The multi-index model
In this section, prove Theorem 2.2 For that matter, prove variations of the lemmas proved in Section but with d replaced by k. The core idea allowing this is the fact that a labeling made by o² (as defined in Section 2.2 for (d, c)-TT- --ppckinn induces labeling of a (k,c) (c)-TT--pckinnn and thus its level of complication depends on rather than on d.
We begin by stating an appropriate version of Lemma Lemma D.1. There exists a subsequence G (w...... Wg of the hidden neurons (hyperplanes) in the first hidden layer of N such that:
1. g S | TS(k, m)), where = (r(G) E {=1}0
2. There exists a function f: {=139 + V, satisfying that for every a E S it holds that -
As in Section C we consider g as the minimal size of subsequence of the neurons in the first hidden layer for which the conditions in Lemma DanmmaD.1Jee hold. Therefore, Lemma C.4 used as also the multi-index setting. The proof the improved upper bound mainly due the following lemma.
1o4maaC.4amm (C.4and and Lemma C.5 can be
Lemma D.2. We have 7 S TS( 71).
To prove this lemma, we need an additional crucial property of the neurons G, proved in the lemma below. For simplicity and convenience of proof, we assume w.l.o.g until the rest of the section that s()) = 64 for all i E [k]. Indeed, if this is not the case, we can rotate the entire system to this state. Lemma D.3. For any w G, w; 0 for all i >> k.
Proof. Suppose towards contradiction that wx+1 * for some ur E Suppose w.l.o.g that the index of w in G' is 1. By Lemma C.4 there exist r, r E {+1}9 such that 1,r1 -1, and Ti = r for all i of 1, and furthermore:
1. S()), are both non-empty.
2. f(r) # f(r') (for f defined Lemma D.I.
Therefore, also R(r), R(r') are both non-empty. Therefore, there exists > 0 so that there exists ball B with the following properties:
1. w intersects with the center of B.
2. has radius c.
3. B
Let be the center of B. Note that has the following properties:
1. (w, c) =
2. |a|| S
Assume w.l.o.g that wh+1 > O. Consider two points c(r), c(r"). The point c(r) is identical to c except that c(r) Ck+1+c/22 The point c(r') is identical except that c(r')++1 Ck+1 cc/2. Note that c(r), c(r') E B and furthermore that
(w, cw))(r)) 0, (w, c(r')) O, since (w,e) c) = 0. Therefore, we have c(r) E R(r) and e(r') R(r'), and since f(r) # f(r') we have
4 (c(r)) * 4' (c(r'))
(2)
On the other hand, e(r); = c(r'); for all < k. Therefore, by the multi-index assumption (<(((r)) = 6² (c(r)) 8² (c((")) = (c(r'))
which contradicts 2
30

---

We may now prove Lemma D.2
Proof of Lemma D.2 It suffices to construct a (k, -n.:nn-TT---ssse of size Z. Denote 2
fri...., rz J. Let P = { 2'2,, where for all E [Z], .² is chosen arbitrarily from the non-empty set STT Let P= (x1 (.1....,,22 ). where for every 2 [2), let 2; be as xy. but only with its first & indices. Let us show that P {I),..... Iy is (k, 71) (en))-SS-pcceee -----packingg of size Z. First, for all i, a E B(R and therefore I; E =B(R*). To show that [P] = Z, we need to show that r; & zj for all distinct i.j. Indeed, since z/1 H' are taken from distinet ((r,,S(r))
there exists E G so that (ign(w, xz()) j (w, Therefore, z JJJ must differ in at least one index where is zeroed. Recall that than & + 1, and therefore r; # 2y. So far, we have established that P B(R)) and that its size is Z. It remains to show that total separability holds with the separation parameter ?1, We define G& to be the same as G. only that all indices larger than are removed from each vector G which is then scaled accordingly to have norm 1, making them all k-dimensional. For E G, denote the appropriate trimmed vector Gg by wgk- Let j E [Z] be distinct indices. From the same argument already given, there exists Wgk Gea that sign (W axi) * sign(w<k,, xz)). Finally, we claim that min,ee (w-sk: 4;)) z 71. Indeed, since C we have minggp: (w, ax) Z 71
O for all t > & by Lemma D.3 and thus they differ in some index smaller
which proves the claim.
Proof of Lemma D.1 Immediate from the joint of Lemma C.5 and Lemma D.2
Lemma D.4. There exists expert who makes at most 2TS(k, (k, n)/7/ many mistakes.
Proof. We apply the exact same arguments as the proof of Lemma C.7 with the only difference of applying Lemma insteadd of Lemma C.3 in (I).
Lemma D.5. We have
M(WM(E),S) S max 116 TS(k, n1/hi (P)(Ts(k C)
where C' a universal constant.
Proof. We apply the same arguments used in the proof of Lemma C.8
with only replacing TS(d, 71)
with TS(k, n)), and Lemma C.7 with Lemma D.4
Proof of Theorem 2.2 Immediate from Lemma D.5
E Learning with large margin everywhere
Fix the input sequence S C (R4 x y)" Recall the definition of a neuron's margin from Section C For any neuron (f.))) in A let
min (W(1),) (f))) =())
Twe..
We now define the minimal margin in the entire net:
TN** S)
min min Tw (S). de (e sE|d;41]
When the identity of N* S (or both) is clear, may omit them from the notation.
We will now prove Theorem 2.3 section E. we explain how to prune the network based on its minimal margin in the case of network that implements binary classification and has a single hidden layer. Then, in Section F.2 we explain how to extend the technique to the general case. Finally, in Section B.3 we give the learning algorithm itself.
31

---

E.1 Margin-based pruning with a single hidden layer and two labels
Let N* be the target net, and suppose that N has single hidden layer of width and that implements a binary function x- (RR") + } (and therefore has single output neuron). The collection of hidden neurons is denoted by C (V1...,,e) vt).
The main idea allowing the mistake bound of Theorem 2.3 is that the hidden layer of N in fact contains only (1//²)) "important" neurons. As usual, by "important", we mean that for every x E S, & (a:) depends only their output. This is formalized and proved in the following lemma, via uniform convergence.
Lemma E.1. There exists a sequence G (W1,... Wg) taken from the neurons in the hidden layer of N such that:
1. - 0(17))
2. For all x E S:
Φ- (1)) = sign Σ sign( (wn (ww;
Proof. We define binary hypothesis class H as follows. The domain of instances is all neurons in the hidden layer of A The input instances S 21...., 2T define the hypothesis class = (he....., hzz) the natural way: For an instance x and neuron hx()) sign((x, v)). By assumption, (x, z for all E X, E S. Therefore, the online perceptron algorithm will make at most 1/7² many mistakes on any input sequence realizable by H. It is known forr example by [Littlestone] 1988), that uniform mistake bound in the standard online setting for all realizable sequences upper bounds the VC-dimension of the class. Therefore VC(H) 1/?2.
X,
We now define distribution over = (v1,.... m2) (the hidden neurons). Let be the output neuron of N*, and suppose w.l.o.g that all entries of o are non-negative. We define D to be proportional the weights o. Namely, for every [E] define
o
Let rax) E {+1)² be the output value vector of the hidden neurons when the input instance is æ E S, and let u(r) be the real value calculated by the output neuron when is the output of the hidden neurons. The reason we chose D as the distribution above, is that Q (x) (as defined Section A.3 precisely u(r(x)) for any 2 S:
u(r(x))
Σ 0,
r(()))
xE(e]
Σ D(v+) (r))))
SE(e]
Σ
D(v)) sign(
xE(
ED Ev [sign( x)]
EurD [vx)
QD(x).
Theorem A.1 implies that if we draw an i.i.d sequence G of [1000 VC(H) log neurons (possibly with repetitions) from D, we have
(C(H)
many
Pr Gma Wi My
sup LHEH
- 7/2 s 3/4
Therefore, there exists sequence G of size g of hidden neurons such that
[Qp(hw) Qa(haa) 7/2.
sup EH
32

---

Note also that (x) sign(u(r(z))). Therefore, for all E S we have
sign(u(r(z))) d ('(x)
sign(Qn(ha))
sign(Qc(hzz)
9 sign( sign(
sign Σ
where the third equality is due to 33) and the margin assumption: By the margin assumption and the second equlaity, have [Q |u(r(z)) 2 y, and therefore for any q E (Qp(h,)
7/2, (D(h.) + 7/2), it holds that (4) sign Q (ba)). ) Equation 3 implies that Qa(hz) (12 +2/2]. Recall that VC(H) 1/1² and thus g = O(1/Tt) That completes the proof.
E,2 Margin-based Pruning in the general case
We now adapt the approach from previous section that handled shallow networks and binary output to the general case. The main building block we use to extend the pruning result from the previous
section to general networks is the function g. { {+1] - {+1), where y, I. E N, which we define
inductively as follows. For i E {O...., L - 1}, let p(0) 9. {=1]0" + {=1]s" be defined as
follows. Let E {=13=* For any index j of the output f(:) (r)
g
(r) = sign
Ti
i= 1)+1
In simple words, g. (r) takes every consecutive g entries in and uses the sign of their majority as new entry in the output vector.
We now show how use fg. extend the result from the previous section to the of general network. Suppose that the target network N' has L hidden layers.
Lemma E.2. Fix an output neuron in N*, and let o(x) {+1} be its value when x E S is the input. Let g be as the proof of Lemma E. Then there exists a sequence G of g neurons from the first hidden layer of N*, such that:
fo.(((z)) =(x)
for all x E S, where r(z) is, usual, the output vector of the neurons in G.
Proof. The proof by repeatedly applying Lemma from the output neuron backwards. Lemma E.I immediately implies that in the L'th hidden layer, there exists sequence G2 (w) (L)
, w...,,((L), ()) of g many neurons so that sign of the sum of their outputs when the input
gives o(x) for any x E S. Now, since 7 is the minimal margin the entire net, we can relate to each with
(L) output neuron, and again by Lemma E.1 in the (L 't hidden layer, there exists
sequence GL-1 (w (L-1) ..... w (L-1)) of many neurons so that the sign of the sum of their
outputs when is the input equals to the output of neuron w (L) when is the input, for any æ E S.
Repeating the argument the way up to the first layer gives the stated result.
Lemma E.2 implies that sequence of ((1//A1)) neurons from the first hidden layer suffices to
calculate the output of single output neuron. Therefore, it is clear that Ô log LV g
many neurons
suffice to calculate the output of all output neurons. It remains learn those ò then just fy. to calculate the output neurons. This is done by our meta-leame from Section B
log D 742
neurons, and
33

---

E.3 Learning algorithm with margin everywhere
As mentioned earlier, since there are [log [V1] output neurons, Lemma E.2 implies that Ó
742
many neurons are suffice to calculate the output of all output neurons by calculating fgr (r())()) for every sequence G' of size g' Ö(1/74h) of neurons that suffice to calculate the output of single output neuron. So we use our meta-learner with a (g. rrepresennnn class minimal size, with y C log " log(1/7f), where C' is some large enough universal constant, and La being the function that calculates every output neuron separately by the value of fg _ the appropriate sequence neurons given Lemma
Lemma E.3. We have
M(WM(E),
(7((L)(3))) (S)+
log |
Proof. By Proposition B.2 we have
|8| S (T + g)
where 9 C. log | 7-2
log(1/ (1/²))) By Lemma and thus (E) < g/72. Therefore, the mistake bound guarantee of WM implies that
E.2 there exists an expert E & for which M2(E)
T 3
9 72
+
9 72
log T glogg)
The above inequality is contradiction for any
9C log |
log log (29) git.
g
which proves the stated bound.
Proof of Theorem
2.3 Immediate from Lemma E.3
F
Adapting to the correct parameters
Our mistake bounds are of the form 1/7 where 7 < 1 is the relevant definition of margin and b > 1 a function y and other parameters of the problem, like the TS-packing number, the depth network, etc. Our analysis assumes that upper bounds on 1/7, b are given, and the mistake bounds actually depend on those bounds rather than on the true correct values of those parameters. is thus natural to seek solution for the that the known bounds on 1/y, b are very loose.
In the case where only one of y, known to the learner, relatively standard doubling tricks may be used to recover the original mistake bound (up to constant factors) obtained when both are known. In this section, we show that even both 7, b unknown to the learner, mistake bound of roughly 1/740 can be obtained. It remains open to prove or disprove that the original mistake bound 1 1/7" is achievable (up to constant, or even logarithmic factors) when both 7, are unknown.
The adaptive mistake bound is proven by the Adap(Lrn) algorithm given in Figure 4 where Lrn is the so that
learner requiring knowledge y, b. Let us briefly overview algorithm Adap(Lrn). Let n*, , 6*
M = 1/1=*" is the guaranteed mistake bound of Lrn when y*, b* are known. Adap(Lrn) maintains a guess X of M, and for every guess X, tries enough combinations of 7, so that 1/7² = X. For any such combination, it runs Lrn and stops its execution if X + mistakes are made. At first, we have X 2. After trying all combinations of 7, b that will be shortly defined, Adap(Lrn) updates X = x2, and starts again with the new guess of M. For every guess X of M, Adap(Lrn) does the following: Initialize 6 = X, 1// == 1 and execute Lrn with those parameters. If X +1 mistakes are made, it updates : b 1, 1/1/ == X1/b, and try again with the new parameters. Adap(Lrn) repeats this process until b = If X mistakes are made with b 1, it updates the guess of M from X to 2 and repeat the process.
34

---

Ara)(Lrn)
Input: learner Lrn requiring knowledge of 7,
Initialize: X 2, X, 1/X1/b.
1. Execute Lrn with parameters y, b until it makes + many mistakes.
2. If 1:
(a) Set b : b-
(b) Set 7 := 1//1//0
(c) Repeat Item 1
3. Else, if 1:
(a) Set X = X2.
(b) Set b: x,y y= 1/b
(c) Repeat Item
Figure An adaptive algorithm.
Proposition F.1. Suppose that Lrn is an algorithun with guaranteed mistake bound 1/72 on sequence S, assuming that y is lower bound on the relevant margin definition, and b is upper bound on the relevant exponent. Then Adap(Lrn) described in Figure 4 has mistake bound O(M* on S even if no such bounds y, are known.
Proof. Let us analyze the mistake bound of Adap(Lrn). Let X be the minimal guess of M such that X M, and let us assume w.l.o.g that even for the guess X, combinations failed (more than X many mistakes are made by Lrn). Since X > M, and we begin with b = X which certainly an upper bound b* and end with
y, we have tried
which is certainly a lower bound on b*. there must be j < X -2 2 such that the two consecutive combinations
(1/75,b3) xx (1/7541, (000)))((((((X-))))) (x1XX--1)xx---
satisfy 1/7/41 1/7* and bj 2 b* This means that if Lrn is executed with (1/78+11 by), at most 1/7 many mistakes are made. We argue that a combination with values at least (1/7)+1 1: by) will be tried in the worst case, when the guess of M is changed from X to X2, Indeed, let the guess of M be X2, and let j' x2
+ j. Then in the j''th combination guess of y-, b', we will have by X2 = X 2 and 1/78 (x2) xー X x² We thus require that X 2 X which is equivalent to x23 - which indeed holds for all j < X - which is the required range.
Therefore, in the worst case, when M = X2, Lrn will executed with correct upper bounds on 1/7" and b* and will make on this execution, at most (xx²) X-j
X2 < M many mistakes,
bb It remains to upper bound the number of mistakes made before this execution. By definition of the algorithm, for every guess x of M, the number of mistakes made is at most (a 1)x S (x + 1)2. Recall that in the final guess we have < 2 and thus (x + 1)2 < 4M The exponential update of implies that the total number of mistakes throughout the entire execution is most 8. as required.
and thus will not update the guess of , past this execution.
0
35

---

G
Bounds on the TS-packing number
Theorem G.I. For any N+ and e I 1/2 we have:
max {
1.5 d
{ - (T(d,))
2eV
Proof. The upper bound is the known upper bound for the standard (not totally separable) (d, e)- packing number (see, e.g., the lecture note (Wu and
As for the lower bound, let us start with the first expression. Consider the d'unit cube inscribed in the d-unit ball, where the cube's s sides are parallel to the axis. The vertices the cube are thus precisely the set (+1/Vd] d Supppose that S
2Vd as otherwise the stated bound is 1, which holds trivially
for - 1/2. For every direction i [d]. we define the following
many hyperplanes:
2evd
(es, k 2c), Ak {T-Levv
1
Levd.
2ev
We denote this set of hyperplanes by D,. The sets Dj define grid inside the unit cube. We can choose cell in the grid by choosing for every i, Js E
0, O,.... 2cv }]. where ja specifies the location of the cell in the i'th direction: all points such that sign( 2) + + 2e) 2 0
2rv2
but sign( .T + (j. + 1) 2e) < O. Since we have 2
2ev/d many choices in each direction and d
many directions, the number of cells is precisely (2 the set D.. each cell a d-cube with side length 2e, and thus the inscribed d-ball any such cube has redius precisely 2c. Therefore, the center of any such ball has distance at least from any hyperplane in the sets D.. is also straightforward to see that for two centers of different balls there exsits a separating hyperplane in the sets D, Therefore, the set of all centers of balls inscribed in cells in the defined grid forms a (d, c)-TS --ppkinn..
By definition of the hyperplanes in
2eva
remains to prove the d lower bound for any < 1/2. Consider the d-regular simplex inscribed in the d-unit ball. Dentoe its vertices by V = U1,-..y Ud- We claim that V is (d. e) TS--pckinn.. We construct for every making sure that Kw,, 1y) b,| > 1/2. We start with V1. Consider the hyperplane U1, specified by the same values as the point U1. We will show that sign( (V1. e2)) > 0 + j = 1. The direction j == 1 = sign( v,)) > is trivial. For the other direction, let j * 1, and suppose towards contradiction that sign((e1. simply 21 and Vy.. The third vertex u, is the intersection of the infinite line that intersects i1 and the origin, and the infinite line that intersects Uy and is also orthogonal to f. Let's calculates the triangle sides' lengthes. By assumption, dist(v) u) < 1. Therefore, also dist(u,, u) < 1. Pythagoras' theorem now impies that dist(1ı, 01, U₁} < V2. However, this contradicts Jung's 's theorem, stating that
hyperplane (w,, by) such that sign( (w,, 22) + 6.) > > j = i, while
(11 mz))
> 0. and consider the following triangle. Two of its vertices are
the diameter of V is exactly V /2(d+1) > V2, and therefore dist(11, U2) V2. To conclude,
have (w1, v1) = and (V1, 02) < 0 for all j * 1. Thus, the hyperplane (v1. -1/2) satisfics our requirements for V1. We may define similar hyperplane for all other points in V. Therefore V is (d..e)-TSppckiing -TS-packing for all e s 1/2.
36


Reviews:
[{"review_id": "7gUGFJdxj1", "reviewer": "Reviewer_J2Nn", "summary": "Authors study deriving mistake bounds of NNs with sign activations in the online learning setting.\nThe study considers both the realizable and agnostic cases, and introduces multiple bounds with varying assumptions. Specifically, authors first start with acceptably tight bounds that depend on $TS(d, \\epsilon)$ terms that are exponential in $d$ (input dimensionality) when $\\epsilon$ is small. Then, they move away from $d$ by projecting the input to a $k<<d$ dimensional space, and operate on the lower dimensional manifold that input is assumed to be in. This helps the authors to recover a bound with $TS(k, \\gamma_1) \\leq (1.5 / \\gamma_1)^k$ that is $poly(1/\\gamma_1)$. Then, the authors extend the $\\gamma_1$ treatment to all neurons and derive a logarithmic bound that has an exponential dependency to the NN depth.", "questions": "I have 2 main questions, both stem from my comments above. Regardless, I believe the work is strong and my questions are more towards gaining insights from the authors. If needs to be deprioritized to focus on critical questions from the other reviewers, I don't plan to change my ratings.\n\n1) Can you briefly expand on how well your analyses would generalize to say a ReLU network? What would need to change in your approach to acquire similar bounds, and why wasn't it studied in this work?\n\n2) A crude way to interpret these findings is that NNs can be learned online with reasonable regret when either intrinsic dimensionality of data is low /pattern can be learned by a pruned NN / or the NN is sufficiently shallow (which is somehow complementary to low data complexity). At what point these limitations become too strict that fitting linear model with logarithmic regret is more favorable?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This is a strong paper that studies a fairly underexplored are from a theoretical perspective. It was as refreshing read as many existing works on online learning w/ NNs are highly empirical and they rely on questionable heuristics. Characterization of the problem and the use of pruning seem to be on point, and being able to move away (w/ assumptions) from depending to input dimension seems novel. The findings also align with empirical analyses and common insights on NN learning dynamics as the 3rd bound is exponential in L. The paper is also well-written and easy to follow - I especially appreciate the inclusion of Section 4 to the main body.\n\nMost of my feedback is around organization and emphasis of the points. As the authors also emphasize, the findings do not immediately translate to practice as the study mainly focuses on sign activated NNs. The authors briefly mention the learnings would generalize to popular activation functions, but I believe it needs to be expanded upon. I also like the implied connections to pruning and autoregressive learning, however, it would be great if the authors provide more insights on those connections and propose how their findings can benefit these existing techniques. Finally, given the high quality of the rest of the sections (and appendix), open questions section needs to be rewritten to convey the authors' vision on the domain better.", "was_revised": true, "final_justification": "Very strong paper, hence I keep my score at 5. A 6 would be findings that are groundbreaking and with immediate practical implications.", "rebuttal": "We thank the reviewer for taking the time to carefully read and evaluate our work, and for their thoughtful and positive feedback, as well as their comments and suggestions to improve it. We will make our best efforts to incorporate their valuable suggestions in the next version of this paper. Below, we respond to the main issues raised in the review.\n\n### Response to weaknesses:\nWe thank the reviewer for their suggestions to clarify and expand on the implications of our work to other activation functions, pruning, and autoregressive learning. We will do our best to make sure that those implications are reflected in the text in a clear and detailed way.\nWe will also make another pass on the open questions section and will do our best to draw a more concrete vision for future work.\n\n### Response to question #1:\nUnfortunately, we do not see how our approach can be directly applied to the ReLU activation. A main reason is that our approach uses the classic Perceptron binary online learner as a building block. Roughly speaking, since the sign activation is also binary, this allows us to converge to the correct outcomes of the activations of the \"important\" neurons, which are necessary to predict the final outcome of the network. Obtaining similar results for the ReLU activation might require a completely different approach, and this is an excellent direction for future work. We will add it to the “future work” section. Thank you for bringing this to our attention.\n\n### Response to question #2:\nThe answer may heavily depend on the parameters of the problem. For example, in many online learning settings the horizon ($T$) is considered to be very large with respect to other parameters of the problem. In such cases, even if  the parameters of the problem (like dimension, margin, or network’s depth) cause our realizable mistake bounds to be very large, it might still be better than even a logarithmic dependence on $T$.\n\nOn the other hand, if $T$ is not extremely large, then in cases where a linear model with logarithmic regret is reasonably close to realize the data, and yet for a neural network to completely realize it we need really bad parameters (like a really small margin), the overall number of mistakes made by the linear model might indeed be smaller."}, {"review_id": "CayaoBpcH2", "reviewer": "Reviewer_8nh1", "summary": "This paper gives mistake upper and lower bounds for the problem of online learning of neural networks that have sign functions. It seems that the important parameter is the totally separable packing number (TS) which depends on the dimension of input and $\\gamma_1$ which is the margin of the neuron’s of the first layer from the sample. The authors demonstrate a mistake bound that scales with the $TS(d, \\gamma_1)$. This dependence can be exponential in the dimension $d$. Given this, they consider a different multi-index setting, where the labeling of data only depends on some $k <<d$ unknown dimensions. In this case, they show the learner enjoys a mistake bound that only scales with $TS(k,\\gamma_1)$. Another restricted setting is where every neurone in every layer has margin $\\gamma$. The authors show that in this setting the dependence on the dimension can be removed but an exponential dependence on the depth appears. I like the idea used here where in the space of first layer’s neurons each sample is considered as a hypothesis that gives a value to the neurons. Then it is possible to define a probability distribution over the neurons which is proportional to the weights with which the neurons are connected to the next layer/output. Using uniform convergence we can guarantee a small set of neutrons exists that approximates the output with an accuracy that does not change the sign, thus the output remains the same.\n\nFor the mistake bound a lower bound is also provided which is not tight an has a gap of approximately $1/\\gamma_1^2$ in some cases.\n\nThe authors also make progress in relaxing the knowledge of the margin parameter $\\gamma_1$ and the dimension. I think this is an important part that is worth exploring further because $\\gamma_1$ is a value that strongly depends on the entire sample.\n\nAll the upper bounds are derived for the agnostic case using known agnostic to realizable reduction techniques.", "questions": "The results are considered for the input lying in the unit ball. What is the dependence on the radius of the input? Similar to the linear classifiers where we get a mistake of $R^2/\\gamma^2$ for radius $R$ and margin $\\gamma$, is it possible that the dependence comes in the form of a value $O(R/\\gamma_1)$ in the packing number? Does generalizing the unit ball require different approaches or do the authors  focus on the unit ball for the simplicity of the notation?\n\nHow would one attemp other activation functions? Like if we have ReLU, what happens to the regions? There is a bit of a mention in related work that we can replace the activation by Lipschitz activations with a Lipschitz parameter that dependens on the margin everywhere parameter. But what if we have some layers with smooth activation functions, probably up to last layer, and then have sign functions. Can we reason about how the combined layers separate the space in regions and try to find the set of experts we need? It seems that still the parameter $\\gamma$ could be controlled by the weight of the layers and the Lipschitzness of the layers. Would this then be different than the prior work mentioned or will it give new understandings? This will potentially depend on the smoothness and weight of different layers and the margin of the first layers. To me it seems that we can kind of separate the first layers and then conclude a margin for it, which depends on its depth and weight of the vectors. Then the same analysis for the rest and output layer can be applied.", "limitations": "I believe the main important limitations are already mentioned in the paper. Please see Questions and Strengths and Weaknesses section for more comments.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written, clear and concise. All the ideas are clearly explained and elaborated as much as possible. For the technical parts, please see the summary. In general, I enjoyed the technical part and the attempts to make progress with different assumptions.\n\nI think the question of improving the exponential dependence on depth is an important question because in the supervised classification setting, the depth usually appears linearly. It seems to me that the exponential dependence here still does not come from the nature of the problem, rather than from the technique to approximate a function, i.e., neural network, with a different function that depends on less parameters and is easier to learn. So it is really not clear if the dependence is necessary, as pointed out by the authors too.\n\nI also think knowing having the knowledge of the $\\gamma$ is a very important challenge. I understand in a lot of online learning settings, it is easy in to relax this notion by simulating the learner and doubling the parameters iteratively. In this setting I also think it is a very important parameter because of its dependence on the sample. I however think this may require more efforts and can be addressed in future work. I also think that providing a bound that removes this requirement, although at an exponential price, is still important, which the authors have provided.", "was_revised": true, "final_justification": "I am happy to keep my score. The authors responded well to my questions. I also believed that the questions raised are best suited for future work and the paper is sufficient in its own. The reason I asked the question is that the paper provoked them, which makes me believe that the problem is interesting.", "rebuttal": "We thank the reviewer for taking the time to carefully read and evaluate our work, and for their thoughtful and positive feedback, as well as their comments and suggestions to improve it. We will make our best efforts to incorporate their valuable suggestions in the next version of this paper. Below, we respond to the main issues raised in the review.\n\n### Response to \"Strengths and weaknesses”:\nWe thank the reviewer for the positive and encouraging feedback. We want to make sure that the contribution of Section 2.4 is clear. The price of removing the requirement for prior knowledge of the problem’s parameters (including $\\gamma$) is polynomial, not exponential: the bound we prove is $O(M^4)$, where $M$ is the bound obtained when knowing the parameters in advance. We agree, of course, that even though the upper bound on the “price” that we prove is only polynomial, it will be interesting to improve it (or to show that it is impossible), as also mentioned in the open questions section.\n\n### Response to question on input radius:\nYes, the same approach can be used for any radius R, and we use the unit ball since it is a simplifying assumption that does not actually simplify the problem. Let’s consider linear classifiers as a simple example, as also done in the review. Any input of radius $R$ and margin $\\gamma$ can be shrinked such that it fits into the unit ball, while its labeling does not change. The only difference is that the shrinkage causes the margin to decrease from $\\gamma$ to $\\gamma’ = \\gamma/R$. For linear classifiers, this translates to a mistake bound of $1/\\gamma’^2 = 1/(\\gamma/R)^2 = R^2/\\gamma^2$, as in the original problem. The same shrinking can be done in our setup, and the margin decreases proportionally to the original radius.\n\n### Response to question on other activations:\nRegarding ReLU activation, we unfortunately do not see how our approach can be directly applied to the ReLU activation. A main reason is that our approach uses the classic Perceptron binary online learner as a building block. Roughly speaking, since the sign activation is also binary, this allows us to converge to the correct regions induced by the activation outcomes of the \"important\" neurons. Obtaining similar results for the ReLU activation might require a completely different approach, and this is an excellent direction for future work. We will add it to the “future work” section. Thank you for bringing this to our attention.\n\nRegarding the second part of the question, this sounds like a nice direction for future work. If we understood the reviewer’s intention correctly, they wonder whether we can relax some of the assumptions by replacing the activations in the first layers from sign to a smooth and Lipschitz activation, and then having control over the margin by some assumptions on the weights, rather than a direct margin assumption. It sounds reasonable, but might require further work in order to be formally proven."}, {"review_id": "4VgME7xkYb", "reviewer": "Reviewer_A2P8", "summary": "This paper studies online learning for the class of feedforward neural networks of a fixed architecture (that maps the unit ball to $Y=\\{\\pm 1\\}^k$ for some finite $k$) with the sign activation function. In the realizable setting, where the sequence presented by an adversary respects the labels assigned by some neural network in the class, the first result in the paper (upper bound in Theorem 2.1) shows that there exists a learning algorithm, that makes at most $\\tilde{O}(TS(d, \\gamma_1)/\\gamma_1^2)$ mistakes on any sequence $S=\\{x_1,\\dots,x_T\\}$ labeled by some target network $N$; here, $\\gamma_1$ is the smallest absolute value (margin) of a neuron (pre-activation) in the first layer of $N$ over all the examples in $S$, $d$ is the input dimension, and $TS(d, \\epsilon)$ denotes the totally-separable packing number of the unit ball, which is the size of the largest set such that there exists a hyperplane that separates every pair of points in the set, and is also at least $\\epsilon$ away from every point in the set. Complementary to this, the lower bound in Theorem 2.1 shows that for every learner, there exists a network and sequence of examples for which the number of mistakes is at least $\\Omega(TS(d, \\gamma_1)+(1/\\gamma_1^2))$. \n\n$TS(d, \\epsilon)$ depends poorly on the dimension $d$ (sometimes being exponential in $d$ for small $\\epsilon$)--- thus, to obtain dimension-free bounds, the authors consider two restrictions of the learning setting. The first setting considers the class of sign activation neural networks where the overall function computed by the neural network can be written as some function of the linear projection of the input onto a $k$-dimensional subspace. For this class, denoted as the multi-index model, the authors show (Theorem 2.2) a mistake upper bound of $\\tilde{O}(TS(k, \\gamma_1)/\\gamma_1^2)$. The authors show that $TS(k, \\gamma_1) \\le (1.5/\\gamma_1)^k$, so for small values of $k$, this mistake bound is $1/poly(\\gamma_1)$.\n\nThe second setting that the authors consider is that where every neuron pre-activation in the *entire* neural network has absolute value at least $\\gamma$ over all the examples in the sequence $S$. For this setting, the authors show an upper bound of $\\tilde{O}(\\log(|Y|)/\\gamma^{\\Theta(L)})$, where recall that $Y$ is the label space.\n\nThe algorithms above assume knowledge of $\\gamma_1$ or $\\gamma$: the next results in the paper consider the setting in absence of this knowledge. Theorem 2.4 shows the existence of an algorithm that does not require this knowledge, and attains a mistake bound that is only polynomially-worse than the mistake bound of the algorithm that knows this information. Lastly, the authors touch upon the agnostic setting (Propostiion 2.5)---using a reduction from agnostic to realizable learning for multiclass online classification established by Hanneke et al. 2023a.", "questions": "1) Maybe I am missing something obvious, but with regards to the footnote at the bottom of page 4, why does the lower bound from Theorem 2.1 trivially hold in the multi-index setting? Is it clear that the lower bound instance from Theorem 2.1 is a multi-index model?\n\n2) With regards to pruning: Is the following conclusion accurate given the results in your paper: For any neural network, there exists a small subset of neurons in the first layer, such that, if we retain only these neurons and get rid of all the other parameters of the network, then one can get a near-optimal mistake bound for the online learning game played on examples labeled by the unpruned network?\n\n3) I was trying to parse through the proof of the upper bound Theorem 2.1 in Appendix A, and the final form of the labelling function $L_G$ that the learner uses for the expert in Figure 3 was not clear to me. Could you please spell this out, and also point me to where it gets defined in the proof in Appendix A?\n\n4) Consider the class of neural networks of a fixed architecture (say with sign activations, and a single output neuron)---this class has some Littlestone dimension $d$. Standard realizable online learning says that $d$ is the optimal mistake bound for realizable online learning for deterministic algorithms. Is it fair to say that the upper and lower bounds in Theorem 2.1 are in some sense, *instance-specific* bounds for every target function from the class? That is, is it clear that the upper bound in Theorem 2.1 is uniformly always smaller than the Littlestone dimension of the class? Also, it must be the case that the lower bound is smaller than the Littlestone dimension (because of SOA achieving this bound always), right? Please let me know if what I am asking does not make sense.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is generally very well written, and does a good job of motivating the problem and also situating the work amidst relevant literature on online learning of neural networks. The proof sketches provide sufficient insights with regards to the technical tools used. The mistake bounds presented in the paper in the general setting are near-optimal. The algorithm used for the general setting is a nice adaptation of the standard multiplicative weights algorithm with experts; the class of experts constructed in the paper, and the essential arguments that make the experts algorithm work---namely 1) class of experts is small and 2) some expert is accurate--- are interesting to see. The techniques required to make the general-purpose algorithm work in the more restrictive settings are non-trivial, especially the setting that assumes margin over all the neurons. Lastly, the upper bounds can be be viewed as instantiations of the network-pruning/lottery hypothesis principle, which is quite a curious result. \n\nAs for weaknesses: it would be great if the definition of the precise online learning game considered in the paper (and the definition of the class of neural networks being considered) is included in the main paper, right before stating the results, in a preliminaries section. I understand the page limit restrictions, but hopefully, the extra page after paper decisions will help with this. As written right now, in order to fully understand all the terms in the statement of Theorem 2.1, I had to glance through Appendix A to understand some of the definitions and the precise problem setting.", "was_revised": true, "final_justification": "The authors' response helps clarify some of my confusions. Assuming that they will address them in the revision, I will maintain my positive review of the paper, and remain in favor of accepting the paper.", "rebuttal": "We thank the reviewer for taking the time to carefully read and evaluate our work, and for their thoughtful and positive feedback, as well as their comments and suggestions to improve it. We will make our best efforts to incorporate their valuable suggestions in the next version of this paper. Below, we respond to the main issues raised in the review.\n\n### Response to weakness:\nWe completely agree that some of the terms are only defined in the appendix (as noted in the beginning of Section 2). If the paper is accepted and an extra page is given for the camera-ready version, we will absolutely do our best to include all the key definitions in the main body.\n\n### Response to question #1:\nConsider the $k$-index model (that is, multi-index model with $k$ signals). One can apply the lower bound of Theorem 2.1 with dimension $k$ to the $k$-index model with dimension $d$: we use the instances from the lower bound with dimension $k$, as $d$-dimensional instances where every entry after the $k$’th is zero. Therefore, the target function depends only on the first $k$ directions, and the lower bound matches the statement of Theorem 2.1 with dimension $k$.\n\n### Response to question #2:\nNot exactly. Our work uses pruning in two kind of different ways. In Theorems 2.1 and 2.2, we indeed mostly rely on pruning the first layer of the network. Therefore, with respect to those results, your conclusion is correct, with the two following reservations:\n1. The subset of neurons remaining in the first hidden layer (after pruning it) might be as large as $\\mathtt{TS}(d,\\gamma_1)$, which might not be small, and could even be exponential in $d$ for small $\\gamma_1$, as demonstrated in Theorem G.1 (in Appendix G). Furthermore, this quantity heavily depends on the input, not just on the network, by the definition of $\\gamma_1$.\n2. After pruning, while we can reconstruct the original networks’ labeling based only on the remaining neurons, it is not as simple as just pruning the unimportant neurons and recalculating the value of the pruned network. In more detail, while the pruning process preserves the boundaries between regions with different labels, it loses grasp of **which** label is given to each region, and this knowledge must be reconstructed without relying on the original architecture of the network. We included an explanation in this spirit in Section 3.3, but we will add the above more detailed explanation to the next version of the paper.\n\nHowever, the pruning used in Theorem 2.3 is more similar to your description: it removes a portion of the network’s parameters (and the size of this portion increases with $\\gamma$), and the new, pruned network calculates the same labels as the original network. The difference from your description, is that the depth of the network is preserved, and we just have less neurons in each layer. We will also add this explanation to the next version of the paper.\n\n### Response to question #3:\nYou are absolutely correct that we did not explicitly initialize the labeling function $L_G$ used by the expert in the context of Theorem 2.1. The reason is that the initialization has no effect on the mistake bound of the expert (up to a constant factor). As explained in the second item of our response to question #2, the labeling function needs to be reconstructed from scratch. This seemingly pricey reconstruction has no effect on the expert’s mistake bound, since the bottleneck (that is, the more difficult part) is to identify the boundaries between regions with different labels. That bottleneck is referred to as “mistakes of the first type” and denoted by $M_1$ in Section B.1 of the appendix. Mistakes caused by an incorrect labeling function are what we call  \"mistakes of the second type”, denoted by $M_2$. We show in Lemma C.7 in the appendix that even when reconstructing the labeling function from scratch, we have $M_2 \\leq M_1$ and thus the total mistake bound $M_1+M_2$ is at most $2 M_1$.\n\nAfter clarifying that, we agree that adding an explicit initialization of the labeling functions to arbitrary values (like fixed $1$) will be more accurate and clear, and we will add such an initialization to the next version of the paper. Thank you for bringing this issue to our attention.\n\n### Response to question #4:\nAs mentioned in lines 80-82, even in a very minimal setting of a single input neuron and a single output neuron, any learner can be forced to make an unbounded number of mistakes in the online setting, unless more assumptions are made. This implies that even for the class defined by this simple architecture, the Littlestone dimension is infinite. We are able to obtain finite mistake bounds only when placing more assumptions, involving also the input, not just the class of networks.\n\nHowever, if one wishes to discuss online learning of neural networks in terms of the Littlestone dimension of the relevant class, a possible approach is to use the concept of a partial hypothesis class defined in [AHHM22]. This framework allows to define a hypothesis class as a set of partial functions, enforcing restrictions on the input sequence, such as large margin. We briefly mentioned that in footnote 5 in the appendix.\n\n### References:\n\n[AHHM22] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. Annual Symposium on Foundations of Computer Science (FOCS), 2022."}, {"review_id": "nmuLtcSjLo", "reviewer": "Reviewer_dAug", "summary": "This paper proves lower and upper bounds on the problem of online learning neural networks with the sign activation function in the realizable setting. These bounds relate the problem to the \"totally separable packing number\", a geometric quantity. Bounds are improved for two special cases (e.g., prediction depends only on low-dimensional subspace). Finally, a known reduction from the literature is applied to also say something for the agnostic case.", "questions": "- How difficult is it to compute or approximate the TS-packing number? From a computational complexity perspective?\n- Can Lrn use unbounded computational ressources? It seems so. Is this correct?\n- The paper [Khalife, S., Cheng, H., Basu A. (2023). Neural networks with linear threshold activations: structure and algorithms (Extended version). Mathematical Programming, 2023.] shows that all linear threshold networks (which should be the same as the sign activation networks in this paper, as far as I understand) can be equivalently represented as networks with only two hidden layers. Can this be leveraged to improve Thm. 2.3, which depends exponentially on the depth? Or any other result of this paper?\n- More generally, the division of a neural network into a \"pipeline with two stages\" reminds me of the proof strategy of the result I mention in the previous point. So maybe you should read it and potentially cite it, even if it does not yield an improvement for your results.", "limitations": "adequately addressed", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- problem studied is fundamental and important, and seems to be not well-studied so far (even though I don't know the literature and trust the authors on that).\n- the paper is well-written and seems to contribute quite a few non-trivial technical results to this fundamental and important problem.\n- I like that the authors put significant effort in high-level overviews of their proofs.\n\nWeaknesses:\n- I'm not sure how meaningful Thm. 2.1 is, as it mainly relate some complicated quantity (bounds on online learning) to another complicated quantity (TS-packing number). It is not immediately clear why this is a useful insight.\n- Thm. 2.2 doesn't seem very surprising. It basically says \"if we are in a k-dimensional subspace of R^d, then everything behaves as if we were in R^k\", which seems mathematically trivial. Am I missing something here?\n- For Thm. 2.3, it is not clear how realistic the assumption of \"large margins everywhere\" is. Is this a theortical borderline case, or is there some justification why this is interesting to study?\n- Section 2.4 sounds like a fancy additional technical contribution, but in fact it is only there to remedy a weakness that was swept under the rug before, namely that gamma and b need to be known for the results in Sections 2.1 to 2.3. This should be mentioned immediately when stating the results!\n- Prop. 2.5 is seems to be strong and general, but is only a minor technical contribution, as it basically follows from Hanneke et al. (2023a).\n- sign activation function is not much used in practice (but I recognize it is still a fundamental case that deserves to be studied, as well-argued by the authors).\n\nMinor (no need to discuss in rebuttal, these don't influence my evaluation):\n- line 28: recieves --> receives\n- line 32: Is the architecture of Phi* fixed? Known to Lrn?\n- line 46: typo in \"converasions\"\n- line 97: I don't understand what the distance between \"an input point\" and \"a neuron\" is. Also assumptions should not be \"hidden\" in footnotes. Later, in line 104, I again do not understand what this distance should be: (w,b) is a vector in R^{d+1}, but x_k is in R^d. Do you only compare inputs to the weight vectors, ignoring the bias? In both cases? Please make this clear.\n- line 110: \"Note that the difference between the upper and lower bounds is roughly quadratic in the worst case.\" --> what does this mean? make it more clear. does it mean that one is the square of the other (at most)?\n- line 114: \"not catastrophic\" is very dramatic and judging wording. Can you put this into more scientific terms and justify why it is \"not catastrophic\"?\n- line 150: this definition in prosa is quite unclear. Please provide a more rigorous definition of gamma.\n- line 165: where does the b suddenly come from? Can you explain this better?\n- line 193: randomized --> randomize (remove d)\n- line 342: improvmnt --> improvement (insert e)", "was_revised": true, "final_justification": "I thank the authors for their clear and extensive rebuttal. While I think that my original reservations are still somewhat present, the authors managed to convince me that, overall, their results are deep and interesting enough to justify acceptance at NeurIPS. I therefore increase my score from 3 to 4. I trust the authors that they will implement the promised changes in the final version.", "rebuttal": "We thank the reviewer for taking the time to carefully read and evaluate our work, and for their thoughtful and positive feedback, as well as their comments and suggestions to improve it. We will make our best efforts to incorporate their valuable suggestions in the next version of this paper. Below, we respond to the main issues raised in the review.\n\n### Response to Weakness #1:\nWe respectfully disagree with the reviewer on this weakness, for the following reasons.\n1. In Theorem G.1 (appendix G), we provide quantitative bounds on the TS-packing number. Those bounds are proved via pure combinatorial and geometric arguments that are not directly related to learning theory. Nevertheless, by applying Theorem 2.1, those bounds translate to quantitative bounds on the mistake bound of learning neural networks online. Most importantly, the lower bound of Theorem G.1 demonstrates the unavoidable dependence of the mistake bound on the dimension, showing that additional assumptions must be made in order to obtain dimension-free mistake bounds.\n2. The TS-packing number is not a new quantity defined in this paper. The early study of this quantity (or very similar variations of it) dates back to the 40’s, and it is an interesting quantity in its own right (see the recent thorough survey [BL24], also mentioned in Section 3.2, for more details). Our work provides even further motivation to study the TS-packing number, by proving that bounds on it immediately translate to mistake bounds for online learning of neural networks.\n3. Characterizing the complexity of learning tasks by combinatorial (and often complicated) quantities is a long and fruitful tradition in learning theory. Perhaps the most known examples are the VC-dimension, characterizing PAC-learnability [VC71], and the Littlestone dimension, characterizing online learnability [Lit89] and PAC private learnability [ABL+22]. Other famous examples include the DS-dimension, characterizing multiclass PAC learnability [BCD+22], and both the standard and sequential fat-shattering dimensions, characterizing PAC [KS94] and online [RST15] learnability of real-valued functions, respectively. There are many more examples in the literature.\n\n### Response to weakness #2:\nWe respectfully disagree with the reviewer on this weakness as well. There is a striking difference between being in a known $k$-dimensional subspace of $\\mathbb{R}^d$ and the $k$-index model (that is, the multi-index model with $k$ many directions). The difference is that in the $k$-index model, while we know that the target function depends on $k$ orthonormal directions, we do not know **what those directions are**. The challenge is to find those directions. To illustrate this, imagine that you are in the desert, and there is only one safe way out to the city. Suppose that you are being told that the way out is a straight line (that is, $1$-dimensional). While the problem is now easier than considering all possible paths, it is still much harder to find this straight line, than to simply walk on it, in case you were being told exactly where this line is.\nAt a technical level, the upper bound of Theorem 2.2 is achievable thanks to the specific method used by our algorithm: It quickly identifies the boundaries between regions where the label changes such that the bottleneck (the most significant part) of the mistake bound stems from the number of such regions. The $k$-index assumption ensures that the number of such regions grows at most as $\\mathtt{TS}(k,\\gamma_1)$.\n\n### Response to weakness #3:\nTheorem 2.3 provides an upper bound in terms of the minimal margin over the entire target network. Assuming that this margin is large is not necessary for the theorem to hold, but the bound indeed gets better as the margin gets larger. In other words, the assumption is required for the bound to improve over the previous bounds of Theorems 2.1-2.2.\n\nAs for specific justifications, the theorem is specifically valuable for shallow networks. For such networks, the bound depends only polynomially on the margin’s inverse, which is reasonably tight, by the well known lower bound for learning linear classifiers mentioned after the statement of the theorem (lines 157-158).  \n\nTo illustrate this, let’s consider a prototypical case of a network with a single hidden layer and one output neuron. In such a network, the difference between the set of neurons in the first layer considered in Theorem 2.2 and the entire set of neurons is only the output neuron. Nevertheless, the bound of Theorem 2.3 in this case depends only polynomially on the margin’s inverse, and has no dependence on the input dimension. Thus, it suffices that the margin in the output neuron is not extremely small for the bound of Theorem 2.3 to be much better than the bound of Theorem 2.1.\nWe will add this example to the next version of the paper. Thank you for bringing this to our attention.\n\n### Response to weakness #4:\nWe agree that it will be better to clarify earlier that those parameters should be known to the learner in order to obtain the exact bounds of Theorems 2.1-2.3. Thank you for bringing this to our attention. We would also like to stress that the degradation caused by not knowing the parameters in advance is only polynomial, as stated in Theorem 2.4.\n\n### Response to weakness #5:\nWe agree that Proposition 2.5 is strong and general, **and** only a minor technical contribution – those two statements do not contradict each other. The main technical contributions of the paper are indeed for the realizable case. This is explicitly stated right at the beginning of the paper (lines 31-37).\n\n### Response to weakness #6:\nWe agree with this weakness and with the reviewer’s reservation inside the parentheses. We will add an open question on studying a similar setup with other activations to the next version of the paper.\n\n### Response to minor weaknesses:\nAt the reviewer's request, we will refrain from discussing those weaknesses. We just want to thank the reviewer for their detailed evaluation, and for pointing out typos and unclear points. We will make sure to address and fix these issues in the next version of the paper.\n\n### Response to question #1:\nThis is a very interesting question for future research, and we will add it to the relevant paragraph, starting at line 379. The best approximation of the TS-packing number we know is the bounds stated in Theorem G.1 of the appendix. We are not aware of any bounds on the computational complexity of calculating a better approximation of the TS-packing number.\n\n### Response to question #2:\nYes, we did not restrict the computational complexity of the learner. Designing computationally efficient algorithms for online learning of neural networks is an interesting direction for future work. We have mentioned it in the “future work” section.\n\n### Response to questions #3 and #4:\nThank you very much for bringing this relevant paper to our attention. We indeed were not aware of it. The result you have mentioned unfortunately does not seem to directly improve the bound of Theorem 2.3 (or any other bound), since the process of converting a net of depth L to a net of depth 3 (that is, one with 2 hidden layers) might decrease the margin. However, this might be a possible interesting approach towards improving it. We will definitely add this to Section 5.2, where we discuss the open question of improving the exponential dependence on the depth in Theorem 2.3 (or proving that it is impossible).\n\nIt is also true that our proof strategy of Theorem 2.1 has some similarities with the proof strategy of the result that you have mentioned. We will relate to that matter as well in the next version of this paper.\n\n### References:\n\n[VC71] Vladimir N. Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971.\n\n[ABL+22] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. ACM Journal of the ACM (JACM), 69(4):1– 34, 2022.\n\n[BCD+22] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022.\n\n[KS94] Michael J Kearns and Robert E Schapire. 1994. Efficient distribution-free learning of probabilistic concepts. J. Comput. System Sci. 48, 3 (1994), 464–497.\n\n[RST15] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. J. Mach. Learn. Res., 16(1):155–186, 2015.\n\n[BL24] K´aroly Bezdek and Zsolt L´angi. On separability in discrete geometry. arXiv preprint arXiv:2407.20169, 2024."}]

Author rebuttal:

Meta-review: This paper addresses the problem of deriving mistake bounds for online learning of neural networks with sign activation functions. Following the initial reviews, the authors could convincingly address most reviewer concerns, also leading to score increases. Reviewers agree that the paper presents an interesting and valuable contribution to the field, and, from my perspective, the manuscript is a nice theoretical take on a somewhat underexplored (as also mentioned by J2Nn) branch of online learning of NNs. I am recommending acceptance of this manuscript, and encourage the authors to work-in the requested changes from the reviewers, as well as their own clarifications from the rebuttal phase.
Decision: Accept (poster)