總結優化算法收斂性證明的兩類方法

2021-01-18 KawayiKiwi

這篇文章中，我們總結兩類做數值優化迭代算法收斂性證明的方法，同時也討論了優化算法設計的思路。

1. 簡介

數值優化在工程應用中有非常重要的作用。但在使用優化算法時候，算法的收斂性是我們需要認真考慮的東西，例如我們需要知道梯度下降是一階收斂而牛頓法是二階收斂，因此一般情況下，牛頓法會比梯度下降運行更快。了解收斂性後，我們才能更好地應用算法。這裡，我們總結兩類做數值算法收斂性證明的方法，同時討論以後我們自己設計算法的思路。

2. 不動點類

該類中，收斂性的證明多使用不動點定理(Fixed Point Theorems)進行證明。不動點定理(Fixed Point Theorems)是數學證明中一個非常重要的定理，許多重要的數學定理都是由不動點定理證明的，例如偏微分方程解的存在性、博弈論中納什均衡點的存在性以及我們這裡即將介紹的數值算法的收斂性等。我們首先介紹一下不動點定理，然後介紹如何使用不動點定理進行算法收斂性證明。

簡單地說，對一個函數

巴拿赫固定點定理：對於函數

那麼，

注意到巴拿赫固定點定理不僅給出了不動點的存在性，而且給出了唯一性以及構造不動點的辦法。那麼我們如何使用這個不動點定理來進行算法收斂性證明和指導算法設計呢？給定一個算法，為了證明其收斂性，我們可以將算法的每一次迭代看做一個函數

下面我們通過例子來介紹巴拿赫固定點定理如何指導算法的設計，詳細的證明可以參見更專業的書籍或者論文。

2.1 單個函數的優化

這裡我們考慮下列問題

這裡我們假設

其中

我們定義

觀察上述式子，我們知道對於一般的函數

那麼，根據

因此，要使得

假設

則

可以觀察到，如果我們取。

對算法熟悉的讀者知道，由

其中

上述式子給出

2.2 兩個函數和的優化

這裡我們考慮下列優化問題

問題

根據微積分的定理，我們知道如果

類似上一節中我們構造梯度下降的生成函數的思路，我們需要根據

Forward-Backward Splitting.從

將

其中

因此，我們可以定義

可以看出

Douglas-Rachford Splitting 這裡，為了書寫的方便，我們定義

並定義

其中

注: 可以從上面例子看出，我們有非常多的方法來將優化算法的解表示為某個函數

3. 能量函數類

這裡我們仍然考慮單個函數的優化，我們試圖解決下列優化問題

假設

直覺上講，

下面是幾種常見的能量函數:

當然，這裡列出的能量函數並不完整，例如Fast alteranting direction optimization methods這篇文章中，使用原問題與對偶問題的優化條件的殘差(Primal dual residuals)來定義能量函數。在實際問題中，對於具體的問題如何設計好能量函數，仍然是比較靠科研人員的直覺和經驗。

總結

這篇文章中，我們介紹了兩類證明算法收斂性的方法：固定點類與能量函數類。對於固定點類的算法，我們討論了如何基於固定點的思想來設計新的算法。這裡的總結一定是不完全的，隨著更多地閱讀論文，以後有機會將更多的方法納入這個歸納中。

相關焦點

  • 聽說你了解深度學習最常用的學習算法:Adam優化算法?
    在介紹這個算法時，原論文列舉了將Adam優化算法應用在非凸優化問題中所獲得的優勢：　　直截了當地實現　　高效的計算　　所需內存少　　梯度對角縮放的不變性（第二部分將給予證明）　　適合解決含大規模數據和參數的優化問題
  • 引入Powerball 與動量技術,新SGD優化算法收斂速度與泛化效果雙...
    與目前的主流思路（自適應學習率或者動量法）不同，該論文作者在之前的工作[1]中，通過利用ODE的有限時間穩定性的直觀表達，提出了一種新的加速算法收斂的方法。這類稱為Powerball的方法，是通過簡單的將冪係數 γ∈[0,1）添加到各類基於梯度的優化方法中的梯度上得到的。
  • 【乾貨】機器學習最常用優化之一——梯度下降優化算法綜述
    【新智元導讀】梯度下降算法是機器學習中使用非常廣泛的優化算法，也是眾多機器學習算法中最常用的優化方法。幾乎當前每一個先進的(state-of-the-art)機器學習庫或者深度學習庫都會包括梯度下降算法的不同變種實現。
  • 【乾貨】2018值得嘗試的無參數全局優化新算法,所有測試取得最優...
    【新智元導讀】本文介紹了一個名為LIPO的全局優化方法，這個方法沒有參數，而且經驗證比隨機搜索方法好。基於此，作者提出了MaxLIPO和置信域方法混合使用的優化方法，在所有測試中，都取得了最優結果，而且不需要任何參數。你還在手動調參？不如試一下更好的方法。 　　有一個常見的問題：你想使用某個機器學習算法，但它總有一些難搞的超參數。
  • 乾貨:Google 蘇黎世算法與優化專題講座總結(附演示文稿+視頻)
    雷鋒網 AI 研習社按，近日，谷歌在蘇黎世辦事處舉辦了一場有關算法與優化的專題講座，旨在通過提供一個論壇來交流機器學習理論和大規模圖挖掘領域的想法。該論壇涉及到市場算法、機器學習理論、大規模圖挖掘、隱私與公平、略圖構造、哈希和動態算法這五個方向。
  • 科學家破解了谷歌的量子優化算法
    谷歌為此的短期目標是已經設計出了一種新型的量子增強算法，可以在有真實噪聲的情況下運行。所謂的量子近似優化算法（Quantum Approximate Optimisation Algorithm，簡稱 QAOA）是谷歌目前開發的抗噪聲量子增強算法的基礎。谷歌在量子近似優化算法中採用的這一著名方法引發了廣泛的商業興趣，並激發了全球研究界探索其新穎應用的興趣。
  • 基於遺傳算法的工廠AGV路徑優化研究
    使用Matlab軟體對算法進行仿真，結果表明：該算法是有效的，能夠直接實現AGV在運輸多種類型物料時所產生的不同種路徑的優化。遺傳算法是模仿自然界生物進化機制發展起來的隨機全局搜索優化方法，具有算法效率高、魯棒性強、可實現並行搜索等特點 [3] ，被廣泛用於解決路徑規劃等領域的問題。
  • 10個梯度下降優化算法+備忘單
    gradient-descent-optimisation-algorithms-86989510b5e9梯度下降是一種尋找函數極小值的優化方法在這篇文章中，我會總結應用在目前較為流行深度學習框架中的常見梯度下降算法(如TensorFlow, Keras, PyTorch, Caffe)。本文之目的是為了方便理解和掌握這些內容，因為除此之外總結並不多，而且它可以作為你從零基礎入門的「小抄」。
  • 正項級數及收斂性判斷
    利用比較判別法，常要在討論不等式上花費很大精力同時要對所討論的級數的斂散性有大致的估計，才能決定是證明級數收斂或是發散.太煩人了！為應用上的方便，下面展示比較判別法的極限形式極限形式的比較判別法,在兩個正項級數的一般項均趨於零的情況下，其實是比較它們的一般項作為無窮小量的階.
  • [算法系列]最優化問題綜述
    牛頓法的優缺點總結：        優點：二階收斂，收斂速度快；　　  缺點：牛頓法是一種迭代算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較複雜。Powell證實了這種新的算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。擬牛頓法的本質思想是改善牛頓法每次需要求解複雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的複雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。
  • MLSys提前看|機器學習的分布式優化方法
    隨著機器學習算法和模型的不斷發展，傳統的軟硬體平臺、部署環境等無法支撐機器學習的應用，這也成為了目前機器學習方法落地及大規模推廣應用的主要困難之一。其中，前兩篇文章屬於經典的機器學習分布式優化方法（通信方式、內存分配方法），第三篇文章則是關於一種新的用於機器學習的具有高度系統性和設備（統計、數據）異質性的分布式方法--聯邦學習。
  • 利用遺傳算法優化GANs
    遺傳算法是根據大自然中生物體進化規律而設計提出的，是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。在本片文章中，我們嘗試使用遺傳算法來對訓練GANs進行優化，我們的訓練模型是生成手寫數字。什麼是遺傳算法?
  • 比可微架構搜索DARTS快10倍,第四範式提出優化NAS算法
    近年來，可微分的搜索方法因可以在數天內獲得高性能的 NAS 而成為研究熱點。然而，由於超級網的建設，其仍然面臨著巨大的計算成本和性能低下的問題。 在本文中，我們提出了一種基於近端迭代（NASP）的高效 NAS 方法。與以往的工作不同，NASP 將搜索過程重新定義為具有離散約束的優化問題和模型複雜度的正則化器。
  • 一文看懂各種神經網絡優化算法:從梯度下降到Adam方法
    原標題：一文看懂各種神經網絡優化算法：從梯度下降到Adam方法 王小新 編譯自 Medium 量子位 出品 | 公眾號 QbitAI 在調整模型更新權重和偏差參數的方式時，你是否考慮過哪種優化算法能使模型產生更好且更快的效果？
  • BMS算法設計之SOC估算方法總結篇(五)
    本篇文章是【BMS 算法設計】系列文章的第五篇，也是最後一篇。本期主要內容是對前幾篇介紹的電池SOC 估算方法做一個小結。以後會開啟新的話題，比如SOH算法等。我們一起來學習吧！先放一張各種SOC算法估算的優勢和局限性的對比圖。
  • CAAI 原副理事長焦李成教授：量子學習感知與優化的挑戰與思考
    另外就是它的定性、容錯和指數的生長，這是量子計算技術能和其他方法互補發展的重要因素之一。所以有可能提供新的計算途徑。量子的科學問題表現出相干、糾纏、疊加，包括不可克隆這些性質，我們希望能夠在量子態的空間，包括Hilbert空間中，怎麼去表徵、定義，包括它的完備性證明。
  • 【算法系列】凸優化的應用——Python求解優化問題(附代碼)
    ：無約束優化問題和約束優化問題，約束優化問題又可分為含等式約束優化問題和含不等式約束優化問題。無約束優化問題含等式約束的優化問題含不等式約束的優化問題針對以上三種情形，各有不同的處理策略：無約束的優化問題：可直接對其求導，並使其為0，這樣便能得到最終的最優解；含等式約束的優化問題：主要通過拉格朗日乘數法將含等式約束的優化問題轉換成為無約束優化問題求解；含有不等式約束的優化問題：主要通過KKT條件(Karush-Kuhn-Tucker Condition
  • Adam 優化算法詳解
    據牛津字典的定義，優化是指最好或最有效地利用一種情況或資源，或者簡單地使自己的事物達到最佳狀態的行為。 通常，如果可以對某事進行數學建模，則很有可能可以對其進行優化。 這在深度學習領域起著至關重要的作用（可能是整個人工智慧），因為您選擇的優化算法可能是在數分鐘，數小時或數天（有時甚至是數周）內獲得高質量結果的區別。
  • 優化算法——人工蜂群算法(ABC)
    一、人工蜂群算法的介紹 人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga於2005年提出的一種新穎的基於群智能的全局優化算法
  • 技術| 深度解讀最流行的優化算法:梯度下降
    > 梯度下降法，是當今最流行的優化（optimization）算法，亦是至今最常用的優化神經網絡的方法。本文旨在讓你對不同的優化梯度下降法的算法有一個直觀認識，以幫助你使用這些算法。我們首先會考察梯度下降法的各種變體，然後會簡要地總結在訓練（神經網絡或是機器學習算法）的過程中可能遇到的挑戰。