Cross-Validation Error Dynamics in Smaller Datasets
International Conference on Machine Learning 2025
Bethany Austhof, Lev Reyzin
Abstract
Cross-validation (CV) is the de facto standard for estimating a model’s generalization performance, but in smaller datasets it exhibits an underappreciated quirk: across folds, training and test errors are strongly negatively correlated, while training and holdout errors show a moderate anticorrelation and test versus holdout errors are essentially uncorrelated. Herein, we document these phenomena empirically, on both real and synthetic datasets under AdaBoost and introduce a simple generative model that explains them. By viewing each CV split as hypergeometric sampling from a finite population and incorporating an overfitting parameter δ that shifts expected errors on train, test, and holdout sets, we derive closed-form expressions for the covariances among observed error rates. Our analysis shows that sampling-induced anticorrelation dominates in small datasets, while overfitting contributes an additional negative term, thus accounting for the observed error dynamics. We discuss the limitations of our approach and suggest directions for more refined models and extensions to regression settings.
Non-Adaptive Learning of Random Hypergraphs with Queries
58th IEEE International Symposium on Information Theory 2025
Bethany Austhof, Lev Reyzin, Erasmo Tani
Abstract
We study the problem of learning a hidden hypergraph G = (V, E) by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: “Does this set S ⊆ V contain at least one full hyperedge?” In this model, it is known (Abasi and Nader, 2019) that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than Ω(min{m2 log n, n2 }) even when the hypergraph is constrained to be 2-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. (2019) overcame this lower bound in the setting in which G is a graph by assuming that the graph learned is sampled from an Erdős-Rényi model. We generalize the result of Li et al. to the setting of random k-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.
A Model for Optimizing Recalculation Schedules to Minimize Regret
International Symposium on Artificial Intelligence and Mathematics 2024
Bethany Austhof, Lev Reyzin
Abstract
In this paper we analyze online problems from the perspective of when to switch solutions when the cost is of doing so is high – we call such a solution change a “recalculation.” We analyze this problem under the assumption we have algorithms that achieve per-round regret (which can be otherwise thought of as point-wise error, or other wellstudied quantities) of the form O(1/t^ε) after seeing t data-points. We study schedules with a constant number and an increasing number of recalculations in the total number of datapoints, and we examine when achieving optimal cumulative regret is possible.
The set of ratios of derangements to permutations in digraphs is dense in [0,1/2]
Electronic Journal of Combinatorics. Vol. 29(1), p.1.8.
Bethany Austhof, Nick Christo, Patrick Bennett
Abstract
A permutation in a digraph G = (V, E) is a bijection f : V → V such that for all v ∈ V we either have that f fixes v or (v, f(v)) ∈ E. A derangement in G is a permutation that does not fix any vertex. In [1] it is proved that in any digraph, the ratio of derangements to permutations is at most 1/2. Answering a question posed in [1], we show that the set of possible ratios of derangements to permutations in digraphs is dense in the interval [0, 1/2].
Nearly-Regular Hypergraphs and Saturation of Berge Stars
Electronic Journal of Combinatorics. Vol. 26(4), p.4.49.
Bethany Austhof, Sean English
Abstract
Given a graph G, we say a k-uniform hypergraph H on the same vertex set contains a Berge-G if there exists an injection φ : E(G) → E(H) such that e ⊆ φ(e) for each edge e ∈ E(G). A hypergraph H is Berge-G-saturated if H does not contain a Berge-G, but adding any edge to H creates a Berge-G. The saturation number for Berge-G, denoted satk(n, Berge-G) is the least number of edges in a k-uniform hypergraph that is Berge-G-saturated. We determine exactly the value of the saturation numbers for Berge stars. As a tool for our main result, we also prove the existence of nearly-regular k-uniform hypergraphs, or k-uniform hypergraphs in which every vertex has degree r or r − 1 for some r ∈ Z, and less than k vertices have degree r − 1.