Robustness and Generalization III: Quantile-Value and Truncated-Mean Generalization Bounds for Pseudo-Robust AlgorithmsResearch Paper
Classical generalization bounds control the gap between the expected loss of a learned hypothesis and its average loss on the training sample. The average is sensitive to outliers: when a non-negligible fraction of the sample is corrupted, the mean loss stops describing the quality of a solution, and quantile-type summaries such as the median become the…