ShakyPrepend: A Multi-Group Learner with Improved Sample Complexity
Authors: Lujing Zhang, Daniel Hsu, Sivaraman Balakrishnan
Organizations: Department of Statistics and Data Science Carnegie Mellon University · Computer Science Department Data Science Institute Columbia University · Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University
Multi-group learning is a learning task that focuses on controlling predictors' conditional losses over specified subgroups. We propose ShakyPrepend, a method that leverages tools inspired by differential privacy to obtain improved theoretical guarantees over existing approaches. Through numerical experiments, we demonstrate that ShakyPrepend adapts to both group structure and spatial heterogeneity. We provide practical guidance for deploying multi-group learning algorithms in real-world settings.
Figures & tables
Figure 1: Criterion-selection setup. Top: Ground truth (orange) and noisy training samples (blue). Bottom: Groups are constructed so that the worst-group loss is not aligned with the total loss.
Figure 2: Criterion selection (large sample). Total loss (left) and worst-group loss (right) when tuning hyperparameters by total loss vs. worst-group loss (20 runs; 26,000 training points per run).
Figure 3: Criterion selection (small sample). Total loss (left) and worst-group loss (right) when tuning hyperparameters by total loss vs. worst-group loss (20 runs; 260 training points per run).
Figure 4: Unbalanced-group setup. Top: Ground truth (orange) and noisy training samples (blue). Bottom: Layered group intervals, where only part of the domain is further refined into smaller subgroups, yielding unbalanced granularity.
Figure 5: Unbalanced-group simulation. Total loss (left) and worst-group loss (right) for Prepend , Group Prepend , and Shaky Prepend (20 runs; 120 training points per run).
Figure 6: Spatial adaptivity. Ground truth, observations ( n=200 ), and Group Prepend predictions under additive Normal noise with standard error in {0,0.1} (rows).
Figure 7: Fractional ablation. Total loss (left) and worst-group loss (right) comparing Shaky Prepend and its fractional variant with tuned step size η∈{0.5,1} (20 runs; 200 training points per run).
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Criterion-selection setup. Left: Ground truth (orange) and noisy training samples (blue). Right: Groups are constructed so that the worst-group loss is not aligned with the total loss.
Figure 9: Predictions produced by Prepend , Group Prepend , Shaky Prepend , and Sleeping Expert (top-left to bottom-right) under additive noise with σ=0.1 . All methods recover the target’s spatial structure.
Figure 10: Predictions produced by Prepend , Group Prepend , Shaky Prepend , and Sleeping Expert (top-left to bottom-right) under no additive noise. All methods recover the target’s spatial structure.