Lunjia Hu, Kevin Tian, Chutong Yang
This paper extends a binary omniprediction algorithm to handle multiclass prediction problems, achieving suboptimality bounds with a sample complexity or regret horizon of approximately ε^{-(k+1)} for k-class predictions.
The paper addresses a complex problem in machine learning called omniprediction, which involves making predictions that are optimally balanced across different types of errors or 'losses'. It extends existing solutions from binary (two-class) to multiclass scenarios, which is more challenging due to the potential for an infinite number of comparator predictors. The authors develop a new algorithm that can handle these multiclass predictions efficiently, providing guarantees on how well the predictions perform relative to a set of benchmarks. This work also introduces a novel framework that could be useful for other problems where multiple goals must be achieved simultaneously.
