Summary
This paper introduces the notion of "average Hölder smoothness", generalizing the notion of Holder smoothness.
Authors 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.
After a long recall on needed notions, authors listed their theorems.
The first notable one (Thm 3.1) controls the backeting entropy of the newly defined class of functions with its covering number.
This theorem is crucial as
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),
2. the covering number is more intuitive and known in classical case.
Then, Thm 3.4 follows, providing the generalization error gap on this class of function depending on the number of sampled data.
The 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.
Finally, lower bounds are computed in the section 6.
Overall, this paper seems self contained and complete, generalizing results obtained on average Lipschitz continuous function class.
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:
- 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$.
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}}$ ?
- If I understand correctly, Thm 3.1 and 3.4 are claimed as contribution, but not Proposition 3.2. Where can we find it?
- Thm 3.4: Why did we lose the $log(1/\varepsilon)$ term from Th 3.1?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
- Cor 3.5: Number of needed data for good generalization is exponential in d.