↗ OpenReview ↗ NeurIPS Homepage ↗ Chat
TL;DR#
Multi-distribution learning aims to train a single predictor that performs well across multiple data distributions. Existing algorithms produce randomized predictors, raising the question of derandomization. This poses challenges as deterministic predictors are preferred for their simplicity and guarantees. The paper investigates the computational complexity of this task.
The paper proves derandomizing multi-distribution learning is computationally hard in general, even when the empirical risk minimization (ERM) is efficient. However, it also identifies a crucial structural condition (label-consistent distributions) that allows for efficient derandomization. A novel algorithm is presented, demonstrating a near-optimal sample complexity for deterministic multi-distribution learning under this condition using a black box reduction.
Key Takeaways#
Why does it matter?#
This paper is crucial because it tackles the computational challenge of derandomizing multi-distribution learning, a significant hurdle in machine learning. Its findings are relevant to researchers working on improving the efficiency and robustness of algorithms dealing with diverse data distributions, especially in the context of fairness and robustness.
Visual Insights#
Full paper#
