收斂率概述
在演算法最佳化過程中經常會遇到收斂（Convergence）問題， 尤其目前的深度學習盛行， 如何設計更高效的收斂演算法， 是個極大的挑戰。
而如何評價收斂的快慢呢？ 這就是收斂率的計算， 在這裡我們主要概述一下什麼是收斂率。 因為這個概念用的不是很廣泛， 大家都知道是什麼含義， 但是如何計算，卻不很清楚。
一， 常見的收斂方法
1.1 Bisection方法
每次數列的限制到收斂點的上一次距離的一般距離之內。
這樣如果把這種與收斂點的距離記為誤差， 那麼誤差是2的負的冪次方運算。
如果對邊界值取對數後， 我們發現這個誤差的對數是k的線性函式。
1.2 Fix Point 方法
另外一種常見情況是Fix
Point的方式。 其實我們常見的牛頓法和這個固定點方法是類似的。對於這種情況我們認為兩個點之間是有個函式關係式的。 或者說，
存在一個函式g（x）的曲線， 上一個點的值就是下個點的輸入。 等價於這個曲線與y=x的正斜線之間有個關係。 如下圖所示。
那麼會有兩種情況的收斂到兩個線的交點。
在這種情況下， 我們會有這個線的斜率的絕對值必須小於1。 為什麼會有這個結論呢？ 因為如果斜率絕對值大於1後， 就不會收斂了。
如下圖所示， 當斜率大於1後， 越來越發散， 就不會收斂了。 因此對於斜率的結論是成立。 那麼， 我們連續縮放到k=1的時候， 就有一個冪指數出現了。 並且它的底是一個小於1的值。
這時候，我們對這個表示式取對數。
也有類似結論就是， 這個誤差的對數是K的線性函式。
1.3 Newton方法
牛頓法就是透過切線與橫軸的交點找到第二個點。然後就能反覆找到曲線與橫軸的交點。
根據牛頓法可以得到它的迭代公式如下，
如果我們把這個迭代公式改寫一下， 可以看出牛頓法其實是Fixed Point點法的一個特例。 我們知道固定點法最後是要求g（x）=x，
就是g（x）曲線和y=x斜線的交點。 而在這種要求下， 同樣可以得到， 牛頓法最後的點是f（x）曲線與橫軸的交點。
1.4 Quasi-Newton方法 (近似牛頓方式)
如果把牛頓法的切線的要求放寬一些， 或者近似計算我們就得到了割線法（Secant）。
Secant方法
和牛頓法幾乎一樣， 如下圖：
從上圖上看我們可以看出來， 似乎和牛頓法一樣， 但是斜線好像又不是切線。對的， 這個斜線不是切線， 是一個近似。 首先我們看一下Secant方法的表示式。 我們看到就是把切線寫成 Δf（x） / Δx。
這樣的好處很明顯， 就是不用求導數了， 但是壞處是需要多快取再前面一個點的值。
如果我們稍微修改一下Secant方法， 我們就能夠得到另外一個Quasi-Newton方法，
False position方法
或者regula falsi方法， 有個好聽的中文名叫盈不足術。
直觀上， 我們發現， 這裡似乎距離牛頓法更遠了， 從x1到x3， 所有的切線近似線， 居然有個點不變。 這是為什麼呢？
首先根據Secant的公式， 我們進一步化解， 很容易就化解到一個對稱的形式。
我們對這個對稱形式在選擇找新的點的時候， 我們不是按順序快取前兩個點， 而是快取兩個點是的這兩個點儘量還是橫軸的不同的兩邊。
那麼這種儘量讓快取的點在橫軸兩邊的方式有什麼優點呢？
因為Secant方法是導數的近似， 有時候會很容易就發散了， 但是這種改進後， 變得又快又不太容易發散。
但是這也有個缺點，就是在某些情況下變得不能收斂了。 因為不是快取前兩個點的斜率近似， 這樣的斜線很可能近似誤差太大了。
其實False Position方法就是已經有點插值（Interpolation）的思想了。 更多更復雜的插值思想就不更多的介紹了。
二， 收斂率的階和值
總的說來， 儘管上面講了很多常用收斂方法， 但是總體主要是Bi-section 和Fixed-point方法。 那麼怎麼衡量收斂的快慢呢？ 要注意的是這裡主要是關注快慢， 而不是穩定（Robust）性。
為了比較， 我們先看一下對於收斂率的定義。 這個定義也非常簡單， 就是連續兩次誤差的比值的極限。 首先， 根據收斂我們幾乎可以確定這個比值u不可能大於1，否則就是發散數列了。 所以有
0<= μ <= 1
那麼我先來看一下， Bi-Section和Fixed-Point方法按這個定義的結果。 根據上圖， 或者前面的定義很容易知道 Bi-Section方法中
μ=1/2
，而Fixed-Point方法中
μ=λ
，並且0<λ<1。 根據上面誤差對數是一個線性圖， 我們把這兩個方法都成為線性收斂（linear convergence）。 所以這種定義又成為
Q-linear convergence
， 因為是連續（successive）兩項的商值（
Q
uotient）。
但是除了開區間的（0， 1）不是還有兩個值0和1麼？ 對的。
如果在k 趨向無窮的時候 μ-->0 那麼我們稱為converge superlinearly次線性。
如果在k 趨向無窮的時候 μ-->1 那麼我們稱為converge sublinearly超線性。
2.1 Sublinearly 次線性
對於次線性情況下， 有一個特例就是如果連續兩個修正值（不是誤差）之間的比值也是趨於1的情況的話， 那麼稱為
converges logarithmically 對數收斂
#FormatImgID_29##FormatImgID_30#
2.2 Superlinearly 超線性
如果在超線性情況下， 我們調整商的分母的階（Order）
q > 1
， 我們找到一個高階分母的商收斂到一個非零正數。 那麼我們成為q次超線性收斂。
當q=2的時候， 又稱為二次收斂
Q -
quadratic convergence,
當q=3的時候， 又稱為三次收斂
Q -
cubic convergence,
為了更好的理解， 我們舉例下面四個誤差數列： a， b， c， d
我們畫出他們的對數圖（
k - log { e（k）
}）， 我們就能比較一下線性， 線性， 超線性， 次線性的區別了。
三， 收斂率的估算
我們假設是線性或者超線性收斂的，那麼我們知道階肯定是大於等於1的。 在這種情況下， 我們透過如下近似的公式來估算階， 透過連續的三個誤差， 兩兩比值的log值後的比值來進行估算。 如果估算到1的時候， 我們還要進一步確認是否是次線性的。
但是這樣似乎還是不能直接估算出來這個階， 因為不知道收斂值r。 這裡我們對於Fixed-Point的情況進行進一步細看。
我們先看根據泰勒Taylor展開計算的收斂率：
當
導數在收斂點不為0
的時候， 很明顯就是線性收斂的情況， 跟我們前面分析的一致。 如果假設在收斂點， 二階導數不為零， 那麼可以得到是2次超線性的結果。
那麼更一般的， 我們可以進一步改善估算公式：
因此對於固定點收斂的情況， 我們可以用如下公式進行估算。
總結來說，
對於收斂率來說不是很簡單的事情， 首先對於線性收斂的時候， 很多收斂率是收斂後（0，1）之間的值。
而非線性（次線性，超線性）收斂率往往就和表示式相關了。 如果對這個有理解之後， 就能看明白“Francis
Bach”在總結目標函式本身的連續和凸性， 以及演算法的隨機性對收斂率的總結了：
參考：
https：//
en。wikipedia。org/wiki/R
ate_of_convergence
https：//
en。wikipedia。org/wiki/R
oot-finding_algorithm
http：//www。
math-cs。gordon。edu/cour
ses/ma342/handouts/rate。pdf
http：//
learning。mpi-sws。org/ml
ss2016/slides/mlss_2016_cadiz_slides。pdf