Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory

The paper provides contributions both in the framework it develops, as well as its application to improving existing results in several problem areas. In particular, it suggests guidelines for designing estimators and learning algorithms and provides analysis tools to study them. In addition, it provides some level of unification across problem areas. Specifically, the main contributions are as follows.

(1) We introduce a principled framework to study localization in statistical learning, dubbed the “uniform localized convergence” procedure, which simultaneously provides optimal “direct dependence” on the sample size, correct scaling with problem-dependent parameters, and flexibility to unify various problem settings. Section 2 provides a description of the framework, and explains how it addresses several fundamental challenges.

(2) In the “slow rate” regime, we employ the above ideas to design the first estimator that achieves optimal variance-dependent rates for general function classes. The derivation is based on a novel procedure that optimally penalizes the empirical (centered) second moment. We also establish improved loss-dependent rates for standard empirical risk minimization, which has computational advantages. Section 3 presents these theoretical results (see Section 3.2 for the loss-dependent rate and Section 3.3 for the variance-dependent rate); and Section 4 will illustrate our improvements in non-parametric classes and VC classes.

(3) In the “fast rate” regime, we establish a “uniform localized convergence of gradient” framework for parametrized models, and characterize optimal problem-dependent rates for approximate stationary points and iterative optimization algorithms such as gradient descent and first-order Expectation-Maximization. Our results scale tightly with the gradient norms at the optimal parameter, and improve previous guarantees in non-convex learning, stochastic optimization and missing data problems. See Section 5 for the theoretical results and Sections 6-7 for illustrations of improvements over previous results.

(4) In the “fast rate” regime, we also study supervised learning with structured convex cost, where the hypothesis class can be non-parametric and heavy-tailed. This part of the work has direct relationship to a stream of literature known as “learning without concentration.” Our contributions in this setting lie in technical refinements of the generalization error bounds and some unification between one-sided uniform inequalities and concentration of truncated functions; for this reason we defer its treatment to Section 8.

Denote the empirical risk

$\displaystyle\mathbb{P}_{n}\ell(h;z):=\frac{1}{n}\sum_{i=1}^{n}\ell(h;z_{i}),$

and consider the following straightforward decomposition of the generalization error

$\displaystyle\mathscr{E}(\hat{h})=(\mathbb{P}-\mathbb{P}_{n})\ell(\hat{h};z)+\big{(}\mathbb{P}_{n}\ell(\hat{h};z)-\mathbb{P}_{n}\ell(h^{*};z)\big{)}+(\mathbb{P}_{n}-\mathbb{P})\ell(h^{*};z).$

(2.1)

The main difficulty in studying $\mathscr{E}(\hat{h})$ comes from bounding the first term $(\mathbb{P}-\mathbb{P}_{n})\ell(\hat{h};z)$, since $\hat{h}$ depends on the $n$ samples. The simplest approach, which does not achieve problem-dependent rates, is to bound the uniform error

$$\sup_{h\in\pazocal{H}}(\mathbb{P}-\mathbb{P}_{n})\ell(h;z)$$

over the entire hypothesis class $\pazocal{H}$. In order to obtain problem-dependent rates, a natural modification is to consider uniform convergence over localized subsets of $\pazocal{H}$.

We first give an overview of the traditional “local Rademacher complexity” analysis [3, 26, 79]. Consider a generic function class $\pazocal{F}$ that we wish to concentrate, which consists of real-valued functions defined on $\pazocal{Z}$ (e.g., one can set $f(z)=\ell(h;z)$). Denote

$$\mathbb{P}f:=\mathbb{E}[f(z)],\quad\mathbb{P}_{n}f:=\frac{1}{n}\sum_{i=1}^{n}f(z_{i}).$$

The notation $r>0$ will serve as a localization parameter, and $\delta>0$ will serve for high probability arguments. Let $\psi(r;\delta)$ denote a surrogate function that upper bounds the uniform error within a localized region $\{f\in\pazocal{F}:T(f)\leq r\}$, where we call $T:\pazocal{F}\rightarrow\mathbb{R}_{+}$ the “measurement functional.” Formally, let $\psi$ be a function that maps $[0,\infty)\times(0,1)$ to $[0,\infty)$, which possibly depends on the observed samples $\{z_{i}\}_{i=1}^{n}$. Assume $\psi$ satisfies for arbitrary fixed $\delta,r$, with probability at least $1-\delta$,

$\displaystyle\sup_{f\in\pazocal{F}:T(f)\leq r}(\mathbb{P}-\mathbb{P}_{n})f\leq\psi(r;\delta).$

(2.2)

By default we ask $\psi(r;\delta)$ to be a non-decreasing and non-negative function.³³3Here and in what follows we will assume that such suprema are measurable, namely, the required regularity conditions on the underlying function classes are met (see, e.g., [61, Appendix C], [77, Section 1.7]). The main result of the traditional localization analysis can be summarized as follows. (The statement is obtained by adapting the proof from [3, Section 3.2]; itself more general than the traditional meta-results [3, 26, 79].)

Since its inception, Statement 1 has become a standard tool in learning theory. However, it requires a rather technical proof, and it appears to be loose when compared with the original assumption (2.2)—ideally, we would like to directly extend (2.2) to hold uniformly without sacrificing any accuracy. Moreover, some assumptions in the statement are restrictive and might not be necessary.

We provide a surprisingly simple analysis that greatly improves and simplifies Statement 1. Unlike Statement 1, the following proposition does not require the concentrated functions $g_{f}$ to satisfy the Bernstein condition, and the surrogate function $\psi$ need not to be “sub-root.” Despite placing less restrictions, Proposition 1 is able to establish results that are typically “sharper” than the current blueprint. Note that in the proposition, both the measurement functional $T$ as well as the surrogate function $\psi$ are allowed to be sample-dependent.

The key intuition behind Proposition 1 is that the uniform restatement of the “localized” argument (2.4) is nearly cost-free, because the deviations $(\mathbb{P}-\mathbb{P}_{n})g_{f}$ can be controlled solely by the real valued functional $T(f)$. As a result, we essentially only require uniform convergence over an interval $[r_{0},R]$. The “cost” of this uniform convergence, namely, the additional $\log_{2}(\frac{2R}{r_{0}})$ term in (2.5), will only appear in the form $\log(\delta/\log_{2}(\frac{2R}{r_{0}}))$ in high-probability bounds, which is of a negligible $O(\log\log n)$ order in general.

Formally, we apply a “peeling” technique: we take $r_{k}=2^{k}r_{0}$, where $k=1,2,\dots,\lceil\log_{2}\frac{R}{r_{0}}\rceil$, and we use the union bound to extend (2.4) to hold for all these $r_{k}$. Then for any $f\in\pazocal{F}$ such that $T(f)>r_{0}$ is true, there exists a non-negative integer $k$ such that $2^{k}r_{0}<T(f)\leq 2^{k+1}r_{0}$. By the non-decreasing property of the $\psi$ function, we then have

$$(\mathbb{P}-\mathbb{P}_{n})g_{f}\leq\psi\left(r_{k+1};\delta\left({\log_{2}\frac{2R}{r_{0}}}\right)^{-1}\right)\leq\psi\left(2T(f);\delta\left({\log_{2}\frac{2R}{r_{0}}}\right)^{-1}\right),$$

which is exactly (2.5). Interestingly, the proof of the classical result (Statement 1) relies on a relatively heavy machinery that includes more complicated peeling and re-weighting arguments (see [3, Section 3.1.4]). However, that analysis obscures the key intuition that we elucidate under inequality (2.5).

In this paper, we prove localized generalization error bounds through a unified principle, summarized at a high level in the two-step template below.

Distinct from the blueprint (2.3), the right hand side of our “uniform localized convergence” argument (2.5) contains a “free” variable $T(f)$ rather than a fixed value $r^{*}$. The new principle strictly improves the current blueprint from many aspects, and its merits will be illustrated in the sequel.

Our improvements in the “slow rate” regime originate from the noticeable gap between Proposition 1 and Statement 1, illustrated by the following (informal) conclusion.

Formalizing as well as providing rigorous justification for this conclusion is relatively straightforward: taking the “optimal choice” of $K$ in Statement 1, we can re-write its conclusion as

$\displaystyle(\mathbb{P}-\mathbb{P}_{n})f\leq 20\sqrt{\frac{r^{*}\mathbb{P}f}{B_{e}}}-\frac{r^{*}}{B_{e}}\quad[\text{Statement \ref{state current blueprint}}],$

where the right hand side is of order $\sqrt{{r^{*}\mathbb{P}f}/{B_{e}}}$ when $\mathbb{P}f<r^{*}/B_{e}$, and order $r^{*}/B_{e}$ when $\mathbb{P}f\leq r^{*}/B_{e}$. Our result (2.5) is also of order $r^{*}/B_{e}$ when $\mathbb{P}f\leq r^{*}/B_{e}$. However, for every $f$ such that $\mathbb{P}f>r^{*}/B_{e}$, it is straightforward to verify that under the assumptions in Statetment 1,

	$\displaystyle\psi(2T(f);\delta)\quad$	$\displaystyle{\leq}\quad\psi(2B_{e}\mathbb{P}f;\delta)\quad\text{[Bernstein condition: $T(f)\leq B_{e}\mathbb{P}f$]}$
		$\displaystyle\leq\quad\frac{\sqrt{2B_{e}\mathbb{P}f}}{\sqrt{r^{*}}}\psi(r^{*};\delta)\quad\text{[$\psi(r;\delta)$ is sub-root]}$
		$\displaystyle{\leq}\quad\sqrt{\frac{2{r^{*}}\mathbb{P}f}{B_{e}}}\quad\text{[$r^{*}$ is the fixed point of $B\psi(r;\delta)$]}.$		(2.6)

Therefore, the argument $\psi(2T(f);\delta)\leq\sqrt{{2r^{*}\mathbb{P}f}/{B_{e}}}$ established by (2.3) shows that the “uniform localized convergence” argument (2.5) strictly improves over Statement 1 (ignoring negligible $O(\log\log n)$ factors). Statement 2 indicates that the folklore use of fixed values as straightforward complexity control is somewhat questionable. In the “slow rate” regime, the key point to achieve optimal problem-dependent rates is to bound the generalization error using the function $\psi$. Otherwise the bounds will have the “wrong” dependence on the sample size for all “rich” classes.

Interestingly, the merits of our approach in the “fast rate” regime stem from very different perspectives: the removal of the “sub-root” requirement on $\psi$ allows one to achieve parameter localization; and the added flexibility in the choice of $g_{f}$ allows one to prove one-sided uniform inequalities and uniform convergence of gradient vectors. To better appreciate these, we provide the following informal discussion to help elucidate the key messages. Let $\mu>0$ be the curvature parameter in the “fast rate” regime (a common example is the strong convexity parameter for the loss function). The generalization error is often characterized by the fixed point of $\psi(r;\delta)/\mu$, where $\psi$ is the surrogate function that governs the uniform error of excess risk. The removal of the “sub-root” restriction is crucial because under curvature and smoothness conditions, the uniform error of excess loss typically grows “faster” than the square root function. Consider surrogate functions of the form

$\displaystyle\psi(r;\delta)=\underbrace{\sqrt{a_{n}^{*}r}}_{\text{problem-dependent}}+\underbrace{c_{n}r}_{\text{super-root}},$

(2.7)

where $a_{n}^{*}$ is a problem-dependent rate, and $c_{n}$ satisfies $0<c_{n}<1/(2\mu)$ when the sample size $n$ satisfies mild conditions. We call $c_{n}r$ the benign “super-root” component in the sense that when solving the fixed point equation $r=\psi(r;\delta)/\mu$, that part can be dropped from both side of the equation. As a result, the fixed point solution only depends on order of the problem-dependent component $\sqrt{a_{n}^{*}r}$, and so one obtains problem-dependent rates. In contrast, worst-case parameters will be unavoidable if one wants to use a “sub-root” surrogate function to govern (2.7). In traditional analysis, a loose “sub-root” surrogate function is often obtained via two-sided concentration and Lipchitz contraction, making global Lipchitz constants unavoidable. Furthermore, the added flexibility to choose concentrated functions $g_{f}$ is also useful. In particular, we will show that: 1) our framework unifies traditional value-based uniform convergence and uniform convergence of gradient vectors, which is crucial to study non-convex learning problems and sample-based iterative algorithms; and 2) simple “truncated” functions can be used to established one-sided uniform inequalities that are sharper than two-sided ones, which enable recovery of results in unbounded and heavy-tailed regression problems.

Beyond proving new bounds, an important objective of the paper is to provide some level of unification to the methodology of uniform convergence and localization. Here we present a historical review of uniform convergence and localization, and discuss how the “uniform localized convergence” principle unifies and improves existing approaches. We will overview four general settings where localization plays a crucial role in generalization error analysis and algorithm design: 1) the “slow rate” regime; 2) classification under margin conditions; 3) regression under curvature conditions; and 4) non-convex learning and stochastic optimization (the latter three settings belong to the “fast rate” regime).

Let $\pazocal{V}^{*}$ and $\pazocal{L}^{*}$ be the variance and the “effective loss” at the best hypothesis $h^{*}$:

$\displaystyle\pazocal{V}^{*}:=\textup{Var}[\ell(h^{*};z)],\quad\pazocal{L}^{*}:=\mathbb{P}[\ell(h^{*};z)-\inf_{\pazocal{H}}\ell(h;z)].$

In this section we study finite-sample generalization errors that scale tightly with $\pazocal{V}^{*}$ or $\pazocal{L}^{*}$, which we call problem-dependent rates, without invoking strong convexity or margin conditions.

In the slow rate regime, we assume the loss function to be uniformly bounded by $[-B,B]$, i.e., $|\ell(h;z)|\leq B$ for all $h\in\pazocal{H}$ and $z\in\pazocal{Z}$. This is a standard assumption used in almost all previous works that do not invoke curvature conditions or rely on other problem-specific structure; and our results in the slow rate regime essentially only require this boundedness assumption. Extensions to unbounded targets can be obtained via truncation techniques (see, e.g. [17]), and our problem-dependent results allow $B$ to be very large, potentially scaling with $n$.

We represent the complexity through a surrogate function $\psi(r;\delta)$ that satisfies for all $\delta\in(0,1)$,

$\displaystyle\sup_{f\in\pazocal{F}:\mathbb{P}[f^{2}]\leq r}(\mathbb{P}-\mathbb{P}_{n})f\leq\psi(r;\delta),$

(3.1)

with probability at least $1-\delta$, where $\pazocal{F}$ is taken to be the excess loss class

$\displaystyle\ell\circ\pazocal{H}-\ell\circ h^{*}:=\{{z\mapsto\left(\ell(h;z)-\ell(h^{*};z)\right)}:h\in\pazocal{H}\}.$

(3.2)

(From the perspective of Section 2.2, we choose the excess losses as the “concentrated functions,” and use $T(f)=\mathbb{P}[f^{2}]$ as the “measurement functional”.) To achieve non-trivial complexity control (and ensure existence of the fixed point), we only consider “meaningful” surrogate functions, as stated below.

We note that the above does not place significant restrictions on the choice of the surrogate function. In particular, for the $\psi$ function defined in (3.1) and the excess loss class in (3.2), the left hand side of (3.1) is itself non-decreasing and non-negative; and the boundedness requirement can always be met by setting $\psi(r;\delta)=\psi(4B^{2};\delta)$ for all $r\geq 4B^{2}$. We now give the formal definition of fixed points.

It is well-known that a non-decreasing, non-negative and bounded function only has finite discontinuity points, all of which belong to “discontinuity points of the first kind” [65, Definition 4.26]. Therefore, it is easy to verify that the fixed point of $\varphi(r)$ is the maximal solution to the equation $\varphi(r)=r$.

Given a bounded class $\pazocal{F}$, empirical process theory provides a general way to construct surrogate function by upper bounding the “local Rademacher complexity” $\mathfrak{R}\{f\in\pazocal{F}:\mathbb{P}[f^{2}]\leq r\}$ (see Lemma 5 in Appendix A.6). We give the definition of Rademacher complexity for completeness.

Furthermore, Dudley’s integral bound provides one general solution to construct a computable upper bound on the local Rademacher complexity via the covering number of $\pazocal{F}$. We give the definition of covering number and state Dudley’s integral bound for completeness as well.

In what follows, when comparing different complexity parameters, we often use “$\lor$” to denote the maximum operator, and to interpret correctly, its use should be understood to take precedence over addition but not over multiplication. Throughout we will find it convenient to use “big-oh” notation to simplify various expressions and comparisons that capture order of magnitude effects. For two non-negative sequence $\{a_{n}\}$ and $\{b_{n}\}$, we write $a_{n}=O(b_{n})$, if $a_{n}$ can be upper bounded by $b_{n}$ up to an absolute constant for sufficiently large $n$. The same expression is often used also in the context of probabilistic statements in which case it is interpreted as holding on an event which has a specified (typically “high”) probability. We write $a_{n}=\Omega(b_{n})$ if $b_{n}/a_{n}=O(1)$.

In this section we are interested in loss-dependent rates, which should scale tightly with $\pazocal{L}^{*}:=\mathbb{P}[\ell(h^{*};z)-\inf_{\pazocal{H}}\ell(h;z)]$; the best achievable “effective loss” on $\pazocal{H}$. The following theorem characterizes the loss-dependent rate of empirical risk minimization (ERM) via a surrogate function $\psi$, its fixed point $r^{*}$, the effective loss $\pazocal{L}^{*}$ and $B$.

The loss-dependent rate proved in Theorem 1 contains a complexity parameter $B\pazocal{L}^{*}$ within its $\psi$ function, which may still be much larger than the optimal variance $\pazocal{V}^{*}$. Despite its prevalent use in practice, standard empirical risk minimization is unable to achieve variance-dependent rates in general. An example is given in [56] where $\pazocal{V}^{*}=0$ and the optimal rate is at most $O({\log n}/{n})$, while $\mathscr{E}(\hat{h}_{\textup{ERM}})$ is proved to be slower than $n^{-\frac{1}{2}}$.

We follow the path of penalizing empirical second moments (or variance) [45, 71, 56, 13] to design an estimator that achieves the “right” bias-variance trade-off for general, potentially “rich,” classes. Our proposed estimator simultaneously achieves correct scaling on $\pazocal{V}^{*}$, along with minimax-optimal sample dependence ($n$). Besides empirical first and second moments, it only depends on the boundedness parameter $B$, a computable surrogate function $\psi$, and the confidence parameter $\delta$. All of these quantities are essentially assumed known in previous works: e.g., [45, 71] require covering number of the loss class, which implies a computable surrogate $\psi$ via Dudley’s integral bound; and estimators in [56, 13] rely on the fixed point $r^{*}$ of a computable surrogate $\psi$.

In order to adapt to $\pazocal{V}^{*}$, we use a sample-splitting two-stage estimation procedure (this idea is inspired by the prior work [13]). Without loss of generality, we assume access to a data set of size $2n$. We split the data set into the “primary” data set $S$ and the “auxiliary” data set $S^{\prime}$, both of which are of size $n$. We denote $\mathbb{P}_{n}$ the empirical distribution of the “primary” data set, and $\mathbb{P}_{S^{\prime}}$ the empirical distribution of the “auxiliary” data set.

As we will present later, it is rather trivial to obtain a qualified preliminary estimate $\widehat{{\pazocal{L}}^{*}_{0}}$ via empirical risk minimization. Therefore, we firstly introduce the second-stage moment-penalized estimator, which is more crucial and interesting.

Given an arbitrary preliminary estimate $\widehat{{\pazocal{L}}^{*}_{0}}\in[-B,B]$, we can prove that the generalization error of the moment-penalized estimator $\hat{h}_{\textup{MP}}$ is at most

$\displaystyle\mathscr{E}(\hat{h}_{\textup{MP}})\leq 2\psi\left(c_{0}\left[\pazocal{V}^{*}\lor(\widehat{{\pazocal{L}}^{*}_{0}}-\pazocal{L}^{*}_{0})^{2}\lor r^{*}\right];\frac{\delta}{C_{n}}\right),$

(3.6)

with probability at least $1-\delta$, where $c_{0}$ is an absolute constant, and $r^{*}$ is the fixed point of $16B\psi(r;\frac{\delta}{C_{n}})$. Moreover, the first-stage estimation error will be negligible if

$\displaystyle(\widehat{{\pazocal{L}}^{*}_{0}}-\pazocal{L}^{*}_{0})^{2}\leq O\left(r^{*}\right).$

(3.7)

It is rather elementary to show that performing the standard empirical risk minimization on $S^{\prime}$ suffices to satisfy (3.7), provided an additional assumption that $\psi$ is a “sub-root” function. We now give our theorem on the generalization error following this two-stage procedure.

Recall that our loss-dependent rates and variance-dependent (moment-penalized) rates are

	$\displaystyle\mathscr{E}(\hat{h}_{\textup{ERM}})\leq O\left(\psi(B\pazocal{L}^{*};\delta)\lor\frac{r^{*}}{B}\right)\quad[\text{Theorem \ref{thm slow}}],$		(4.1)
	$\displaystyle\mathscr{E}(\hat{h}_{\textup{MP}})\leq O\left(\psi(\pazocal{V}^{*};\delta)\lor\frac{r^{*}}{B}\right)\quad[\text{Theorem \ref{thm variance rate}}],$		(4.2)

respectively. In contrast to our results (4.1) (4.2), the best known loss-dependent rates [3] and variance-dependent rates [13] are

	$\displaystyle\mathscr{E}(\hat{h}_{\textup{ERM}})\leq O\left(\sqrt{\frac{\pazocal{L}^{*}r^{*}}{B}}\lor\frac{r^{*}}{B}\right)\quad[\text{existing result \cite[cite]{[\@@bibref{Number}{bartlett2005local}{}{}]}}],$		(4.3)
	$\displaystyle\mathscr{E}(\hat{h}_{\text{previous}})\leq O\left(\sqrt{\frac{\pazocal{V}^{*}r^{*}}{B^{2}}}\lor\frac{r^{*}}{B}\right)\quad[\text{existing result \cite[cite]{[\@@bibref{Number}{foster2019orthogonal}{}{}]}}],$		(4.4)

respectively (we use $\hat{h}_{\text{previous}}$ to denote the previous best known moment-penalized estimator proposed in [13]). To illustrate the noticeable gaps between our new results and previous known ones, we compare the two different variance-dependent rates, (4.2) and (4.4) on two important families of “rich” classes: non-parametric classes of polynomial growth and VC classes. The implications of this comparison will similarly apply to loss-dependent rates.

Before presenting the advantages of the new problem-dependent rates, we would like to discuss how to compute them. In Theorem 1 and Theorem 2, the class of concentrated functions, $\pazocal{F}$, is the excess loss class $\ell\circ\pazocal{H}-\ell\circ h^{*}$ in (3.2). As we have mentioned in earlier sections, a general solution for the $\psi$ function is to use Dudley’s integral bound (Lemma 1). Knowledge of the metric entropy of the excess loss class,

$\displaystyle\log\pazocal{N}(\varepsilon,\ell\circ\pazocal{H}-\ell\circ h^{*},L_{2}(\mathbb{P}_{n})),$

can be used to calculate Dudley’s integral bound and construct the surrogate function $\psi$ needed in our theorems. Note that there is no difference between the metric entropy of the excess loss class and metric entropy of the loss class itself: from the definition of covering number, one has

$\displaystyle\pazocal{N}(\varepsilon,\ell\circ\pazocal{H}-\ell\circ h^{*},L_{2}(\mathbb{P}_{n}))=\pazocal{N}(\varepsilon,\ell\circ\pazocal{H},L_{2}(\mathbb{P}_{n})).$

We comment that almost all existing theoretical literature that discusses general function classes and losses [3, 45, 71, 13] imposes metric entropy conditions on the loss class/excess loss class rather than the hypothesis class $\pazocal{H}$, and we follows that line as well to allow for a seamless comparison of the results. As a complement, we will discuss how to obtain such metric entropy conditions for practical applications in Section 4.2.

In practical applications it is more standard to consider metric entropy conditions of the hypothesis class $\pazocal{H}$. In view of this, we introduce two important settings where the metric entropy on the loss/excess loss class can be obtained from metric entropy conditions on the hypothesis class $\pazocal{H}$. Thus, the improvements illustrated in Section 4.1 can be directly transferred to these application areas.