  In this work, we aim to characterize the statistical complexity of realizable
regression both in the PAC learning setting and the online learning setting.
Previous work had established the sufficiency of finiteness of the fat
shattering dimension for PAC learnability and the necessity of finiteness of
the scaled Natarajan dimension, but little progress had been made towards a
more complete characterization since the work of Simon (SICOMP '97). To this
end, we first introduce a minimax instance optimal learner for realizable
regression and propose a novel dimension that both qualitatively and
quantitatively characterizes which classes of real-valued predictors are
learnable. We then identify a combinatorial dimension related to the Graph
dimension that characterizes ERM learnability in the realizable setting.
Finally, we establish a necessary condition for learnability based on a
combinatorial dimension related to the DS dimension, and conjecture that it may
also be sufficient in this context. Additionally, in the context of online
learning we provide a dimension that characterizes the minimax instance optimal
cumulative loss up to a constant factor and design an optimal online learner
for realizable regression, thus resolving an open question raised by Daskalakis
and Golowich in STOC '22.
