1. 概要

下記のarXiv論文を紹介します。

Jinshan Zeng, Tim Tsz-Kit Lau, Shaobo Lin, Yuan Yao (2018).
Block Coordinate Descent for Deep Learning: Unified Convergence Guarantees.arXiv:1803.00225

現時点では投稿されて間もない論文ですが、個人的には機械学習の論文を読んでいて久々に楽しい気持ちになれました。

論文の提案手法はgradient-free methodと呼ばれる手法の一種なので、本記事はそのあたりのレビューも少し兼ねます。

2. 勾配法の収束条件

ニューラルネットの構造をひとつ固定し、その構造を使って表せる関数の全体を F$\mathcal{F}$ と書きます。ニューラルネットの学習とは、与えられた損失を最小化する関数を見つけることです。例えば、二乗損失なら

のようになります。Part 1で述べたとおり、この最適化問題が解けるという前提のもとで、いくつかの新しい汎化誤差バウンドが得られています。しかし、これは一般には非凸最適化となり、大域最適解へが得られることは保証できません。

現在、ニューラルネットの学習はSGD, AdaGrad, Adam, RMSPropといった勾配法ベースの最適化手法が使われていることが多く、主要な深層学習ライブラリも、勾配計算 (Backprop) の機能を提供することを主な目的としていると思います。これらの手法は、目的関数が凸であれば大域解への収束が保証されていることが多いです。

が、実際に興味のある目的関数は凸ではなく、もっというと、ReLUを使った場合は微分可能ですらありません。ちなみに、目的関数が凸でも、微分可能性のようなもの (正確にはsmoothness) は収束レートに関わることがあります。

また近年、ハードウェアへの移植などを目的として、Binarized Neural Networksのようにパラメータが離散的な値をとる深層学習モデルがあります。このようなモデルではそもそも勾配が存在しないため、勾配ベースの最適化アルゴリズムを直接適用することはできません。

3. Block Coordinate Descent (BCD, ブロック座標降下法)

だけど、

• 目的関数が非凸でも
• 微分不可能でも
• 勾配を使わなくても
• 初期値をどこに設定しても

局所解に収束することを理論的に示せるよ。ブロック座標降下法 ならね!!

3.1. アルゴリズムの概要

記号

T$T$ 層のニューラルネットを学習する問題を抽象的に定義します。まず、

• d0,d1,…,dT$d_0,d_1,\dots ,d_T$ : ニューラルネットの各層の幅。特に、d0$d_0$ は入力 x$x$ の次元、dT$d_T$ はラベル y$y$ の次元と一致
• Wi∈Rdi×di−1$W_i\in {\mathbb{R}}^{d_i\times d_{i-1}}$ : 第 i$i$ 層のパラメータ
• σi${\sigma }_i$ : 活性化関数

として、ニューラルネットで表現している関数は

であるとします。また、

• X:=[x1,…,xn]∈Rd0×n$X:=[x_1,\dots ,x_n]\in {\mathbb{R}}^{d_0\times n}$ : 入力データ
• Y:=[y1,…,yn]∈RdT×n$Y:=[y_1,\dots ,y_n]\in {\mathbb{R}}^{d_T\times n}$ : ラベルデータ
• L(f,y)$\mathcal{L}(f,y)$ : 損失関数 (非負・連続だが凸とは限らない)

として、経験損失を

と定義します。ri,si$r_i,s_i$ を事前分布や正則化項を表す関数とします。このとき、興味のある最適化問題は、以下のような等式制約のある問題として書けます。

なお、本来最適化すべきパラメータは Wi$W_i$ (i=1,…,T$i=1,\dots ,T$) ですが、スラック変数を導入して (Wi,Vi,Ui)$(W_i,V_i,U_i)$ の三つ組を最適化するという意味で、論文中では上の最適化問題を3-splitting formulationと呼んでいます。

BCDアルゴリズム

BCDアルゴリズムのアイデアは簡単です。まず、上記の等式制約をFrobeniusノルムによるペナルティとして表現します。

拡張ラグランジュ関数 から線形のラグランジュ乗数を取り除いた格好ですが、なんと呼ぶのが適切かはちょっと知りません。二次バリア関数とか？

あとは、Vi,Ui,Wi$V_i,U_i,W_i$ のそれぞれに関する最小化をサイクリックに行うだけです。論文からアルゴリズムを引用します。

それぞれの部分問題はちょうど近接作用素を求めるような形になっており、例えば「損失 ℓ$\ell$ が2次関数、σ$\sigma$ がReLU、si$s_i$, ri$r_i$ が0」といった典型的な場合ではclosed-formの解が得られます (e.g. Lemma 1)．

ニューラルネットがconvolution層を含む場合も等式制約を追加すればよいので、アルゴリズムを拡張することは容易であることが述べられています。また、ResNetに拡張した例がAlgorithm 2として提案されています。

なお、後述するように、このアルゴリズムには理論収束保証もあります。しかし、オリジナルの問題についてではなく、この L¯$\overline{\mathcal{L}}$ が局所解に収束することを保証するものですので、その点に関しては注意が必要です。

3.2. 数値例

論文の数値例を紹介します。追実験などはしていません。

T=4$T=4$ 層のDNNでMNISTとCIFAR-10の学習を、BCDおよびSGDで行った結果の引用です。NNの構造やSGDの学習率の詳細は論文を参照してください。

実時間ではなくエポック数の比較ですが、SGDが学習に約100エポック必要とするのに対し、BCDは5エポック以下（！）で学習がほとんど終了していることがわかります。また、最終的なtest accuracyもSGDと比較して遜色ないものとなっています (Table 1).

定式化から明らかなようにBCDの1回の更新にかかるコストは大きく、メモリに乗らない量のデータをどう扱うかなど疑問点はありますが、promissingな結果であることは間違いないと思われます。

3.3. その他のgradient-free method / 先行研究

先行研究に少し触れておきます。（このあたりはまだ勉強中です）。

ニューラルネットの学習をgradient-freeに行うアルゴリズムとしては、 ADMMベースの手法[1],[2],BCDベースの手法[3]が提案されています。Gradient-freeな方法の動機として、紹介論文や [1] では勾配法との比較が述べられています。計算面での主な違いは、勾配法は小さなミニバッチを使った低コストな更新を多数回行うのに対し、勾配フリー法は多くのデータを使った高コストな更新を小数回行う手法になっており、前者はGPU、後者はCPU上での実行が適しています。勾配法の収束については、勾配消失やプラトーなど既知の問題がありますが、勾配フリー法では紹介論文のような収束保証が得られています。

[1] Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, Tom Goldstein (2016).
Training Neural Networks Without Gradients: A Scalable ADMM Approach. In ICML2016. arXiv:1605.02026

[2] Ziming Zhang, Yuting Chen, Venkatesh Saligrama (2016).
Efficient Training of Very Deep Neural Networks for Supervised Hashing. In CVPR2016. arXiv:1511.04524

[3] Ziming Zhang, Matthew Brand (2017).
Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks. In NIPS2017. arXiv:1711.07354

4. 収束保証

BCDアルゴリズムでは、L¯$\overline{\mathcal{L}}$ が局所解に収束することが、比較的広い条件のもとで示されています。

4.1. Kurdyka-Łojasiewicz (KL)条件

最近の非凸最適化の論文では、目的関数に課す正則条件としてKurdyka-Łojasiewicz (KL) propertyというものがトレンドになっているようです。まず定義を書きます

記号

(凸とは限らない) 関数 f:Rd→R∪{+∞}$f:{\mathbb{R}}^d\to \mathbb{R}\cup \{+\mathrm{\infty }\}$ の x∈Rd$x\in {\mathbb{R}}^d$ における劣勾配 g∈∂f(x)$g\in \mathrm{\partial }f(x)$ とは (xk,gk)→(x,g)$(x_k,g_k)\to (x,g)$ となる点列が存在して、f(xk)→f(x)$f(x_k)\to f(x)$ かつ

が成り立つことをいう (正確な定義は この文献 など)。劣勾配の集合 ∂f(x)$\mathrm{\partial }f(x)$ を x$x$ における f$f$ の劣微分という．

∂f(x)$\mathrm{\partial }f(x)$ が空でない x∈Rd$x\in {\mathbb{R}}^d$ の集合を dom(∂f)$\mathrm{d}\mathrm{o}\mathrm{m}(\mathrm{\partial }f)$ と書く。また、

とする。

定義：KL条件

関数 f:Rd→R∪{+∞}$f:{\mathbb{R}}^d\to \mathbb{R}\cup \{+\mathrm{\infty }\}$ が点 x∗∈dom(∂f)$x^{\ast }\in \mathrm{d}\mathrm{o}\mathrm{m}(\mathrm{\partial }f)$ においてKL propertyをもつとは、3つ組

• η∈(0,+∞]$\eta \in (0,+\mathrm{\infty }]$
• x∗$x^{\ast }$ の近傍 U$U$
• 凹関数 φ:[0,η)→R+$\phi :[0,\eta )\to {\mathbb{R}}_{+}$

が存在して以下の条件を満たすことをいう：

1. φ(0)=0$\phi (0)=0$, φ$\phi$ は (0,η)$(0,\eta )$ で C1$C^1$ 級
2. 任意の s∈(0,η)$s\in (0,\eta )$ に対して φ′(s)>0${\phi }^{\mathrm{\prime }}(s)>0$
3. 任意の x∈U∩{x:f(x∗)<f(x)<f(x∗)+η}$x\in U\cap \{x:f(x^{\ast })<f(x)<f(x^{\ast })+\eta \}$ に対して、次の Kurdyka-Łojasiewicz不等式 が成り立つ
   
   φ′(f(x)−f(x∗))dist(0,∂f(x))≥1.$${\phi }^{\mathrm{\prime }}(f(x)-f(x^{\ast }))\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(0,\mathrm{\partial }f(x))\ge 1.$$

KL不等式が何を言っているかというのが問題ですね。KL条件の意味についてはこのスライド がわかりやすいです。(確か、以前tmaeharaさんに教えていただいたものです)

まず、0∈∂f(x)$0\in \mathrm{\partial }f(x)$ というのは x$x$ が f$f$ の停留点であるということなので、逆に dist(0,∂f(x))$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(0,\mathrm{\partial }f(x))$ が大きいならば点 x$x$ において f$f$ が大きく傾いているということを表します。もし f$f$ の等高線でスライスした領域 {x:a<f(x)<b}$\{x:a<f(x)<b\}$ において一様に dist(0,∂f(x))≥c>0$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(0,\mathrm{\partial }f(x))\ge c>0$ が成り立つのであれば、関数の「谷」のような部分に向かって急に落ち込んでいるものと考えられます。

(図は Bolte(2015) から引用)

この性質が成り立つとき、f$f$ はこのスライスにおいてsharpである、ということにします。もし f$f$ がsharpであれば、近接点法のようなアルゴリズムは有限ステップで「谷底」のような部分に到達できます (ラフな証明は Bolte(2015) p.17)。

KL条件は、本質的には

と等価です。これは、凹関数 φ$\phi$ によって、等高線のスライスを高さ f(x∗)$f(x^{\ast })$ の「谷底」に近づける速さをコントロールしたときにsharpと見做せる、ということを述べています。よって、なんとなくですが、f$f$ 自身が凸でなくても、谷底に到達する何らかの手段は手に入るような感じがします。

KL条件を満たす関数

重要な点は、実はかなり多くの関数がKL条件を満たすことがわかります。というか、「KL条件を満たす関数がたくさんある」ということそのものがこの理論の根幹をなす結果になっているようです。

• 解析関数はKL条件を満たす。
• グラフが半代数的集合になる関数を半代数的関数 (semialgebraic function) という。すべての半代数的関数はKL条件を満たす。
• 半代数的関数は有限個の和や積、合成などの操作で閉じる。

例えば、2次関数やReLUなどは半代数的関数なのでKL条件を満たします。よって、それらの和・積・合成によってできている訓練損失もKL条件を満たすことが示せます (Proposition 1)。

KL条件から何が言えるか

ずばり、近接点法や座標降下法のようなアルゴリズムの収束保証と収束レートの導出に使えます[4] [5]。具体的には、近接点法では φ(s)=cs(1−θ)$\phi (s)=c{s}^{(}1-\theta )$ (θ∈[0,1)$\theta \in [0,1)$) のような形をしているとき、θ=0$\theta =0$ なら有限ステップで停留点に収束、0<θ≤1/2$0<\theta \le 1/2$ ならば誤差が O(exp(−k))$O(\exp (-k))$ で収束、1/2<θ<1$1/2<\theta <1$ ならば O(k−(1−θ)/(2θ−1))$O(k^{-(1-\theta )/(2\theta -1)})$ で収束、という結果が得られており [4]、紹介論文でもこの結果に帰着することで収束レートを出しています。

[4] Hedy Attouch, Jérôme Bolte (2009).
On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116, 5–16. プレプリント

[5] Hedy Attouch, Jérôme Bolte, Benar Fux Svaiter (2013).
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Mathematical Programming, 137, 91–129. URL

4.2. BCDの収束

DNNに対するBCDの収束は次のことが示せます。(L¯$\overline{\mathcal{L}}$ の収束であることに注意)

仮定

• i=1,…,T−1$i=1,\dots ,T-1$ について、活性化関数 σi${\sigma }_i$ は L$L$-Lipschitzである
• 関数 L¯$\overline{\mathcal{L}}$ はある点でKL条件を満たす。特に、(a) si,ri$s_i,r_i$ が半代数的関数であり、(b) 損失関数が2乗損失、ロジスティック損失、ヒンジ損失のいずれかであり、(c) 活性化関数がReLU、シグモイド、線形リンクのいずれかであれば、どの組み合わせでもこの条件は満たされる。

Theorem 2 (要点のみ)
上の仮定が成り立つとする。BCDアルゴリズムの第 k$k$ ステップでの出力を Pk$P^k$ とする。

1. BCDアルゴリズムにおいて、dist2(0,∂L¯(Pk))${\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}}^2(0,\mathrm{\partial }\overline{\mathcal{L}}(P^k))$ のrunning best rate (k$k$ステップまでの最良値) は o(1/k)$o(1/k)$ である。
2. 関数 L¯$\overline{\mathcal{L}}$ がある点において、φ(s)=cs1−θ$\phi (s)=c{s}^{1-\theta }$ に対してKL条件を満たすならば、停留点への収束レートが得られる。

5. 結論

現在、「GPUに廃課金して勾配法で殴る」という手法が主流になっていると思われますが、これを機に今後はgradient-freeな手法にも期待できるかもしれません。

(参考)