Asymptotic sequential Rademacher complexity of a finite function class
This work provides theoretical insights into sequential learning complexity, but it is incremental as it builds on existing sublinear expectation theory.
The authors tackled the problem of characterizing the large-sample limit of sequential Rademacher complexity for finite function classes, showing it equals the viscosity solution of a G-heat equation and relates to multidimensional G-normal random variables, with results including derived upper and lower bounds.
For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a $G$-heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $G$-normal random variable. We illustrate this result by deriving upper and lower bounds for the asymptotic sequential Rademacher complexity.