Deep learning theory of distribution regression with CNNs

Abstract

We establish a deep learning theory for distribution regression with deep convolutional neural networks (DCNNs). Deep learning based on structured deep neural networks has been powerful in practical applications. Generalization analysis for regression with DCNNs has been carried out very recently. However, for the distribution regression problem in which the input variables are probability measures, there is no mathematical model or theoretical analysis of DCNN-based learning theory. One of the difficulties is that the classical neural network structure requires the input variable to be a Euclidean vector. When the input samples are probability distributions, the traditional neural network structure cannot be directly used. A well-defined DCNN framework for distribution regression is desirable. In this paper, we overcome the difficulty and establish a novel DCNN-based learning theory for a two-stage distribution regression model. Firstly, we realize an approximation theory for functionals defined on the set of Borel probability measures with the proposed DCNN framework. Then, we show that the hypothesis space is well-defined by rigorously proving its compactness. Furthermore, in the hypothesis space induced by the general DCNN framework with distribution inputs, by using a two-stage error decomposition technique, we derive a novel DCNN-based two-stage oracle inequality and optimal learning rates (up to a logarithmic factor) for the proposed algorithm for distribution regression.

Appendix

1.1 The sequence factorization lemma

Lemma 1

([36]) Let $s\ge 2$ and $W=(W_k)_{k=-\infty }^{\infty }$ be a sequence supported in $\{0,1,...,\mathcal {M}\}$ with $\mathcal {M}\ge 0$. Then there exists a finite sequence of filters $\{\omega ^{(j)}\}_{j=1}^p$ each supported in $\{0,1,...,s\}$ with $p\le \lceil \frac{\mathcal {M}}{s-1}\rceil$ such that the following convolutional factorization holds true

$$\begin{aligned}W=\omega ^{(p)}*\omega ^{(p-1)}*\cdots *\omega ^{(2)}*\omega ^{(1)}. \end{aligned}$$

1.2 The Cauchy bound of polynomial roots and Vieta’s formula of polynomial coefficients

Lemma 2

If $w=\left\{ w_{j}\right\} _{j \in \mathbb {Z}}$ is a real sequence supported in $\{0, \ldots , K\}$ with $w_{K}=1$, then all the complex roots of its symbol $\widetilde{w}(z)=\sum _{j=0}^{K} w_{j} z^{j}$ are located in the disk of radius $1+\max _{j=0, \ldots , K-1}\left| w_{j}\right|$, the Cauchy bound of $\widetilde{w}$. If we factorize $\widetilde{w}$ into monic polynomials of degree at most s, then all the coefficients of these factor polynomials are bounded by $s^{\frac{s}{2}}\left( 1+\max _{j=0, \ldots , K-1}\left| w_{j}\right| \right) ^{s} \le$ $s^{\frac{s}{2}}\left( 1+\Vert w\Vert _{\infty }\right) ^{s}$.

1.3 The covering number bound of the function set $\mathcal {H}_{J+1}^l$

Lemma 3

For any $l\in \{1,2,...,(2N+3)\widetilde{d}\}$ with $\widetilde{d}=\lfloor (d+J s) / d\rfloor$. The covering number of $\mathcal {H}_{J+1}^l$ satisfies

$$\begin{aligned}\log \mathcal {N}(\mathcal {H}_{J+1}^l,\epsilon ,\Vert \cdot \Vert _{C(\Omega )})\le \mathcal {A}_1 N \log \frac{\widehat{R}}{\epsilon }+\mathcal {A}_2 N \log N, \ 0<\epsilon \le 1, \end{aligned}$$

where $\mathcal {A}_1$, $\mathcal {A}_2$ and $\widehat{R}$ are defined as in Lemma 6.

Proof

Since the function set $\mathcal {H}_{J+1}^l$ inherits the substructure up to $(J+1)$th-layer of the hypothesis space $\mathcal {H}_{R, N}^{\mathcal {P}(\Omega )}$, the proof can be derived by following the similar procedures of the proof in Lemma 4 and Lemma 6.

For any $l\in \{1,2,...,(2N+3)\widetilde{d}\}$ and any $H\in \mathcal {H}_{J+1}^l$, if we choose another function $\widetilde{H}$ in $\mathcal {H}_{J+1}^l$ induced by $\widetilde{\omega }^{(j)}$ for $j=1,2,...,J$, $\widetilde{b}^{(j)}$ for $j=1,2,...,J+1$, $\widetilde{F}^{(J+1)}$, satisfying the restriction that $\left\| \omega ^{(j)}-\widetilde{\omega }^{(j)}\right\| _{\infty }\le \epsilon$ for $j=1,2,...,J$, $\left\| b^{(j)}-\widetilde{b}^{(j)}\right\| _{\infty }\le \epsilon$ for $j=1,2,...,J+1$, $\left\| F^{(J+1)}-\widetilde{F}^{(J+1)}\right\| _{\infty }\le \epsilon$, $\left\| c-\widetilde{c}\right\| _{\infty }\le \epsilon$, then via a similar way of getting 3.18 in Lemma 6, we have

$$\begin{aligned} \nonumber \left\| H-\widetilde{H}\right\| _{C(\Omega )}=&\left\| \left( F^{\left( J+1\right) } \mathfrak {D}_{d}(h^{\left( J\right) }(x))-b^{\left( J+1\right) }\right) _l-\left( \widetilde{F}^{\left( J+1\right) } \mathfrak {D}_{d}(\widetilde{h}^{\left( J\right) }(x))-\widetilde{b}^{\left( J+1\right) }\right) _l\right\| _{C(\Omega )}\\ \nonumber \le&\left\| \left( F^{\left( J+1\right) } \mathfrak {D}_{d}(h^{\left( J\right) }(x))-b^{\left( J+1\right) }\right) -\left( \widetilde{F}^{\left( J+1\right) } \mathfrak {D}_{d}(\widetilde{h}^{\left( J\right) }(x))-\widetilde{b}^{\left( J+1\right) }\right) \right\| _{l^{\infty }(\Omega )}\\ \le&6J^2((s+1)R)^J\epsilon \le 6d^2((s+1)R)^{d-1}\epsilon :=\check{\epsilon }. \end{aligned}$$

(1.1)

We observe that

$$\check{\epsilon }=6d^2((s+1)R)^{d-1}\epsilon <95d^2N^4((s+1)R)^{d+1}\epsilon =\widehat{\epsilon }$$

which is defined in 3.19 and that the free parameters till $(J+1)$-th layer in $\mathcal {H}_{J+1}^j$ is not larger than free parameters till $(J+2)$-th layer in $\mathcal {H}_{R,N}^{\mathcal {P}(\Omega )}$. Hence, by taking a $\epsilon$ net of the set of free parameters in $\omega ^{(j)}$ for $j=1,2,...,J$, $b^{(j)}$ for $j=1,2,...,J+1$, and $F^{(J+1)}$, we derive that

$$\mathcal {N}\left(\mathcal {H}_{J+1}^l,\check{\epsilon },\Vert \cdot \Vert _{C(\Omega )}\right)\le N^{\mathcal {A}_2N}\left( \frac{\widehat{R}}{\check{\epsilon }}\right) ^{\mathcal {A}_1N},$$

which completes the proof after taking the logarithm.$\square$