Omnipredicting Single-Index Models with Multi-Index Models
summary
This work constructs omnipredictors for single-index models by a sharp, agnostic analysis of the Isotron algorithm, giving a learner that is eps-competitive for all matching losses with bounded linear comparators, requiring eps^-4 samples and running in nearly-linear time, and improving to eps^-2 samples for bi-Lipschitz links. The output is a multi-index hypothesis with about eps^-2 prediction heads, and a new n log^2 n bounded isotonic-regression solver makes the procedure practical.
AI-written summary · about
chapters (11)
- 0:00Omniprediction overview
- 1:37What is omniprediction
- 12:19Single-index models
- 20:16Goal of omniprediction
- 25:17Existing approaches
- 26:21Main results overview
- 29:14Isotron in realizable/agnostic
- 33:09Omnigap role
- 36:27Efficient algorithm
- 37:50Faster isotonic solver
- 38:53Future directions
related talks
37mOmnipredictors
24mLoss Minimization through the lens of Outcome Indistinguishability
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
30mLearned Indexes in PostgreSQL: Theory & Implementation
37mLearned Indexes: a New Idea for Efficient Data Access #bbuzz
47mA Complex Picture of Multi-task Learning
51mHow to Predict When Estimation is Hard: Algorithms for Learning on Graphs
44mMachine Learning for Faster Optimization