[發明專利]一種基于條件梯度的加速分布式在線優化方法

在審

• 申請號: 201911045411.1
• 申請日: 2019-10-30
• 公開（公告）號: CN110768841A
• 公開（公告）日: 2020-02-07
• 發明（設計）人: 申修宇;李德權;董翹
• 申請（專利權）人: 安徽理工大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 暫無信息
• 代理人: 暫無信息

基于條件梯度，提出了一種加速分布式在線條件梯度優化方法，可以有效地解決了分布式在線優化算法時間復雜度高的問題。所提方法將網絡優化目標函數分解為每個節點或個體的局部目標函數之和，每個個體只知道自己的目標函數，通過與相鄰個體之間的信息傳遞，協同解決優化問題。該方法通過在每個個體的局部代價信息中加入正則化項，構造了一個新的時變代價函數，避免了傳統條件梯度算法對梯度大小不敏感的缺點。該方法還利用局部線性優化設置代替投影運算，使算法的收斂速度成倍提高。最后，對各種任務進行了實驗驗證，結果表明該方法在實際應用中運行良好，與現有的優化方法相比具有一定的優越性。

技術領域

本發明涉及一種基于條件梯度的加速分布式在線優化方法，屬于機器學習領域。

背景技術

分布式凸優化一直受到許多領域研究者的極大關注。分布式跟蹤，估計和檢測等經典問題本質上也是優化問題。分布式優化問題主要是執行分配給網絡中每個節點的全局優化任務。由于每個節點具有有限的資源或關于任務的部分信息，因此節點協作以執行數據收集并通過共享所收集的信息來更新本地估計。分布式優化對節點施加較低的計算負擔，并且即使節點經歷本地故障，網絡系統仍然保持穩健，因此它可以有效地克服集中式場景中單個信息處理單元中的缺陷。

分布式優化已廣泛應用于時不變成本函數的情況。然而，在實際應用中，分布式網絡系統通常處于動態且不確定的環境中。例如，考慮跟蹤移動目標的問題，其目的是跟蹤目標的位置，速度和加速度。這些問題一直是機器學習領域在線學習的主要焦點。因此，將在線優化與分布式優化相結合，利用任意可變成本函數來表示多智能體網絡系統的不確定性，可以有效地用于實時處理網絡節點的動態數據流。

隨著分布式在線優化的快速發展，許多傳統的優化算法已經擴展到分布式在線案例中。近年來，梯度下降法、對偶平均法等傳統優化算法在分布式在線優化中得到了廣泛的應用。條件梯度法(也稱為Frank-Wolfe，FW)本質上是一階優化方法，理論上可以實現比其他有效優化算法更低的收斂速度，但目前各種變量都存在大量變量。高維度的實際優化問題，因此使用二階信息或其他超線性操作實際上是不可行的。此外，FW方法已被證明是解決大規模優化問題的有力工具，因為它可以有效地避免諸如在一階優化方法中計算正交投影的難度等關鍵問題。因此，在原有的條件梯度算法中引入局部線性優化步驟，提出了加速分布式在線條件梯度算法，并將條件梯度在線優化算法擴展到分布式情況。

發明內容

本發明所要解決的技術問題是：提供一種基于條件梯度的加速分布式在線優化方法，旨在加速分布式網絡中模型的收斂。

為解決以上技術問題，本發明采用如下的技術方案：

在分布式在線凸優化設置中，每個節點代表一個個體，在每輪迭代中，個體產生決策信息，個體獨立得提交決策信息并獲得相應的成本函數。每個個體在進行信息交流時相對于其他個體有重要程度之分，通過加權平均的形式目的在于給重要程度高的個體賦予更高的權重讓其信息更有價值，從而降低整個分布式系統的誤差。在原有的條件梯度算法中引入局部線性優化步驟，加速整個網絡模型的收斂。

附圖說明

圖1是本發明的方法在L1正則化邏輯回歸模型的收斂圖。

圖2是本發明的方法在L2正則化邏輯回歸模型的收斂圖。

具體實施方式

本發明解決在連通無向網絡上的分布式優化問題，避免集中式場景中單個信息處理單元中的缺陷，造成中心節點通信成本過高。

具體步驟為：

Step1：揭示損失函數f_t(t)＝f_i,t(t)

Step3：計算個體產生信息的次梯度，g_it∈f_i,t(x_i,t)