Functions with average smoothness: structure, algorithms, and learning
Authors: Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich
JMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, we define a local slope at each point and gauge the function complexity as the average of these values. Since the mean can be dramatically smaller than the maximum, this complexity measure can yield considerably sharper generalization bounds assuming that these admit a refinement where the Lipschitz constant is replaced by our average of local slopes. Our first major contribution is to obtain just such distribution-sensitive bounds. This required overcoming a number of technical challenges, perhaps the most formidable of which was bounding the empirical covering numbers, which can be much worse-behaved than the ambient ones. Our combinatorial results are accompanied by efficient algorithms for smoothing the labels of the random sample, as well as guarantees that the extension from the sample to the whole space will continue to be, with high probability, smooth on average. Along the way we discover a surprisingly rich combinatorial and analytic structure in the function class we define. |
| Researcher Affiliation | Academia | Yair Ashlagi EMAIL Computer Science Department Ben-Gurion University Beer Sheva, Israel Lee-Ad Gottlieb EMAIL Computer Science Department Ariel University Shomron, Israel Aryeh Kontorovich EMAIL Computer Science Department Ben-Gurion University Beer Sheva, Israel |
| Pseudocode | No | The paper describes algorithms in text, for example, under '5. Learning algorithms: training' and provides mathematical formulations for optimization problems (e.g., 'Minimize W = P i [n] wi subject to P i [n] Li L wi |zi yi| i [n] |zi zj| Liρ(xi, xj) i, j [n] 0 wi, zi 1 i [n]'). However, it does not present any structured pseudocode blocks or algorithms in a visual format typically seen in research papers. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing code or links to source code repositories. |
| Open Datasets | No | The paper introduces a theoretical framework for functions with average smoothness on metric probability spaces. It does not refer to any specific real-world datasets for empirical evaluation, nor does it provide access information for any datasets. |
| Dataset Splits | No | The paper is theoretical and does not use any specific datasets that would require training/test/validation splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions in learning theory and algorithm design. It does not describe any experimental setup that would involve specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, presenting mathematical analysis and algorithm descriptions. It does not mention any specific software or programming libraries with version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setups, hyperparameters, or training configurations for empirical evaluations. |