---
title: '深度學習理論-1. Approximation: preface'
disqus: hackmd
---

# 深度學習理論 1 Approximation: preface

> [name=黃志勝 Chih-Sheng (Tommy) Huang]
>
**此份筆記為「Deep learning theory lecture notes」翻譯，[原始文章路徑](https://mjt.cs.illinois.edu/dlt/?fbclid=IwAR1UOFJJKbpIf2-tMiK4TQgiVupxVaCeZUFzFtQZJJhADGc2kcfqUOPpqkY#sec:apx:omitted)
原著作者為[Matus Telgarsky]([e-mail])**

我盡量不要直譯，所以有疑問的部分我會將原文放置在內文。

越寫越覺得很難將內容物白話。

---
第0章前言已經提到學習演算法基本上是要將經驗風險(emperical risk)降到最小。
從第0章介紹已經知道我們是希望我們的預測器(Predictors, $F$)(例如:一個特定架構的神經網路)會有$\bar f \in F$ 使得我們有小的$R(f)$和小的複雜度。因此我們可以先假設說$F$是一個在特定類別下低複雜度的預設器，我們的目的是希望讓 ${\rm {inf}}_{f \in F}R(f)$ 越小越好。

## 傳統的作法(Classifical Setup)
在傳統的標準程序是設定一個比較基準(Natural baseline)，例如和所有可量測且連續的函數(measurable and continuous functions)比較:
$$
{\rm {inf}}_{f \in F}R(f) \qquad vs. \qquad {\rm {inf}}_{g \, {\rm {continuous}}}R(g)
$$

我們希望能限制住 ${\rm {sup}}_{g \, {\rm {cont.}}}{\rm {inf}}_{f \in F}R(f) - R(g)$的上界
但這個條件很難被滿足
所以我們要給予一些假設，當$l$(損失函數)為$\rho-\rm Lipschitz$，則

$$
R(f)-R(g)= \int{(l(yf(x))-l(yg(x)))}\,{\rm d}\mu(x,y) \\
\leqslant \int{\rho |yf(x)-yg(x)|} \,{\rm d}\mu(x,y)
= \rho \int{|f(x)-g(x)|}\,{\rm d}\mu(x,y)
$$

所以整個$R(f)-R(g)$會被$\rho \int{|f(x)-g(x)|}\,{\rm d}\mu(x,y)$給Bound住。
因此會以研究function space的norms為主($\| f-g\|$)。
**Note**:$\rho-\rm Lipschitz$可參考[$\rho-\rm Lipschitz$](https://zh.wikipedia.org/wiki/%E5%88%A9%E6%99%AE%E5%B8%8C%E8%8C%A8%E9%80%A3%E7%BA%8C)。
簡單來看就是${\displaystyle |f(a)-f(b)|\leq K|a-b|\quad \forall a,b\in D}$

<font color=#FF00FF> **Remark 1.1.** </font>
(***Is this too strenuous?***)
大部分的經典方法大多採用
$$
uniform \, norm:\| f-g\|_u= {\rm {sup}}_{x \in S}|f(x)-g(x)|
$$
並且與連續函數(continuous functions)進行比較。$S$為緊湊集(compact set)。
但如果目標為Lipschitz連續，這意味著我們的函數的複雜度會隨著維度的增加呈現指數增長。
(***Lower bounds.***)
uniform norm對於證明上界(upper bounds)有一些不錯的性質，但他是否能代表lower bound?在函數之間他們只需要一點有較大的差異，即使函數之間幾乎相同，函數也可以在uniform norm被完美的分離。因此在$L_1$ norms, $\int_{[0,1]}|f(x)-g(x)|\,{\rm d}x$可以被表示為lower bounds。

### How to parameterize function classes.

$$
F := \{x \mapsto f(x;w): w \in R^p\}
$$
$f$為帶有參數($w \in R^p$)的函數，例如第0章介紹的深層神經網路。
Classical perspective: 函數$F$是固定架構和不同參數。
Modern perspective: 函數$F$是和資料和演算法相關的。
這很複雜，但我們只用了norm限制條件:
$$
F_{\|.\|}(r):=\{ {x\mapsto f(x;w): w \in R^p, \|w\|\leqslant r} \}
$$
**範例:** $f(x;W):=a^T\sigma(Wx)$，$a \in R^m$為維度為$m$的固定實數
$$
F_q(r)=\{ x\mapsto f(x;w): \|W\|_{2,q} \} \\
\|W^T\|_{2,q}=(\sum_{j=1}^m {\|W_{j:}\|_2^q})^{1/q}
$$
通常$q=\infty$，$q$對改變$F_{\|.\|}(r)$影響很大。

問題是:
- $q$怎麼影響$F_q$ ?
- 哪個$q$可以找出梯度下降(gradient descent)的輸出 ?

*這邊的$q$我認為是第$q$個參數解的表示，所以參數的解集合為無窮大(前面提到，通常$q=\infty$)。

<font color=#FF00FF> **Remark 1.2.** </font>
雖然norms近期用來評量複雜度受到了很多關注，這個想法依舊經典。例如:1990年代開始興盛於證明深度網路的VC Dimension bounds，然而在P. L. Bartlett 1996很快就證明了即使網路架構(連線數)在固定狀況下，但得到的norms也會不同。

----------------
###### tags: `DeepLearningTheory`