Computable Combinatorial Overfitting Bounds
Computable combinatorial data dependent on generalization bounds are studied. This approach is~based on simplified probabilistic assumptions: it is assumed that the instance space is finite, the labeling function is deterministic, and the loss function is binary. A~random walk across a~set of~linear classifiers with low error rate is used to compute the bound efficiently. The experimental evidence to confirm that this approach leads to practical overfitting bounds in classification tasks is provided.