NIPS 2016有什麼值得關注的呢？

01-14

Wikipedia: Conference on Neural Information Processing Systems (NIPS),homepage:2016 Conference

來強答一發，推薦關注新的優化(Optimization)演算法。

前段幾天NIPS出結果，朋友圈裡幾位小夥伴曬了自己的NIPS戰績。之前審NIPS2016的時候，發現優化發麵的投稿有不少我感興趣和我所做的方向相關的論文，借這個問題，簡單講講這方面的進展，以及今年NIPS可能會出現的新方法。

隨著數據規模和參數規模的增加，設計更快速的優化演算法顯得非常必要。通常加速現有的優化演算法有兩個思路

一方面是從老演算法中設計新演算法，通過證明和實驗說明其在收斂速度上更快
另一方面是設計非同步分散式的演算法通過多機來加速，並證明其正確性和通過實驗驗證其有效性。

優化演算法一直也是ML各大會議非常重視的方向，每年NIPS、ICML都會有一大票優化相關的paper。近幾年，隨機優化方向的一些新演算法都發表在機器學習會議上，比如SAG、SVRG、SAGA這一類可以線性收斂的SGD變種。

近段時間，個人比較關註上面提到的第二種思路，也就是在多機多線程環境下設計優化演算法，並通過實驗和證明來驗證演算法的正確性。這裡回顧一下非同步分散式梯度下降演算法：

假設目標函數是 $frac{1}{n} sum_{i=1}^N f_i(mathbf{x}) + h(mathbf{x})$ ，其中 $f_i(mathbf{x})$ 是第 $i$ 個樣本的損失函數， $h(mathbf{x})$ 是一個非平滑的正則化項，這個目標函數常常使用Proximal Stochastic Gradient Descent (P-SGD)求解，更新式子是這樣。

$mathbf{x}_{k+1} = ext{Prox}(mathbf{x}_k - eta_k riangledown f_i(mathbf{x}_k))$ ，這裡的 $ext{Prox}(.)$ 叫做Proximal operator，目的是為了處理非平滑的正則化項 $h(mathbf{x})$ 。

在採用非同步加速的演算法中，早期做非同步SGD的演算法比較出名的有Hogwild!，參考：Hogwild: A lock-free approach to parallelizing stochastic gradient descent，只是Hogwild!並不處理非平滑正則化。此外，還有[Alekh Agarwal et al.] Distributed delayed stochastic optimization、[Xiangru Lian et al.]Asynchronous parallel stochastic gradient for nonconvex optimization等。

把演算法換到多機或者多線程的情況下，採用parameter server結構，讓master存儲參數並負責更新，而worker負責計算梯度並交給master，master來完成 $ext{Prox}(.)$ 操作，那麼更新式子會變成。

$mathbf{x}_{k+1} = ext{Prox}(mathbf{x}_k - eta_k riangledown f_i(mathbf{x}_{d(k)}))$ ，注意這裡的梯度中所使用的參數是 $x_{d(k)}$ ，它是一個有延遲的參數（ $d(k)leq k$ ），也就是說這個參數是『過期』的，造成這個『過期』的原因是當worker從master上拉取參數計算完梯度再提交給master的時候，master的參數可能已經被其他worker更新了好幾次，具體可以參考 @李沐的論文Communication Efficient Distributed Machine
Learning with the Parameter Server。一般可以證明到次線性收斂速度。

如果 $ext{Prox}(.)$ 不是特別複雜（比如L1 norm的Proximal operator），把它交給master來計算是比較合適的，但是，有的時候由於求解的問題帶有更加複雜的Nuclear norm、Group Lasso、Fused Lasso這些norm，他們的Proximal operator如果交給master做，會加大master的負擔，如果有多個master的話，還會造成master之間的通信。這個時候，我們就有必要設計一種非同步的SGD，使得它能夠把Proximal operator的計算交給worker，並且不會讓worker和worker之間，master和master之間產生額外的通信。

為了解決這個問題，我們設計了一種新的非同步優化演算法，也往今年NIPS投了，目前paper在Arxiv上：http://arxiv.org/abs/1605.06619。很遺憾我們的沒有中今年NIPS。簡單介紹一下，我們這篇paper的思路，我們把更新式子設計成兩步

$x_{d(t)}$

$mathbf{x}_{t+1} = mathbf{x}_{t} + mathbf{x}_{d(t)}$

把第二步中的加法更新交給master計算，剩餘部分都可以交給worker來計算，此時，無論 $ext{Prox}(.)$ 的計算過程多麼複雜，都可以由每個worker單獨完成，而master僅僅需要做加法計算。

目前我們能證明這個演算法是次線性收斂的 $O(frac{log T}{T})$ ，試驗中性能也很好。

此前，非同步的SGD採用variance reduction後已經能做到線性收斂，參考On Variance Reduction in Stochastic Gradient
Descent and its Asynchronous Variants。但是非同步的Proximal SGD目前還沒看到有線性收斂的方法。

在NIPS2016審稿bid階段，看到幾篇用了variance reduction trick的非同步Proximal SGD，比較期待今年會不會出現能夠線性收斂的非同步Proximal SGD。

SGD演算法只是優化演算法之一，還有很多值得關注的演算法。等NIPS的paper列表放出來了，再來補充一些具體的。

最近在讀NIPS文章，列出兩個自己關注的方向里幾篇有代表性的文章，算是拋磚引玉吧。

方向1：deep generative probabilistic model

最近一段時間，generative model正在引起越來越多的關注，深度神經網路雖然在識別（分類）問題上體現出巨大優勢，但discriminative learning的框架也有明顯的局限，例如對大量有標註數據的依賴和有限的泛化能力，而generative learning著眼於直接對數據本身分布的建模，在對識別以外的問題（例如圖像重建、生成）上具有更大的優勢，更吸引人的是可以用無監督學習利用更海量的數據。而深度神經網路作為大容量模型，將其用於構建generative model無疑非常具有吸引力。例如2014年提出的Variational Auto-encoder，2015年的Generative Adversarial Network，都是將神經網路作為單元結構，嵌入probabilistic generative learning的理論框架中，今年就有不少基於VAE和GAN的工作。加上早一點的Deep Boltzmann Machine, Deep Belief Network基本上構成了目前的幾大深度generative模型的架構。今年的NIPS又出現了一些新的具有探索意義的工作，同樣是深度generative模型，但是卻有新的架構。

An Architecture for Deep, Hierarchical Generative Model

A Probabilistic Framework for Deep Learning

方向2：learning by synthetic data

有的時候數據不夠多，模型容量再大也用不了，那就用生成一些數據吧，這樣做的好處是因為數據是生成的，所以可以自帶標註信息，但挑戰就是得保證生成的數據足夠好。（當然夠好的話就發NIPS了，比如說目前最熱的一個策略就是GAN）

Generating Videos with Scene Dynamics

MoCap-guided Data Augmentation for 3D Pose Estimation in the Wild

Visual Dynamics: Probabilistic Future Frame Synthesis via Cross Convolutional Networks

Dynamic Filter Networks