Omnipredictors for Regression and the Approximate Rank of Convex
  Functions
Parikshit Gopalan Princewill Okoroafor Prasad Raghavendra Abhishek Shetty Mihir Singhal
Consider the supervised learning setting where the goal is to learn to
predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An
\textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class
$\mathcal C$ of hypotheses is a predictor whose predictions incur less expected
loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$.
Since the work of [GKR+21] that introduced the notion, there has been a large
body of work in the setting of binary labels where $\mathbf y \in \{0, 1\}$,
but much less is known about the regression setting where $\mathbf y \in [0,1]$
can be continuous. Our main conceptual contribution is the notion of
\textit{sufficient statistics} for loss minimization over a family of loss
functions: these are a set of statistics about a distribution such that knowing
them allows one to take actions that minimize the expected loss for any loss in
the family. The notion of sufficient statistics relates directly to the
approximate rank of the family of loss functions.
  Our key technical contribution is a bound of $O(1/\varepsilon^{2/3})$ on the
$\epsilon$-approximate rank of convex, Lipschitz functions on the interval
$[0,1]$, which we show is tight up to a factor of $\mathrm{polylog}
(1/\epsilon)$. This yields improved runtimes for learning omnipredictors for
the class of all convex, Lipschitz loss functions under weak learnability
assumptions about the class $\mathcal C$. We also give efficient omnipredictors
when the loss families have low-degree polynomial approximations, or arise from
generalized linear models (GLMs). This translation from sufficient statistics
to faster omnipredictors is made possible by lifting the technique of loss
outcome indistinguishability introduced by [GKH+23] for Boolean labels to the
regression setting.