KDD 2020 开源论文 | 稀疏优化的块分解算法
?PaperWeekly 原創 ·?作者｜袁淦釗
單位｜鵬城實驗室
研究方向｜數值優化、機器學習
?
這次向大家分享的工作是鵬城實驗室牽頭，聯合騰訊 AI 實驗室和中山大學在 SIGKDD 2020 上發表的文章：A Block Decomposition Algorithm for Sparse Optimization。
論文標題：A Block Decomposition Algorithm for Sparse Optimization
論文鏈接：https://arxiv.org/pdf/1905.11031.pdf
相關資料（代碼/PPT/相關論文）：https://yuangzh.github.io
稀疏優化由于其內在的組合結構，一般比較難求解。組合搜索方法可以獲得其全局最優解，但往往局限于小規模的優化問題；坐標下降方法速度快，但往往陷入于一個較差的局部次優解中。
?
我們提出一種結合組合搜索和坐標下降的塊 K 分解算法。具體地說，我們考慮隨機策略或/和貪婪策略，選擇 K 個坐標作為工作集，然后基于原始目標函數對工作集坐標進行全局組合搜索。我們對塊 K 分解算法進行了最優性分析，我們證明了我們的方法比現有的方法找到更強的穩定點。
此外，我們還對算法進行了收斂性分析，并構建其收斂速度。大量的實驗表明，我們的方法目前取得的性能臻于藝境。我們的塊 K 分解算法的工作發表在國際人工智能會議 SIGKDD 2020 和 CVPR 2019 上。
?
簡介
?
本文主要討論求解以下稀疏約束或稀疏正則優化問題：
?
我們假設 f(x) 是光滑的凸函數。這類問題在壓縮感知、信號處理、統計學習等問題上有著廣泛的應用。
提出的算法
?
以下是我們提出的塊 K 分解算法：
?
算法非常簡潔，只有兩步。第一步：選擇 K 個坐標集，第二步：基于原始目標函數 f(x)，對選擇的 K 個坐標作全局組合搜索。
?
該算法也被稱為塊坐標下降方法，但和以往方法有所不同，有以下四點值得注意：
?
我們使用了臨近點策略，這個策略是為了保證充分下降條件和全局收斂性質；
我們直接求解原來具有組合結構的子問題，而不使用替代函數最小化其上界；
在坐標選擇上，以往可以根據一階最優條件 / KKT 條件殘差來選擇坐標，但這種策略對于非凸問題不再適用。我們采用兩種策略。一種是隨機策略，這種策略的最大的好處是保證算法得到塊 K 穩定點（下方將討論）；另一種是貪心策略，這種策略直接根據目標值下降的多少來選擇坐標，在實際中通常可以加速算法收斂；
在求解子問題中，雖然子問題是 NP 難的，且沒有快速的封閉解，但是我們依然可使用全局樹形搜索獲得全局最優點。注意，K 通常是一個很小的整數；例如，在我們的實驗中，K=16。我們考慮簡單的二次函數例子：。我們先系統地窮舉下面的全二叉樹，通過求解 個線性系統得到所有可能的局部極小值；然后我們選出使得目標值達到最小的那個作為最優解。
與以往的方法的比較
?
目前常見的稀疏優化方法有四類：
?
a. 第一類是松弛近似方法。這類方法最大的缺點是不能直接每一步控制問題的稀疏特性。
?
我們方法優點：可以直接控制解的稀疏特性。
?
b. 第二類是貪心算法。這類方法最大的缺點是初始化點必須為空集或零。
?
?
我們方法優點：可以任意初始化，而且最終精度對初始化不敏感。
?
c. 第三類方法是全局優化算法。這類方法的最大缺點是僅限于小規模問題。
?
?
我們方法優點：利用了全局最優化算法，提高了算法精度。
?
d. 第四類方法是臨近梯度方法。這類方法的最大缺點是算法陷入到較差的局部次優值。
我們方法優點：從理論和實驗上都優勝于臨近梯度方法。
?
最優性分析
?
以下我們定義稀疏優化問題的穩定點：基本穩定點、李普希茨穩定點，塊 K 穩定點。
基本穩定點就是指，當非零元指標集已知時，解達到全局最優。這類穩定點的一個很好的性質是：穩定點是可枚舉的，這使得我們能夠驗證某個解是否是該問題的全局最優解。
?
?
李普希茨穩定點是通過一個臨近算子來刻畫，經典的臨近梯度法得到的是李普希茨穩定點。臨近梯度法每一步需要求解一個臨近算子，該算子有快速封閉解，但是這種簡單的上界替代函數方法通常導致算法精度不高。
?
?
這是我們提出的塊 K 穩定點的概念。塊 K 穩定點是指，當我們（全局地）最小化任意的 K 個坐標（其余的 n-K 個坐標固定不變），我們都不能使得目標函數值得到改進。
?
我們得到以下的關于這三類穩定點的層次關系：
?
?
我們已證明，我們的塊 K 穩定點比以往的基本穩定點和李普希茨穩定點更強。可以以上圖舉例。假如我們從上方的圖中的綠色區域（塊 K 穩定點）選擇一個點，該點落入黃色區域（最優點集）中有一個概率 P1；我們從上方的圖中的紅色區域（李普希茨穩定點）選擇一個點，該點落入黃色區域（最優點集）中有一個概率 P2。由于 P1 總是大于 P2，因此我們的方法更大的概率落入最優解集中。
?
稀疏優化問題由于其組合結構，完全求解這個問題屬于大海撈針。我們對稀疏優化問題的全局最優點有了更準確細致的描述，我們對這類問題給出了更精確的近似。
?
可以打個比喻：甲說，鵬城實驗室在廣東；乙說，鵬城實驗室在廣東深圳；丙說，鵬城實驗室在廣東深圳南山區萬科云城（詳細廣告信息可參考本文下方）。丙的說法更準確。
?
收斂性分析
?
我們證明了算法在期望意義上收斂到塊 K 穩定點。
?
?
此外，我們證明了算法線性收斂性質（我想大家可能不太感興趣，可參考我的論文和 PPT）。
?
數值實驗
?
6.1 對于稀疏約束優化問題，我們比較了以下9種方法：
?
Proximal Gradient Method (PGM)
Accerlated Proximal Gradient Method (APGM)
Quadratic Penalty Method (QPM)
Subspace Pursuit (SSP)
Regularized Orthogonal Matching Pursuit (ROMP)
Orthogonal Matching Pursuit (OMP)
Compressive Sampling Matched Pursuit (CoSaMP)
Convex `1 Approximation Method (CVX-L1)
Proposed Decomposition Method (DEC-RiGj, 我們的方法)
?
實驗1
結論1
?
我們的分解方法精度優于其它方法。此外，K 越大，精度越高；
使用貪心策略選擇 2 個坐標和使用隨機策略選擇 2 個坐標兩種策略相比，前者收斂快但精度差，因此兩種坐標選擇策略需要結合來使用；
我們的方法在 30 秒內收斂。
?
實驗2
結論2
?
基于迭代硬閾值的方法 {PGM, APGM, QPM} 性能較差；
OMP 和 ROMP 有時性能較差；
在這幾個數據集中，我們的方法一致地和較大地優于目前的方法。
?
6.2 對于稀疏正則優化問題，我們比較了以下5中算法：
?
PGM-L0: PGM for L0 Problem
APGM-L0: Accerlated PGM for L0 Problem
PGM-L1: PGM for L1 Problem
PGM-Lp: PGM for Lp Problem (p=1/2)
Proposed Decomposition Method (我們的方法)
?
實驗1
?
結論1
?
PGM-Lp 比 PGM-L1 所取得的精度要好；
在所有數據集上，我們的分解算法總的來說比其他的方法要好。
?
總結全文
?
我們提出了一種求解稀疏優化問題的有效實用的方法。我們的方法利用了組合搜索和坐標下降的優點。我們的算法無論從理論上還是從實際上，都優于目前最具代表性的稀疏優化方法。我們的塊分解算法已被擴展到解決稀疏廣義特征值問題（見CVPR 2019）和二值優化問題。
?
招聘
鵬城實驗室誠聘 博士后 / 助理研究員（數值優化方向）
崗位名稱：博士后/助理研究員
工作地點：鵬城實驗室（深圳南山區萬科云城）
研究方向：數值算法/（半）離散優化/二階優化/非凸優化/非光滑優化/機器學習
應聘材料：個人簡歷+學術成果（論文、科研項目、所獲獎項等）發送到下方郵箱
應聘條件：35歲以下近三年內取得計算機/計算數學等學科博士學位+在數值優化/機器學習/機器視覺/數據挖掘等領域以第一作者發表過高水平論文（e.g., CCF A類/SIAM Journal）
崗位待遇：全球范圍內有競爭力。
聯系方式：yuangzh@pcl.ac.cn
更多閱讀
#投 稿?通 道#
?讓你的論文被更多人看到?
如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。
總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?
PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。
?????來稿標準：
? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?
? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?
? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志
?????投稿郵箱：
? 投稿郵箱：hr@paperweekly.site?
? 所有文章配圖，請單獨在附件中發送?
? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通
????
現在，在「知乎」也能找到我們了
進入知乎首頁搜索「PaperWeekly」
點擊「關注」訂閱我們的專欄吧
關于PaperWeekly
PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。
總結
以上是生活随笔為你收集整理的KDD 2020 开源论文 | 稀疏优化的块分解算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 银华心诚005543净值
- 下一篇： 深蓝汽车 10 月 1~7 日累计大定