Introduction

Russo and Van Roy [37] introduced the notion of eluder dimension for a function class and used it to analyze algorithms (based on the Upper Confidence Bound (UCB) and Thompson Sampling paradigms) for the multi-armed bandit problem with function approximation. Since then, eluder dimension has been extensively used to construct and analyze the regret of algorithms for contextual bandits and reinforcement learning (RL) with function approximation [see, e.g., 46,36,44,6,14,19,12,16,26,24]. Even though the eluder dimension has become a central technique for reinforcement learning theory, little is known about when exactly it is bounded. This paper makes progress toward filling this gap in our knowledge.

Russo and Van Roy [37] established upper bounds on eluder dimension for (i) function classes for which inputs have finite cardinality (the "tabular" setting), (ii) linear functions over R d of bounded norm, and (iii) generalized linear functions over R d of bounded norm, with any activation that has derivatives bounded away from 0. Apart from these function classes (and those that can be embedded into these), understanding of eluder dimension has been limited. Indeed, one might wonder whether a function class has "small" eluder dimension only if it can be realized as a class of (generalized) linear functions! This leads us to our first motivating question: Question 1. Are all function classes with small eluder dimension essentially generalized linear models?

Answering this question has substantial ramifications on the scope of prior work. An answer of "yes" would imply that the results in the aforementioned work which gives regret guarantees in terms of eluder dimension do not go beyond already-established regret guarantees for generalized linear bandit or RL settings [see, e.g. 17,32,45,31]. An answer of "no" can be construed as a positive result for RL theory, as it would indicate that existing (and future) results which use the eluder dimension apply to a richer set of function classes than generalized linear models.

To answer Question 1, we first formally define what it means for a function class to be written as a generalized linear model (GLM). Informally, for an activation σ : R → R and a function class F ⊆ (X → R), we define the σ-rank to be the smallest dimension d needed to express every function in F as a generalized linear function in R d with activation σ (see Definition 3). Intuitively, the σ-rank captures the best possible upper bound on eluder dimension that the results from Russo and Van Roy [37] can give for a given F by treating it as a GLM with activation σ. We ask how the eluder dimension of any function class relates to its σ-rank for various activations σ. We show that the answer to Question 1 is indeed "no", i.e., there exists a function class with eluder dimension d but the σ-rank for any monotone σ is at least exp(Ω(d)). Thus, while Russo and Van Roy [37] show that the set of function classes with small eluder dimension is a superset of the set of GLM function classes, we (roughly speaking) show that the set of function classes with small eluder dimension is strictly larger than the set of GLM function classes.

We also prove that the requirement from Russo and Van Roy [37] that the derivative of the activation is bounded away from 0 is necessary in order to bound the eluder dimension of GLMs. The upper bound in the paper [37] becomes vacuous when the activation function has zero derivative; we show a lower bound which indicates this requirement cannot be dropped. Namely, when σ is the relu activation, we show that eluder dimension can be exponentially larger than σ-rank.

In a second line of inquiry, we study a combinatorial version of eluder dimension. The original definition of Russo and Van Roy [37] is defined for real-valued function classes, but one can specialize the definition to binary-valued function classes, leading to a so-called combinatorial eluder dimension. Thus, our second motivating question is: Question 2. Can we bound the combinatorial eluder dimension, perhaps in terms of more familiar learning-theoretic quantities?

One might wonder: if the combinatorial eluder dimension is just a special case of the scale-sensitive version, why study it at all? Our reasons are threefold.

• The first and most immediate reason is that we are able to show new characterizations of eluder dimension once we move to the combinatorial definition. We elucidate a fundamental connection between eluder dimension and two other well-studied learning-theoretic quantities: (1) star number, a quantity that characterizes the label complexity of pool-based active learning [21], (2) threshold dimension, a quantity that characterizes the regret of online learning [3]. 1 We believe that this new result may help us better understand how different learning tasks relate to each other.

• The second reason is that the combinatorial eluder dimension (or a multi-class variant of it) has already been studied for policy-based learning for contextual bandits and RL [see, e.g., 19,34]. Thus, understanding the combinatorial eluder dimension may shed light on the challenges of policy-based RL.

• Our last reason has more philosophical bent. Historically, the discovery of VC dimension placed statistical learning theory on solid footing. Specifically, the fundamental theorem of statistical learning allows us to precisely characterize the statistical complexity of PAC learnability in terms of the combinatorial VC dimension. The insights from understanding the role of VC dimension in classification have led researchers to develop scale-sensitive complexity measures such as fat shattering dimension to provide sharper guarantees on learning. While we do not claim that the eluder dimension is fundamental to online RL and bandit settings, we believe that a better combinatorial understanding can lead to a better understanding of online decision making. In some sense, we are "working backwards" from the original scale-sensitive definition of eluder dimension to understand its combinatorial properties.

Main contributions

In this work, we provide several results which show when eluder dimension can be bounded (or is unbounded). Our results can be separated into two categories: (1) those pertaining to the (scalesensitive) eluder dimension (as originally defined by Russo and Van Roy [37]); (2) those pertaining to the combinatorial eluder dimension, defined for binary-valued function classes.

First, we investigate the relationship between eluder dimension and our notion of generalized rank that captures the realizability of any function class as a GLM. In Section 2, we formally introduce the eluder dimension (as well as a related quantity of the scale-sensitive star number). In Section 3, we formalize the notion of "generalized rank". In Section 4, we provide several results.

1. We show that eluder dimension can be exponentially smaller than σ-rank for any monotone activation σ, not just those with derivatives bounded away from 0 (Theorem 6). 2. We show that the condition on the derivative being bounded away from 0 is necessary for σ-rank to be an upper bound on eluder dimension. Namely, when σ is the relu activation, we show that eluder dimension can be exponentially larger than σ-rank (Theorem 7). 2In Section 5, we specialize the eluder dimension to the binary-valued setting and present our results on the combinatorial eluder dimension.

1. We show that eluder dimension is finite if and only if both star number and threshold dimension are finite. Specifically, in Theorem 8 we show the following:

Furthermore, we demonstrate that both inequalities can be tight (see Theorem 9 and discussion above it). 2. We investigate the comparison between eluder dimension and sign-rk and prove stronger separations than in the scale-sensitive case; namely we show examples where one quantity is finite while the other is infinite (Theorem 10).

Related work

In this section, we highlight several related works.

Bounds on eluder dimension. Several papers provide bounds on eluder dimension for various function classes. The original bounds on tabular, linear, and generalized linear functions were proved by Russo and Van Roy [37] (and later generalized by Osband and Van Roy [36]). Mou et al. [34] provide several bounds for the combinatorial eluder dimension, mostly focusing on linear function classes. When the function class lies in an RKHS, Huang et al. [25] show that the eluder dimension is equivalent to the notion of information gain [41,38], which can be seen as an infinite dimensional generalization of the fact that the eluder dimension for linear functions over R d is Θ(d). In concurrent work, Dong et al. [12] also prove an exponential lower bound on the eluder dimension for ReLU networks.

Applications of eluder dimension. The main application of the eluder dimension is to design algorithms and prove regret guarantees for contextual bandits and reinforcement learning. A few examples include the papers [46,36,44,6,14,19,28,16,26,24,34]. While the majority of papers prove upper bounds via eluder dimension, Foster et al. [19] provided lower bounds for contextual bandits in terms of eluder dimension, if one is hoping for instance-dependent regret bounds. In addition, several works observe that eluder dimension sometimes does not characterize the sample complexity, as the guarantee via eluder dimension can be too loose [23,20]. Beyond the online RL setting, eluder dimension has been applied to risk sensitive RL [15], Markov games [24,29], representation learning [47], and active online learning [10].

Other complexity measures for RL. We also touch upon other complexity measures which have been suggested for RL. One category is Bellman/Witness rank approach [see e.g. 27,11,42], which is generalized to bilinear classes [13]. These complexity measures capture an interplay between the MDP dynamics and the function approximator class; in contrast, eluder dimension is purely a property of the function approximator class and can be stated (and studied) without referring to an online RL problem. Jin et al. [28] define a Bellman-Eluder dimension which captures function classes which have small Bellman rank or eluder dimension. Lastly, Foster et al. [20] propose a Decision-Estimation Coefficient and prove that it is necessary and sufficient for sample-efficient interactive learning.

Notions of rank. The notion of rank we propose is a generalization of the classical notion of sign rank, also called dimension complexity. Sign rank has been studied extensively in combinatorics, learning theory, and communication complexity [see e.g. 1, 18, 5, 2, and references therein]. The norm requirements in our definition of σ-rank are related to the notion of margin complexity [5,7,30].

Eluder dimension and star number

Eluder dimension is a "sequential" notion of complexity for function classes, originally defined by Russo and Van Roy [37]. Informally speaking, it characterizes the longest sequence of adversarially chosen points one must observe in order to accurately estimate the function value at any other point. We consider a variant of the original definition, proposed by Foster et al. [19], that is never larger and is sufficient to analyze all the applications of eluder dimension in literature.

Definition 1. For any function class F ⊆ (X → R), f ∈ F, and scale ε ≥ 0, the exact eluder dimension Edim f (F, ε) is the largest m such that there exists (x 1 , f 1 ), . . . , (x m , f m ) ∈ X × F satisfying for all i ∈ [m]:

Then for all ε > 0:

This definition is never larger than the original definition of Russo and Van Roy [37], which asks for a witnessing pair of functions f i , f i ∈ F (the above restricts f i = f ). Hence, all lower bounds on our variant of eluder dimension immediately apply to the original definition. Moreover, all upper bounds on eluder dimension in this paper can also be shown to hold for the other definition (unless stated otherwise).

We also consider the closely related notion of star number defined by Foster et al. [19], which generalizes a combinatorial parameter introduced in the active learning literature by Hanneke and Yang [21] (we will denote it as Sdim for consistency). We study the combinatorial star number in more detail in Section 5. The only difference between the definitions of eluder dimension and star number is that j<i is replaced by j =i , which makes the star number a "non-sequential" notion of complexity.

Definition 2. For any function class F ⊆ (X → R), f ∈ F, and scale ε ≥ 0, the exact star number Sdim f (F, ε) is the largest m such that there exists

Then for all ε > 0:

It immediately follows from these definitions that the star number is never larger than eluder dimension. On the other hand, the star number can be arbitrarily smaller than eluder dimension.

Proposition 1. For all F, f * ∈ F and scale ε ≥ 0, it holds thatfoot_3

Proposition 2 (simplified from Foster et al. [19,Prop 2.3]). For the class of threshold functions given as

, where f i (x) := 1 {x ≥ i}, and for f = f n+1 , it holds for all ε < 1 that Sdim f (F, ε) = 2 and Edim f (F, ε) = n.

Generalized rank

Dimension complexity has been studied extensively in combinatorics, learning theory, and communication complexity [see e.g. 1,18,5,2]. The classical notion of dimension complexity, also known as sign rank, corresponds to the smallest dimension required to embed the input space such that all hypotheses in the function class under consideration are realizable as halfspaces. We consider a generalized notion of rank that is specified for any particular activation σ : R → R, and captures to the smallest dimension required to represent the function class as a GLM when σ is the activation. In what follows, we let

Definition 3. For any σ : R → R, the σ-rank of a function class F ⊆ (X → R) at scale R > 0, denoted as σ-rk(F, R), is the smallest dimension d for which there exists mappings φ : X → B d (1) and w :

or ∞ if no such d exists. For a collection of activation functions

Examples. We present some examples of Σ-rk that motivate our definition above.

1. Threshold activation. sign(z) yields the classic notion of sign-rank (equivalent to dimension complexity, as already mentioned). In this case, the scale R is irrelevant, so we denote sign-rk(F) := sign-rk(F, R) for any R. Note that this quantity is meaningful only for F ⊆ (X → {-1, 1}).

2. Identity activation. For id(z) := z, id-rk(F, R) is the smallest dimension needed to represent each f ∈ F as a (norm-bounded) linear function. We abbreviate rk := id-rk, as this corresponds to the standard notion of rank of the matrix (f (x)) x,f (albeit with the additional norm constraint).

3. Monotone activations. For L ≥ µ ≥ 0, M L µ consists of all activations σ such that for all z < z , it holds that µ ≤ σ(z )-σ(z) z -z ≤ L (for differentiable σ, this is equivalent to µ ≤ σ (z) ≤ L for all z ∈ R). 5 An important special case is when µ = 0, and a particular σ ∈ M 1 0 of interest is the rectified linear unit (ReLU) defined as relu(z) := max {z, 0}. For ease of notation, we denote M µ := M 1 µ . While we will always be explicit about the Lipschitz constant, note that the scale of the Lipschitz constant L (and µ) is interchangable with the scale of R. In particular,

4. All activations. Σ all consists of all activations σ. We mention this notion of rank only in passing, and we will not focus on it for the rest of the paper.

We present a result which relates the aforementioned quantities (proof in Appendix A).

rk

for all F, where the dependence on R and ε is suppressed for clarity (see Propositions 1, 3, 4 for precise bounds). Whenever M 2 → M 1 arrow is missing, there is an example of a class F where M 1 (F)

Proposition 3. For all F ⊆ (X → R), R > 0 and µ ∈ (0, 1], we have:

where the last inequality is meaningful only for F ⊆ (X → {-1, 1}). Moreover, for each inequality above, there exists a function class F which exhibits an infinite gap between the two quantities.

Eluder dimension versus generalized rank

In this section, we compare eluder dimension and star number with each notion of generalized rank: rk, M µ -rk (for µ > 0) and M 0 -rk. Our results are summarized in Figure 1.

Eluder vs. rk and M µ -rk. Russo and Van Roy [37] and Osband and Van Roy [36] provided upper bounds on eluder dimension for linear and generalized linear function classes. For completeness, we restate this result, with a slight improvement and include the proof with precise dependence on problem parameters in Appendix B. Intuitively, the generalized linear rank allows us to capture the tightest possible upper bound that the guarantees in the papers [37,36] can provide on eluder dimension. Proposition 4 (cf. [37], Prop. 6, 7; [36], Prop. 2, 4). For any function class F ⊆ (X → R) and ε > 0:

This result has been used to prove upper bounds on eluder dimension of various function classes beyond GLMs; for example, the class of bounded degree polynomials, by taking the feature map φ(x) to be the vector of low degree monomials. The upper bound in Part (i) is in fact tight (up to constants) for the class of linear functions, as shown in Proposition 5 below. This trivially implies the optimality of the bound in Part (ii) up to the factor of (L/µ) 2 which to the best of our knowledge is open. Proposition 5 ([33]). For any R > 0, X := B d (1) and

For completeness, we include the proof in Appendix C.

Eluder vs. M 0 -rk. It turns out that eluder dimension and M 0 -rk are incomparable. That is, there exists a function class for which eluder dimension is exponentially smaller than M 0 -rk (and hence M µ -rk and rk by Proposition 3). Moreover, there exists a different function class for which eluder dimension (even the star number) is exponentially larger than relu-rk (and hence M 0 -rk).

First, we show that the eluder dimension can be exponentially smaller than M 0 -rk for the class of parities over d bits. Thus, parities over d bits exhibits an example where the eluder dimension is exponentially smaller than the best possible bound one can derive using the existing results of Proposition 4. Theorem 6. For X = {-1, 1} d and

Proof. Part (i). From Proposition 3, we have that M 0 -rk(F ⊕ , R) ≥ sign-rk(F ⊕ ) -1 for any σ ∈ M 0 . The proof is now complete by noting a well known result that sign-rk(F ⊕ ) ≥ 2 d/2 [18].

Part (ii). For any x ∈ {-1, 1} d consider its 0-1 representation x ∈ F d 2 (representing +1 by 0 and -1 by 1). All functions in F ⊕ can be simply viewed as linear functions over F 2 . Namely, any parity function is indexed by a vector a ∈ F d 2 , with f a (x) := (-1) a, x . Note that Edim(F ⊕ , ε) = 0 for all ε ≥ 2. For any ε < 2, suppose Edim f (F ⊕ , ε) = m, witnessed by (x 1 , f a1 ), . . . , (x m , f am ) ∈ {-1, 1} d and f = f a . We have

• f ai (x j ) = f a (x j ) for all j < i : since j<i (f ai (x j ) -f a (x j )) 2 < ε 2 < 4 iff all terms are 0. Thus, we have a i -a , x = 0 for all x ∈ F 2 -span({ x 1 , . . . , x i-1 }). But a i -a , x i = 1 and hence x i is linearly independent of { x 1 , . . . , x i-1 } over F d 2 . Thus, { x 1 , . . . , x m } are all linearly independent over F d 2 , and hence m ≤ d.

The bound in part (ii) of Theorem 6 was also calculated by Mou et al. [34,Prop. 3].

Next, we show a separation in the other direction for eluder dimension vs. M 0 -rk using the ReLU function class. Thus, we cannot hope to remove the requirement for the activation function σ to be strictly monotonically increasing in Proposition 4 (ii) for bounding the eluder dimension. Theorem 7. Let R > 0 and X = B d (1). Define

It holds that

Proof. Part (i) is immediate from the definition. We show Part (ii) in the special case of R = 2; the general case follows by relatively scaling ε, since relu is homogeneous, namely, relu(ax

A standard sphere packing argument shows that such a set U exists with |U | ≥ (1/2ε) d/2 for all ε < 1/2. In particular, the δ-packing number of the unit sphere is at least We remark that while we considered the variant of eluder dimension as defined by Foster et al. [19], the lower bound on eluder dimension in Theorem 7 immediately holds for the notion defined by Russo and Van Roy [37]. On the other hand, the upper bound on eluder dimension in Theorem 6 can be shown to hold even with the definition of Russo and Van Roy [37] (by replacing every instance of a by a i ).

Figure 2: Illustration of witnessing sequences of length 6 for eluder dimension, star number and threshold dimension with respect to f = 0 (we use the 0/1 representation of functions for clarity). '*' in the eluder witness sequence refers to a free value, either 0 or 1.

Relationships between combinatorial measures

In this section, we specialize the eluder dimension to binary-valued function classes and prove several additional characterizations that relate this combinatorial eluder dimension to other learning-theoretic quantities. First, we (re)define these learning-theoretic quantities. The first two definitions (of combinatorial eluder dimension and star number respectively) are the specialization of the scalesensitive versions (cf. Definition 1 and 2) to the binary-valued function setting. We abuse notation by dropping the argument ε from previous definitions in order to be consistent. Definition 4. Fix any function class F ⊆ (X → {1, -1}) and any f ∈ F.

• The combinatorial eluder dimension w.r.t. f , denoted Edim f (F), is defined as the largest m such that there exists (x 1 , f 1 ), . . . , (x m , f m ) ∈ X × F satisfying for all i ∈ [m]:

, and for all j < i :

• The star number w.r.t. f , denoted Sdim f (F), is defined as the largest m such that there exists (x 1 , f 1 ), . . . , (x m , f m ) ∈ X × F satisfying for all i ∈ [m]:

, and for all j = i : f i (x j ) = f (x j ).

• The threshold dimension w.r.t. f , denoted Tdim f (F), is defined as the largest m such that there exists (x 1 , f 1 ), . . . , (x m , f m ) ∈ X × F satisfying for all i ∈ [m]:

, and for all j < i :

As before, we define the combinatorial eluder dimension (resp. star number and threshold dimension) to be Edim(F) := sup f ∈F Edim f (F) (Sdim(F) and Tdim(F) are defined similarly).

Let us pause to unpack these definitions and give some background. In fact, the star number definition stated above is the original definition of Hanneke and Yang [21], who give tight upper and lower bounds on the label complexity of pool-based active learning via the star number Sdim(F) and show that almost every previously proposed complexity measure for active learning takes a worst case value equal to the star number. Roughly speaking, the star number corresponds to the number of "singletons" one can embed in a function class; that is, the maximum number of functions that differ from a base function f at exactly one point among a subset of the domain {x 1 , . . . , x m } ⊆ X .

The threshold dimension has recently gained attention due to its role in proving an equivalence relationship between private PAC learning and online learning [see, e.g., 3,9]. We slightly generalize the definition of Alon et al. [3] to allow for any base function f , in the spirit of the other two definitions. A classical result in model theory provides a link between the threshold dimension and Littlestone dimension (which we denote Ldim), a quantity which is both necessary and sufficient for online learnability [8,4]. In particular, results by Shelah [40] and Hodges et al. [22] show that for any binary-valued F and any f ∈ F:

A combinatorial proof of this fact can be found in Thm. 3 of Alon et al. [3]. 6 Thus, finiteness of threshold dimension is necessary and sufficient for online learnability (albeit in a much weaker, "qualitative" sense).

A qualitative equivalence

Now, we prove a rather surprising characterization that closely ties all three quantities in Definition 4 together. Our result implies that for any binary-valued function class, finiteness of the combinatorial eluder dimension is equivalent to finiteness of both star number and threshold dimension. Theorem 8. For any function class F ⊆ (X → {1, -1}) and any f ∈ F, the following holds:

The proof of Theorem 8 can be found in Appendix D. The lower bound is trivial by examining Definition 4. To prove the upper bound, we rely on a novel connection to Ramsey theory. In particular, we show that sequences (x 1 , f 1 ), . . . (x m , f m ) which witness Edim f = m form a bijection with redblue colorings of the complete graph K m , while subsequences of the witnessing eluder sequence that are valid star number witnesses or threshold dimension witnesses can be interpreted as monochromatic colorings of subgraphs of K m (see Figure 2). Thus, applying classical bounds from Ramsey theory implies the result.

We also show that the upper bound cannot be improved, for example, to Edim(F) ≤ poly(Sdim(F), Tdim(F)) in general. Theorem 9. For every N > 0, there exists a function class F N such that Edim(F N ) = N and max{Sdim(F), Tdim(F)} < c • log 2 N , where c > 1/2 is some absolute numerical constant.

The proof of Theorem 9 can be found in Appendix E. It relies on the probabilistic method to show the existence of a randomly constructed F which satisfies the desired properties.

Comparisons with sign-rk

In this section, we investigate the comparison of these combinatorial quantities (eluder, star, threshold) with sign-rk, and examine whether we can prove stronger separations. One direction is clear; for the class of linear classifiers in R d , the combinatorial eluder dimension, star number, and threshold dimension are all infinite. However, we ask if the other separation is also possible: can we construct F where eluder/star/threshold are finite but sign-rk = ∞? We have already provided an explicit exponential separation: Theorem 6 shows that for the function class F ⊕ , we had Edim(F ⊕ ) = Sdim(F ⊕ ) = d but sign-rk(F ⊕ ) ≥ 2 d/2 . (One can also show that Tdim(F ⊕ ) = d.) We are able to show stronger (but nonconstructive) separations by extending the probabilistic techniques of Alon et al. [2], who recently provided similar separations for VC dimension versus sign-rk. In view of Proposition 3, this result also provides a separation for the scale-sensitive Definition 1. Theorem 10. For every N > 0, there exists a function class F N ⊆ ([N ] → {1, -1}) such that Edim 1 (F N ) = 4 and sign-rk(F N ) ≥ Ω(N 1/9 / log N ), where 1 is shorthand for the all 1s function.

The proof of Theorem 10 can be found in Appendix F. It is straightforward to replace the reference function f (x) = 1 with any fixed reference function f : [N ] → {1, -1}. First, we use Lemma 22 of Alon et al. [2] which bounds the number of distinct matrices with sign-rk = r; then using a probabilistic argument we show that there must be many (more) matrices with Edim 1 = 4, so at least one of them must have large sign-rk.

The careful reader might notice that we do not prove the existence of a function class where Edim(F) is constant and the sign-rk is infinite; instead we prove the weaker statement that a function class exists with Edim w.r.t. any fixed function f is bounded. We conjecture that the stronger statement holds; see Appendix F.1 for more details.

Back to scale-sensitive?

It is natural to ask if our results can be extended back to the scale-sensitive definitions. First, we require a scale-sensitive version of threshold dimension. One proposal is the following: Definition 5. For any function class F ⊆ (X → R), f ∈ F, and scale ε ≥ 0, the exact threshold dimension Tdim f (F, ε) is the largest m such that there exists (x 1 , f 1 ), . . . , (x m , f m ) ∈ X × F satisfying for all i ∈ [m]: ∀j ≥ i : |f i (x j ) -f (x j )| > ε, and j<i (f i (x j ) -f (x j )) 2 ≤ ε 2 .

Then for all ε > 0:

• the threshold dimension is Tdim f (F, ε) = sup ε ≥ε Tdim f (F, ε ).

• Tdim(F, ε) := sup f ∈F Tdim f (F, ε) and Tdim(F, ε) := sup f ∈F Tdim f (F, ε).

Definition 5 mirrors the scale-sensitive definitions for eluder and star; it also recovers the combinatorial definition when F is binary-valued. By definition, the relationship that Edim f (F, ε) ≥ max{Sdim f (F, ε), Tdim f (F, ε)} for every F, f ∈ F, ε > 0 is trivial. However, one cannot hope to prove the corresponding upper bound under this definition. For example, for any ε > 0, take the function class which is represented by the N × N matrix:

It is easy to see that Edim 0 (F, ε) = N , while Sdim 0 (F, ε) = 2 and Tdim 0 (F, ε) = 1. Notice that this class is still "threshold-like", but Definition 5 does not capture this for said value of ε. Generally speaking, it is unclear how to carry over the intuition from Ramsey theory that applies in the combinatorial case to the scale-sensitive case; we leave this to future work.