Near-optimal learning with average Hölder smoothness
Authors: Guy Kornowski, Steve Hanneke, Aryeh Kontorovich
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Steve Hanneke Department of Computer Science Purdue University steve.hanneke@gmail.com Aryeh Kontorovich Department of Computer Science Ben-Gurion University of the Negev karyeh@cs.bgu.ac.il Guy Kornowski Department of Computer Science and Applied Mathematics Weizmann Institute of Science guy.kornowski@weizmann.ac.il |
| Pseudocode | No | The paper does not include any clearly labeled pseudocode or algorithm blocks. Algorithmic procedures are described in prose. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies using datasets, hence no information about public datasets or their access is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | The paper is theoretical and does not discuss experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setups with hyperparameters or training configurations. |