Technical Summary: Online Realizable Regression and Applications for ReLU Networks

Problem Statement

This paper investigates realizable online regression in the adversarial setting, where no stochastic assumptions or margin conditions are imposed. The core problem is to determine when realizability (the existence of a target hypothesis $h^* \in \mathcal{H}$ that perfectly generates the labels) implies a horizon-free (finite) cumulative loss bound, and to identify the complexity parameters governing this bound.

The authors contrast this with online classification, where even simple classes like Perceptrons can have infinite mistake bounds without margin assumptions. In regression, however, realizability can enforce finite total loss under metric-like losses, even when the analogous classification problem is unlearnable. The study focuses on loss functions $\ell$ that satisfy an approximate triangle inequality (approximate pseudo-metrics), a condition necessary to prevent degenerate scenarios where a learner can predict intermediate labels with negligible loss despite large gaps in the hypothesis space.

Methodology

The paper introduces a generic potential method to upper bound the scaled Littlestone dimension ($D_{\text{onl}}$), an abstract dimension introduced by Attias et al. [2] that characterizes the minimax realizable cumulative loss.

The Entropy Potential Framework

Instead of directly computing $D_{\text{onl}}$, which can be difficult, the authors upper bound it using a Dudley-type entropy integral based on the covering numbers of the hypothesis class $\mathcal{H}$ under the induced sup pseudo-metric $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$.

1. Entropy Potential Definition: For a hypothesis class $\mathcal{H}$ with finite diameter, the entropy potential is defined as:
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   where $N(\mathcal{H}, \varepsilon)$ is the $\varepsilon$-covering number of $\mathcal{H}$ with respect to $d_\ell$.

2. Main Theorem: The authors prove that for any $c$-approximate pseudo-metric loss, the scaled Littlestone dimension is bounded by the entropy potential:
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   The proof utilizes a branch bound argument on realizable scaled Littlestone trees. By analyzing version spaces at each node, they show that the approximate triangle inequality forces any $\varepsilon$-cover to split across the children of a node with gap $\gamma$ when $\varepsilon < \gamma/(2c)$. Integrating this "cover splitting" across scales yields a potential drop proportional to the gap, bounding the total gap along any branch by $\Phi(\mathcal{H})$.

3. Implication: If $\mathcal{H}$ has polynomial covering numbers (i.e., $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$), then $\Phi(\mathcal{H}) < \infty$, implying a horizon-free realizable cumulative-loss bound.

Key Contributions and Results

1. Lipschitz Regression under $\ell_q$ Loss

The authors apply their framework to the class $\mathcal{H}_L$ of $L$-Lipschitz functions on $[-1, 1]^d$ under the loss $\ell_q(y, y') = |y - y'|^q$. They establish a sharp phase transition based on the relationship between $q$ and the dimension $d$:

• Learnable Regime ($q > d$): The entropy potential is finite. The minimax realizable cumulative loss is $\Theta_{d,q}(L^d)$. The authors provide an efficient deterministic proper algorithm based on Lipschitz envelopes (lower and upper bounds) that achieves this bound.
• Unlearnable Regime ($q \leq d$): The entropy potential diverges.
  • If $q < d$, the minimax cumulative loss grows polynomially with the horizon $T$.
  • If $q = d$, the loss grows logarithmically with $T$.
  • In both cases, $D_{\text{onl}}(\mathcal{H}_L) = \infty$.
• Eventual Learnability: For any continuous loss $\ell$ with $\ell(y,y)=0$, the authors show that for $L$-Lipschitz functions, the instantaneous loss $\ell(\hat{y}_t, y_t)$ converges to 0 as $t \to \infty$, regardless of whether the total cumulative loss is finite.

2. Bounded $k$-ReLU Networks

The paper studies the class $\mathcal{H}_{k,d}$ of bounded $k$-ReLU networks (sums of $k$ ReLUs with bounded weights) over $[-1, 1]^d$ with squared loss.

• Regression vs. Classification Separation:
  • Classification: Under 0/1 loss, realizable online classification is impossible for $\mathcal{H}_{2,1}$ (two hidden neurons, 1D input), as the Littlestone dimension is infinite even with bounded weights.
  • Regression: Under squared loss, realizable online regression admits finite total loss.
• Upper Bounds:
  • There exists an (information-theoretic) online algorithm with cumulative loss $O(k^2 \log^4 d) = \tilde{O}(k^2)$.
  • For a single ReLU ($k=1$), there is an efficient algorithm with $O(1)$ cumulative loss, independent of dimension $d$.
• Lower Bounds:
  • A lower bound of $\Omega(k^2 \log(d/k^2))$ is proven, showing the dependence on $k$ and $\log d$ is necessary.
• Computational Hardness:
  • Assuming the Gap-ETH hypothesis, the authors rule out the existence of an efficient proper online learner for $k \geq 2$ that achieves accumulated loss $e^{o(d)}$ in time polynomial in $d$. This suggests that while finite loss is information-theoretically possible, computing it efficiently for proper learners is likely hard.

3. Generalization to Deep Networks

The results are extended to depth-$L$, width-$k$ networks. The minimax realizable cumulative squared loss is shown to be $\tilde{O}(k^L)$, with a matching lower bound of $\Omega(k^L \log(d/k^L))$ when $d/k^L \to \infty$.

Significance and Claims

The paper claims that realizability fundamentally alters the landscape of online learning compared to the agnostic setting. Specifically:

1. Metric Entropy as a Complexity Measure: The authors establish that for realizable regression under approximate pseudo-metrics, the metric entropy (via the entropy potential $\Phi$) is a sufficient and often tight proxy for the online dimension $D_{\text{onl}}$. This provides a concrete, calculable tool for analyzing learnability where abstract dimensions are intractable.
2. Phase Transitions in Nonparametric Regression: The work identifies precise conditions ($q > d$) under which nonparametric Lipschitz regression is horizon-free, contrasting sharply with the unlearnability of classification or regression with $q \leq d$.
3. Neural Network Learnability: The paper highlights a stark separation between classification and regression for ReLU networks. While bounded ReLU networks are unlearnable in the classification setting (infinite Littlestone dimension), they admit finite cumulative loss in the regression setting. However, this learnability comes with caveats: for $k \geq 2$, achieving this loss efficiently via proper learners is likely computationally intractable.
4. Limitations: The authors note that the entropy potential bound is not always tight; there exist classes where $\Phi(\mathcal{H}) = \infty$ but $D_{\text{onl}}(\mathcal{H}) < \infty$. Thus, $\Phi$ serves as an explicit upper bound surrogate rather than a complete characterization in all cases.

The work relies on recent advances in online dimension theory [2] and adapts techniques from stochastic processes (Dudley integrals) to the adversarial online setting, avoiding sequential chaining in favor of standard covers due to the realizability assumption.