Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Authors: Idan Attias
Steve Hanneke
Alkis Kalavasis
Amin Karbasi
Grigoris Velegkas
Venue: NeurIPS 2023 oral (2023)
Keywords: Learning Theory
Regression
PAC Learning
Online Learning
TL;DR: We provide (almost) optimal learners, in terms of their sample complexity, for realizable regression in the context of PAC learning and in the context of online learning.

Abstract: In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of the fat shattering dimension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards a more complete characterization since  the work of Simon 1997 (SICOMP '97). To this end,  we first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable.  We then identify a combinatorial dimension related to the graph dimension that characterizes ERM learnability in the realizable setting. Finally, we establish a necessary condition for learnability based on a combinatorial dimension related to the DS dimension, and conjecture that it may also be sufficient in this context. Additionally, in the context of online learning we provide a dimension that characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression, thus resolving an open question raised by Daskalakis and Golowich in STOC '22.

Optimal Learners for Realizable Regression:
PAC Learning and Online Learning
Idan Attias
Steve Hanneke
Ben-Gurion University of the Negev idanatti@post. www.:pppoottuuuu.eooooo bgu. ac.
Purdue University steve hawneke@gmail.coom com
Alkis Kalavasis
Amin Karbasi
Yale University
Yale University, Google Research
alvertos, alvertos.kalavaeee wwa.:osss....aaaaisslllllle.e.
amin karbasi@yall.eoommo..aa.a edu
Grigoris Velegkas
Yale University
grigoris. wel.iieweelegaaaaaleeeeeee
Abstract
this work, we aim to characterize the statistical complexity of realizable regres- sion both in the PAC learning setting and the online learning setting.
Previous work had established the sufficiency of finiteness of the fat shattering di- mension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards ization since the work of Simon (SICOMP '97). To this end, we first introduce minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. We then identify a combinatorial dimension related to the Graph dimension that characterizes ERM learnability in the realizable setting. Finally. we establish necessary condition for learnability based on a combinatorial dimension related to the DS dimension, and conjecture that it may also sufficient in this context.
complete character-
Additionally, the context of online learning we provide a dimension that charac- terizes the minimax instance optimal cumulative loss up constant factor and design an optimal online learner for realizable regression, thus resolving an open question raised by Daskalakis and Golowich in STOC '22.
Introduction
Real-valued regression is of the most fundamental and well-studied problems in statistics and data science [Vap99, GBC16, Bac21], with numerous applications domains such as economics and medicine [DG17]. However, despite its significance and applicability, theoretical understanding of the statistical complexity of real-valued regression still lacking-
Perhaps surprisingly. in the fundamental realizable Probably Approximately Correct (PAC) setting [Va184] and the realizable online setting [Lit88, DG22], we do not know of any characterizing dimension optimal learners for the regression task. This comes in sharp contrast with binary and multiclass classification, both in the offline and the online settings, where the situation is much more clear [Lit88, HLW94, BEHW89, Hanl6, DSS14, BCD+2 22, Nat89, DSBDSS15, RST23J. Our goal in this work to make progress regarding the following important question:
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Which dimensions characterize PAC and online learnability for realizable real-valued regression?
Consider an instance space X, label space y = [o, 1] and hypothesis class H C [0, 1|* In this work, we focus on the case of the regression framework with respect to the absolute loss {zz y) _ |x - yl for any 2, y E [0, 1]. following previous works [BLW94, Sim97, ABDCBH97, BL98, DG22]. Our qualitative results hold for more general losses, namely any approximate pseudo-metric loss, which includes common losses such lp for any p 2 1. See the formal statements in Appendix H.
PAC/Offline Realizable Regression, Let us first recall the definition of realizable real-valued regression in the PAC setting. Informally, the Iearner is given ii.. labeled examples drawn from an unknown distribution D with the promise that there exists a target hypothesis ht E H that perfectly labels the data. The goal is to this training set to design predictor with small error on future examples from the same distribution. Note that given a learner A and sample S ~ D", we let 2() be its prediction X E N' when the training set is S.
Definition 1 (PAC Realizable Regression). Let e: =0,, - R22 be the absolute loss function. Consider a class H. S [0, 1] for some domain X. Let h- E H be an unknown target function and let Dx be an unknown distribution on X. A random sample S of size n consists of points ;1,..., Tn drawn i.d. from Dx and the corresponding values he (z1),..... hh" (xn) of the target function.
An algorithm A (Xx x [0, 11)* -0->>00, 1]xt is an n-sample PAC learner for H with respect to & if. for all 0 < E, < 1, there exists n(E, 6) E N such that for any h" E H and any domain distribution Dx. it holds that E Ez~Dx (((A(S;)),)) (x))) S E, with probability at least 1 1 over S ~ D
An algorithm A (X x [0, 11)* [0, 1j is an n-sample cut-off PAC learner for H with respect to E if. for all 0 < 0, < there exists n n(e, 6, 7) E N such that for any h-* H and any domain distribution Dx, it holds that PraNDx (((((S)))) ht (x)) > 7) E, with probability at least 1 - over S ~ D'x
We remark that these two PAC learning definitions are qualitatively equivalent (cf. Lemma 1). We note that, throughout the paper, we implicitly assume, as c.g., in [HKS19], that all hypothesis classes are admissible in the sense that they satisfy mild measure theooric conditions, such as those specified in [DKLD84] (Section 10.3.1) or [Pol12] (Appendix C).
The question we would like to understand in this setting (and was raised by [Sim97]) follows: Question 1. Can we characterize learnability and design minimax optimal PAC learners for realiz- able regression?
Traditionally, in the context of statistical learning minimax optimal learner A is one that, for every class H. given an error parameter E and a confidence parameter requires minA maxp MM D) samples to achieve it, where MA (H;E,, 5, D) is the number of samples that some learner A requires to achieve error with confidence i when the data-generatiog distribution D. There seems to be some inconsistency in the literature about realizable regression, where some works present minimax optimal learners when the maximum is also taken over the hypothesis class H. i.e., min maxp, H MA (H, e, 5, D). This is a weaker result compared to ours, since shows that there exists some hypothesis class for which these learners are optimal.
Our main results in this setting, together with the uniform convergence results from prior work, give rise to an interesting landscape of realizable PAC learning that is depicted in Figure 1.
Online Realizable Regression. We next shift our attention to the classical setting of online learning where the learner interacts with the adversary over a sequence of T' rounds: in every round the adversary presents an example 2, X. the learner predicts a label De and then the adversary reveals the correct label y/. In this context, realizability means that there always exists some function h4 E H. that perfectly explains the examples and the labels that the adversary has chosen. In the agnostic setting, the goal of the leamnr is to compete with the performance of the best function in H. i.e., achieve small regret. This setting was introduced by [Lit88] in the context of binary classification, where they also characterized learnability in the realizable setting and provided an optimal algorithm. Later, [BDPSS09] provided an almost optimal algorithm in the agnostic setting, which suffered from additional log T factor in its regret bound. This extra factor was later shaved

---

Finite y-Fat-Shattering
Finite y-Grahh Dimension
Finise Y-OIG Dimension
Finite y-Natarajan
Dimension
Dimeusion
Finite
Uniform
Learnability by any ERM
PAC
Y-DS
Convergence
Learuability
Dimension
Figure I: Landscape of Realizable PAC Regression: the "deleted" arrows mean that the implication not true. The equivalence between finite fat-shattering dimension and the uniform convergence property is known requires finite scaled Natarajan dimension is proved in [Sim97]. The properties of the other three dimensions (scaled Graph dimension, scaled One-Inclusion-Grann Daniely-Shalev Shwartz (DS) dimension) are shown in this work. We further conjecture that finite scaled Natajaran dimension not sufficient for PAC learning, while finite scaled DS does suffice. Interestingly, we observe that the notions of uniform convergence, learnability by any ERM and PAC learnability are separated in realizable regression.
in the realizable case (see [SSSSS10]) and the fact that PAC learnability
(OIG) dimension, and scaled
by [ABED* SOEED+211 21]. The study of multiclass online classification was initiated by [DSBDSSI5], who provided an optimal algorithm for the realizable setting and an algorithm that is suboptimal by a factor of log k log in the agnostic setting, where k is the total number of labels. Recently, [RST23] shaved off the log l factor. The problem of online regression differs significantly from that of online classification, since the loss function has received lot of attention and there is series of works that provides optimal minimax guarantees [RSTIO, RS 14, RSTI5b, RSTI5a, 5a, BDR21].
binary. The agnostic online regression setting
To the best of our knowledge, the realizable setting has received much less attention. A notable excep- tion is the work of [DG22] that focuses on realizable online regression using proper' learners. They provide an optimal regret bound with respect to the sequential fattnttaalaaaaaaaeea fat-shattering dimension. However, as they mention in their work (cf. Examples 1 and 2), this dimension does not characterize the optimal cumulative loss bound.
Interestingly, Daskalakis and Golowich [DG22] leave the question of providing dimension that characterizes online realizable regression open. In our work, we resolve this question by providing upper and lower bounds for the cumulative loss of the learner that are tight up constant factor of 2 using a novel combinatorial dimension that is related to (scaled) Littlestone trees (cf. Definition 13). Formally, the setting of realizable online regression defined as follows:
Definition 2 (Online Realizable Regression). Let é [0, 1]2 R22 be loss function. Consider class H C [0, 1jx for some domain X. The realizable online regression setting over T rounds consists of the following interaction between the learner and the adversary:
The adversary presents It E.
The learner predicts Ir E [o, 1), possibly using randomization.
The adversary reveals the true label yt E [0, 1] with the constraint that Eh; E H, VT S t, h(xx)) y²-
The learner suffers loss ((Tr, vt).
The goal of the learner is to minimize its expected cumulative loss E Everry liT v7)
We remark that in the definition of the cumulative loss Cr, the expectation is the randomness of the algorithm (which is the only stochastic aspect of the online setting). As we explained before, the main question study in this setting is the following:
A learner is proper when the predictions ğ. be realized by some function ht E H.

---

Question 2. Can we characterize the optimal cumulative loss and design optimal online learners for realizable regression?
Our main result in this setting provides a dimension that characterizes the optimal cumulative loss up to factor of 2 and provides an algorithm that achieves this bound.
1.1 Related Work
Our work makes progress towards the characterization of realizable regression both in the offline and online settings. Similar results are known for the more studied settings of binary and mul- ticlass (PAC/online) classification [Lit88, HLW94, BEHW89, Han DSS14, BCD+22, Nat89, DSBDSS15, RBR09, BLM20, RST23, ABED 21, HKLM22, KKMV23, BGH* The funda- mental works of [BLW94, Sim97, ABDCBH97, BL98J study the question of PAC learnability for the regression task. However, none of them characterizes learnability in the realizable setting. [Sim97] showed that finiteness of scaled Natarajan dimension is necessary for realizable PAC regression. [BL98] employed the one-inclusion graph (OIG) algorithm get real-valued predictor whose expected error is upper bounded by the Vy-dimenniin, whose finiteness is sufficient but not necessary for realizable learnability in this setting. We refer to [KS23] for details about this dimension which was introduced in [ABDCBH97]. [ABDCBH97] showed that finiteness of the fat shattering dimen- sion at all scales is equivalent to PAC learnability in the agnostic setting. Nevertheless, this does not hold in the realizable case as Example 1 demonstrates. Similarly, the work of [BLW94] shows that fat shattering dimension characterizes the regression task when the labels are corrupted by noise. Recently, the concurrent and independent work of [ACC233] provides high-probability bounds for the one-inclusion graph algorithm in the realizable PAC regression setting using the Vy-dimension. We underline that this dimension does not characterize realizable regression. For more general losses, see [Men02, BBMO5].
In the area of online regression, the work of [DG22] studies the realizable setting of online regression with the absolute loss (as do) and presents a randomized proper learning algorithm which achieves a near-optimal cumulative loss in terms of the sequential fat-shattering dimension of the hypothesis class. We emphasize that this dimension does not tightly capture this setting and, hence, does not address the question that we study. In particular, the lower bound they provide is related to the unimprovability of a bound concerning the sequential fat-shattering dimension and does not tightly capture the complexity of the problem. In the more general agnostic case, regret bounds have been obtained in the work of [RST15a], using the sequential fat-shattering dimension and sequential covering numbers. These quantities are also not tight in the realizable setting, See also [RS14, RST15b, RST17J. Moreover, regression oracles have been used in contextual bandits problems, see [FR20, SLX22] for further details.
Our characterization (cf. Theorem 2) for the offline setting via the OIG algorithm [HLW94] is further motivated by the work of [MHS22], where they propose a dimension of similar flavor for adversarially robust PAC learnability. We mention that recently the OIG algorithm has received a lot of attention from the statistical learning theory community [AACSZ22, BHM 21, KVK22, SMB22, AHHM22, CP22]. Finally, for a small sample of works that deal with offline and online regression problems, [BDGR22, Go121, AH22, HKS19, She17, MKF122] and the references therein.
2 PAC Learnability for Realizable Regression
In this section, we present various combinatorial dimensions that provide necessary or sufficient conditions for lcarnability of real-valued functions. All the definitions that we consider have a similar flavor. We first define what it means for class H. to "shatter" set of n points and then define the dimension to be equal to the cardinality of the largest set that H can shatter. Moreover, since we are considering real-valued learning, these dimensions are parameterized by a scaling factor y (0, 1) which should be interpreted as the distance that we can get to the optimal function. We start with the standard notion of projection of a class Definition 3 (Projection of H to 5). Given S = (#1...., ,.)) E X",, the projection of H C y to S is HIs (((())) ... h(xx)) : h E H).
set of unlabeled examples.
Furthermore, we say that a labeled sample SE (X x [0, 1))* is realizable with respect to H if there exists h H such that h(z.) yı, Vi E [m].
4

---

2.1 7--Fat Shattering Dimension
Perhaps the most well-known dimension in the vellevelued learning setting the fat shattering dimension that was introduced in [KS94]. Its definition is inspired by the aseudo-dimensiee [Po190] and it is, essentially, a scaled version of it.
Definition (n-Fat Shattering Dimension [KS94]). Let H [0, 1J We say that a sample S E x is 7-fat shattered by H if there exist ,1,-..,88 8n E [0, 1j"h such that for all b E {0, 13 there exists hy H. such that:
. hbo())) 2 8, Vi [2]] such that b, = 1.
. ho((as) S 7, Vi [n] such that b; = 0.
The f-fat shattering dimension Dist is defined to be the maximum size of 7--fal shattered set.
In the realizable setting, finiteness of the fat-shattering dimension (at all scales) is sufficient for learnability and it is equivalent to uniform convergence" [BLW94]. However, the next example shows that it is not a necessary condition for learnability. This comes in contrast to the agnostic case for real-valued functions, in which learnability and uniform convergence are equivalent for all H.
Example 1 (Realizable Learnability + Finite Fat-Shattering Dimension, see Section 6 in [BLW94J). Consider class H. S [0, 1]x where each hypothesis is uniquely identifiable by a single example, i.e. for any x E X and any f. E HH we have that f(r) # g(x), unless f = g. Concretely, for every d S
N. let (S)) (S)losisa-1 be a partition of X and define Hd (bbg....bb- by E sis.)
where
3 d-1
lbo be (x)
E1
1s, (z)6,
Σ k=0
bx2
8
j=0
For any y 1/4 Dlat (Ha) d, since for a set of points zo, Jd-1 E X such thut euch 3. belongs
to Sj. 0 j dd,1,, Ha contains all possible patterns of values above 3/4 and below 1 1/4. Indeed, is not hard to verify that for any j E (0....,, 1} if we consider any == hbog.. E Ha with b;- we have h' hl(z,) 2 3/4. Similarly, if bj = 0 then it holds that h' hl(x,) S 1/4. Hence, Nevertheless, by just observing one example (xr, h²" (x)) any ERM learner finds
Diaa (UdeNHa)) the exact labeling function hi*
We remark that this example already shows that the PAC learnability landscape of regression is quite different from that of multiclass classification, where agnostic learning and realizable learning are characterized by the same dimension [BCI+*2]] 22].
To summarize this subsection, the thatteat dimension a natural way to quantify how well the function class can interpolate (with gap 7) some fixed function. Crucially, this interpolation contains only inequalities (see Definition 4) and hence (at least intuitively) cannot be tight for the realizable setting, where there exists some function that exactly labels the features. Example 1 gives a natural example of a class with infinite shatthatg dimension that can, nevertheless, be learned with a single sample in the realizable setting.
2.2 7- --Natraaaan Dimension
The --Nataraaan dimension was introduced by [Sim97] and is inspired by the Natarajan dimension [Nat89], which has been used to derive bounds in the multiclass classification setting. Before explaining the --Natarajan dimension, let us begin by reminding to the reader the standard Natarajan dimension. We say that set S = {x1, ..., _n,} of size n is Natarajan shattered by concept class shhaaajan-ssatteeeedd
H. C yx if there exist two functions f.g: : S - y so that fxx) + g(x,) for all i E [m], and for all b E {0, 13" there exists h E H such that h(x;;) f(x;) if b, = 1 and h(x;) g(æ,) if 0. Note that here we have equalities instead of inequalities (recall the fat-shattering case Definition 4).
From geometric perspective (see [BCD+22]), this means that the space H projected on the set contains the set (f(z)), g(x))) x x (fx,)))((r.) This set is "isomorphic" the Boolean
2 Informally, uniform convergence means that for all distributions D. with high probability over the sample, the error of all l H. on the sample is close to their true population error.
5

---

hypercube of size n by mapping f(z)) to 1 and g(z;) to 0 for all i E [n]. This means that the Natarajan dimension is essentially the size of the largest Boolean cube contained in H.
[Sim97] defines the scaled analogue of the above dimension as follows.
Definition 5 (7-Naaarajan Dimension [Sim97].. Ler H S [0, 1] We say that a set S E X is Sautarajjnnshatteeee by H if there exist f.g E(f(i),9(1) 2 27, and
[n] - [0, such that for every i [n] we have
H|s 2 (f(1). x... g())).
The 7-Natarajan dimension Ta is defined be the maximum size of --Nataarjjan-shatteee set.
Intuitively, one should think of the --Nataraja dimension as indicating the size of the largest Boolean cube that is contained in H. Essentially, every coordinate i [n] gets its translation of the 0, labels of the Boolean cube, with the requirement that these two labels are at least 2y far from each other. [Sim97] showed the following result, which states that finiteness of the Natarajan dimension at all scales is a necessary condition for realizable PAC regression:
Informal Theorem (Theorem 3.1 in [Sim97]). H. [ [0, 1]x is PAC learnable in the realizable regression setting only if ID < for all y E 1).
Concluding these two subsections, we have explained the main known general results about realizable offline regression: (i) finiteness of fat-shattering is sufficient but not necessary for PAC learning and (ii) finiteness scaled Natarajan is necessary for PAC learning.
2.3 y-Graph Dimension
We are now ready to introduce the 7-graph dimension, which is a relaxation of the definition of the y-Natarajan dimension. To the best of our knowledge, it has not appeared in the literature before. Its definition is inspired by its non-scaled analogue in multiclass classification [Nat89, DSS
Definition (7-Graph Dimension). Let H C [0, 1]x f: TR2 + 10, 1]. We say that a sample $ E x is y-graph shattered by H if there exists f [m]] [0, 1] such that for all b E (0, 1)" there exists hg E H such that:
>ho(as) = f(1), Vi [r]] such that b; O.
E(ho(zs): y, Vi E [n] such that b, 1.
The y-graph dimension D& is defined to be the maximum size of ry-graph shattered set.
We mention that the asymmetry in the above definition is crucial. In particular, replacing the equality hz, = f()) with ( f()) S 7 fails to capture the properties of the graph dimension. Intuitively, the equality in the definition reflects the assumption of realizability, i.e., the guarantee that there exists hypothesis 4t that exactly fits the labels. Before stating our main result, we can collect some useful observations about this combinatorial measure. In particular, we provide examples inspired by [DSS14, DSBDSS15) which show (i) that there exist gaps between different ERM learners (see Example 3) and (ii) that any learning algorithm with close to optimal sample complexity must be improper (see Example 4).
Our first main result relates the scaled graph dimension with the learnability of any class H C [0, 1]x using a (worst case) ERM learner. This result is the scaled analogue known multiclass results [DSS14, DSBDSS15] but its proof for the upper bound follows different path. For the formal statement of our result and its full proof, we refer the reader to Appendix B.
Informal Theorem 2 (Informal, see Theorem 1). Any H S [0, 1]2² is PAC learnable in the realizable regression setting by worst-case ERM learner if and only if Dy (H) < co for all E (0.
Proof Sketch. The proof of the lower bound follows similar way as the lower bound regarding learnability of binary hypothesis classes that have infinite VC dimension [VC71, BEHW89]. J. If H has infinite 7-graph dimension for some 7 E (0, 1), then for any n E we can find a sequence of that are 7-graph shattered by H. Then, we can define a distribution D that puts most of its mass on F1, so if the learner observes n samples then with high probability will not
points .... .......ee Fy
observe at least half of the shattered points. By the definition of the 7-graph dimension this shows

---

that, with high probability, there exists at least one ERM learner that is 7-far on at least half of these points. The result follows by taking n + 00.
The most technically challenging part of our result is the upper bound. There are three main steps in our approach. First, we argue that by introducing "ghost" sample of size n. top of the training sample, which is also of size n, we can bound the true eτror of any ERM learner on the distribution by twice its error on the ghost sample. This requires a slightly more subtle treatment compared the argument of [BEHW89] for binary classification. The second step is to use "random swaps" type of argument order to bound the performance of the ERM learner on the ghost sample as follows: we "merge" these two samples by considering any realizable sequence S of 2n points, we randomly swap elements whose indices differ by n, and then we consider an ERM learner who gets trained on the first n points. We can show that if such a learner does not make many mistakes on the unseen part of the sequence, in expectation over the random swaps, then has a small error on the true distribution. The main advantage of this argument is that it allows us to bound the number of mistakes of such a learner on the unseen part of the sequence without using any information about D. The last step of the proof is where we diverge from the argument of [BEHW89]. In order to show that this expectation is small, we first map H. to partial concept class H. [AHHM22], then we project H. to the sequence S, and finally we map H back to a total concept class by considering a disambiguaatin of it. Through these steps, we can show that there will be at most (2n) OODS (1) log(2n)) many different functions in this "projected" class. Then, we can argue that, with high probability, any ERM learner who sees the first half of the sequence makes, in expectation over the random swaps, a small number of mistakes on the second half of the sequence, Finally, we can take a union bound over all the (2n) O(D9 (7t log(2n)) possible such learners to conclude the proof.
2.4 7- 7-Onn-Inclusion Graph Dimension
In this section, we provide a minimax optimal learner for realizable PAC regression. We first review fundamental construction which is crucial ingredient in the design of our learner, namely the one-inclusion (hyper)graph (OIG) algorithm A ofG for a class H S yxx [HLW94, RBR09, 18S14, BCD+22]. This algorithm gets as input training set (Z1, 81) ..., (In, Dn) realizable by H and an additional example x. The goal is to predict the label of x. Let S = { Tn,,,,,.. r). The idea is to construct the one- one-inclusion graph GOIG induced by the pair H)). The node set V of this graph
corresponds to the set His (projection of H to S) and, so, V F yf++ll, For the binary classification case, two vertices are connected with an edge if they differ exactly one element x of the n + 1 points in S. For the case where y is discrete and D > 2, the hyperedge is generalized accordingly.
Definition 7 Inclusncnsioon Hypergraph [HLW94, RBR09, BCD+221) 221). Consider the set [n] and hypothesis class H. C yya), We define graph GOIG (V, E) such that V H. Consider direction i E [m)] and a mapping f [n] \ {i} - y. We introduce the hyperedge es,f = (h E V h(j) = f(),, Vj E [n] {i}}- We define the edge set of G to be the collection
F. = (es, : [m). [m] \ (1) V.e., + 0].
In the regression setting, having created the one-inclusion graph with y 10. 1). the goal is to orient the edges; the crucial property is that "good" orientations of this graph yield learning algorithms with low error. An orientation is good the maximum out-degree of the graph is small (cf. Definition 8). Informally, if the maximum out-degree of any node is M, then we can create predictor whose expected error rate is at most M/(n- + 1). Note that in the above discussion we have not addressed the issue that we deal with regression tasks and not classification and, hence, some notion of scule is required in the definition of the out-degeee.
Intuitively, the set S that induces the vertices H|s of the OIG consists of the features of the training examples {zi,..., } and the test point x. Hence, each edge of the OIG should be thought of as the set of all potential labels of the test point that are realizable by H. so it corresponds to the set of all possible meaningful predictions for x. An orientation a maps every edge e to a vertex e E e and, hence, it is equivalent to the prediction of a learning algorithm. We can now formally define the notion of an orientation and the scaled out-de.
For introduction to partial concept classes and their disambiguations refer the reader to Appendix B.
7

---

Definition 8 (Orientation and Scaled Out- Out-Degree), Let E [0.1].n E N.H. S [0. (0.) An orientation of the mneiinclusion graph G (V,E) E) is a mapping : E V so that (e) f any E F. Let (e(e) E [0, 1] denote the i-th entry of the orientation.
For a vertex V, corresponding to some hypothesis h E H (see Definition 7), let vs be the i-th entry of which corresponds to h(ā). The (scaled) out-degree of a vertex v under a is outdeg(u; a, a.7) = Hi E [m] ((o,(ei,)) vi) > ?H| The maximum (scaled) out-degree of is outdeg(o, =
maxvev outdeg(1; a, 7)
Finally, we introduce the following novel dimension in the context of real-valued regression. An analogous dimension was proposed in the context of learning under adversarial robustness [MHS22].
Definition 9 (--OIG Dimension). Consider a class H S [o, 11xt and let 7 E [0,1]. We define the y-one-inclusiee graph dimension DOIG of H as follows:
DIG (7{ supin E N: BS X such that finite subgraph G = EV of GHls (V En)) such that v orientations a, 3 E V, where outdeg (1; o, 7, > n/3}.
We define the dimension be infinite if the supremum is not attained by a finite
In words, it is the largest n E N (potentially oc) such that there exists an (unlabeled) sequence S of length n with the property that no matter how one orients some finite subgraph of the one-inclusion graph, there is always some vertex for which at least 1/3 of its coordinates are y-different from the labels of the edges that are attached to this vertex. We remark that the hypothesis class in Example 1 has --IIG dimension equal to O1)). Moreover, finite fat-shattering dimension of hypothesis class implies a finite OIG dimension of roughly the same size (see Appendix C). We also mention that the above dimension satisfies the "finite character" property and the remaining criteria that dimensions should satisfy according to [BDHM* 19] (see Appendix F). As our main result in this section, we show that any class H. is learnable if and only if this dimension is finite and we design an (almost) optimal learner for it.
Informal Theorem 3 (Informal, see Theorem 2). Any H C [0, 1 is PAC learnable in the realizable regression setting if and only if if (H) < co for all E 1).
The formal statement and its full proof are postponed to Appendix C.
Proof Sketch. We start with the lower bound. As we explained before, orientations of the one- inclusion graph are, in some sense, equivalent to learning algorithms. Therefore, if this dimension is infinite for some y > O, then for any N, there Thus, for any learner we can construct some distribution D under which it makes a prediction that is y-far from the correct one with constant probability, which means that H is not PAC learnable. Let us now describe the proof of the converse direction, which consists of several steps. First, notice that the finiteness of this dimension provides good orientations for finite subgraphs of the one- inclusion graph. Using the compactness theorem of first-order logic, we can extend them to good orientation of the whole, potentially infinite, one-inclusion graph. This step gives us weak learner with the following property: for any given there is some no E N so that, with high probability over the training set, when it is given ny examples as its training set it makes mistakes that are of order at least on a randomly drawn point from D with probability at most 1/3. The next step is technique
orientations with small maximum out-degree.
to boost the performance of this weak learner. This is done using the mmedian-boostinn [Kég03] (cf. Algorithm 2) which guarantees that after a small number of iterations we can create an ensemble of weak learners such that, a prediction rule according to their (weighted) median will not make any y-mistakes on the training set. However, this is not sufficient to prove that the ensemble of these learners has small loss on the distribution D. This is done by establishing sample compression schemes that have small length. Essentially, such schemes consist of compression function K which takes as input a training set and outputs a subset of it, and a reconstruction function p which takes as input the output of and returns predictor whose error every point of the training set S is at most y. Extending the arguments of [LW86] from the binary setting to the real-valued setting we show that the existence of such scheme whose compression function returns set of "small" cardinality implies generalization properties of the underlying learning rule. Finally, we show that our weak learner combined with the boosting procedure admit such a sample compression scheme.
Before proceeding to the next section, one could naturally ask whether there is a natural property of the concept class that implies finiteness of the scaled OIG dimension. The work of [Men02] provides
8

---

sufficient and natural condition that implies finiteness of our complexity measure. In particular, Mendelson shows that classes that contain functions with bounded oscillation (as defined in [Men02]) have finite fat-shattering dimension. This implies that the class is learnable in the agnostic setting and hence is also learnable in the realizable setting. As result, the OlG-based dimension is also finite. So, bounded oscillations are general property that guarantees that the finiteness of OlG-based dimension and Tat-shattering dimension coincide. We also mention that deriving bounds for the OlG-dimension for interesting families of functions is an important yet non-trivial question.
2.5
DDD Dimension
So far we have identified a dimension (cf. Definition 9) that characterizes the PAC learnability of realizable regression. However, it might not be easy to calculate it in some settings. Our goal in this section is to introduce a relaxation of this definition which we conjecture that also characterizes learnability in this context. This new dimension is inspired by the DS dimension, combinatorial dimension defined by Daniely and Shalev-Shwartz [DSS14]. In recent breakthrough result, [BCD+22] showed that the DS dimension characterizes multiclass learnability (with possibly unbounded number of labels and the 0-1 loss). We introduce scaled version of the DS dimension. To this end, we first define the notion of scaled pseudo-cube.
Definition 10 (Scaled Pseudo-Cube). Let v E [0, 11. A class H S [0, 1]4 is called a 7-pseudo-cube of dimension d if is non-empty, finite and, for any H and direction i [d], the hyper-edge ei,- = [gg E H. g(j) = f(i) Vj E [d], + j} satisfies lea, > 1 and E(g1 (i),g2())) > y for any 91.92 92 E et, 91 * 92-
Pseudo-cubes can be seen as a relaxation of the notion of a Boolean cube (which should be intuitively related with the Natarajan dimension) and were crucial tool in the proof of [BCD + 22]. In our setting, scaled pseudo-cubes will give us the following combinatorial dimension.
Definition 11 (y-DS Dimension). Let H. S [0, an n-ddiensionall y-pseudo-uube. The DDDS dimension DDS is the maximum size of y- DD DS-shattered
_ A set S E X" is y-DS shattered if H|s contains
set.
Extending the ideas from the multiclass classification setting, we show that the scaled-DS dimension is necessary for realizable PAC regression. Simon (Section 6, [Sim97]) left as an open direction to "obtain supplementary lower bounds [for realizable regression] (perhaps completely unrelated the combinatorial or Natarajan dimension)". Our next result is a novel contribution to this direction.
Informal Theorem 4 (Informal, see Theorem 3). Any H S [0, 1) is PAC learnable in the realizable regression setting only if ID (H) < co for all E (0, 1).
The proof is postponed Appendix D. We believe that finiteness of IIX) is also a sufficient condition for realizable regression. However, the approach of [BCD+22] 22] that establishes a similar result in the setting of multiclass classification does not extend trivially to the regression setting.
Conjecture (Finite yDD is Sufficient). Let H S 10,1]*' If D (HL) < so for all ? E (0, then H. is PAC learnable in the realizable regression setting.
3 Online Learnability for Realizable Regression
In this section we will provide our main result regarding realizable online regression. Litrlestone trees have been the workhorse of online classification problems [Lit88]. First, we provide definition for scaled Littlestone trees.
Definition 12 (Scaled Littlestone Tree). A scaled Littlstonne tree of depth d S oc is a complete binary tree of depth defined collection of nodes
U ( E (0,1) = (#r U (10 U (Non, Fo,, Vio, 211) U U... OSeed
and real-valued gaps
U (% E [0,1] e (0.139) (ra) U tro, n U 1700, 701, nio, 7u3 U... 0sted

---

such that,fr every path y E {0, 1 and finite n < d, there exists h E H. so that h((yg)) ) = Syselt for 0 S S n, where Syger is the label of the edge connecting the nodes I Tyge and Tyges1 and E (Sygtt..
Tyse.
In words, scaled Littlestone trees are complete binary trees whose nodes are points of X and the two edges attached to every node are its potential classifications. An important quantity is the gup between the two values of the edges. We define the online dimension Doni (H) as follows.
Definition 13 (Online Dimension). Let H. C [0. 11x Let Ta be the space of all scaled Lit- rlestone trees of depth d (cf. Definition 12) and T U Ta. For any scaled tree T
Ussegdep(r) (Tr, 7u) E (X, [0, 1]) u E {0, 133 lee P(T) = {v = (yo..., Vdep(T)) : Vi E
{0. 10)) be the set of all paths in T. The dimension Tyoul (H) is
dep(T)
monl (H) = =sup inf TET VEP(T)
Σ 1=0
Tys
In words, this dimension considers the tree that has the maximum sum of label gaps over its path with the smallest such sum, among all the trees of arbitrary depth. Note that we are taking the supremum (infimum) in case there is no tree (path) that achieves the optimal value. Providing characterization and a learner with optimal cumulative loss Up for realizable online regression was left as an open problem by [DG22]. We resolve this question (up to a factor of 2) by showing the following result. Informal Theorem 5 (Informal, see Theorem 4). For any H. = [o, 1| and & > O, there exists a deterministic learner with Cx S [H) E and any, potentially randomized, learner satisfies Ex 2
The formal statement and the full proof of our results can be found in Appendix E. First, we underline that this result holds when there is no bound on the number of rounds that the learner and the adversary interact. This follows the same spirit as the results in the realizable binary and multiclass classification settings [Lit88, DSBDSS151 15J. The dimension that characterizes the minimax optimal cumulative loss for any given T follows by taking the supremum Definition 13 over trees whose depth is at most T and the proof follows in an identical way (note that even with finite fixed depth T the supremum over infinitely many trees). Let us now give a sketch of our proofs.
Proof Sketch. The lower bound follows using similar arguments as in the classification setting: for any > O, the adversary can create a scaled I. Littlestone tree T that achieves the sup inf bound, up to an additive e. In the first round, the adversary presents the root of the tree zig. Then, no matter what the learner picks the adversary can force error at least /// The game is repeated on the new subtree. The proof of the upper bound presents the main technical challenge to establish Theorem 4. The strategy of the learner can be found in Algorithm 3. The key insight in the proof is that, due to realizability, we can show that in every round there is some D. E [0, the learner can predict so that, no matter what the adversary picks as the true label yi, the online dimension of the class under the extra restriction that h(x))) = yr i., the updated version space V (h E H: h(x,) yr, 1 < T < t}. will decrease by E(T Te). Thus, under this strategy of the learner, the adversary can only distribute up to [jon((H) across all the rounds of the interaction. We explain how the learner can find such a Z. and we handle technical issues that arise due to the fact that we are dealing with sup inf instead of max min in the formal proof (cf. Appendix E).
4 Conclusion
In this work, we developed optimal learners for realizable regression in PAC learning and online learning. Moreover, we identified combinatorial dimensions that characterize Iearnability in these settings. We hope that our work can lead to simplified characterizations for these problems. We believe that the main limitation of our work is that the OlG-based dimension we propose is more complicated than the dimensions that have been proposed in the past, like the fat- fat-shattering dimension (which, as we explain, does not characterize learnability in the realizable regression setting). Nevertheless, despite its complexity, this is the first dimension that characterizes learnability in the realizable regression setting. More to that, our work leaves as an important next step to prove (or disprove) the conjecture that the (combinatorial and simpler) 7-DS dimension is qualitatively equivalent to the 7-OIG dimension. Another future direction, that is not directly related this conjecture, is to better understand the gap between the fat-shattering dimension and the OIG-based dimension.
10

---

Acknowledgements
Amin Karbasi acknowledges funding direct support of this work from NSF (IS-1845032), ONR (N00014- 19-1-2406), and the Al Institute for searning-Enabled Optimization at Scale (TILOS). Grigoris Velegkas is supported by TILOS, the Onassis Foundation, and the Bodossaki Foundation. This work was done in part while some of the authors were visiting Archimedes Al Research Center.
References
[AACSZ22] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivo- tovskiy. The one-inclusion graph algorithm is not always optimal. arXiv preprint arXiv:2212.09270. 2022. 4
[AACS723] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhiv- otovskiy. Optimal pac bounds without uniform convergence. arXiv preprint arXiv:2304.09167 2023. 4
[AB99] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical founda- tions, volume 9, Cambridge university press Cambridge, 1999. 18, 21
[ABDCBH97] Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler. Scale- sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), 4444)6615-631, 1997. 2,4
[ABDH*2] Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM), 1-(6):1-42, 2020. 25
IABE++21 Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret online classification. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pages 447-455, 2021. 3,4 4
[AH22] Idan Attias and Steve Hanneke. Adversarially robust learning of real-valued functions. arXiv preprint arXiv:2206.1291 2022. 4, 25
[AHHM22] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 202/ IEEE 62nd Annual Symposium on Foundations Computer Science (FOCS), pages 658-671 IEEE, 2022. 4, 7, 17, 19, 25
[AHM22] Idan Attias, Steve Hanneke, and Yishay Mansour. A characterization of semi- supervised adversarially-roous. pac learnability. arXiv preprint arXiv:2202.05400) 2022. 25
[Bac21] Francis Bach. Learning theory from first principles. Online version, 2021.
[BBM05] Peter Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complex- ities, Annaly of Statistics, 497-177777-1537, 2005.
[BCD+13 +2] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Ychudayoff. A characterization of multiclass learnability, In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943-955. IEEE, 2022. 1, 4, 9, 25,28
[BDGR22] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. Conference on Learning Theory, pages 1716-1786. PMLR, 2022. 4
[BDHM+19) 19] Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Learnability can be undecidable. Nature Machine Intelligence, 1(1):44 48, 2019. 30
11

---

[BDPSS09] Shai Ben-David. Dávid Pál. and Shai Shalev-Shwartz. Agnostic online learning, In COLT, volume 3, page 1. 2009. 2
[BDR21] Adam Block, Yuval Dagan, and Alexander Rakhlin. Majorizing measures, sequential complexities, and online learning. In Conference Learning Theory, pages 587-590. PMLR, 2021.
[BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkl dimension. Journal of the ACM (JACM), 36(4):929-965. 1989. 1, 4, 6,
[BGH+23) 23] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 520-527, 2023. 4
[BHM+21] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Ychudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532-541, 2021. 4
[BHMZ20] Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal svm bound. In Conference Learning Theory, pages 582-609. PMLR, 2020. 25
[BL98] Peter L Bartlett and Philip M Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences, 56(2):174- 190, 1998. 2,
[BLM20] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 099-402. IEEE, 2020.
[BLW94] Peter Bartlett, Philip M Long, and Robert Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings the seventh annual conference on Computational learning theory, pages 299-310, 1994. 2, 4,5
[CKW08] Koby Crammer, Michael Kearns, and Jennifer Wortman. Learning from multiple sources. Journal of Machine Learning Research, 9()), 2008. 31
[CP22] Moses Charikar and Chirag Pabbaraju. A characterization of list learnability, arXiv preprint a 1.0956, 2022. 4
[DG17] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[DG22] Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizability to learning in games, In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 10, 28
2022. 1,
[DKLD84] Richard M Dudley, H Kunita, Ledrappier, and RM Dudley. A course on empirical processes. In École d'été de probabilités de Saint-Flos Flour XI1- pages 1-142. Springer, 1984. 2
[DMY16] Ofir David, Shay Moran, and Amir Yehudayoff. Supervised learning through the lens of compression. Advances in Neural Information Processing Systems, 29, 2016. 25, 26
[DSBDSS15] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai learnability and the erm principle. Mach. Learn. Res., 16(1):2377-2404, 2015. 1, 3, 4, 6, 10, 20,30
Multiclass
[DSS14] Amit Daniely and Shai Shalev-Shward Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR, 2014. 4, 6, 7, 9, 17, 25, 30
12

---

[FHMM23] Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal predic- tion using expert advice and randomized littlestone dimension. arXiv preprint arXiv:2302. 100002./33449 /3849, 2023. 30
[FR20] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
[FW95] Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the chhninkchervonenniis dimension. Machine learning. 21(3):269-300 1995. 25
[GBC16] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016. 1
[GHSTO5] Thore Graepel, Ralf Herbrich, and John Shawe-Taylor. Pac-bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59:55-76, 2005, 25
[GKN14] Lee-Ad Gottlieb, Aryeh Kontorovich, and Pinhas Nisnevitch. Near-optimal sample compression for nearest neighbors. Advances in Neural Information Processing Systems, 27, 2014. 25
[Gol21] Noah Golowich.
Differentially private nonparametric regression under growth condition. In Conference on Learning Theory, pages 1192. PMLR, 2021. 4
[Han16] Steve Hanneke. The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 17(1):1119-1333 2016. 1,4
[HKLM22] Max Hopkins, Daniel M Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Conference on Learning Theory, pages 3015-3069. PMLR, 2022. 4, 31
[HKS18] Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Agnostic sample compression for linear regression. arXiv preprint Xrxi:11810.01886 2018. 25
[HKS19] Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Sample com- pression for real-valued learners. In Algorithmic Learning Theory, pages 466-488. PMLR, 2019. 2, 4, 25, 26
[HLW94] David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0. 1}- functions on randomly drawn points. Information and Computation, 115(2):248-292.
1994. 1, 4,
[J$03] Tadeusz Januszkiewicz and Jacek Swiętkowski. Hyperbolic coxeter groups of large dimension. Commentarii Mathematici Helvetici, 78(3):555-583 2003. 28
[Kég03] Balázs Kégl. Robust regression by boosting the median. In Learning Theory and Kernel Machines, pages 258-272. Springer, 2003, 8, 25
[KMV23] Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms. arXiv preprint arXiv:2305. 1, 2023.
[KS94] Michael Kearns and Robert Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464-497, 1994. 5
[KS23] Pieter Kleer and Hans Simon. Primal and dual combinatorial dimensions. Discrete Applied Mathematics, 327:185-199 2023,
KSW17] Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Nearest-neighhor sample compres- sion: Efficiency, consistency, infinite dimensions. Advances in Neural Information Processing Systems, 30, 2017. 25
13

---

[KVK22] Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi. Multiclass learnability beyond the pac framework: Universal rates and partial concept classes. arXiv preprint arXiv:22/0.02299, 2022. 4
[Lit88] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. Machine learning, 2:285-313 1988. 1, 2, 4, 9, 10
[LW86] Nick Littlestone and Manfred Warmuth. Relating data compression and learnability, 1986. 8, 25, 26
[Men02] Shahar Mendelson. Improving the sample complexity using global data. IEEE transactions on Information Theory, 48(7):1977-1991, 2002. 4, 8,
[MHS19] Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pages 2512-2530. PMLR, 2019. 25
[MHS20] Omar Montasser, Steve Hanneke, and Nati Srebro. Reducing adversarially robust learning to non-robust pac learning. Advances in Neural Information Processing Systems, 33:14466-1444 14637, 2020. 25
[MHS21] Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning with unknown perturbation sets. In Conference Learning Theory, pages 3452- 3482. PMLR, 2021. 25
[MHS22] Omar Montasser, Steve Hanneke, and Nati Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. Advances in Neural Informa- tion Processing Systems, 35:37458-37477 2022. 4, 8, 25
[MKF122] Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis Ioannidis. Differen- tially private regression with unbounded covariates. International Conference on Artificial Intelligence and Statistics, pages 3242-3273. PMLR, 2022.
[MY16] Shay Moran and Amir Yehudayoff. Sample compression schemes for classes. Journal of the ACM (JACM), 63(3);1-10, 2016. 25, 27
[Nat89] Balas K Natarajan. On learning sets and functions. Machine Learning. 4(1):67-97, 1989. 1, 5,
[Osa13] Damian Osajda. A construction of hyperbolic coxeter groups. Mathematici Helvetici, 88(2):353-367, 2013. 28
Commentarii
[Po190] David Pollard, Empirical processes: theory and applications. Ims. 1990. 5
[Pol12] David Pollard. Convergence of stochastic processes. Springer Science Business Media, 2012. 2
[RBRO9] Benjamin IP Rubinstein, Peter L Bartlett, and Hyam Rubinstein. Shifting: One- inclusion mistake bounds and sample compression. Journal of Computer and System Sciences, 75(1):37-59, 2009. 4,
[RS14] Alexander Rakhlin and Karthik Sridharan. Online con-parametric regression. In Conference on Learning Theory, pages 1232-1264. PMLR, 2014. 3,
[RST10] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances in Neural Information Processing Systems, 23, 2010.
[RSTI5a] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. J. Mach. Learn. Res., 16(1):155-186, 2015. 3, 4, 30
[RST15b] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probubility theory and related fields, 161:111-153, 2015. 3, 4,
14

---

[RST17] Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy. minimax regret and minimax risk. 2017. 4
[RST23] Vinod Raman, Unique Subedi, and Ambuj Tewari. A characterization of online multiclass learnability. arXiv preprini arXiv:2303. 17716, 2023. 1,
[She17] Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 3105-3114. PMLR, 2017. 4
[Sim97] Hans Urrich Simon. Bounds on the number of examples needed for learning functions. SIAM Journal on Computing, 26(3):751-763, 1997. 2. 3, 4, 6,
[SLX22] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler op- timal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904-199 2022.
[SMB22] Han Shao, Omar Montasser, and Avrim Blum. A theory pac learnability under transformation invariances. arXiv preprint 2rxX1::2022.07552, 2022.
[SSSSS10] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnabil- ity, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010. 3
[Val84] Leslie Valiant. A theory of the learnable. Communications of the ACM,
27(11):1134-114, 1984.
[Vap99] Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10(5):988-99) 19988,9999900 1999.
[VC71] V. Vapnik and A. Chervonenkis. On the uniform convergence relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264- 280, 1971.
[WHEY15] Yair Wiener, Steve Hanneke, and Ran El-Yaniv. A compression technique for analyzing disagreement-basse active learning. J. Mach. Learn. Res., 16:713-745, 2015. 25
15

---

A Notation and Definitions
We first overview standard definitions about sample complexity in PAC learning.
PAC Sample Complexity.
The realizable PAC sample complexity M(H:e, of H. is defined as M(H;e, inf Ma(H;s,0), AEA
(1)
where the infimum is over all possible learning algorithms and M Ma 5) is the minimal integer such that for any
Ma(H;e, 8), every distribution Dx on X, and, true target ht H, the
expected loss E [[ (T) 4 (x)) of is at most & with probability 1 - over the training set T ((1, h² (z)) : DIE E S}. S DT.
PAC Cut-Off Sample Complexity. and we define
We slightly overload the notation of the sample complexity
M(Hie, inf (,(H;,,0,7) AEA
(2)
where the infimum is over all possible learning algorithms and MA (Hi 5, is the minimal integer such that for any m 2 MM E, 7), every distribution Dx on X, and, true target h" e H. the expected cut-off loss Pra-D, (((((T)()) hx), > >> of A is at most with probability 1 6 over the training set T= {(xx, ht (x)) x S), S Dx
Lemma 1 (Equivalence Between Sample Complexities). For every e, 8 E (0, 1)² and every H. C [0, 1] where X' is the input domain, it holds that
M(H: V2.8. S &M(H:E,8) /(H+:E/2,&.=/2
Proof. Let A be a learning algorithm. We will prove the statement for each fixed and for each data- generating distribution D, so the result follows by taking the infimum the learning algorithms.
Assume that the cut-off sample complexity of A is MM e/2, 8, e/22. Then, with probability over the training sample S ~ D, for its expected loss it holds that
E z~Dx
I(AA(S))), 1 (x)) <
E 2
(1 2 S
thus, MA MA(::; S //
The other direction follows by using Markov's inequality. In particular, if we have that with probability least 1 5 over S ~ D it holds that
E I((A(S)=),,' Se. x z~Dx
then Markov's inequality gives that
Pr ((A(S:z),h* 2 VE] S VE, a~
which shows that (H;;E) (H,
ERM Sample Complexity. In the special case where A is the class ERM of all possible ERM algorithms, i.e., algorithms that return a hypothesis whose sample error exactly 0, we define the ERM sample complexity the number of samples required by the worst-case ERM algorithm, i.e., sup MA(H:e,5), AEERM
MERM ()
(3)
and its cut-off analogue as
MERM(H;;
sup Ma(His,, AEERM
(4)
B y-Graph Dimension and ERM Learnability
In this section, we show that 7-graph dimension determines the learnability of H S [0, 1]x using any FRM learner. We first revisit the notion of partial concept classes which will be useful for deriving algorithms.
16

---

B.1 Partial Concept Classes and A Naive Approach that Fails
[AHHM22] proposed an extension of the binary PAC model to handle partial concept classes, where H S {0. pew.teepppooooee
] for some input domain X, where h(x) = * should be thought of as h not knowing the label of x E X. The main motivation behind their work is that partial classes allow one to conveniently express data-dependent assumptions. As an intuitive example, halfspace with margin partial function that is undefined inside the forbidden margin and is a well-defined halfspace outside the margin boundaries. Instead of dealing with concept classes H S yxt where each concept E H is total function h X - y, we study partial concept classes H S ()' U {*])*² where each concept h is now partial function and h(x) = * means that the function / is undefined at We define the support of as the set supp(h) = {x E X h(()) + *). Similarly as in the case of total classes, we say that a finite sequence S = (#1, 1/1, ................................ Fna Mn) is realizable with respect to H. if there exists some h* E H. such that h" (zx) = y/. Vi E [m]]
An important notion related to partial concept classes is that of disambiguation.
Definition 14 (Disambiguation of Partial Concept Class [AHHM22]). Let X be an input domain. A total concept class H. S 10, is special type of partial concept. Given some partial concept class H. S {0, 1, + we say that H is a disanbiguation of H if for any finite sequence S (X {0, 1})" if is realizable with respect H. then S is realizable with respect H.
Intuitively, by disambiguating a partial concept class we convert it to a total concept class without reducing its "expressivity".
Let us first describe approach to prove the upper bound, i.e., that if the scaled- saaled-raaph dimension is finite for all scales then the class is ERM learnable, that does not work. We could perform the following transformation, inspired by the multiclass setting [DSS14]: for any h E H S [0, 1] let us consider the function h X [0. 1] + (0.1) with Ma, y) if and only if h(x) = y, h( y) = if and only if ((h(z), v) > and (1r, y) = * otherwise. This induces a new binary partial hypothesis class H = {h: h E H} S {0, 1, We note that D (H) VC(H). However, cannot use ERM for the partial concept class since in general this approach fails. In particular, sufficient condition for applying ERM is that VC((supphh) h E H)} < oc.
Remark 1. Predicting * in [AHHM22] implies mistake for the setting of partial concept classes. However, in our regression setting, is interpreted differently and corresponds to loss at most ? which is desirable. In particular, the hard instance for proper learners in the partial concepts paper (see Proposition 4 in (AHHM22]) is good in settings where predicting * does not count as a mistake, as in our regression case.
B.2
Main Result
We are now ready to state the main result of this section. We will prove the next statement. Theorem 1. Let E be the absolute loss function. For every class H C [0, 1 and for any e, e, E (0, 1),, the sample complexity bound for realizable PAC regression by any ERM satisfies
DC (H) + log(1/5)
DD log(1/)) + log(1/5)
Ω
< MF; 5, s
E
In particular, any ERM algorithm A achieves
(G(H)) + log(1/))
E I((A(S;)), DNDx
inf 7E(0,11
7 θ P
n
with probability at least 1 - 5 over S of size
Proof. We prove the upper bound and the lower bound of the statement separately.
Upper Bound for the ERM learner. We deal with the cut-off loss problem with parameters (c, E (0, 1)3. Our proof is based on technique that uses "ghost" sample to establish generalization guarantees of the algorithm. Let us denote
(h) A Pr [e(h(z), (x)) > 71.
(1)
x=Dx
17

---

and for a dataset 2 E (X' x [),"
êt , (h) -
Σ (a.))E=
He((()), > 7).
(2)
We will start by showing the next symmetrization lemma in our setting. Essentially, it bounds the probability that there exists a bad ERM learner by the probability that there exists an ERM learner on sample whose performance on hidden sample is bad. For similar result, Lemma 4.4 in [AB99]]
Lemma 2 (Symmetrization), Lete,y E (0.1)",n> 0.x Z X x 1]. Let
Qun = (=E 3h E H =. (h) = 0, erp, 5)
(3)
and
RE, {(r,s) T Z 3h E H: erD, (h) >E, E, ,t, 0, (h,,(()) 2 8/2).
(4)
Then, for 2 c/c, where is some absolute constant, have that
("(Qen)) S. (Re,))
We will show that D2n (Re,)) 2 D" (*().))
Proof.
By the definition of Ren we can write
(Re( = =
f D* 3h E H. HrD (h) > (h) = (h) (r))
Q.n
For E Qen, fix hr H that satisfies ot, (h,, = 0, CTD, (h) > It suffices show that for hy (a é (h2) 2 e22) 1/2.
Then, the proof of the lemma follows immediately. Since erp,, (h, > follows binomial distribution with probability of success on every try least & and n number of tries. Thus, the multiplicative version of Chernoff's bound gives
we know that é (h)
Da Gr (h,) E/2) Se
Thus, if n c/e, for some appropriate absolute constant see that
D" Gr, < e < 1/2,
which concludes the proof.
Next, we can use random swap argument to upper bound D2 (Be,,) with quantity that involves set of permutations over the sample length 2n. The main idea behind the proof is to try to leverage the fact that each of the labeled examples is likely to occur among the first n examples or the last n examples.
Following [AB99], we denote by In the set of all permutations on (1...., 2n] that swap i and + i, for all that belongs to (1.....n) n). In other words, for all a E Tn and i E fl...... n) either (i) i, (n + i) n + i or (i) n + i, (n + i) = i. Thus, we can think of as acting on coordinates where (potentially) swaps one element from the first half the sample with the corresponding element on the second half of the sample. For some E 2 we overload the notation and denote (2) the effect of applying to the sample z.
We are now ready to state the bound. Importantly, it shows that by (uniformly) randomly choosing a permutation
I'n we can bound the probability that sample falls into the bad set Re, by quantity that does not depend on the distribution D.
Lemma (Random Swaps; Adaptation of Lemma 4.5 in [AB99]) Fix Z X' 10, 11. Let Re, be any subset of 7 and D any probability distribution on Z. Then
D2n (Re,)e
E
Pr
[o(2) E Real, [0(2) E Re,) < max Pr
SE2 a>U(TT)
where U(T,)) x)) is the uniform distribution over the set of swapping permutations In.-
18

---

Proof. First, notice that the bound
Pr INDDAN UiT
E
(0(2) E Re,l S max
Pr [a(2) E Re =e o
follows trivially and the maximum exists since Pr ProwD(r,)) (z))) E Reyl takes finitely many values for any finite n and all 2 E 2 Thus, the bulk of the proof is to show that
D2m (Re,)) = 2nDPPn anD
[o(2) E RE Pr
First, notice that since example drawn i.i.d., for any swapping permutation a E Pn we have that
DLn (Re()),))= DD" ((= E 7 :0(2) REa)))
(5)
Thus, the following holds
D2m (Re,n) / If2 E Re,) (z)
1a((2) E REa } (2)
Σ Ha(z) e Rea) (x)
T (o(2) E Rea),
Pr DoD TT
where the first equation follows by definition, the second by Equation (5), the third because the number of terms in the summation is finite, and the last one by definition.
As a last step we can bound the above RHS by using all possible patterns when H. is (roughly speaking) projected in the sample rs z
Lemma (Bounding the Bad Event). Fix Z = x [0, 1]. Let Re Z be the set
RE ((,,s) E z n 3h H (hr 0, ét., (h) 2 e/2}.
Then
Pr (o(2) E Re,l < (2m) O (7L) log(2n)) n2e/2_ )TL
Proof. Throughout the proof we fix z = (21, =2n) E Z where z; = (xi, y:) = (x h (x::) and let S { J2 -2nn Consider the projection set H|s. We define partial binary concept class H'' C (0, 1, *] 2n as follows:
h(x.) yb: ((h(a:), > 7, E(h(2.)..)) ST
h'(1) 0
H' N [0,10,1 36 E His Vi [2n]
h'(i)
I(ii) =
Importantly, we note that, by definition, VC(H') S (H))
Currently, we have a partial binary concept class H'. As a next step, we would like to replace the symbols and essentially reduce the problem to a total concept class. This procedure is called disambiguation (cf. Definition 14). The next key lemma shows that there exists compact (in terms of cardinality) disambiguation of VC partial concept class for finite instance domains.
Lemma 5 (Compact Disambiguations, see [AHHM221). Let H. be partial concept class on finite instance domain X' with VC(H) = Then there exists a disambiguation H. of H with size [7 = (ddloo (21)
This means that there exists disambiguation H. of H' of size most
(2 O(0 ( (H) log(2n))
19

---

Since this (total) binary concept class is finite, we can apply the following union bound argument. We have that (22) E Rif if and only if some h E H. satisfies
Ei=1 I(((h(Fo()) Ma(h) > 7) =0 En= (((C)((()))))) yo(n+
7 2 e/2.
72
n2
We can relate this event with an event about the disambiguated partial concept class H' since the number of I's can only increase. In particular, for any swapping permutation of the 2n points, if there exists a function in H that is correct on the first n points and is off by at least y on at least En/2 of the remaining n points, then there a function in the disambiguation H that is 0 on the first points and is 1 on those same e of the remaining points.
If we fix some a E n. and some h/' E H' then // is a witness that (2) E Re,y only if E [n] we do not have that hi(i) = 1, li + n) = 1. Thus at least one of (i)),, h'(n + i) must be zero. Moreover, at least ne/2 entries must be non-zero. Thus, when
draw random swapping permutation the probability that all the non-zero entries land on the second half of the sample sample is at most 2 2-ns/2
Crucially since the number of possible functions is at most HH' S (2m) ((D) log(2n)) union bound gives us that
Pr [o(2) RI,y1 s (2n) (10) .2 2-ne/2 a~D(T.)
Thus, since a E z was arbitrary we have that
max Pr (o(=) E Rend S (2n) (og((2)) 2-ne/2 zm aU(T.))
This concludes the proof.
Lower Bound for the ERM learner.
Our next goal show that
(H) + log(1/5)
6 7) 2 Co
&
To this end, we will show that there exists an ERM learner satisfying this lower bound. This will establish that the finiteness of 7-graph dimension for any 7 (0, 1), is necessary for PAC learnability using a worst-case ERM. It suffices to show that there exists a bad ERM algorithm that requires
at least Co (1)) samples to cut-off PAC learn H. First let us consider the case where = (H) < oo and let S = {=1...... hd} be r-graph-shattered set by H. with witness fo- Consider the ERM learner A that works as follows: Upon seeing a sample T S S consistent with fo- A returns function A(T)) that is equal to fo on elements of T and y-far from fo on S \ T. Such with witness fo. Let us take 1/100 and < 1/12. Define distribution over 5 _ X' such that
function exists since S is
Pr[c.] = 2s, =r(zz)=2e//0 1), VI (2,.....,
Let us set h²* = So and consider m samples {(z): fo(2:)) Since we work in the scaled PAC model, A will make a y-error on all examples from S which are not in the sample (since in that
case the output will be 7-far from the true label). Let us take m < d-1 include most (d - 1)/2 examples which are not œ with probability 1/100, using Chernoff's s bound. Conditioned on that event, this implies that the ERM learner will make a 7-error with probability at least 2r (d-1 -
Br Then, the sample will
e, over the random draw of the test point. Thus, M (Ht;e,
6, 5, = Ω (-)))
Moreover, the probability that the sample will only contain is (1 (1 )mm > e -4em which is greater that å whenever m < log(1/6)/(4s). This implies that the y-cut-off ERM sample complexity is lower bounded by
{ d 1 log(1/0)
Co }
D& (H) + log(1/))
max
25 }
=
65
E
Thus MERM(H: e, 5, 7), satisfies the desired bound when the dimension is finite. Finally, it remains to claim about the case where ID (H) oo for the given 7. We consider sequence of 7-graph- shattered sets S,, with SSa| n and repeat the claim for the finite case. This will yield that for any the cut-off ERM sample complexity is lower bounded by 2((n + log(1/5))/e) and this yields that
MERM(H. d, 7) 00.
D
20

---

However, as Example 4 shows, the optimal learner cannot be proper and as a result, this dimension does not characterize PAC learnability for real-values regression (there exist classes whose y-graph dimension is infinite but are PAC learnable in the realizable regression setting).
C Y-OIG Dimension and Learnability
In this section we identify a dimension characterizing qualitatively and quantitatively what classes of predictors H S [0, 1 PAC learnable and provide PAC learners that achieve (almost) optimal sample complexity. In particular, we show the following result.
Theorem 2. Let be the absolute loss function. For every class C (0, 1] and for any e, (0, 1)², the sample complexity bound for realizable PAC regression satisfies
OOIG (H)
DOIG (H)
DOIG (H)
+ log )
92
M.HHi, SO
log"
In particular, there exists an algorithm A such that
(OIG(H) + (1/()
E (()(S) inf 7 + θ >E(0,1]
7
with probability at least 1 over ~ D
A finite fat-shattering dimension implies a finite OIG dimension. Let J C [0, 1| be function class with finite 7-fat shattering dimension for any 7 0. We show that DOIG (F) upper bounded (up to constants and log factors) by (D (F), for some c > O, where the OIG dimension is defined with respect to the l loss. Note that the opposite direction does not hold. Example 1 exhibits function class with an infinite fat-shattering dimension that can be learned with a single example, and as a result, the OIG dimension has to be finite. On the one hand,
have upper bound on the sample complexity of O ( äg (F) log² + log })) for any e, 8 (0, 1). See sections 19.6 and 20.4 about the restricted model in [AB99]. On the other hand, we prove in Lemma a lower bound
on the sample complexity of 22.0 for any E (0, 1). and so DOIG (F) is upper bounded by Drtat (F) up to constants and log factors. cryy
C.1 Proof of the Lower Bound
Lemma 6. [Lower Bound of PAC Regression] Let A be any learning algorithm and e, 6, y E (0, 1)s
such that 8 E. Then,
DDIG (H)
(7 20
E
Proof. Let no = (HH) Letn N,1 S no. We know that for each such there exists some S E X such that the one-inclusion graph of H|s has the property that: there exists a finite subgraph G (V, E) of GOIG such that for any orientation E E- V of the subgraph, there exists a vertex E V with outdeg(u; (,y) > DOG (H)/3.
Given the learning algorithm A (X' x [0, 11)= x + [0, 1]. we can describe an orientation a of the edges in F. For any vertex (V1,-.., Un)) V let P, be the distribution over (I1, v1). (,,,,,,,...... .... (Iay vn) defined as
Po((21, v1)) = - E, (or ox))
n 1 1 tE (2....,n)
Let m n/ (2x). For each vertex V and direction t [ri]. consider the hyperedge et, For each u E ct, we define
(u Pr (((A(S; u)) (x,,, u)) S]. Pm
and let Cr... {u Ct, (u( < 1/2). If Co,,, = 0, we orient the edge er, arbitrarily. Since for all u, Ct,v the distributions pm pm conditioned on the event that (It, u.), (I,, vx) respectively
21

---

are not in S are the same, we can see that Vu, E Cea, it holds that E(u,, v2) S 2y. We orient the edge et,- using an arbitrary element of Ce...'
Because the previous discussion, we can bound from above the out-degree of all vertices v E V with respect to the orientation σ follows:
outdeg(r;
Σ (p) 2 1/2] 21+2 >
Pr [((A(S))))) (1 (((2e,,))) y1) & 5). SmpP
Notice that
Pre [E(AASS xz). 31) > 7) A {TE,, Me) SH
Pr ((). > (1 Ma) SS
Sm-P
P Pm (1 V1h
and by the definition of P.. we have that
Pr (Tx, yr) $ S]
2 1 2(n 1
E
n
S Pm
1)
since = (22)). Combining the above, we get that
ouldeg((;0A.27) $1+2 (1
Σ
E ((((A(S,x))))) > >> [[ ve) $ SH).
2(n 1)
and
27) 2
71
I(((A(S, m1
2(n 1)
SmmP Pm
= = +2 2
11
E
(e)A(S.))), vt)
2(n 1)
Pm
2
$14 1 2
11
E
E
[(((A((:)),)) 71
2(n 1)
SNPm
(a.y)~P.
1+2 2
1
n1
-
E
Pr [a.M)PP
((A(S:)))))
2(n
2
11
E
Pr [((A(S)))))>>
S
(x.
By picking "hard" distribution that
Por, where on max outdeg(u's (v'; o a 27) we get that
Pr (((A(S=))))) 2) (x.
6 2 (outdeg(e's (o,,, -1) n 2
Smmm
21m m
IV
since outdeg(v" J.A 27) n/3. By picking no see that when the learner uses no/e samples then its expected error is at least e /6. Notice that when the learner uses m' MM (H(H:,,6,1) samples have that
Pr (((A(S=)),)) > 2 <8+ 8)E 56+05 25. (..N))~..-
E
Pmn
Thus, we see that for any algorithm A
DOIG (H)
8
hence
DIG (H)
2
5
22

---

C.2 Proof of the Upper Bound
Let us present the upper bound. For this proof. we need three tools: will provide weak learner based on the scaled one ine-inclusoon graph, boosting algorithm for real-valued functions, and consistent sample compression schemes for real-valued functions.
To this end, we introduce the one-inclusion graph (OIG) algorithm A for realizable regression at scale 7
C.2.1 Scaled One-Inclusion Graph Algorithm and Weak Learning
First, we show that every scaled orientation a of the one-inclusion graph gives rise to a learner A. whose expected absolute loss is upper bounded by the maximum out-degree induced by a.
Lemma (From Orientations to Learners). Let Dx be distribution over X and ht E E [0. let n and y E (0, 1). Then, for any orientation a : En + Vn of the cooled-one-inclaeee G (Vn; En), there exists learner As (X x [0, - [0, 1]xt such that
graph
max.ev, outdeg(u;0,
E
Pr x>>xx
(e(Aa(a), h (x)) 7
SND
where Ag is trained using sample S of size realized by ht"
Algorithm From orientation o to learner Ag
Input: An H-realizable sample {(1,, w:)) W and a test point æ E EX 7 E (0,
Output: A prediction (z)).
1. Create the one-inclusion graph GOIG
"H(ep 1.0)
2. Consider the edge in direction defined by the realizable sample (( y)) let
e e= (h- E H (1).))--13))) e [n - 1] h(i) = wi).
3. Return =
Proof.
By the classical leave-one-out argument, we have that
Pr (((, v = E [T(((hs(z).)) 8) > 71 S'NDD ((U())))((())
((((hs,((xt)).) > >7],,
SNDD D>
(s.().)))>
where hs is the predictor As using the examples S, and U([n] is the uniform distribution (1,...,,,, Now for every fixed S' we have that
Σ I(((o(e)((. > 7) outdeg(v':a,7) iE|M
[[E(hs (2/). v/1 > 7 [~U([()]
n
where y' is the node of the scaled OIG that corresponds to the true labeling of S' By taking expectation over S' ~ D we get that
outdee()/:a..))
max autdeg(u;g,))
E [Lllsss S'NDD INDD))
> SH
E SINDD
1
n
Equipped with the previous result, now ready show that when the learner gets at least Do (H) samples as its training set, then its expected y-cutoff loss is bounded away from 1 1/2.
Lemma 8 (Scaled OIG Guarantee (Weak Learner)). Lei Dx be distribution over X and h E H C [0, 1j and (0, Then, for all DDIG (H) there exists an orientation o* such that for the prediction error of the one-inclusion graph algorithm AGIG (X [0, 1))" -1 X - [0, 1]. it holds that
E
Pr D=Nx
[(AAII
OIG (x),
> 7| $ 1/3.
SwD x
23

---

Proof. Fix E (0. Assume that > D (H) and let GOIG () = (Va, Ex) be the possibly
infinite scaled one-inclusion graph. By the definition of the 7-OIG dimension (see Definition 9), for every finite subgraph G = (V, E) of G there exists an orientation E + V such that for every vertex in G the out-degree is at most n/3, i.e.
(8.x)
SS E X", A finite G = (V, F.) of GHls orientation og s.t. Ve E V, it holds outdeg((;dn,))) S n/3.
First, we need to create an orientation of the whole (potentially infinite) one-inclusion graph.
We will create this orientation using the compactness theorem of first-order logic which states that set of formulas & is satisfiable if and only if it is finitely satisfiable, i.c., every finite subset &' C & is satisfiable. Let GOIG (Vns En) be the (potentially infinite) one-inclusion graph of H|s. Let Z Our goal is assign binary values each
be the set of pairs 2 (U. e) E Vn E, so that 2 E Z. We define the following sets of formulas:
For each e En we let &e -3 exactly one e: ((, = 1.
Vn we let 4. (Ev' E e (2(1',e) A l(0,, v,) > 7))
For each
most n/3 different fi,f E En E eif
It is not hard to see that each Te. t can be expressed in first-order logic. Then, we define
(n & n NoE F.,
(
+
n
L
Notice that an orientation of the edges of GHls is equivalent to picking an assignment of the elements of Z that satisfies all the le. Moreover, notice that for such assignment, if all the 4, are satisfied then then maximum 7-scaled out-degree of G is at most n//3.
We will now show that is finitely satisfiable. Let Φ' be finite subset of & and let F' C En, V C Vn, be the set of edges, vertices that appear in Φ', respectively. If Vf 0, then edges in E' arbitrarily and satisfy Φ' Similarly, if F' = we can let all the z(e, v) = 0 and satisfy all the 2., v E V'. Thus, assume that both sets are non-empty. Consider the finite subgraph of GOIG
orient the
that is induced by V and let E" be the set of edges of this subgraph. For every edge E E' E"4 pick an arbitrary orientation, i.e, for exactly one u E set z(e, v) = and for the remaining r' E set =(e, v²) O. By the definition of IDOIG (H) there is an orientation Øg of the edges in E" such that Ve E V'uuddcg(e;; , I n//3. For every e E E" pick the assignment of all the z(u,e), E e, according the orientation grr. Thus, because of the maximum out-degree property of dg we described before, we can also see that all the D,,, v E V', are satisfied. Hence, we have shown that & finitely satisfiable, so satisfiable. This assignment on z(v,e) e) induces an orientation o under which all the vertices of the one-inclusion graph have out-degree at most n/3.
We will next use the orientation o* of GOIG (Vn, En) design a learner A (X' x [0, 1))-~1x "Hss X + [0, 1), invoking Lemma 7. In particular, we get that, from Lemma 7 with the chosen orientation,
>>>> S maX outdeg(o; 0* o*;
E
Pr x>Dx
OIG [e(Aa] (x),
< 11/3,
SWDR
which concludes the proof.
C.2.2 Boosting Real- Valued Functions
Definition 15 (Weak Valued Learner). Let E be loss function. Let Y E [0, 11. 3 E () and H. C [0, 1|x For distribution Dx over X and true target function h² E H. we say that f. X + [0, 1] is (y, -wwak learner with respect to Dx and h", if
Pr [((f()), D-xx
7
33
"Since the edges in En are of finite length, first need map them the appropriate edges in E".
24

---

Following [HKS19], we define the weighted median as
Σ 1=1
anllys <vel
1
(yd. Mr: a1,............................. QT) min
Øj
<
Ei=1 a1
and the weighted quantiles, for 0 (0,1/2),e)) as
T Vjj
_1=1 a <Veel
1
Q (y1..... Mri a1...., aT) min
0
2
-1=1 ardly, > yel
1 0
Qø (11, .. Mri ,..,,)a.. aT) max 1/j
Σ Ot
2
and
let (x)
Q (2)) y.... (n... Q7 (2)
Q7 (z)..., (x);; a....... aT), where his.... lo,, at,,a,, ...,.., or are the values returned
by Algorithm 2. The following guarantee holds for this procedure.
Lemma (MedBoost guarantee [Kég03]). Let be the absolute loss and S {(x,, ) ( log(m)). Let h1, .h...., hyp and Ogr...,, Our be the functions and coefficients returned from Meoso For any i (1,...,,. .m it holds that
max e (Q0r)((t)) ( (((07)201)))11) S7.
Algorithm 2 MedBoost [Kég03]
Input: S [(x;,, y:))
Parameters: 7, 3, Initialize P. = Uniform(SS)
For t = ,..
1. Find (y,33)-wakk learner he with respect to (Iz Us) ~ Pt, using a subset S, S S.
2. For i = 1,..., m..
(a) Set w (()
(1((( 3/) 7|.
(1-7) (1-7) Eis Pelors.))) 10! 11
(b) Set ai = 2 log
(1+)) E:= Pe( 10!
(c) If 04 oo: return T copies of his (an 1,....,00 or 1), and S.. Pi (x))ex((-arp /Ze. where Z.
Else: Pi+ ( Vi)
Σ Pa( Uj) exp exp(-aru)))
Output: Functions h1,..., lr, coefficients 01,,..,, or and sets Si,....,Sp ST
C.2.3 Generalization via Sample Compression Schemes
Sample compression scheme a classic technique for proving generalization bounds, introduced by [LW86, FW95]. These bounds proved to be useful in numerous learning settings, such as binary classification [GHSTO5, MY16, BHMZ200, multiclass classification [DSBDSS15, DSS14, DMY16, BCD-22] 22], regression [HKS18, 18, HKS19], active learning [WHEY15], density estimation [ABDH+20]. adversarially robust learning [MHS19, MHS20, MHS21, MHS22, AHM22, AH22], learning with partial concepts [AHHM22], and showing Bayes-consistency for nearest-neighhor methods [GKN14, KSW17J. As a matter of fact, compressibility and lcarnability are known to be equivalent for general learning problems [DMY16]. Another remarkable result by [MY16] showed that VC classes enjoy a sample compression that is independent of the sample size.
We start with formal definition of sample compression scheme.
Definition 16 (Sample compression scheme). A pair of functions (K. is a sample compression scheme of size & for class H if for any E N, h E H and sample S= {(x, h(xx)))= holds for the compression function that K (S) C S and 1K (S) < E, and the reconstruction function (K (S)) h satisfies h(xx)) h(xx)) for any E [n].
25

---

We show a generalization bound that scales with the sample compression size. The proof follows from [LW86].
Lemma 10 (Sample compression scheme generalization bound). Fix margin Y E [0,, 1]. For any k E N and fixed function & (X' x [0, 1)) + [0, 1|x, for any distribution 'D over X x [0, 1] and any m N. for S ( ys) he(m) Lid. D-distributed random variables, if there exist indices i1, ... di E [m]] such that E (awyes I (((((((zi) : "..,, (Fis Via (z), y) > 7 0, then
1 [ Uer), ..., (Ii Bie (2), 71l - m (a.
E
(k log m + log(1/))).
with probability at least - over S.
Proof. Let us define (h;
1s) Elawes [(((h(z),)) y) 7) and l,
(ay))D [U(((((z),)) v) > 7H. For any indices ú, is E [m]. the probability of the bad event
Pr (o(1,, vi.),... (De vw))): - ( (6, Vo,), (Ii Vie Bi:):: > el
SmDm
most
E v, > (r(,, Vi,
(( Mi, )E(())) 0f((21, Vi, ), Detal (1 m)
where the expectation is over (Ii, :0i,,9i,. Vi),, (Fig Via ) and the inner probability is over $ (Mig, Wi.).... (Fig )..) Taking a union bound over all m possible choices for the k indices, we get that the bad event occurs with probability at most
1 m k
n exp(-e(m k))= s =
(klog + log(1/8))
C.3 Putting Together
We now have all the necessary ingredients in place to prove the upper bound of Theorem 2. First, we use Lemma on a sample of size no = DOTG (H) to obtain learner which makes y-errors with probability at most 1/35. Then, we use the boosting algorithm we described (see Algorithm 2) to obtain learner that does not make any --mistakes
the training set. Notice that the boosting
algorithm on its own does not provide any guarantees about the generalization error of the procedure. This is obtained through the sample compression result we described in Appendix C.2.3. Since run the boosting algorithm for a few rounds on sample whose size is small, we can provide a sample compression scheme following the approach of [DMY16, 16, HKS19].
Lemma 11 (Upper Bound of PAC Regression). Let H S [0. 1]xt and E, E 10, Then,
DOIG (H) log
DOIG (H)
M(H;&, 8, S
log
E
Proof. Let n be the number of samples = ((z), 31) y1..... (Ins vn)) that are available to the learner, ni = [DOIG(H) and let A be the algorithm obtained from Lemma 8. We have that
Pr (())) ZNDx
>] 1/3.
S-D
This means that, for any distribution Dx and any labeling function h+ E H we can draw sample S* ((.1,1)),........... (Ino-1 1, Mno .)) with non-zero probability such that
1
Pr [(AA(S;))), > < 3 x~
In expectation the training set.
26

---

Notice that such classifier is a (y, 1/66)-well learner (see Definition 15), Thus, by executing the MedBoost algorithm (see Algorithm 2) for T (loggn rounds obtain a classifier h X IR such that, ((h(z)), y4) S 7, Vi E [n]. We underline that the subset St that is used in line of Algorithm 2 has size at most rag, for all rounds E [T]. Thus, the total number of samples that is used by MedBoost most (ng logn), n). Hence, following the approach of [MY16] we can encode the classifiers produced by MedBoost as a compression set that consists of k = O(1o log n) samples that were used train the classifiers along with & log & extra bits that indicate their order. Thus, using generalization based on sample compression scheme as in Lemma 10, we have that with probability least 1 over D
> (e(()()))))
C
E
(no log² log(1/6))
(r.y)>
n no log(n)
which means that for large enough n.
no log n H [((((()),)) >>>>>>>>>> > 5o
log(1/6)
E
(a.w)-
n
Thus,
no log*
log log(1/8)
((h(x).)) 7) so
(D
n
n
Hence, we can see that
DOIG (H)
DOIG (H)
M(HLE,,,,)
log
2
+
log
D DDD Dimension and Learnability
In this section, we will show that finiteness of y-DS dimension is necessary for PAC learning in the realizable case.
Theorem 3. Let H 1] 5,, (0, Then,
IDDS + log (1/0)
E
Proof. Let d= = DDG (H). Then, there exists some S = (f xa) E x' such that H|s contains a 27-pseudo-cube, which we call H'. By the definition of the scaled pseudo-cube, vh E H', i E [d], there is exactly one h H' such that h(zy) h hx,z),, # and (hh(r,). ((xx)) > 27, We pick the target function h* uniformly at random among the hypotheses of H. and we set the marginal distribution Dx of as follows
Pr[mi] = 2e, Pr(c:]=2e/(d-- 1),,
=
{,,...,.
d-1 Then, the sample Consider m samples {(2,, htt (z:)) drawn i.i.d. from D. Let take < 65-
will include at most (d 1)/2 examples which are not æ1 with probability 1 1/100, using Chernoff's bound. Let us call this event E. Conditioned on E, the posterior distribution of the unobserved points is uniform among the vertices of the d/ d/2-dimensionnl 27-pseudo-cube. Thus, if the test point æ falls among the unobserved points, the learner will make a 7-mistake with probability at least 1/2. To see that, let y be the prediction of the learner z. Since every hyperedge has size at least 2 and all the vertices that are on the hyperedge differ by at least 2y in the direction of x, no matter what is the correct label y" is at least ffar from it. Since Pr[E]= > 1/100, we can see that M (H;; 8, 7) 2( Moreover, by the law of total probability there must exist deterministic choice of the target function h², that could depend on A, which satisfies the lower bound. For the other part of the lower bound, notices the probability that the sample will only contain 21 is
27

---

(1-2e) 2 e- which is greater that ó whenever m I log((/6)/(4s). This implies that the y-cut-off sample complexity is lower bounded by
max (c ....c.............. log(1/6)
22 (H) + log(1/6)
Co
Thus MM(Hi; 6, 7), satisfies the desired bound when the dimension is finite. Finally, it remains to claim about the case where 22 (H) = oo for the given y. We consider a sequence of 2y-DS shattered sets S, with [.p = n and repeat the claim for the finite case. This will yield that for any the 7-cut-off sample complexity is lower bounded by SQ(n log(1/6))/e) and this yields that M(H::,,6,) oc.
We further conjecture that this dimension also sufficient for PAC learning. Conjecture 2. A class H S (0, 1)x is PAC learnable the realizable regression setting with respect to the absolute loss function if and only if TT (HH) < for any y E (0,1).
We believe that there must exist modification of the approach of [BCD+ 22] that will be helpful in settling the above conjecture. Conjecture 3. There exists H. S (0, x for which DN 1 forall y (0, but DD) < oo for some 1).
In particular, we believe that one can extend the construction of [BCD 22] (which uses various tools from algebraic topology as a black-box) and obtain a hypothesis class S [0, [] that has y-Natarajan dimension 1 but is not PAC learnable (it will have infinite 7-DS dimension). This construction though is not immediate and requires new ideas related to the works of [JS03, Osal3]
E
Online Realizable Regression
In this section, we present our results regarding online realizable regression. The next result resolves open question of [DG22]. It provides an online learner with optimal (off by factor of 2) cumulative loss realizable regression.
Theorem 4 (Optimal Cumulative Loss). Let H C [0, 1]x and > 0. Then, there exists deterministic algorithm (Algorithm 3) whose cumulative loss in the realizable setting is bounded by monl (H) + Conversely. for any >> 0, every deterministic al algorithm in the realizable setting incurs loss at least Donl (H)/2- -.
Algorithm 3 Scaled SOA
Parameters: {Et)EN Initialize (11) = H.
For f I,...
1. Receive E X.
2. For every y E [0, 1). let ()() (w).w) (h V(O) h(xx)) y)-
3. Let Dr be an arbitrary label such that
Donl (v(t)
2 sup Donl
(v(() ((eer))
Ex
4. Predict Tc-
5. Receive the true label oł and incur loss l()r. v²)-
6. Update ((++)) { E ((t,, h(x,) vi
Proof. Let us begin with the upper bound. Assume that Io)) < oo. Suppose we pre-
dicting the t-th point in the sequence and let (t) be the version space so far, i.c. y(t)
28

---

{ E H: WT E it 11,)((+)) y-) Let 24 be the next point to predict on. For each label R, let v-(t) (m. {h e v(O, h((r)) = y). From the definition of the dimension monl, we know that for ((t)
all y,y E R such that (mx.))) (#..v' + 0.
Do (V*) Ely. v/) + min ( DDon ((mee))) Donl (v((t) ((oear))
Let Vo be an arbitrary label with Tyoul (V(ss, (a.,0e) 2 supy Moat (v(() (z..0/)) - Et. where &, some sequence shrinking arbitrarily quickly in the number of rounds t. The learner predicts Yt. Assume
that the adversary picks yt as the true label and, so, the learner incurs loss E(Ti, ut) at round Then, the updated version space
Vit) ((..977
has
Donl (vlo) ((e..i1) I sup 1onll (v(e) ((e.)))
(v (2n.2)) Ee
which implies
min Donl (v/(t) TDonl (v(2) } Dool (v((2 (olue))
This gives that
nonl (v(1) 2 ((T.. vf) + min (Doul (v/C)) (ar.80) Donl (v/t) ((s.07)) }
2 E(Tr, v + Donl (v(e) (V(o.18)) Ec
and, by re-arranging,
Dinl (v(() (().0t)) < (Vol((()))) ((tr Se.
(1)
So every round reduces the dimension by at least the magnitude of the loss (minus et). Notice that Doal (V(++1)) = Doul (v(t))., Thus, by choosing the {Et)EE sequence such that
Σ e Se,
and summing up Equation (1) over all / E N, we get cumulative loss bound
I e vt) < Monl (H) +
Hence, we that by taking the limit E' goes to 0 shows that the cumulative loss is upper bounded by (H)). This analysis shows that Algorithm achieves the cumulative loss bound Tooal (H) + s', for arbitrarily small e > O.
Let us continue with the lower bound. For any >> 0, we are going to prove that any deterministic learner must incur cumulative loss at least [non (H)/2 By the definition of [)en((H) for any e > 0, there exists tree T3 such that, for every path y.
Yusi 2 Monl (H) 2
i.e. the sum of the gaps across the path is at least Moal (H) 2s. The strategy of the adversary is the following: in the first round, she presents the learner with the instance Iι = zp. Then, no matter what label ý1 the learner picks, the adversary can choose the label yf so that Ó vřl 2 78 /2. The adversary can keep picking the instances 2; based on the induced path the choices of the true labels {v: brrr and the loss of the learner in every round is at least / /2. Thus, summing up all the rounds as + oc, we see that the total loss of the learner is at least
Donl (HL)
E.
2
29

---

Remark 2 (Randomized Online Learners). We highlight that, unlike the setting of realizable online classification, in the case of realizable online regression randomization does not seem to help the learner (see also [FHIM23]]. In particular, the lower bound of D (H))
holds even for randomized learners. To see it, notice that for all distributions over D over [0, 1] it holds that
2
max
E R-D
(e(e((),)),, E cal1] 2 __ 02)1,
Example 2 (Sequential Complexity Measures). Sequential fat-shattering dimension and sequen- tial covering numbers are two standard combinatorial measures for regression in online settings [RSTI5b, RSTI5aJ. Note that Example I can be learned with I sample even in the online realizable setting. Hence, Example I shows that sequential fat-shattering dimension fails to characterize online realizable regression (since this dimension is at least as large as fat-shattering dimension which is infinite in this example). Moreover, we know that sequential covering numbers and sequential fat shatteritn dimension are of the same order of magnitude and they are also infinite in the case of Example I.
F Dimension and Finite Character Property
[BDHM*19 19] gave formal definition of the notion of "dimension" or "complexity measure", that all previously proposed dimensions in statistical learning theory comply with. In addition to characteriz- ing learnability, a dimension should satisfy the finite character property:
Definition 17 (Finite Character [BDHM 19]). dimension characterizing learnability can be abstracted as a function F that maps class H to N U {oo} } and satisfies the finite character property: for every d E and H. the statement "F(H) 2 d" can be demonstrated by a finite set X S X of domain points, and finite set of hypotheses H C H. That is, "F(H) 2 d" is equivalent to the existence of a bounded first order formula Φ(X, H) in which all the quantifiers are of the form: Ar E X, Vx E X or 3h E H. wh E H.
Claim 1. The scaled one-inclusion graph dimension DO (H) satisfies the finite character property.
Proof. To demonstrate that IDOIG (H) 2 d, it suffices to find set of n domain points and present a finite subgraph G (V, E) of the one-inclusion hypergraph induced by S where every orientation a: + V has out-degree at least n/3. Note that V is, by definition, a finite collection of datasets realizable by H. and so this means that we can demonstrate that DIG (H) 2 d with finite set of domain points and a finite set of hypotheses.
G Examples for Scaled Graph Dimension
These examples are adaptations from [DSS14, DSBDSS15].
Example 3 (Large Gap Between ERM Learners). For every d E N. consider domain Xa such that [Kal= = d and Na, Xx are disjoint for d + d'. For all d E N. let P(Xa) denote the collection of all finite and co-finite" subsets of Xa. Let us fix
(0, 1). Consider a mapping f UdENP (Xa) + E(7,1) for all d E N, As E P(Xa), and ((Aa) # [AAs) for all Aa + [0, 1] such that f(Aa) E
A/g, Ad E P(Ka), Ad E P.(x)). Such mapping exists due the density of the reals. For any d E N, S Xg. let (2) = f(A)) 1(x E Ast and consider the scaled first Cantor class Hxr,, = (hA, :Ad E P(Xa)}- We claim that TDNat (Hxar) = 1 and that DD (Hxx,)) Kal = since one can use fo for the graaph shattering. Consider the following two ERM learners for the scaled first Cantor class Hxa.7:
1. Whenever sample of the form S= (z;, (eh is observed, the first algorithm outputs bufas Keja) which minimizes the empirical error. If the sample contains non-zero element, the ERM learner identifies the correct hypothesis. The sample complexity of PAC learning is (dd).
2. The second algorithm either returns the all-zero function or identifies the correct hypothesis if the sample contains a non-zero label. This is a good ERM learner A JERM with sample complexity mls, 5) log (1)
good
A set S Xa co-finite if its complement S is finite.
30

---

The construction that illustrates the poor performance of the first learner is exactly the same as in the proof of the lower bound of Theorem The second part of the example is formally shown in Claim 2, which follows.
Claim 2 (Good ERM Learner). Let E, E (0, 1)2. Then, the good ERM learner of Example 3 has sample complexity M(e,8) = log (t).
Proof. Let d N, Dx, be distribution over Xa and ha; be the labeling function. Consider sample of length m. If the learner observes a value that is different from among the labels in S, then will be able to infer a and incur error. On the other hand, if the learner returns the all zero function its error can be bounded as
E Do
Pr | E AM z=Dxx
Since in all the m = 1 log (3) draws of the training set there were no elements from A we can that, with probability least 1 over the draws of 5 it holds that
Pr Dx
[x: E A c.
Thus, the algorithm satisfies the desired guarantees.
The next example shows that no proper algorithm can be optimal in the realizable regression setting.
Example 4 (No Optimal PAC Learner Can be Proper). Let Xa contain d elements and let v E (0. 1). Consider the subclass of the scaled first Cantor class (see Example 3) with H's, = {ha A P(Ka), |A| [- First, since this cluss is contained in the scaled first Cantor class, we can employ the good ERM and learn it. However, this learner is improper since he & H'd.r Then, proper al algorithm able to PAC learn H's., using o(d) examples.
Proof. Suppose that adversary chooses hA H',, uniformly random and consider the distribu- tion X. which is uniform the complement of A, where |A| (d)) Note that the of every hypothesis hB E H'd is at least B/ \ A/dd. Therefore, to return hypothesis with small error, the algorithm must recover a set that is almost disjoint from A and so recover A. However the size of A implies that it cannot be done with o(d) examples.
Formally, fix wo E Na and E (0, 1). Let C Xa> \ {2o} of size d/2. Let DA be a distribution with mass DA ((zo, h (xa))) =1 1 16e and is uniform on the points har, x E A*), where A the complement of (without .in).
Consider proper learning algorithm A. We will show that there is some so that when A run DA with Oddee), it outputs a hypothesis with error at least y with constant probability.
set A.
Pick A uniformly random from all sets of size d/2 of Xa \ {xo)- Let Z be the random variable that counts the number of samples in the m draws from DA that are not (Zo. ha Standard concentration bounds imply that with probability {mo}) A is at most d/4. Conditioning on this event, A is uniformly chosen random set of size d/2 that is chosen uniformly from all subsets of set X' C Xa with |X' 2 3d/4 (these points present in the sample). Now assume that the learner returns a hypothesis hg, where B is a subset of size d/2. Note that EllB B AI] 2 d/6. Hence there exists set A such that with probability 1/2, B \ A and the mass of each such point is ((e/d). Hence, in total, the learner will incur loss of order y s.
least 1/2, the number of points from (X,
holds that [B \ A 2 d/6. This means that A incurs a loss of at least y on all points in
H Extension to More General Loss Functions
Our results can be extended to loss functions that satisfy approximate pseudo-metre axioms (see e.g., [HKLM22, CKW0 The main difference from metric losses is that we allow an approximate triangle inequality instead of strict inequality, Many natural loss functions are captured by this definition, such as the well-studied Ep losses for the regression setting, Abstractly, in this context, the
31

---

label space" is an abstract non-empty set V equipped with general loss function é ) - R20 satisfying the following property.
Definition 18 (Approximate Pseudo-Metric). For 2 1, a loss function 8 : ) + R20 is approximate pseudo-metric (i) f(x, = 0 for any x E V. (ū) ((x, y) = fly, x) for any x, y E Y, and, (iii) & satisfies a c-approximate triangle inequality; for any y1 U2. ys V, it holds that Ely1. 92) 5 c(((y1, ys) + E(y22 93)).
Furthermore, note that all dimensions for H. DC DDGG (H)) mp (H), and Det (H) are defined for loss functions satisfying Definition 18.
Next, we provide extensions of our main results for approximate pseudo-metric losses and provide proof sketches for the extensions.
ERM Learnability for Approximate Pseudo-Metries. For ERM learnability and losses satisfying Definition 18, we can obtain the next result.
Theorem 5. Let E be a loss function satisfying Definition 18. Then for every class H C y² H is learnable by any ERM in the realizable PAC regression setting under if and only if D (H) < co for all y E (0, 1).
The proof of the upper bound and the lower bound follow in the exact same way with the absolute loss.
PAC Learnability for Approximate Pseudo-Metries. As for PAC learning with approximate pseudo-metris losses, we can derive the next statement.
Theorem 6. Let E be loss function satisfying Definition 18. Then every class H S yx is PAC learnable in the realizable PAC regression setting under E if and only if DD (H) < 00 for any 7 E 1).
Proof Sketch. We can generalize the upper bound in Theorem 2 for the scaled OIG dimension as follows. One of the ingredients of the proof for the absolute loss is to construct a sample compression scheme through the median boosting algorithm (cf. Algorithm 2). While the multiplicative update rule is defined for any loss function, the median aggregation is no longer the right aggregation for arbitrary (approximate) pseudo-metrics. However, for each such loss function, there exists an aggregation such that the output value of the ensemble is within some cutoff value from the true label for each example in the training set, which means that we have sample compression scheme for some cutoff loss. In particular, we show that by using weak Iearners with cutoff parameter 7/ (2c). where is the approximation level of the triangle inequality, the aggregation of the base learners can be expressed as a sample compression scheme for cutoff loss with parameter 7y.
Indeed, running the boosting algorithm with (7/(2c), 1/6)-weak learners yields set hy..... hy of weak predictors, with the property that for each training example (z,,y,, at least 2/3 of the functions h;; (as weighted by coefficients a;), 1 < < N, satisfy {(h:(z), v) I 7/(2)) For any x, let h(x)) be value in y such that least 2/3 of h2 (as weighted by az), 1 S N, satisfy ((,,(x),(()) h(z)) I (2c),, if such a value exists, and otherwise h(z)) is an arbitrary value in V. In particular, note that on the training examples (z, y). the label y satisfies this property, and hence h(x) is defined by the first case. Thus, for any training example, there exists h; (indeed, at least 2/3 of them) such that both ((h(()).)) v) S (2c) and E(h,(x), h(x)) S (2c) are satisfied, and therefore
we have
{((()),)) < c(((h(z), + E(ha(=), v)) Sn
This function can be expressed as a sample compression scheme of size O ODOIG (H) log(m) 7/(2))
for cutoff loss with parameter 7: namely, it is purely defined by the h2 functions, where each h2
Wee would like to mention that, in general, we do not require that the label space bounded. In contrast, we have to assume that the loss function takes values in bounded space. This is actually necessary since having an unbounded loss in the regression task would potentially make the learning task impossible. For instance, having some fixed accuracy goal, one could construct learning instance (distribution over labeled examples) that would make estimation with that level of accuracy trivially impossible.
32

---

specified by O ( (H) training examples, and we have N (m)) such functions, and f (26))
satisfies (((()). y) S for all training examples (x, v). Thus, by standard generalization bounds for sample compression, we get an upper bound that scales with Ô (DOIG 2/(e)) (H) m) for the cutoff
loss with parameter ",, and hence by Markov's inequality, an upper bound
E(((h(o) Ö - (17 (H) |TT))
We next deal with the lower bound. For the absolute loss, we scale the dimension by 27 instead of since for any two possible labels 11 3/ the learner can predict some intermediate point, and we want to make sure that the prediction will be either far from 8/1 For an approximate pseudo-metric we should take instead 2cy in order ensure that the prediction is y far, which means that the lower bounds in Theorem 2 hold with scale of 20%..
Online Learnability for Approximate Pseudo-Metrics. Finally, we present the more general statement for online learning.
Theorem 7. Let l be loss function satisfying Definition 18 with parameter e 2 1. Let H C y and > O. Then, there exists deterministic algorithm whose cumulative loss in the realizable setting bounded by De (H) + E. Conversely, for any > O, every deterministic algorithm in the realizable setting incurs loss at least Thol (2) -
Proof Sketch. The upper bound of Theorem 4 works for any loss function. Recall the proof idea; in every round there is some Th E y the learner can predict such that no matter what the adversary picks the true label yr, the online dimension of the version space round i.e, V {h E H. h(zr) = Vテ, S т S t}. decreases by E(y," Vt), minus some shrinking number et that we can choose as parameter. Therefore we get that the sum of losses is bounded by the online dimension and the sum of e, that we can choose to be arbitrarily small.
The lower bound for online learning in Theorem 4 would be (To) c, for any 0, since the adversary can force a loss of /ygs/ in every round f, where TuSt is the sum of the gaps across the path y.
33


Reviews:
[{"review_id": "ep3w2yz2kq", "reviewer": "Reviewer_seAb", "summary": "This paper provides combinatorial dimensions that characterize realizable regression in both batch as well as online settings. Moreover, it provides minimax optimal learner up to polylog factor in the batch setting and minimax optimal learner in the online setting. ", "questions": "I assume that fat-shattering dimension upper bounds the OIG based dimension proposed here. Is there a combinatorial proof of this fact? Also, is there a general property of the class that guarantees that the finiteness of OIG based dimension and fat-shattering dimension co-incide? \n\n", "limitations": "N/A\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written, easy to follow, and solves an important open problem of characterizing realizable learnability for real-valued function classes. \n2. The paper uses classical ideas such as Median Boosting algorithm, sample compression schemes as well as some recent developments in PAC learning theory such as partial concept classes, OIG based dimensions, etc. Overall, the paper is technically sound and is definitely an important technical contribution to the field. \n3. In online setting, the paper introduces a novel idea of summing scales along each branch of the tree and defining dimension as the sum of scales. This is a novel and useful technical tool as it provides a new way of defining dimensions that are not parametrized by a scale even though some form of scale is inherent to the problem setting. ", "weaknesses": "Although the paper does provide a combinatorial characterization of realizable regression, I am not sure if the OIG-based dimension is very insightful. Theoretically, it is a useful abstraction as it has a finite-character property and thus the learnability of the problem can, at least technically, be determined using finitely many domain points and functions in function classes. However, the practical utility of such dimension is questionable. Can be computed for natural classes such a linear classes, Lipschitz classes, and so forth? Computing upper bounds is generally difficult even for classical dimensions like VC and fat-shattering, but the lower bounds of these dimensions are typically easy to compute for some natural classes because of simplicity of their shattering conditions. Is it also the case for this OIG based dimension?\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the positive feedback and insightful questions.\n\n> *Although the paper does provide a combinatorial characterization of realizable regression, I am not sure if the OIG-based dimension is very insightful. Theoretically, it is a useful abstraction as it has a finite-character property and thus the learnability of the problem can, at least technically, be determined using finitely many domain points and functions in function classes. However, the practical utility of such dimension is questionable. Can be computed for natural classes such a linear classes, Lipschitz classes, and so forth? Computing upper bounds is generally difficult even for classical dimensions like VC and fat-shattering, but the lower bounds of these dimensions are typically easy to compute for some natural classes because of simplicity of their shattering conditions. Is it also the case for this OIG based dimension?*\n\nIn general, we believe that it is difficult to compute the $\\gamma$-OIG dimension. Nevertheless, $\\gamma$-OIG dimension is the first complexity measure that tightly characterizes realizable regression. More to that, we propose the much more combinatorial $\\gamma$-DS dimension which we conjecture to be the right dimension for this setting. As the reviewer suggests, it would be interesting to compute the OIG-based complexity measure for natural and useful complexity classes. For instance, for the class of linear functions $f(x) = a \\cdot x$, when the features are single-dimensional then $\\mathbb{D}^{\\mathrm{OIG}}_\\gamma = 1$ (one sample suffices; each hyperedge of the OIG is a single hypothesis) and the OIG dimension scales with the dimension of the feature space in higher dimensions. Similar analysis can be done for the affine case. Deriving bounds for other families of functions is an important yet non-trivial question.\n\n> *I assume that fat-shattering dimension upper bounds the OIG based dimension proposed here. Is there a combinatorial proof of this fact? Also, is there a general property of the class that guarantees that the finiteness of OIG based dimension and fat-shattering dimension coincide?*\n\nThe work of Mandelson (2002) provides a sufficient and natural condition that implies finiteness of both measures. In particular, Section 5 of this work shows that classes that contain functions with bounded oscillation (as defined in the aforementioned paper) have finite fat-shattering dimension. This implies that the class is learnable in the agnostic setting and hence is also learnable in the realizable setting. As a result, the OIG-based dimension is also finite. So, bounded oscillations are a general property that guarantees that the finiteness of OIG-based dimension and fat-shattering dimension coincide. For the first part of the question, we are not familiar with a combinatorial proof of this statement. Investigating such connections would be an interesting direction for future work.\n\n[Mandelson, Improving the Sample Complexity Using Global Data, 2002]\n"}, {"review_id": "x659SAdBiD", "reviewer": "Reviewer_EXPx", "summary": "This work analyzes the realizable regression and connects it with several notions of dimensions. They care about the online learning and the PAC learning. They first show that the $\\gamma$-OIG dimension characterizes the PAC learning and that PAC learning requires finite $\\gamma$-DS. Finally, they show that for the online regression, the authors find a dimension that characterize it. They show that this dimension is an upper bound over the cumulative loss and it is a lower bound up to some constant.", "questions": "The question in the weaknesses section.", "limitations": "no limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": " The paper provides complexity results for regression in online learning and PAC learning. In binary classification, we have a better understanding of the complexity and how different dimensions connect. In the regression setting, we do not know a lot and this paper provides a very good understanding and nice results. The paper is well written and explains the previous work well. ", "weaknesses": "Not a weakness, but can the authors explain why is there a requirement for bounded labels? What happens if the labels are not bounded?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the positive feedback regarding the importance and the clarity of our results.\n\n\n> *Not a weakness, but can the authors explain why is there a requirement for bounded labels? What happens if the labels are not bounded?*\n\nWe would like to mention that, in general, we do not require that the label space is bounded. In contrast, we have to assume that the loss function takes values in a bounded space. This is actually necessary since having an unbounded loss in the regression task would potentially make the learning task impossible. For instance, having some fixed accuracy goal, one could construct a learning instance (distribution over labeled examples) that would make estimation with that level of accuracy trivially impossible. We will clarify this point in the first revision of our work."}, {"review_id": "2WCmAPZqUs", "reviewer": "Reviewer_DqR8", "summary": "This paper introduce some dimensions that characterize PAC learnability for realizable regression. The authors introduce $\\gamma-$ Graph dimenion which is necessary and sufficient for PAC learnability by ERM, and $\\gamma-$OIG dimension which is necessary and sufficient for PAC learnability. $\\gamma-$DS dimension is introduced which is necessary and conjectured to be sufficient. There are also results for online learning.", "questions": "Line 263, is there some typo? maybe you dont mean $\\forall i$.", "limitations": "None", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "PAC learnability for realizable regression is characterized by an appropriate dimension. This seems to be an important open problem that is resolved.", "weaknesses": "The various dimensions are hard to understand. It would be nice to see examples. For instance, lines 188-192 were not particularly helpful to understand Definition 5, since I am not sure what it means for $\\mathcal{H}$ to contain a cube. Do you mean there is a hypercube of a certain size embedded in every function in $\\mathcal{H}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the positive and insightful feedback and questions.\n\n> *The various dimensions are hard to understand. It would be nice to see examples. For instance, lines 188-192 were not particularly helpful to understand Definition 5, since I am not sure what it means for H  to contain a cube. Do you mean there is a hypercube of a certain size embedded in every function in  H ?*\n\nLet us first give some intuition behind the definition of the fat-shattering and $\\gamma$-Natarajan dimensions. The other dimensions follow in a similar manner. The crucial idea is to understand what it means to shatter a set of points in each definition. Then the associated dimension is the maximum size of a set shattered by the hypothesis class.\n\nFat-shattering dimension is a natural way to quantify how well the function class can interpolate (with gap $\\gamma$) some fixed function. Crucially this interpolation contains only inequalities (see Definition 4) and hence (at least intuitively) cannot be tight for the realizable setting, where there exists some function that exactly labels the features. Example 1 gives a natural example of a class with infinite fat-shattering dimension but which can be learned with a single sample in the realizable setting.\n\nBefore explaining the $\\gamma$-Natarajan dimension, let us begin with the definition of the standard Natarajan dimension [Natarajan, 1989]. We say that a set $S = \\\\{x_1,...,x_n\\\\}$ of size $n$ is Natarajan-shattered by a concept class $H \\subseteq \\mathcal{Y}^\\mathcal{X}$ if there exist two functions $f,g : S \\to \\mathcal{Y}$ so that $f(i) \\neq g(i)$ for any $i \\in S$ and\nfor any $b \\in \\\\{0,1\\\\}^n$ there exists $h \\in H$ such that\n$h(x_i) = f(x_i)$ if $b_i = 1$ and\n$h(x_i) = g(x_i)$ if $b_i = 0.$ Note that here we have equalities instead of inequalities (recall the fat-shattering case).\n\nFrom a geometric perspective (see [Brukhim et al., 2022]), this means that the space $H$ projected on the set $S$ contains the set\n$ \\\\{ f(x_1), g(x_1)\\\\} \\times … \\\\{ f(x_n), g(x_n) \\\\} $.\nThis set is \"isomorphic\" to the Boolean hypercube of size $n$ by mapping $f(x_i)$ to 1 and $g(x_i)$ to 0 for any $i \\in [n]$.\nThis means that the Natarajan dimension is essentially the size of the largest Boolean cube contained in $H$.\n\nThe $\\gamma$-Natarajan dimension is the scaled version of the above definition. The only modification is that the two functions $f,g$ map $S$ to $[0,1]$ and we require that not only $f$ and $g$ are everywhere different but we have that the distance between $f(x_i)$ and $g(x_i)$ is at least $\\gamma$. Nevertheless, the geometric perspective is still the same: $\\gamma$-Natarajan dimension is the size of the largest Boolean cube contained in $H$. This is what we mean after Definition 5.\n\nExamples 3 and 4 contain some examples computing $\\gamma$-Graph and Natarajan dimensions. Adding more intuitive examples is an important direction for future revisions. \n\nWe will make the above discussion more clear in the first revision of our work.\n\n\n> *Line 263, is there some typo? maybe you dont mean \\forall i*\n\nThis is indeed a typo, thanks for bringing it up. We meant to say $\\forall j \\in [n] \\setminus \\{ i \\}$, not $\\forall i, j$. We will fix it in the next version of our draft.\n"}, {"review_id": "DTc1wWEZWe", "reviewer": "Reviewer_dt9f", "summary": "This paper develops optimal learners and characterizes learnability with new combinatorial dimensions for realizable regression (where the best predictor has zero regret) in PAC and online learning, significantly depicting the landscape of learnability in PAC/online learning. \n\nFor PAC learning, they show that: \n- the PAC learnability in the realizable regression by a worst-case ERM iff the gamma graph dimension is finite \n- learnability in the realizable regression is fully characterized by a finite gamma One-Inclusion dimension \n- finite gamma-DS dimension is a necessary condition for PAC learnability in the realizable regression \n\nFor online learning, they devise a new combinatorial dimension, namely online dimension that is built up on the scaled Littlestone dimension. They show that the online dimension characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner. ", "questions": "N/A", "limitations": "The paper might need to discuss the limitations of the results and analysis. ", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Significant results that complete the landscape of learnability of PAC/online learning in realizability regression \n", "weaknesses": "- None that I know (note that this problem area is not my research domain)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the positive feedback on the significance of our results.\n\n> *The paper might need to discuss the limitations of the results and analysis.*\n\nWe believe that the main limitation of our work is that the OIG-based dimension we propose is more complicated than the dimensions that have been proposed in the past, like the fat-shattering dimension (which, as we explain, does not characterize learnability in the realizable regression setting). Nevertheless, despite its complexity, this is the first dimension that characterizes learnability in the realizable regression setting. More to that, our work leaves as an important next step is to prove (or disprove) our conjecture that the (combinatorial and simpler) $\\gamma$-DS dimension is qualitatively equivalent to the $\\gamma$-OIG dimension. We will add a discussion on the limitations in the first revision of our manuscript.\n"}, {"review_id": "TZapZtXa5G", "reviewer": "Reviewer_JHXn", "summary": "This paper studies the statistical complexity of realizable regression in the PAC learning and online learning setups. The main results are the following combinatorial conditions that characterize the PAC and online learnability:\n- PAC learnability by (worst-case) ERM learner is equivalent to having a finite $\\gamma$-graph dimension for all $\\gamma \\in (0, 1)$.\n- PAC learnability is equivalent to the finiteness of $\\gamma$-one-inclusion graph dimension for all $\\gamma \\in (0, 1)$.\n- The minimax cumulative loss in online learning is characterized (up to a constant factor) by the online dimension.\nThe combinatorial dimensions are above are newly introduced in the paper. The authors also conjectured that the DS dimension in the literature also characterizes PAC learnability.\n\nIn addition, the paper provides several other examples that shed light on the landscape between learnability, uniform convergence, and other complexity measures of the hypothesis class (Figure 1).", "questions": "Regarding Conjecture 1:\n- Could you elaborate on the obstacle that prevents the approach of [BCD+22] to be applied towards the regression setting?\n- Are there any evidence/heuristic arguments that support the conjecture? Are there interesting assumptions under which finite $\\gamma$-DS dimension implies learnability?", "limitations": "This is a theory paper and its limitations lie in the assumptions on which the validity of the results rely, including the realizability assumption and the focus on PAC and online learning. This has been formally stated in the paper, and also explicitly mentioned in the title and abstract.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper studies a fundamental problem in learning theory, which has, surprisingly, been left open for several decades. The results are strong and comprehensive, and the authors did a great job in introducing the prior results and presenting the high-level roadmaps behind the technical proofs.", "weaknesses": "My only complaint is on the short conclusion and a lack of discussion on future directions (apart from the obvious one of proving Conjecture 1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the positive feedback on the significance and presentation of our results and the interesting questions and suggestions.\n\n> *My only complaint is on the short conclusion and a lack of discussion on future directions (apart from the obvious one of proving Conjecture 1).*\n\nIn the next version of our draft, we will include a more detailed conclusion section where we will summarize the main contributions of our work and the important next steps. Another future direction, that is not directly related to Conjecture 1, is  to better understand the gap between the fat-shattering dimension and the OIG-based dimension. In particular, it would be interesting to come up with examples of ``natural’’ hypothesis classes, other than the one we provide in Example 1, which witness the fact that the fat-shattering dimension does not characterize learnability.\n\n>*Could you elaborate on the obstacle that prevents the approach of [BCD+22] to be applied towards the regression setting?*\n\nIn [Brukhim et al., 2022], the authors start by showing that if the DS dimension of $H$ is bounded by $d$, then using the OIG algorithm they can derive a learner that has error at most $d/(d+1)$. Notice that this learner is very weak, but has non-trivial guarantees. Subsequently, they use non-trivial arguments that go through list-PAC learning and sample-compression schemes to boost this very weak learner. This step is crucial for the multiclass setting since it reduces nontrivially the infinite label space. However, in the realizable regression setting, it is trivial to derive a learner that has error at most $1/2$. Indeed, if we focus on the $\\ell_1$ loss and $Y = [0,1]$, by always predicting $1/2$ we can design such a learner. To the best of our knowledge, using the definition of the $\\gamma$-DS dimension in a similar way as in [Brukhim et al., 2022] does not result in a non-trivial learner in the regression setting. This is the main and crucial difference between classification and regression. \n\n>*Are there any evidence/heuristic arguments that support the conjecture? Are there interesting assumptions under which finite  gamma-DS dimension implies learnability?*\n\nLet us first elaborate on the connection between OIG and the DS dimension. We will focus on the multiclass setting, studied in  [Brukhim et al., 2022]. Our Conjecture 1 essentially claims that this connection extends to the realizable regression task. Interestingly, there is some notion of “duality” between one-inclusion graph algorithms and pseudo-cubes (the combinatorial objects that define the DS dimension). In particular, Lemmas 12 and 13 in [Brukhim et al. 2022] show that there is a certain duality between orientations of OIG and the DS dimension. In particular, let us consider a class $H$ with DS dimension $d$. Then intuitively even if the algorithm is given $d$ labeled examples, then any orientation of the OIG will have large out-degree (which means that it will be a bad learner). More to that, if the algorithm is given $d+1$ labeled examples, then there exists a good orientation (one with small out-degree) which implies the existence of a good learner. These intuitive statements shed light to the connection between the DS dimension and learnability through the OIG structure. \n\nDeriving sufficient conditions is actually an interesting question for future work, and probably easier than proving the conjecture to its full extent. The reason we believe it is true is that, similar to the multiclass classification problem, the $\\gamma$-DS dimension feels more ``natural’’ than the dimensions that have been proposed in the past, and seems to be capturing the learnability problem in a tighter way. Moreover, its definition is closely related to the outdegree of the OIG (as we discussed in the previous paragraphs), which, as we have shown, is the quantity that controls learnability in this setting. "}]

Author rebuttal:

Meta-review: This paper solves an open problem in the learning theory community that is of fundamental importance (i.e. the statistical complexity of realizable regression in both the PAC setting and the online setting), and both introduces novel conceptual quantities and techniques. All reviewers are very enthusiastic about the paper's contributions and supportive of an oral presentation.
Decision: Accept (oral)