Near-optimal learning with average Hölder smoothness
Authors: Guy Kornowski
Steve Hanneke
Aryeh Kontorovich
Venue: NeurIPS 2023 poster (2023)
Keywords: Hölder smoothness
average smoothness
bracketing numbers
generalization
risk bounds
metric space
TL;DR: We establish nearly-tight risk bounds in terms of average smoothness in noiseless and noisy regression

Abstract: We generalize the notion of average Lipschitz smoothness proposed by Ashlagi et al. (COLT 2021) by extending it to Hölder smoothness. This measure of the "effective smoothness" of a function is sensitive to the underlying distribution and can be dramatically smaller than its classic "worst-case" Hölder constant.
We consider both the realizable and the agnostic (noisy) regression settings, proving upper and lower risk bounds in terms of the average Hölder smoothness; these rates improve upon both previously known rates even in the special case of average Lipschitz smoothness.
Moreover, our lower bound is tight in the realizable setting up to log factors, thus we establish the minimax rate.
From an algorithmic perspective, since our notion of average smoothness is defined with respect to the unknown underlying distribution, the learner does not have an explicit representation of the function class, hence is unable to execute ERM. Nevertheless, we provide distinct learning algorithms that achieve both (nearly) optimal learning rates.
Our results hold in any totally bounded metric space, and are stated in terms of its intrinsic geometry.
Overall, our results show that the classic worst-case notion of Hölder smoothness can be essentially replaced by its average, yielding considerably sharper guarantees.

Near-optimal learning with average Hölder smoothness
Steve Hanneke
Aryeh Kontorovich Department of Computer Science
Department of Computer Science
Purdue University
Ben-Gurion University of the Negev
steve. s haaeeeeehhaeeeeemma...cmmmm
karyehucs bgu.ac.
Guy Kornowski
Department of Computer Science and Applied Mathematics
Weizmann Institute of Science
guy koy.koonnwsiiooo @eeeiiiwweeeee wwwwwiizaan...m ac.
Abstract
We generalize the notion of average Lipschitz smoothness proposed by Ashlagi et al. [2021] by extending it to Hölder smoothness. This measure the "effective smoothness" of function is sensitive the underlying distribution and be dramatically smaller than its classic "worst-case" Hölder constant. We consider both the realizable and the agnostic (noisy) regression settings, proving upper and lower risk bounds in terms of the average Hölder smoothness; these rates improve upon both previously known rates even in the special case of average Lipschitz smoothness. Moreover, our lower bound is tight in the realizable setting up to log factors, thus we establish the minimax rate. From an algorithmic perspective, since our notion of average smoothness is defined with respect to the unknown underlying distribution, the function class, hence is unable to execute ERM. Nevertheless, we provide distinct learning algorithms that achieve both (nearly) optimal learning rates. Our results hold in any totally bounded metric space, and are stated in terms of its intrinsic geometry. Overall, our results show that the classic worst-case notion Hölder smoothness can be essentially replaced by its average, yielding considerably sharper guarantees.
learner does not have an explicit representation of
Introduction
fundamental theme throughout learning theory and statistics that "smooth" functions ought to be easier to learn than "rough" ones intuition that has been formalized and rigorously established in various frameworks [Györfi et al., 2002, Tsybakov, 2008, Giné and Nickl, 2021]. Hölder continuity natural and well-studied notion of smoothness that measures the extent to which nearby points can differ in function value and includes Lipschitz continuity as an important special case.
These global moduli of smoothness, while convenient for theoretical analysis, suffer from the short- coming being overly pessimistic. Indeed, being distribution-indeeendee they fail to distinguish function that is highly oscillatory everywhere from one that is smooth over most of the probabil- ity mass; see Figure for simple illustration. Moreover, classically studied classes average smoothness (e.g. Besov space) typically fix some distribution in advance (predominantly uniform), and then turn to consider smooth functions with respect to that single distribution. Thus, from distribution-fre free statistical learning perspective where the underlying distribution is assumed to be unknown such classes fall short.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

u(x)
Figure Illustration of function and a measure μ exhibiting large gap between "worst-case" smoothness (occurring in low density regions) and average-smoothness with respect to jr.
Sceking to address these drawbacks, Ashlagi al. [2021] proposed a natural notion of average Lips- chitz smoothness with respect to a distribution. Their average Lipschitz modulus can be considerably (even infinitely) smaller than the standard Lipschitz constant, while still being able to control the excess risk. However, the risk bounds obtained by Ashlagi et al. are far from optimal, while the optimal rates for distribution-fiet learning of average smoothness classes remained unknown. In particular, the cost of adapting to the smoothness with respect to the underlying distribution (in contrast using classic worst-case smoothness) remained unclear far.
Our contributions. In this work, we generalize the aforementioned notion of average Lipschitz smoothness by extending to Hölder smoothness of any exponent 3 10. After formally defining the average Hölder smoothness of a function with respect to distribution in Section 2.1, our contributions can be summarized as follows:
Bracketing numbers upper bound (Theorem 3.1). We establish nearly-optimal distribution- free bound on the bracketing entropy of our proposed average- sootgh function class, serving as the main crux on which we hase our analyses throughout the paper. particular, although it is known that asymptotically empirical covering numbers yield sharper bounds than bracketing numbers, in the case of average smoothness we reveal that the latter are tight up to logarithmic factor.
Realizable sample complexity (Theorem 3.4). We derive a nearly-optimal sample complexity required for uniform convergence of Everage-Hölder functions in the realizable case, which was not previously known even in the special case of average Lipschitz functions.
Optimal realizable learning algorithm (Theorem 4.1). Since our notion of average smoothness is defined with respect to the unknown sampling distribution, the learner does not have an explicit representation of the function class, and hence is unable execute ERM. 2 We are able to overcome this obstacle by constructing realizable nonparametric regression algorithm with nearly-optimal learning rate. Such rate was not previously known even in the special case of average Lipschitz smoothness.
Agnostic learning algorithm (Theorem 5.1). We provide yet another learning algorithm for the fully agnostic (i.e. noisy) regression setting. Once again, our derived rate was not previously known even in the special case of average Lipschitz smoothness.
Matching lower bound (Theorem 6.1). We prove lower bound, showing that all the results mentioned above are tight up to logarithmic factors the realizable case, establishing the (nearly) minimax risk rate for average-smooth classes.
Illustratvve comparisons (Section 7). Finally, we illustrate the extent to which the proposed smoothness notion is sharper than previously studied notions. We provide examples in which
Unifform convergence of the Li distance between the upper and lower bracket functions implies that, in the limit of sample size, the e-bracket functions almost surely an empirical (1 + o(L))e-cover; see Section for reminder of relevant definitions.
'Indeed, the learner cannot know for sure whether any given non non-classions con-classccally Hölder function belongs to the average-Höldd Hölder class.

---

the "optimistic" average-Hölder Hölder constant is infinitely apart from both its "pessimistic" worst-case counterpart, or even the average- (3 1) constant, exemplifying the substantial (possibly infinite) speed-ups in terms of learning rates.
1.1
Related work.
The sample complexities associated to distribution- free learning of (classic) Hölder classes is well covered in the literature, see for example the books by Györfi et al. [2002], Tsybakov [2008].
Previous notions of average smoothness include Bounded Variation (BV) [Appell et al., 2014] in dimensions one and higher [Kuipers and Niederreiter, 1974, Niederreiter and Talay, 2006]. One- dimensional BV has found learning-theoretic applications [Bartlett et al., 1997, Long, 2004, Anthony variants have not. Moreover, the
and Bartlett, 1999]. but to our knowledge the positive results require μ to be uniformly distributed on segment, and the aforementioned results break down for more general measures - especially if μ is not known to the learner.
Sobolev spaces, and the resemblance to our average Hölder smoothness. However, Ashlagi et al. [2021, Appendix IJ demon- strate that from a learning-theoree or Lebesgue) measures, as it cannot be used to control sample complexity. Results for controlling bracketing in terms of various measures of average smoothness include Nickl and Pötscher [2007], who bound the bracketing numbers of Besov- and Sobolev-type classes and Malykhin [2010], who used the averaged modulus of continuity developed by Sendov and Popov [1988]: again. these are all defined under the Lebesgue measure. While it is easy to define these smoothness notions with respect arbitrary distributions, we are not aware of any existing work to bound their corresponding sample complexity (or even their covering or bracketing numbers) in Destributionnindepentt manner. Moreover, the smoothness notion studied in this paper is defined over arbitrary metric spaces, whereas previous notions are typically restricted to Euclidean structures (or variants thereof). Despite of the considerable generality of our setting, we are able to provide tight bounds for all metric spaces alike, without requiring specialized analyses.
norm in particular [Agranovich, 2015], bear some
perspective this notion is inadequate for general (i.e., non-uniform
seminal work on recovering functions with spatially inhomogeneous smoothness from noisy samples is Donoho and Johnstone [ [1998]. Arguably in the spirit of ju-lependent Hölder smoothness, some of the classic results on k-NN risk decay rates were refined by Chaudhuri and Dasgupta [2014] via an analysis that captures the interplay between the metric and the sampling distribution. Another related notion is that of Probabilistic Lipschitzness (PL) [Urner and Ben- Ben-David, 2013, Urner et al., 2013, Kpotufe et al., 2015], which seeks to relax a hard Lipschitz condition on the regression function. While PL is in the same spirit as our notion, one critical distinction from our work is that, while existing analyses of learning under PL have focused specifically on binary classification, our interest the present work is learning real-valued functions.
As previously mentioned, the main feature setting this work apart from others studying regression under average smoothness is that our notion is defined with respect general, unknown measure μ. The notable exception is, of course, Ashlagi et al. [2021] - who introduced the framework of efficiently learning smooth-on-average functions with respect to an unknown distribution. Although extending their definition from Lipschitz to Hölder average smoothness was straightforward, optimal minimax rates are likely inaccessible via their techniques, which relied on empirical covering numbers. Estimating the magnitude of these random objects was a formidable challenge, and Ashlagi et al. were only able to do so to within an additive error decaying with sample size; this sampling noise appears to present an inherent obstruction to optimal rates. Thus, our results required a novel technique to overcome this obstruction, which we did by tightly controlling the bracketing entropy. Our Hölder- type extension is direct adaptation of the Pointwise Minimum Slope Extension (PMSE) developed for the Lipschitz special case by Ashlagi et al., which in turn is closely related the one introduced by Oberman [2008].
2 Preliminaries.
Setting. Throughout the paper we consider functions Ω -- [0, where (Ω, p) is metric space. We will consider a distribution D over Ω x [0. 1] with marginal μ over S2, such that (Ω,, p. 11) forms a metric probability space (namely, μ is supported the Borel -lagebrra induced by p). We associate
3

---

to any measurable function f : Ω - [0. its L1 risk Lp(f) == RXXY)) - YI, and its empirical risk (s( := _ > (f(,)) Yil with respect to sample S (X, D More generally, we associate to any measurable function its L1 norm ( == Ex~ fX),, and given a sample XI....,A. Xn. ~ n we denote its L, norm with respect to the empirical measure (.))) =
We say that distribution D over Ω x [0, 1] is realizable by function class F C [0, 1) if there exists an f E F such that (D( = 0. Thus, (*( = Y almost surely, where (X ~.
Metric notions. The diameter of A C Ω is diam(A) == a p(2, and we denote by B(x, == {a' Ω p(r,, x') I r) the closed ball around E Ω of radius r 0. For a t-cover of B if c UseA B(a, t), and define the t-covering
t > O, A, B C St we say that number (t) to be the minimal cardinality of any t-cover of B. We say that A C B C is t-packing of B if p(a,a') 2 for all + a' A. We call V t-ner of B if it is t-cover and t-packing. The induced Voronoi partition sharing the same nearest neighbor in V (with ties broken in some consistent arbitrary manner). A metric space (92, p) is said to be doubling if there exists E N such that every r-ball in Ω is contained in the union of some d r /alls..s.. The doubling dimension is defined mina21 log2 d where the minimum is taken over d satisfying the doubling property.
B with respect to a net V is its partitioning into subsets
Bracketing. Given any two functions 1, u: 22 - [0. 1], we say that f -> [0. 1] belongs to the bracket [1, u] if S f I u. A set of brackets B is said to cover function class F if any function in F belongs to some bracket B. We say that [,, u] is a f-bracket with respect to a norm || ||u - I|I < L. The l-bracketing number Ni (F, ||. ||, (.) is defined as the minimal cardinality of any set of (-brackets that covers F. The logarithm of this quantity is called the brucketing eniropy.
Remark 2.1 (Covering vs. bracketing). Having recalled two notions that quantify the "size" of normed function space (F, (F,1I11) - -namlly covering and bracketing numbers is useful to note they are related through
No(c) MG
though no converse inequality of this sort holds in general. On the other hand, the main advantage of using bracketing numbers for generalization bounds is that it suffices to bound the ambient bracketing numbers with respect to the cettriuution-speccpi metric, as opposed to the empirical covering numbers which are necessary guarantee generalization [van der Vaart and Wellner, 1996, Section 2.1.1].
Strong and weak mean. For any non-negative random variable Z we define its weak mean by w[z] == sup / Pr[Z 2 1). and note that W[Z] S E by Markov's inequality. In the special case where 7 has finite support of size N > 3 where each atom has mass 1 1/N we have the reverse inequality E[Z] < 2og 2log(N)W(2 [Z] [Ashlagi et al., 2021, Lemma 22].
2.1 Average smoothness.
For (0, 1] and f Ω R. we define its 9-slope at æ E to A2(x) == supyee a(a.)))
[[x) f(v)
Recall that f called (-Hölder continuous if [| = supzen Af(x)) < co, with this quantity serving as its Hölder seminorm. In particular, when / = 1 these are exactly the Lipsehitz functions equipped with the Lipschitz seminorm. For metric probability space (8, p, μ)) we consider the average B-slope be the mean of (X) where X p. Namely, define
Xu(1)= = Ex 3xmu|Af((X))
Kz(m) = W Wxxppl (x = sup L. p(x: Ag(x)) 21). t>0
Notably,
K((w) s <X((e) S [[fll
(2)

---

where each subsequent pair can be infinitely apart - as we demonstrate in Section 7. Having defined notions of averaged smoothness, we can further define their corresponding function spaces
(1) = {f: : :2 [0,1] HoT, (Q, p)) =
Il & L):
Ty(n) - 1).
@ (1. = ff:: f [0,1] (7 s Höl,
We occasionally omit j when is clear from context. Note that Hal (92) C H c Höl, (S2, μ)) due to Eq. (2), where both containments are strict in general. The special case of 3 = recovers the average-Lipschitz spaces (1)) C. (9, C. Lip, p) studied by Ashlagi al. [2021].
3 Generalization bounds
Our first goal is to bound the bracketing entropy (namely, the logarithm of the bracketing number) of average-Hölder classes. We present this bound in full generality in terms of the underlying metric space, as captured by its covering number (see Corollary 3.5 for the typical scaling covering numbers). As will soon establish, this bound implies nearly-tight generalization guarantees in terms of the average smoothness constant.
Theorem 3.1. For any meiric probubility space (S, p. u1), any B (0, 1] and any 0 < < L, it holds
log. (H v), ()), < log, (H 8 (S, 11), Li e)
Nn
E 128L log(1/e)
1/9
log 1610gg(1/E)
Crucially, the bound above does not depend on μt, allowing us to obtain distribution free generalization guarantees. We defer the proof of Theorem 3.1 Appendix B.1. We start by showing that bounding the bracketing entropy implies a generalization bound in the realizable case:
Proposition 3.2. Suppose (Ω, p) is metric spuce, F C [0, 1jst is a function class, and let 'D be distribution over Qt x [0, 1] which realizable by F. with marginal over Q. Then with probability at least 1 - 8 over drawing sample S ~ D it holds that for all F
205 log (,F,
205 log(1/6)
LD(f) S 1.01L((f) + inf a
a20
n1
n
Remark 3.3 (Constant is arbitrary). In Proposition 3.2 and in what follows, the constant multiplying Ls( is arbitrary, and can be replaced by (1 +7) for any >> O at the expense of multiplying the remaining summands by -1. In the next section we will provide a realizable regression algorithm that returns an approximate empirical risk minimizer f for which Ls(f) se 0, thus this constant will matter for our purposes.
We prove Proposition 3.2 in Appendix B.2. By combining Theorem 3.1 with Proposition 3.2 and setting a = e/2, we obtain the following realizable sample complexity result.
Theorem 3.4. For any metric space (S, p). any B (0, 1] and any 0 < e < L, let D be distribution over Ω x [0, 1] realizable by Höl, 1. (2, u).. Then there exists
N(3, 8) E N satisfying
N Ō ( e
Nn ((
1/8 (10) log(1/8)
256L log(1/e)
such that long 2 N. with probability at least 1 8 over drawing sample S D it holds -
for all f E 10,
LD(J) S 1.01Ls((
The same claim holds for the smaller class Höl, (X, p).
5

---

Corollary 3.5 (Doubling metrics). In most cases of interest. (Ω, p) is a doubling metric space of some dimension d,² egg. when Q is a subset of Te (or more generally a d-dimensional Banach space). For d-dimensional doubling spaces of finite diameter we have Nn(e) (g) [Goulieb al., 2016, Lemma 2.1 2, which, plugged into Theorem 3.4, yields the simplified sample complexity bound
L
N =Ō
eld+33/8
or equivalently
La((d+3)
Lo(J) S (1.01L(() +
nB/(d+3)
up to constant which depends (exponentially) on d, but is independent of L,, Remark 3.6 (Tightness). The bounds Theorem 3.1 and Theorem 3.4 are both tight up to logarithmic factors, as we will prove in Section 6.
4 Realizable learning algorithm
Recall that without knowing μA, the underlying distribution over Ω2 cannot know for sure whether a function f belongs to Höl (R, μ)) (except for the trivial case f E Hölţ, (ft).. This gives rise to the challenge of designing fully empirical algorithm since standard empirical risk minimization is not possible. To that end, we provide the following algorithmic result with optimal guarantees (up to logarithmic factors).
Theorem 4.1. For any metric space (2, p). any (0. 1] and any e let D be a distribution over Ω [0, 1] realizable by Höl, (St, p). Then there exists polynomial time learning algorithm A, which, given a sample S ~ D of size n 2 N for some N =N(3, E, 6) E N satisfying
Nn
((256L1og( log(/e)
1/9
+ log(110)
= δ
E
constructs a hypothesis f = A(5) such that Lp(f) I E with probability at least Remark 4.2 (Doubling metrics). As mentioned Corollary 3.5, in most cases of interest we have Na(E) & (t)* In that case, the algorithm above has sample complexity
I
N =
eld+3)/8
or equivalently
Ld((d+8)
LD( =
33((+88)
up constant which depends (exponentially) d, but is independent of I.,.
Remark 4.3 (Computational complexity). The algorithm constructed in Theorem 4.1 involves one-time preprocessing step after which f(xx) can be evaluated at any given x. E S in O(1) time. We note that the computation at inference time matches that of (classic) Lipschit//Hülder regression (e.g. Gottlieb et al., 2017). Furthermore, the computational complexity of the preprocessing step is similar that in Ashlagi et al. [2021, Theorem 7] for the average Lipschitz case, where is shown to run in time Ōnn²). The complexity analysis of our prepossessing step is entirely analogous to theirs, and we forgo repeating it here.
We will now outline the proof of Theorem 4. which appears in Appendix B.3. The key idea is to analyze natural fully-empirical quantity that will serve estimator of the true unknown average
Namely, any ball of radius 0 can be covered by 2d balls of radius r/2.

---

smoothness. To that end, given a sample S () ~ D" and function f f + [0,1]. consider the following quantity which can be established directly from the data:
A, : -
((X))-(X)) X p(X,,X,)²
Namely, this is the empirical average smoothness with respect to the sampled points. It would suit well if the empirical average smoothness of function did not greatly exceed its true average smoothness, with high probability. The fact something like this turns out to be true is somewhat surprising and may of independent interest:
Proposition B.1. (Informal) Let f Ω + [0, 1]. Then with high probability A2. S KY..
The proposition above implies that restricting the sample, and letting f(X,) == Y, yields function over {X1.... Xa} which is empirically average-smose over the sample (with high probability). We then turn to show that any such function be approximately extended to the whole space, in way that guarantees its average smoothness with respect to the underlying distribution.
Proposition B.3. (Informal) Let f (Xi....,X4 + [0, 1] where (Xi) μ². Then it is possible to construct f Ω [0, 1] such that with high probability f(X.) f(X,) all i [N]. and K2 < Ag.
We will now sketch the procedure described in Proposition B.3, which serves as the main challenge in proving Theorem 4.1. Roughly speaking, the algorithm sorts the sampled points with respect their relative slope to one another. Then, it discards a fraction of the sampled points with largest relative slope, which be thought of "outliers", Then, the algorithm proceeds extend the function in smooth fashion among the remaining "well- beel-bbehaved" samples. A careful probabilistic analysis shows that disregarding just the right amount of samples induces small error, while being average-smon smooth with high probability.
Overall this procedure yields function f Ω - [0, which is approximate empirical-minee (since (X), Re f(X,) Y)), while guaranteed to averagely-smooth with respect to the unknown distribution. Thus we can apply the uniform convergence of Theorem 3.4, proving Theorem 4.1.
5 Agnostic learning algorithm
Noticeably, up to this point, both the uniform convergence result we derived (Theorem 3.4) as well as the algorithmic result (Theorem 4.1) tailored for the realizable regression setting. Inspired by recent result of Hopkins et al. [2022] that showed a reduction from agnostic learning to realizable learning, provide algorithm for agnostic (i.e. noisy) regression of average-smootf functions. worth noting that the following algorithm does not require any prior assumption on the noise model, unlike many nonparametrie regression methods, due
distribution free analysis.
Theorem 5.1. There exists a learning algorithm A such that for any metric space (2, p). any E (0, 1], 0 < L, and any distribution over St x [0, 1], given a sample ~ D of size N for some N N (3, satisfying
1/3 ( ((BBL log//e (1/e)
Nn
+ 1ogg(11))
N -
22
the algorithm constructs hypothesis f A(S) such that LD(f) < inf f-emaf (a.p) Lo(f*) + with probability at least 1 Remark 5.2 (Doubling metrics). As mentioned Corollary 3.5, in most cases of interest we have Na(e)) S (2) In that case, the algorithm above has sample complexity
dd18
=
cdd+28)/8
7

---

or equivalently
(LL)(4+)0)
LD(f)=
inf relle
LD(f*) + n22/(d+20)
up to a constant which depends (exponentially) on d, but is independent of I,, n.
Though our agnostic algorithm is similar in spirit that obtained by the reduction of Hopkins et al. [2022], our analysis is self-contained and crucially relies on the bracketing bound given by Theorem 3.1, as well as analyzing the empirical smoothness estimator as provided by Proposition B. We also note that unlike our algorithm for realizable learning, the agnostic algorithm is not computa- tionally efficient. This seems be inherent for such reductions, and we do not know whether this blow-up in running time can be avoided or not.
We will now describe the proof of Theorem 5.1 which appears in Appendix B.4. Given sample S of size n, consider dividing it into two sub-samples S1 U S2 = S of size n/2 each. We first use S1 in order to construct an empirical e-net fi.....,hy ,, S1 + [0, 1]. namely a of functions which are sufficiently empirically smooth over the sample, yet far away enough from one another when averaged over the sample. Recalling that bracketing numbers upper bound covering numbers (Eq. (1)), and since Theorem 3.1 holds true for every measure (in particular for the empirical measure), we can bound log N S (N(((e/)2//)) Moreover, using Proposition B. we know that f" := arg min m seHal, (Rt,z) (ff is likely to be Ö(L) average average-smooth smooth over S1, there must exist some hy with e excess empirical loss (since f" is in the class we are e-covering). Thus running the realizable algorithm of Theorem 4.1 over all {/1...... hN }. producing f1.... fN Ω - [0. 1], yields at least one function which has both small excess empirical error, while being smooth with respect to the underlying distribution. Finally, running ERM over (f1...., with respect the fresh sample S2 reveals such a good candidate function within log(N)+lon(1(0) samples by applying standard uniform convergence for finite classes (i.e. Hoeffding's ' inequality with the union bound).
6
Lower bound
We now turn to show that the bounds proved in Theorem 3.1, Theorem 3.4 and Theorem 4.1 are all tight up to logarithmic factors. In fact, since the bracketing entropy bound of Theorem 3.1 implies the generalization bound of Theorem 3,4 and the latter implies the sample complexity in Theorem 4.1, it enough to show that the latter is nearly optimal.
Theorem 6.1. For any 8 (0, 1], E (0, 1) any metric space (2, p) and L 2 Jiam(S)) there exists
a distribution D over Ω x [0, 1] which is realizable by Höl, (St) such that any learning algorithm that produces f A(S) with LD( S e with constant probability, must have sample complexity
n = (No((E/L))/18)
Remark 6.2 (Typical case). In most cases of interest it holds that Nn(e) Z (2)² for some constant d, egg. when Q is subset of non-empty interior in Id (or more generally in any d-dimensional Banach space).* 4 That being the case, Theorem 6.1 yields the simplified sample complexity lower bound of
I
=
cld+3)/0
Equivalently, we obtain an excess risk lower bound of
Ld/(d+ h1(000
Lo(f)= =
We will now provide a proof sketch of Theorem 6. while the full proof appears in Appendix B.5. -ee -net most of Ω yet 20 E some "isolated" point at constant Suppose K C Ω a (E8
'Note that assuming a subset has nonempty interior implies that it cannot be isometrically embedded to lower dimensional space. Hence, this d encapsulates the "true" intrinsic metric dimension.

---

distance away from K (we show that such 20. K always exist). Let be the measure that assigns 1 probability mass to zg. while the rest of the probability mass distributed uniformly over K. Now consider (random) function that independently assigns either 0 or to each point in K uniformly, and is constant over Since points in K are (e/ away from one another, the local 8-slope at each point in K is roughly 1/((e/ = L/e, while the slope at Do is small since it is far enough from other points. Averaging over the space with respect J., we see that the function is u(K) L/s = L wverage-Hölder. Now, we imitate the standard lower bound proof for VC classes over K: Since any point in K is sampled with probability e/|K], any learning algorithm with much fewer than KI/E Nn((e/L))//
examples will guess wrong a large portion of K, suffering
Ll-sss of at least order of ())
Illustrative examples
Having established the control that average-Hölder smoothness has on generalization, illustrate the vast possible gap between the average smoothness and it's "worst-case" classic counterpart. Indeed, in the examples we provide, the gap is infinite. Moreover, we also show that classes of average-Hölder smoothness are significantly richer than the previously studied average- -irrgg-Lipsschzz, motivating the more general Hölder framework considered in this work. Finally, it is illuminating to notice that both claims to follow actually consist of the same simple function f(x) = [ > 2 though with respect different distributions, emphasizing the crucial role of the underlying distribution in terms of establishing the function classes.
Claim 7.1. For any L O, E (0,1), 1), there exist f - [0, 1] and a probability measure such that
f is average-Hölder f E Höt, (2.
f is not Hölder with any finite Hölder constant: For all M > 0: f & H (2).
I is not (even) veakly-avvrrge--ipptee with any finite modulus: For all M > 0: S e
(S2,
Thus, H0, & UM=o (H51 J (1),
Claim 7.2. For any 0, (0, 1), there exist 1 - [0, and a probability measure μ such
that
f is weakky--veragg--tööleer f Höl, (R,
f is not strongly-avergg- with any finite modulus: For all M > 0: f HoT x (9)
is not (even) weadky-areruge-Lipsshe with any finite modulus: For all M > 0: $ (SpM((2,)) ()).
Thus, Hol, (2, u) & US
HoT M (4) Lip
We prove both of the claims above in Appendix B.6.
8 Discussion
In this work, we have defined notion of an average-Hölder smoothness, extending the average- Lipschitz one introduced by Ashlagi al. [2021]. Using proof techniques based on bracketing numbers, we have established the minimax rate for werage-smoottness classes in the realizable setting with respect to the Ln risk up to logarithmic factors, and have provided a nontrivial learning algorithm that attains this nearly-optimal learning rate. Moreover, we have also provided yet another learning algorithm for the agnostic setting. All of these results improve upon previously known rates even in the special case of average-Lipschitz classes.

---

A few notes are in order. First, the choice of focusing on L1 risk as opposed to general Lp losses is merely a matter of conciseness, to avoid introducing additional parameters. Indeed, the only place throughout the proofs which we use the L, loss is in the proof of Proposition 3.2, where we show that the loss-class L5 = (a + -(xx= - (x)) FF F) satisfies
Ni)(Cr, S Li)),
easy to show via essentially the same proof that for any p E [1, 00), the Lp-composed loss- class satisfies ([j(C [1(H), a) s (1)) and the remaining proofs can be invoked verbatim, This yields a realizable sample complexity (in the typical, d-dimensional case) of order La/na N Ö ((dtsmirs) ). or equivalently Lp-risk decay rate of LD(f) = Ō ( ( (287(d-p8))
which are also
easily translatable their corresponding agnostic rates.
Focusing again on L1 minimax rates of average-Hölder classes, is interesting to compare them to the minimax rates of "classic" (i.e., worst-case) Hölder classes. Schreuder [2020] has shown the minimax risk to be of order n -//d whereas we showed the average-smooth case has the slightly worse rate of n -88((4+0) (which cannot be improved, due to our matching lower bound). However, comparing the rates alone is rather misleading, since both risks are multiplied by factor depending on their corresponding Hölder constant, which can be considerably smaller in the average-case result. Still, it is interesting to note that in the asymptotic regime there is a marginal advantage in case the learned function is worst-case Hölder, as opposed to Hölder on average.
Our work leaves open several questions. A relatively straightforward one is to compute the minimax rates and construct an optimal algorithm for the classification setting, which is not addressed by this paper. Moreover, there is a slight mismatch between our established upper and lower bounds in the agnostic setting, ranging between (f((422)) and O(n ((n=8/((++))) Closing this gap is an interesting problem which we leave for future work.
References
Mikhail S. Agranovich. Sobolev spaces, their generalizations and elliptic problems in smooth and Lipschitz domains. Springer Monographs in Mathematics. Springer, Cham, 2015. ISBN 978-3- 319-14647-8; 978-3-319-1464855, doi: 10. 10000/98----319-14444 14648-5, URL https: /doii //oii.or//////////////// 5. Revised translation of the 2013 Russian original.
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge
University Press, Cambridge, 1999. ISBN 0-521-57353-X. doi: 10.1017/CBB0978011162211 URL http:://xx: http://xxddd.iioo/ www.do/ooooo.o...oooo...o....... 10. 1011111///0 11111100111000000001111777777
Jürgen Appell, J6zef Banaš, and Nelson Merentes. Bounded variation and around, volume 17 of
De Gruyter Series in Nonlinear Analysis and Applications. De Gruyter, Berlin, 2014. ISBN
978-3-11-006507--1 978-33--11199---111-1---- 978-3-11-0222
Yair Ashlagi, Lee-Ad Gottlieb, and Aryeh Kontorovich. Functions with average smoothness: structure, algorithms, and learning. In Conference on Learning Theory, pages 186-236. PMLR, 2021.
Peter L. Bartlett, Sanjeev R. Kulkarni, and S. E. Posner. Covering numbers for real-valued function classes. IEEE Trans. Information Theory, 43(5::1721 1997. doi: 1411109188622311 URL
https://doi. org/10. 10. 1109/18. 623181
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. In NIPS, 2014.
David L. Donoho and lain M. Johnstone. Minimax estimation via wavelet shrinkage. Ann. Statist., 26 (3)8879-921, 1998. ISSN 0090-5364. doi: 10. 42.1214//0//024461005 URL https://dooi org/ 10. 012114//00/1044691088
Evarist Giné and Richard Nickl. Mathematical foundations of infniite-dimensional statistical models. Cambridge university press, 2021.
Lee-Ad Gottlieb Aryeh Kontorovich, and Robert Krauthgamer. Adaptive metric dimensionality reduction. Theoretical Computer Science, 620:105-118, 2016.
10

---

Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression in metric spaces via approximate lipschitz extension. IEEE Transactions on Information Theory, 63(8):4838 4849, 2017. doi: 10.1 00.1199/T1:201:27133300
László Györfi, Michael Kohler, Adam Kızyžak, and Harro Walk. A distribution-free theory of nouparametric regression. Springer Series Statistics. Springer- Verlag, New York, 2002. ISBN 0-387-95441-4. doi: 10. 10.1007/b97848, URL http::/dxx doi. org/ 10. 10000000000000 /b97848.
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.
Michael J Kearns and Umesh Vazirani. An introduction computational learning theory. MIT press, 1994.
Samory Kpotufe, Ruth Urner, and Shai Ben-David. Hierarchical label queries with data-dependent partitions. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 1176- 7766-189, JMLR.orgg 2015. URL http://
proceedings. mml..mlr.... wwwpppessesepeeeeeepe ppress/v40/poouuflll html. wtt.e//d/.........eee///////////
L. Kuipers and H. Niederreiter. Uniform distribution of sequences. Wiley-Intersciene [John Wiley & Sons], New York-London-Sydlen 1974. Pure and Applied Mathematics.
Philip M. Long. Efficient algorithms for learning functions with bounded variation. Inf. Comput., 188 (1):99-115, 2004, doi: 10.1016/50000054000 (033000000 URL https: //oo:///ooioo/ org/10.101/// S0890-5401 0016--0
Yu. V. Malykhin. Averaged modulus of continuity and bracket compactness. Mat. Zamerki, 87(3):
468 071- 2010. ISSN 0025-567X. doi: 10.1134500011554600001111. URL https://doi org/ 10. 000114//500004441000000100000010
Richard Nickl and Benedikt M. Pötscher. Bracketing metric entropy rates and empirical central limit theorems for function classes of Besov- and Sobolev-type. Theorel. Prubab., 1772):177-199, 2007. ISSN 0894-9840. doi: 10.10007/1199559000-000000 =10959-007 007-999-0770088-111 0.58-1
URL https://doi. wrg/10...... 1007/ 1007/
Harald Niederreiter and Denis Talay, editors. Monte Carlo and quasi-Monte Carlo meth- ods 2004, 2006. Springer-Veriiee Berlin. ISBN 978-3-540-25541-33; 3-540-25541-9, doi:
10.1007/3-540. 186-6. URL http://s///boi.ooo100100////////
Adam M. Oberman. An explicit solution of the Lipschitz extension problem. Proc. Amer. Math.
Soc., 136(12):4329 4338, 2008. ISSN 0002-9939. doi: 10. 00w0:/000000099990-00--99990 URL https://doi http:::///ooo.o/////o.//// 1101100199//00000 99-9-99-999990
Nicolas Schreuder. Bounding the expectation of the supremum empirical processes indexed by hölder classes. Mathematical Methods of Statistics, 29(1):76-86, 2020.
Blagovest Sendov and Vasil A. Popov.
The averaged moduli of smoothness. Pure and Applied Mathematics (New York). John Wiley & Sons. Ltd., Chichester, 1988. ISBN 0-471-91952-77 Applications in numerical methods and approximation. A Intee--ne Publication.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
Ruth Urner and Shai Ben-David. Probabilistic Lipschitzness: A niceness assumption for deterministic labels. Learning Faster from Easy Data WorkshopNIPS,, 2013.
Ruth Urner, Sharon Wullf, and Shai Ben- Ben-David. PLAL: Cluster-based active learning. In Conference Learning Theory, 2013.
Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer, 1996.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.

---

A Minimal B-slope Hölder extension
In this section we describe a procedure that extends Hölder functions in an optimally smoothest manner at every point, as it will serve as crucial ingredient in our proofs. That is, given subset of metric space A 52 and function f + [0, 1]. produces FA 52 [0. 1] such that
1. It extends fIa+ FAlA = fla-
2. For any F 52 > [0, 1] that extends fla, it holds that A (x) &f)(2) for all Ω.
Such procedure described for Lipschitz extensions (namely when 3 in Ashlagi al. [2021]. The purpose of this section is to generalize this procedure to any Hölder exponent.
Throughout this section we fix B (0, 1]. 0 + A Q and f: 9 + [0, 1], and will always assume the following.
Assumption A.1. ||]al|ни
and diam (A) co.
Keeping in mind that the case we are really interested in is when A is finite (i.e. a sample), the conditions above trivially satisfied. Nonetheless, everything will present continues to hold in this more general setting. For E A we introduce the following notation:
Rz(u, = f(v) f(u)
p(x, 0) p(xx, us
Palu,v) v) = -[(u) Ru, v)p(e, u)
R² = sup R)(u,)),
u.DEA
W. =
A: (2( > R - =] 0< R2 $ (c) = (F,(u, (u, v) Wx(e))
Definition A.2. We define the 8-pointwise minimal slope extension (8-PMSE) to be the function FA R satisfying
FA(x) = lim 2z(E). c-0
In the degenerate case in which f(u) f() for all u, E A, define FA(x) = f(u) for some (and hence any) u E A.
Theorem A.3. Let 0 AAC f [0, 1]. such that Assumption A.I holds. Then FA S > [0, 1] is well defined, and satisfies for any x E Q A (x) I (z). Furthermore, if A is finite, then FA Fa(x) can be computed for any Ω within O(I arithmetic operations. Remark A.4. When Rx((,)) has a unique maximizer (u uz) E AxA, the definition of FA simplifies
p(x, 4 u(
FA(x) = f(u))+ + p(z, ) + p(z, u2)8 (f(x))
(3)
We conclude that under Assumption A.I, we can assume without loss of generality that for each E there is such a unique maximizer (since the function is well defined, thus does not depend on the choice of the maximizer). Furthermore, this readily shows that when A is finite, FA (x) for any x S within O([A(2) arithmetic operations - simply by finding this maximizer.
compute
Proof. (of Theorem A.3)
We will assume that there exist u, v A such that f(u) + f(v), since the degenerate (constant extension) case is trivial to verify. This assumption implies that R > O. It is also easy to verify that supzen R DC +
[[fll < oo.
Lemma A.5. FA is well defined. Namely, under Assumption A.I the limit lim +o+ 2x(E) E [0. exists.
Proof. Fix & E Ω (we will omit the x subscripts from now on). Let < R2 /2, (u, (1', e (e)) Note that R(u, v) > and that F(u, v) = f(v) R(u, v),(, v.P. Hence
f(u) F(u,v) < f(t),
(4)
12

---

and the same clearly holds if we replace (u, v) by (u'. Assume without loss of generality that F(u,v) v) I F(u', v'). hence f(u)= - u(u,v) v F(u', o') S f(v'). We get
(uu',')++E2 R
[(v) [(u)
2
p(z, 1/88 + p( u)a
5(6') F(u', 1z) + F(u, f(u)
F(u', v') F(u,v) ola + p( u}s
a(x, + +px,,
R(w' ('),,)))(()))))))) 1188 + R(u, v)p(z, w) p(a, 10)8 + p(xx, u)o
F(u', v²) F(u, 2)
plz, v')0 + txxx, u)a
R(u',v))pa v/) + (R(uu, v²) - =)p(o, w) + Flu', x²) F(u, v) Mx. v1)3 + p(rr, u)
2diam (A)s
2 R( - F(u', v/) F(u, 2) We conclude that if diimm()))) (A) < oo then lim oz indeed exists.
2diam(AA]
F2 v) - (u v')l I 4c diam
remains to prove the optimality of the 3-slope. Throughout the proof we will denote for any E
Slu, r) = [Fa(u) - Fa(w)]
p(u, u)s
and for any point E Ωt subset B lt and function g 12 - [0, 1] we let
[g(z) g(v)l
(x, = sup sEBI(u)
p(x, 9)
The proof is split into three claims.
Claim I. Ye EEER A: A (x, A) S (1(1, A).
Let E 22 A, and let (u", v*) ) E AAx x A be its associated maximizer of Rz, Recall Eq. (4) from which we can deduce that Fa(")) I Fx(x)= S (v").. Also note that a simple rearrangement based on Eq. (3) (and the fact that f and FA agree on A) shows that (("",x) = R. (u", ,,") = S(a, v²). Furthermore, we claim that A (Ir, A) == suPyE S(x; y) S(x, w²). If this were not true then we would have S(x, y) > S(x, u²) = S(z, o*) for some y E A \ (xr,",,"" Using the mediant inequality, if (3) 2 f()) this implies
f(y) - f(u')
Fx(y) - FA(T) + Fx - Fa(u")
(u 9) p(x, 8)8 + p(æ, w
> S(x,22) Ro(u",
p(a, v)8 + p(z, )
while if fly f (z) then
f((*) f(y
FA(U*) - FA(x) + FA(x) - FA(U) > -(I,10) =
(y, p(z, )* + p(zz y)
D( + +(xx
both contradicting the maximizing property of (u², so indeed A (I, = ((x,u') = S(x, v*). In particular, we see that if FA(x)= 2 f(x) then
(f()) f(x))
f(0²) - fxx) Fa(w*) - -Fa(e) = S(x,00) =A (I. A),
(a A) = sup
yEAl(#) p(y,x))
p(u*,x))
p(v", x2)
while if Fa(x)) < fxx then
lf(z) p(x,y)
f(x)
f(x) - f(u²)
Fa(x) - FA(u*) p(x,u*))
Af A) sup
S(x, u²) = -A, (z, A),
p(x, )3
yEAv(z)
proving Claim in either case.
13

---

Claim II.
Vr E EEERAA A: A (2 ( A) S A (z, A), in particular (z, = A (z. A).
suffices to show that for any x, y E 82 A:
S(z, v) S [ F4 (z, A), (v.
since taking the supremum of the left hand side over y E Q2) A shows the claim. Let (M o2), (uy,o)) the associated maximizers of Rgz Ry respectively, and note that by definition we have
A (z, A) = sup S(x, 2) Z max{S(x, w,), Stx, v.))
(5)
sEAVie)
We assume without loss of generality that A.A (x, & A (y. A). and recall that by Eq. (4) we can deduce that FA (")) I Fa(x) I FA( and FA(U)) S Fa(y) S FA(eT). Now suppose by contradiction that ((x, y) N (x, A). Pf(x) - Fy(y) then Fa(U)) Fx(x) + p( 5(1, v) ply, A1 (y/, A) > FA(x) + p(., A/ (z., A) + ply, 17)) A A) 2 FA(x) + p(10 11)) " A (2, A) [F(()) F((e!1) p(2,ug)"
thus Sar, m5))
> No. (I. A) which contradicts Eq. (5). On the other hand,
Fa(x)= > Fg) then
FΛ(x) = Fa(u))) + +(u,,, ") A (v, A) + x) 5(x,u)) > FA(UT)) + p(uy, ") N/ (2, A) plu. ))8 A3. (2, A) 2) )
'A (z. A), 2 FA(U)) + p(y
FA())) A (x, A) which contradicts Eq. (5), and proves claim Claim
thus S(x, ug)
o(z.g))
Claim III. V E A: F2 (r, .)- = A (I, A) S ().
Let 20 E A. Assume towards contradiction that there exists y & A such that
AF (x, 2) 2 S(x, v) > A FA (I, A).
We denote by (uy) "[))) E A x A the maximizer of Ry(:, Recall that since x E A, in the proof of
Claim we showed that S(x, 8) I S(y, ug)) = S(y, m.)) If Fx I FA(y) - FA (x5) then
S(z, 0.) Fa(eT) - FA(x) FA(U)) - FA(y) + FA(y) - FA(x)
plvg, x)3
98 +p(xx,))
2 min(S(y. vy),, S(,, v)} S(x, > Al. (x. A),
while on the other hand if FA(x) > FA(U) 2 FA(Ug) then
S(x, ut) FA(x) FA(u.) FA(x) - F FA(U) + FA
p(z,G))
p(x, 1) + p(u,, y)a
min(S(z, v). Sly. u()) S(x, A (x.
where in both calculations we used the mediant inequality. Both incqualities above contradict the definition of A FA (x,, A), thus proving Claim III.
Combining the ingredients. We are now ready to finish the proof. For & E Q, if then Claim III provides the desired inequality. Otherwise, if x E Ω \ A then
A (z. 22) Claim II
A (x,
Claim
S (x, S (z)
14

---

B Proofs
B.1
Proof of Theorem 3.1
We start by stating a strengthened version of the triangle inequality (also known as the "snowflake" triangle inequality) which we will use later on. For any 3 E (0, 1], x * v, 2 e Q:
pla,v) S p(x,, 2) + p(2,)))
Indeed, this follows from
p(x,2)² + p(z, 20
p(x,2) 2) + o(2,8))
p(z,2)
p(2,8) p(x, + p((,2))
+
p(x,8)
(p(x, 2) ((2,1)1>
p(x,2) + p(2,
p(x, 2)
p(2, 9)
+ p(z,2) 2) + p(z,
=1.
2xx,2) p(2,z)
Let 8 < denote K = [logo (1/e)]
e' (K+1)ø* and note that
1
(log2 (1/s) + 2)
2l0g2(1/e)+1
(11og(11/)++2 +2
(log2(1/e)
1/8
s'' 1/8
Let N = {i 2 | be a
-net of Ω of size |N| NNo
and let 11
327.
327.
(CI,..., CNND } be its induced Voronoi partition. We define B = [141 un uyllee C [0, 1 1|02 x [0. 1| to be the pairs functions constructed as follows:
1 are both constant over every cell C2 E II, and map each cell to a value in 35' 2..... ,... 1}.
{0, E,,
Choose some cells S Il such that u(UG,es, Ci) S e' and set for any C, E S ll. 0, u/c. = 1.
For m 2,...KK K choose some "unchosen" cells Sn c II Ujem Sy such
that 1u(Uc,Esm C.) S 2m- and set for any C. E Sm lcc. 2 2-121, J. w/c. = 1+ I
{0,
In the "remaining" cells SK+1
II \
U
jSk Sn set for any C₁ SK+1
Nc. E =(0, 2K+T
1 2
2 2
n/c, =1 1
2k+1
2k+1
2
Notice that for any [1. u] E we have
K+1
- u--ullate ul]
Σ
[(x)) - u(=)ldp(x))
Σ
[[xx) u(x)ldp(x)
C.en
m=1 C3ES
C.
R+1
K+1
C. 2m-1 dp(x)) =
((C))
2m-1
m= CLESm
m= 1
C.ESm
K+1
2m 2m-18/
1
= e'(( +1) 2k SE.
2m
Furthermore, we can bound [B] by noticing that any such is defined by its values over |N cells who all belong to {0, E',,,... 1}, and that once I is fixed then any associated has at most K + 1 possible values over each cell since it equals I 2 for some E [K + 1]. Thus
8 5
|N|
())
( 16 log)(1/E)
( ((1251162177)) )19)
B <
(K
+
1)
< loga
15

---

where the last inequality uses Eq. (7) and definition of K. In order to finish the proof, in remains to - show that B indeed cover Höl, (S2, ()) as brackets. Namely, that for any f E Höl, (2, μ)) there exist - [. ul B such that S f S To that end, let f E Höl, (2, pt). Denote
sf G V C. C 1)) L
E
= MUfi, E S(1) S Hence we can pick [1, u) E B such that (4c; ulc,) = (0, 1) for any C, E of (serving as S in their construction). Clearly any such I, bound / over these cells. Furthermore, for ..... K we denote
and notice that UfC, s/} S fx 2
S/n = [=
L
U jmm
vx C. Af(a)( 2 2m-1e'
and notice that UfC, E S S (x: Consequently let Sy, serve Sm in the construction of [1, E B, assuming we will show such a choice can serve as bracket of f over such cells. Indeed, for any E Cj we have
L/(2m-16)} = m(UEs e S S 2m
Eq.
L
2
- s(zi) S A7(=s) =
2m-2g'
32T
2m42'
which by the triangle inequality shows in particular that for any x. y E C₁
1f(x) - f(v)] s 1f(x) - + f(w)] S 2m+1 4. 2
(ー= such that a; S flc. S a, + zoi.t and by setting lc.. ulc. (a,, a; + I for any C₁ E S we ensure the bracketing property. Finally, for any of the remaining cells S/+1 := II UjSk Sf we get by construction that Ez, E C; Af < 2k (otherwise they would satisfy the condition some previously constructed S% Hence for any E C2 we have
So clearly there exists Og {0, 2
2
L
Eq. Eq. x
L
2s'
1sx) f(=)) s A)(=)) p(x, 2
2k
32L
2K+4
which by the triangle inequality shows that for any 1 C;:
1
1s(x) - [(w)) S 2k+3 8 $K
So as before, there clearly exists a; E {0, 2k 2 ........
2x11-2) such that a; S fle, S aa 2k:
and by setting I c,, w/c, = (a,, a; + ztx for any C E sh, we ensure the bracketing property over all of Ω which finishes the proof.
B.2 Proof of Proposition 3.2
Recalling that the realizability assumption ensures a "perfect" predictor f E F. we start by introducing the loss class L5 [0, 1J
C (c)))) = -())
Fix a > 0. We observe that L is no larger than F in terms of bracketing entropy, namely
Li(CF, a) < (F,
(8)
Indeed, suppose are given an arbrackeging of F denoted by B., and denote for any E F by 1 uy] E B2 its associated bracket. Then any ε L5 is inside the bracket iee, ue, where
l max(0, min(l; f - ue, min(1, max(u; f"
16

---

It is straightforward to verify that llue, - le, (w) - Ilyy - (1len60) S a, and clearly the set of all such brackets is of size at most BBl yielding Eq. (8).
Now notice that for any f E F
Lp(f) - (f) - |||
1.01111 S a [le,llei - 1.01 (()()))
hence
sup fer
(Io((f) -10/f)~1.000000 (.011s(( sa+ "y
- 1.01/1,,lla
In order to bound the right hand side, fix some le,- and note that Var(Ie,) & (12, S We (lr.)))
since l, (x) E [0, 1]. Thus by Bernstein's inequality and the AM-GM inequality we get that with probability at least 1 y
log(1/7)
2112,, ( log(1/7)
Me (aa - I1,e, (l)))))))
V
n
202 log (l/7) 1
|l (m))
n
101
205 l0glog(1/1)
[el 1.01|lle, (()))))))))
n
Setting 7 (F, LL ar) and taking union bound over le, whose number is bounded due Li(n), Eq. (8), we see that with probability d
205 log (1, + 205 log(1/6)
max((le,)le,,()) 1.01|]4, (011l1, 5 ",
n
Plugging this back into Eq. (9), and minimizing over a > finishes the proof.
B.3 Proof of Theorem 4.1
Proposition B.1. Let f Q + [0,1]. 1]. Then with probability at least 1 - 8/2 over drawing sample holds that
X < 4 (4n/)AA)))) + 4 (4n/6)
Corollary B.2. Df is realizable by HoT,, (St, pl. then for f : Ω - [0.1] such that Lp(f*) holds with probability at least 1 -5/2: Xo S 5 5lg (4n/6)I. Hence, f(X:) = fxx))) Y; satisfies Ls( 0 and N. 5log² 5log2(4n/8)) (4n/8)L.
Proof. (of Proposition B. Fix f Ω - 10, 1]. Given sample (X,) 1²" which induces an empirical measure Mnn we get
f()) = E [x)(x)] 2(X,,))
A 3 Σ sup #XX,
(10)
x~
where the last inequality follows from the reversed strong- weak mean inequality for uniform measures. We will now show that with high probability W Wx~a, [A) z WXxm|AA Ae. To that end, we denote for any > (1) = (a 1z(x) 2 f} c Ωt let = Kz(m). N [2 logg(4n, 4n/8) log log(4n/55)) and note that
W WXxmmIAf(X) (x)(
sup fu (t)
(1I)
t>0
Iua (M) + oCIšk
sup
max 2' 2M, jE(0......NNII
+ sup tum tum(( (M₃(t). 122KK
We will bound all three summands above. We easily bound the first term by
sup lp (M,(()((()) K 1 1=x,(xx) oCtŠK
(12)
17

---

For the second term, denote for any t > 0 by (t) 5 Mt( a containing set for which - U(M (t)) & (t) x We can always assume without loss of generality that such set exists." By the multiplicative Chernoff bound we have for any t, a 0:
Pr s [M3 (1) 2 (1 + a))((M) (0)) 2 ea
(1 (1+a)l+a*
hence by the union bound we get with probability at least 1 (Ita)
Ne
max je N11) 2 2z (M)
- max
2 (M7
jc Je(0,1....A-1)
$ (1 (1+a) a)
max Je(0.1...N-11
2 L ( (2²
2 (M(M, + 1
1 (1 + a)
max JE(0.I.....NI1
s (1+ + {
++a
n
Letting a = log(4n/6) - 1, by our choice of N = [2 log log(4n/0)] we get that with probability least 1 5/4:
2 K pm (M, K)) < 2log(4m/0)) + 2 2log(4n/0)
2
max JE (O.1.....N-1)
(13)
In order to bound the last term in Eq. (11), we observe that the empirical measure satisfies for any A Ω (A) definition of K (1) we have pMM, (t)) I K, hence by Markov's inequality
= (A( O, and that Ms(s) C Mt(() for s > Furthermore, by
Pr sup pn (n (M)( # 0 S Pr (M₂ (Pr(u,(M,())) 0] Pr s2
Mm (M, 2 1 a
For = 2 K yields Prs [sup522< Mhn (M)(s) + 0] 2 S 2. Combining this with Eq. (12),
Eq. (13) and plugging back into Eq. (11), we get that with probability at least 18/2:
Wx-m. [A((X)) s (1+2log(4n/00)) 2 2 (lgg(4)/))
< (1+2 (1+2log(44/88) (n)+ 2 log( (og(4n//)
n
n
Recalling Eq. (10), we get overall that
2 1lgg4nn00)
A < 2 log(n) (l+22l((4n/8)) +
Simplifying the expression above finishes the proof.
Proposition B.3. Under the same setting, for any yy 0 there exists algorithm that given a sample S ~ D and any function f S + [0, 1], provided that 2 N for N = Ö (Na(r)+
constructs a function f : Ω + [0, 1] such that with probability at least - 5
. 'Ifs- 1 --llka(um) S 51 27 In particular L. < Ls( 711 + 25
(x( < 55
'Such a set does not exist only the case of atoms To E Q with large probability mass y(zo). that is the case, consider "copy" metric space f2 with wo split into two points x1 E Ol distance apart and each of mass /( Any function f Ω > R is extended to f Ω R via f(x1) f(22) f(2)). Repeating the split if necessary and taking e 0, we obtain space Q with all of the relevant properties of S but atoms of large mass.
18

---

Proof. Throughout the proof, we denote for any point E Ω subset B C Ω and function g B - [0.1]
(Ø(x)) g(v)l
Ag (3, B) = sup
p(x,y)² y)
(E
Give the sample S (X,, Yi)= we denote S (Xi) Lety O. The algorithm constructs f: 0 + [0, 1] as follows:
Let Sx(7) C Sn consist of the [yn] points whose A A S.) values are the largest (with ties broken arbitrarily), and (7) = S, (x(7) be the rest.
2. Let A (1) be a 1/1 of (1).
3. Define f Ω + [0, 1] to be the 3-PMSE extension of from A to Ω as defined in Definition A.2 (and analyzed throughout Appendix A),
We will prove that f satisfies both requirements. For the first requirement, since fla = fla and
S. -5,()) w S2(7) have
|| All))(m) - E - -()))(()))1==
Σ (x))) 2ES.())A
E - 2E8((t)AA
The first summand above is bounded by since 0 I f.f < = 1f(x) f(x) S and
[S2(1)] & yn. In order to bound the second term, we denote by NA ('())) + A to be the mapping of each element to its nearest neighbor in the net, and note that p(z, (2())) //1/.. Then
1f(x) f(x)1 n (T)A
Σ
Σ
? plz, (l Na(x)) ((()))) f(x))
n
=ESTGAAA
[f(x) - F(NA)() +1F(N((=)) F(x))
1
Σ
((,,N(()))
=ESA
((N(()]
(((N(()) - f(0))
1
Σ
n
((z)Na()))
plx, Na(x))
< 7
Σ
A) + AA(0,
n
27
Theorem A.3] <
Σ
Af(1,A)
22
So overall we get |lf - fll,, 5 2 = 7/1 2L) as claimed in the first bullet.
1/8 We move on to prove the second bullet. Let U c f2 be a -net of Ω be its induced Voronoi partition and let m = [II| < \/8 2/84). Let Consider the following partition of II into "light" and
"heavy" cells:
I, (C E IT (C) < ny/m), II = IT 17.
We will now state three lemmas required for the proof, two of which are due to [Ashlagi et al., 2021].
Lemma B.4. Suppose A C Ω and that f : Ω + [0, 1] is the 3-PMSE extension of some function from
Az
to Ω. Let E Ω such that diam(E) 1 mingereeA x') x')a. Then supa, A7(r))
2
Proof. Let uh og E A be the pair of points which satisfy ()(x)) (w))-f(u?) By assumption E, we know that 2d)am(E)3 I p( ) 2)u),z) + p(u 2) hence
19

---

x)) + p(u,, x) + 2diam(E) - (pplu x) + 2)))) We get
f(1²) f((())
p x²) + p x²)
f(v)) - f(ux))
p 3)0 + (iiam()) F.) + ((, + diam E))
((v)) ((x))
2 A 2)((x)
1
2(p(ug, x)0 +
Lemma B.5 (Ashlagi et al., 2021, Lemma 16). 1n 2 m, then
Nn (C) 1
Pr S-D"
min CETTA ((C)
> - (-n7//m),,
2
Pn [C)
Pr SwDa
max CETTA
<
2 1 m mxxp( mmxp(-nny/33m -n7/3mm)
Pr SwD"
Σ c(C) 27
2 1 exp (-n(1 mm//n2/12
LETT
Lemma B.6 (Ashlagi et al., 2021, Lemma 17), ||/ S 21
Equipped with the three lemmas, we calculate
NG(n)= 1 Ag(x)du E Cell.
l Al(x)dd E 1 Af(x)dd.
(14)
Cella
The first summand above is bounded with high probability using Lemma B.5 and Lemma B.6, since under the event described in Lemma B.5 we have:
Σ [ ()(ddd S
Σ
2L
du
2L
Σ m(C)
J
7 Cell.
Cell.
CEll.
2T.
$ 7
24 =
In order bound the second term in Eq. (14), let C IT, x' C and note that by applying
Lemma B.4 E S. we get that A (x') S 2 2minzes,ne Az(x). Thus, under the high probability event described in Lemma B.5 have
Σ / Ng(e)dy Σ CETT
[
min ZES ()(r)d 22
Σ
min zES
(x))(((
CEll,
CEllA
< Σ
min zES,nc
(C)
Σ Σ
min #ES.nC
1z(x)
CEll.
CElla z'ES.nc
< Σ
Σ
A9(x') Σ Af(x)) SL,
Cell, .'Es,nc
z'ES,
where the last inequality is due to the extension property of Theorem A.3. Overall, plugging these bounds into Eq. (14) and using the union bound ensure all required events hold simultaneously. we see that the desired second bullet holds holds with probability at least - m exp(-nr/4m) exp (-n(1- / / A straightforward computation shows that by our assumption on n being large enough, this probability exceeds - 8/2 as required.
We are now ready finish the proof of Theorem 4.1. Let ? > 0. By Corollary B.2, we can construct f + [0, 1] such that with probability at least - 8/2 Ls(f) = and Ag <
20

---

5 log (4n/6)L. llgg2(4n/8)14
Assuming n is appropriately large, we further apply Proposition B.3 in order to obtain f : + [0, 1] such that with probability at least 8/2 f Höl25 (4n/888) (22 and also Ls( - Ls (f) + 71 + 2L) = 7(1 + 2L). By the union bound, we get that with probability at least 1 - 8:
Lp(f) l.) + (LD(f) - (.)) S 7(1 + 2L) +
sup
(LD(f)- - 1.01Ls(f)
f feHol 25 logg2) (
(
2 ;
where (+) is justified by setting (ccLL) L) and applying Theorem 3.4 for appropriately large
B.4 Proof of Theorem 5.1
Given a sample
(Xi, Vi) D denote the empirically smooth class
Höl (X1, [n/2] [0, X < log l (
Consider the following procedure:
1. (Empirical cover) Construct hi...., hy E Höl for maximal N such that Vi + E
[N]: : ||/, - -1,l-(lllaaa)) 2 q.
2. (Run realizable algorithm on cover) For any j E [N], execute the realizable algorithm
Arcalizable of Theorem 4.1 the "relabeled" dataset (Xx)))) [n/2] and obtain fy
Ω + [0, 1].
3. (ERM) Return arg min......fx E Ei (X,) Y?l.
We will now prove that the algorithm above satisfies the theorem. Let f E arg min yenaf LD(f), and note that by Proposition B.1 (as explained in Corollary B.1) have / E Höl with probability at least 1 - 5/2. By construction, Iu,..., ,, is a maximal g-packing of Höl, which is known imply that also a --net [Vershynin, 2018, Lemma 4.2.8] with respect to the metric L, (. In particular, this implies there exists j E [N] such that
If h2- (1. S
Ls(h)-) S Ls(f)
Further note for any [ hy HöL, realizable algorithm (as manifested in Proposition B.3 for 7 = L)) when fed the "smoothed" labels (X,, h (X.)) will produce f, such that Ls(J,) S Ls(h,) S and N2, (n) S 55% S 25 log (4n/)(4 In particular
Ls(fr) < Ls(.)) + (s(
Finally, by Eq. (1) and Theorem 3.1 (which holds for any measure, in particular for the empirical measure (kn)
log N < log. Noa.N
< lo (Höi, To ()
1/8
16 logz (1/s)
< loggNa
6400 (4n/6) Log(L//)
log
Hence, by a standard Chernoff -oenofff bound over the finite class (fi...., ff J. step (3) of the algorithm yields? & excess risk as long as = (oggN)+
We assume without loss of generality that the infimum is obtained. Otherwise we can take function whose loss is arbitrarily close enough to the optimal value and continue with the proof verbatim.
21

---

B.5 Proof of Theorem 6.1
We start by providing simple structural result which we will use for our lower bound construction, showing that in any metric space there exists a sufficiently isolated point from a large enough subset. Lemma B.7. There exists point zo E Q and subset K C Q such that
Vx E K.K p( x) 2 diam(O)
Vx tyEK K; p(x,)) 2 (E/L)UB. Nalle/L)//
|
Proof. Denote D) = diam((2), let 20. be two points such that (( > D/2, and let = {Co, C1) be Voronoi partition of Ω induced by { For > 0, let N,, be maximal y-packing of S2. By the pigeonhole principle there must exist a cell C. E IT such that |C; n N,, 2 1/2 which we assume without loss of generality to be C1- Now note that any x E C1 satisfies p( z
(0) ( 21) 2 (1(00, 21) > D/4. Finally, set 7 = g2/3 and let K C Ci O Ny be any subset of size (a
Given zo, K from the lemma above, we denote K = { U K and define the distribution μ over Q supported on such that μ(mо) = 1 - & and p(x) = 2| proof is similar to a classic lower bound strategy for VC classes in the realizable case (e.g. Kearns and Vazirani, 1994, Proof of Theorem 3.5). To that end, it is enough to provide distribution over functions in HōT (9, 1u) such that with constant probability any algorithm must suffer significant loss for some function supported by the distribution.
E for all x E K. From now on, the
We define such distribution over functions F: K - {0, as follows: Pr(f(xu) = 0] = 1, while for any K (x] 0] Pr](2) 1] 2 independently of other points. We will now show that any such f K + 10,1] is average Hölder smooth with respect to μ. Indeed, for every E K
((w)-((c))
AG(=== = sup ('ER((a)
e/T 3
while
AG(20)=
[F(r)) -[x'))
4
sup d'ER((ao)
p(z0.2²) z/)3
diam(12)/4 diam([2)
hence
A7(x) = u(zo) + Em(=)A(())
4 L D
2 SL.
Finally, we define the (random) function f* S2 - [0. 1] to be the 8-PMSE extension of f from K to Ωt as defined in Definition A.2, and note that f satisfics the required smoothness assumption. Setting D over Ω2 x [0, 1] to have marginal and Y = f (X), we ensure that D is indeed realizable by Har
Now assume is a learning algorithm which is given a sample S of size |S| < K A(S) : 52 -> [0, 1]. We call point & E K "misclassified" by the algorithm if ( and denote the set of misclassified points by M C K. Recalling that Va K Prif(z)=
4= and produces
>
Pr[f(z) = 1] = 1 independently, and that p(x) = " we observe that with probability at least the algorithm will misclassify more than K1/2 points.? 7 Thus, we get that with probability least ]
Lo(A(S)) E X~p
Σ p(x) (A())()))
>
K
E
1
2
2
REM
Indeed, denoting C \\ A we see that Pr[[C| 2 |K//|] S TKT
B[C
= म
p(K)
5
22

---

By rescaling we see that in order to obtain Lp(A(5)) S E the sample size must be of size
K E
(Nalle//D)V1))
Ω
B.6 Proofs from Section 7
Proof of Claim 7.1. Let 3 E 1). Consider the unit segment f = =00,
1] with the standard
metric, equipped with the probability measure l with density du Sg | - < oo is normalizing constant). We examine the function f(x:) = 1 [z 2
de 2 |z 1=1 (where Z
which is
clearly not Hölder continuous since it is discontinuous. Furthermore,
a(tx: (x) 2 t})
(1
x
N 2
2
e-1 da X t -
Z
0
AJ sup - pl (z 2 ()} x sup
1 20,
t>o
t>0
hence/ f & Lip u) for all M > 0. On the other hand, Af(xx)
= 10-
- so
X S.' AQ(o)du= Z
1
/
1
1
dx (0<1)
Jo
dr
Z
Jo
1
21
00,
thus f E Hol, (9t) for some L < co. Note that by normalizing the function, the claim holds even for
L -=1.
Proof of Claim 7.2. Let E 1). Consider the unit segment f [0. 1] with the standard
metric. equipped with the probability measure j with density # ビ 1/1-1 (where Z =
Jo | 2 00-dd dx < is normalizing constant). We examine the function f(x) 1[x 211 Note that for any x # f A)(x)= -- hence
m(( (x) 2 (}) 1 (f0::lo- 11::10-21- {1,)) 1
2
gi x
dr x x8
7 0
This shows that
X supt - ulfx : A)(z) 2 f)) x suupt t' 1-88 =00,
1>0
t>0
hence / $ Lipar n) for all > 0. Furthermore, for x + 1/2 Az(x) = -2-211 80
1 dp
1 1
dr x0
3o x
Z Jo x
2
8
hence f $ HölM (S2 n)) for all M 0. On the other hand
2 ( 1/8
u((x: : (x)) 2 13) p(1 [ 1 -/1)) 7
x - 11
+ X supt t ultz Af(x) 2 t}) <
t>o
thus f E (9) for some I. < co. Note that by normalizing the function, the claim holds even for
L L=1.
23


Reviews:
[{"review_id": "Bx4cmP2pN2", "reviewer": "Reviewer_LpFP", "summary": "This paper generalizes the notion of average Lipschitz smoothness proposed by Ashlagi et al. by extending it to Hölder smoothness. Eventually, the class of the average holder smooth function is much larger than the class of the worst-case holder smooth function. Further, the paper provides upper and lower risk bounds in terms of the average Hölder smoothness for realizable regression and noisy regression. ", "questions": "See weaknesses. ", "limitations": "yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Though I am not an expert in this area, the results provided in the paper are clearly better than the previous result for the average Lipschitz case. The bounds provided in the paper for bracketing number is distribution-free. Using this distribution free bound on the bracketing number, the authors prove sample complexity for obtaining uniform convergence of average-Hölder functions in the realizable case. the learner does not have an explicit representation of the function class, running an ERM is not possible in this case. Hence, the authors construct a non-parametric regression algorithm with nearly an optimal rate. \nThe authors also provide results for agnostic settings using the reduction from agnostic to realizable settings proposed in the previous work of  Hopkins et al. [2022]. A matching lower bound is also provided in the paper. ", "weaknesses": "Overall, I find the paper quite well written. However, it would be great if more details about the algorithm could be provided in the paper. Again, this is coming from non an expert in this area. To obtain the result in theorem 4.1, what is the modification needed in the algorithm as running ERM is not possible? It would be great if that could be explained in detail. The same goes for the agnostic result. \nAlso, the worst-case rate in remark 4.2 is exponential in dimension, can the authors please comment that under what conditions we might get rid of exponential dimension independence? For example, approximation results in sobolev space get rid of exponential dependence if the function is differentiable O(d) times. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review and helpful comments.\n- In the revision, we will provide a cleaner explanation of the algorithm in the main text.\n- Regarding the exponential dimension dependence, this is very typical of non-parametric regression methods, as exemplified e.g. by the results in the classic textbook “A distribution-free theory of nonparametric regression” by Gyorfi et al. Moreover, note that our lower bound has such exponential-dimension scaling as well. Indeed higher-order smoothness assumptions circumvent such dependence, and it is not clear whether this phenomenon holds for average smoothness (as studied in our paper). We leave this interesting question for future work."}, {"review_id": "jKQq4SVNEa", "reviewer": "Reviewer_VoQT", "summary": "This paper introduces the notion of \"average Hölder smoothness\", generalizing the notion of Holder smoothness.\nAuthors motivate the introduction of this class, explaining that the Holder constant is a supremum over many slopes that can eventually not be representative of the general behavior of this slope.\nAfter a long recall on needed notions, authors listed their theorems.\n\nThe first notable one (Thm 3.1) controls the backeting entropy of the newly defined class of functions with its covering number.\nThis theorem is crucial as\n    1. the bracketing entropy is used to encode the number of \"packs\" (brackets) one needs to enclose all the average holder smooths functions, and then naturally bounds the generalization error (See Thm 3.2),\n    2. the covering number is more intuitive and known in classical case.\nThen, Thm 3.4 follows, providing the generalization error gap on this class of function depending on the number of sampled data.\n\nThe next 2 sections discuss learning algorithms to minimize the empirical function keeping the generalization gap low. Note that an approximation of holder constants is used since its exact value cannot be computed.\n\nFinally, lower bounds are computed in the section 6.\n\nOverall, this paper seems self contained and complete, generalizing results obtained on average Lipschitz continuous function class.", "questions": "- What motivates these definitions of « semi-local » holder constants? Would we be able to say something with $\\Lambda_f^{\\beta}(x) = inf_{\\varepsilon>0} sup_{y\\in B(x, \\varepsilon) -\\lbrace x \\rbrace} \\frac{|f(x)-f(y)|}{\\rho(x, y)^{\\beta}}$ ?\n- If I understand correctly, Thm 3.1 and 3.4 are claimed as contribution, but not Proposition 3.2. Where can we find it?\n- Thm 3.4: Why did we lose the $log(1/\\varepsilon)$ term from Th 3.1?\n", "limitations": "- Cor 3.5: Number of needed data for good generalization is exponential in d.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is self-contained, well written, notions are explained clearly and the reasoning is explained step by step to obtain a generalization bound on a newly proposed class of functions that is much larger than the classical ones and describes functions better.", "weaknesses": "Minor:\n\n- l.147: What about N=1? What is the log basis? I checked in [Ashlagi et al., 2021, Lemma 22]: the log basis is e and there is a small mistake at the very end of their proof. The actual bound should be $E[Z] \\leq (1 + log(N)) W[Z]$. Finally, the provided bound only holds for $N\\geq 3$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review and helpful comments.\n- Thank you for spotting the bug for small $N$, we will fix this in the revised version.\n- Regarding the proposed alternative notion of local smoothness: Though this is a natural idea, unfortunately it does not suffice to control generalization. To see this, consider a step function, for which its local smoothness constant (according to the proposed definition) would yield $0$ everywhere except for the jump point. Thus any distribution which does not have an atom at the jump will assign $0$ as the average measure of smoothness. On the other hand, it is clear that any learning algorithm requires more than a single sample point in able to distinguish between such functions (with jumps at different points). This is actually a nuance that motivates our seemingly less natural definition.\n- Regarding Proposition 3.2, we do not claim it is a novel contribution since this may be known (or some variant thereof) to experts in the field. We are not certain, and could not find a reference to this claim — which lead us to prove it ourselves.\n- Regarding the log factor in Theorem 3.1., thank you for spotting this typo. We will fix it in the camera ready version.\n- Regarding the exponential dimension dependence, this is very typical of non-parametric regression methods, as exemplified e.g. by the results in the classic textbook “A distribution-free theory of nonparametric regression” by Gyorfi et al. Moreover, note that our lower bound has such exponential-dimension scaling as well. "}, {"review_id": "pJnYBnX7Cv", "reviewer": "Reviewer_uWsQ", "summary": "The authors proposed a notion named average Hölder smoothness, which is a generalization of average Lipschitz smoothness. They gave sample complexity bounds of learning the averge Hölder smooth function class in both the realizable and agnostic setting with corresponding algorithms. They also gave lower bounds which matches the upper bound up to logarithmic factors. ", "questions": "1. Is it possible to derive tighter bounds for subclasses of average Hölder smooth function classes? In the paper only learning from the entire class is considered but it could be much easier to learn from a subclass in some cases, right? Is it possible to derive a bound dependent on the specific function class? If so, will the average Hölder smooth parameter still show up somewhere in the bound?\n\n2. I think it's better to give some concrete examples in applications, like giving a setting where ERM fails and we can only use your algorithm. Learning finite sums with a distribution concentrating on positions where the smooth parameter is small may be a good example.\n\n3. I think maybe you should compare your bound more with the classical PAC learning bound to help reader better understand. \n\n4. Are there any other works giving sample complexity bounds on distribution free learning for generic or specific function classes? Maybe adding these to the related work section.", "limitations": "The authors addressed the limitation of their theoretical work properly.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The writing is clear. The paper is easy to follow and the authors explain their contributions well. The technical part in the main article, although concise, highlights the major part of the proof.\n2. The contributions are valuable. The sample complexity of learning an average smooth Hölder function class is previous unknown even in the special case of average Lipschitz smoothness and so is the lower bound. The authors also showed the class of average smooth Hölder functions are strictly richer than previous notions like average smooth Lipschitz functions.\n3. The algorithm is novel and has great potential. Indeed the classical ERM fails on learning the average smooth Hölder function class in the distribution free setting so it is conceivable that the algorithm could be used to solve some real problems arising from practice that couldn't be solved before.\n4. The results are quite complete. The upper bound is tight up to only logarithmic factors and the bounds is analogous to classical PAC learning sample complexity bounds.", "weaknesses": "1. I'm not quite convinced that there's no efficient algorithm for the agnostic case unless more evidence is provided. The reduction from agnostic setting to realizable setting is quite generic. But for this learning problem, it feels quite possible that we can find an efficient algorithm. \n2. There are some typos. In line 182 it should be \"There exits a positive number $N$\" instead of a \"function\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review and helpful comments.\n- Regarding computational efficiency, we agree this is very plausible. In fact, after the initial submission we were able to prove a generalization of Proposition 3.2 in the agnostic case, with an excess error decaying as $\\frac{1}{\\sqrt{n}}$ (instead of $\\frac{1}{n}$). We believe that repeating the analysis of Theorem 4.1 (realizable learning algorithm), when paired with this additional result leads to a computationally efficient agnostic learning algorithm with the same guarantee as Theorem 5.1. up to constants.\n- We thank the reviewer for drawing our attention to typos, which we will fix.\n- Regarding learning subclasses: This is an intriguing direction for future work. Notably, learning smoothness classes as a whole is a classically studied problem in non-parametric statistics (see for example the books by Gyorfi et al., or by Gine and Nickl).\n- Regarding applications and comparison to PAC: Thank you for these suggestions, we will indeed make an effort to include them in the final version if space permits.\n- Regarding distribution-free learning: Indeed, the sample complexity of classically studied function classes (e.g. Holder, Sobolev, Besov etc.) are well studied and provided in the references we mention in the introduction. We will emphasize this in the revision and explicitly mention such results."}]

Author rebuttal:

Meta-review: All the reviewers agreed that the the paper is well-written and the subject is important. The extended discussions within the program committee (ACs, SAC, reviewers) discussed the novelty of the submission with respect to the COLT 2021 paper (where the submission extends it to the Hölderian setting), concluding that it may be somewhat limited. However, the result does contribute to our understanding of this setting, and there could be techniques of interest, and thus the paper is accepted.
Decision: Accept (poster)