CoCoA: 大規模機械学習の分散最適化のための一般的なフレームワーク

昨年、Michael I. Jordan 研究室は「CoCoA: 通信効率の高い分散最適化のための一般的なフレームワーク」と題した論文を発表し、機械学習における分散最適化のための一般的なフレームワーク CoCoA を提案しました。 Synced の技術コンサルタントである Yanchen Wang 氏が、この研究について詳細な解説を行いました。

1. はじめに

ディープラーニングを行う場合、現代のデータセットの規模に応じて効率的な設計と開発が必要となり、理論的にはアルゴリズムも分散して最適化する必要があります。分散システムは、垂直方向と水平方向の両方向のスケーラビリティを実現し、コンピューティング機能とストレージ機能を向上させますが、アルゴリズム設計者にいくつかの特有の課題も提示します。特に重要な課題の 1 つは、機械学習のワークロードのコンテキストでマシン間の通信を効率的に調整する方法を開発することです。実際、ほとんどの本番クラスターでは、ネットワーク通信は単一のワーカー マシン上のローカル メモリ アクセスよりもはるかに遅くなります。ただし、単一のマシンをスケーリングすることは明らかに実現不可能です。問題はさらに複雑になる可能性があります。ローカル コンピューティングとリモート通信の最適なバランスは、データセットの特定のプロパティ (次元、データ ポイントの数、スパース性、歪度など)、分散システムの特定のプロパティ (データ ストレージ形式、分散スキーム、データ アクセス モードの論理設計、およびネットワーク階層、帯域幅、コンピューティング インスタンス仕様などの物理的条件など)、および負荷の特定のプロパティ (たとえば、単純な ETL プロセスは、ロジスティック回帰の反復フィッティングとは明らかに異なります) によって異なります。したがって、アルゴリズム設計者は、高速収束を確保しながら、特定の分散システムの「計算と通信」の間の最適なバランスを実現できるほど柔軟な最適化/機械学習アルゴリズムを作成する必要があります。

CoCoA は、カリフォルニア大学バークレー校の Michael I. Jordan 研究室によって最近提案されたフレームワークであり、さまざまな最適化問題をインテリジェントに分解することで上記の目標を達成します。解決する主目的または二重目的を自由に選択することで、フレームワークは凸双対性をうまく利用し、グローバル問題をワーカーマシン上で効率的に並列に解決できる一連のサブ問題に分解し、ローカル更新を組み合わせて、証明可能な方法で高速なグローバル収束を確保できるようにします。 CoCoA には 2 つの大きな利点があります。1) 任意のローカル ソルバーを各ワーカー マシン上で最も効率的に実行できます。 2) 計算と通信のトレードオフは問題の形式化の一環として調整できるため、異なる問題やデータセットごとに効果的に調整できます。

分散クラスター上のデータの分布（特徴またはデータ ポイントによる）に応じて、CoCoA はグローバル問題を近似的なローカル サブ問題に分解し、主目的を解決するか二重目的を解決するかを推奨します。各サブ問題は、最先端の既成の単一マシン ソルバーを使用して解決され、各反復からのローカル更新が単一の REDUCE ステップで結合されます (REDUCE という用語は MAP-REDUCE から借用されています)。実験では、CoCoA は SVM、線形/ロジスティック回帰、Lasso アルゴリズムで最大 50 倍の高速化を達成できることが示されています。

このレポートでは、CoCoA の核となる考え方と最も重要な結論を理解します。興味のある読者は、参考文献で詳細な議論とさらに多くの実験を見つけることができます。このレポートの目的は、分散機械学習の分野における読者の理解を深め、より多くの人々に議論に参加してもらい、知識を交換し、技術コミュニティに貢献してもらうことです。

2. 問題設定

CoCoA の目標は、機械学習アルゴリズムで一般的な次の最適化問題を解決することです。

ここで、l と r はベクトル変数 u の凸関数です。機械学習の分野では、l は通常、すべてのデータ ポイントの経験的損失の合計を表す単一の関数です。一方、pノルムの正規化項を表します。 SVM、線形/ロジスティック回帰、Lasso、スパース ロジスティック回帰はすべてこのカテゴリに分類されます。この問題は通常、主空間または双対空間のいずれかで解決されます。私たちの議論では、この主/双対問題を次のフェンチェル-ロックフェラー双対形式に抽象化します。

ここで、α と w は主/双対変数、A はデータ ポイントの列ベクトルを含むデータ マトリックス、f* と g* は f と g の凸共役です。非負双対ギャップ（w(α) = ∇f(Aα)）は、主または双対のいずれかの準最適性の計算可能な上限を提供し、強い凸性の下での最適解でゼロに減らすことができます。ソリューションの品質を検証し、収束のマーカーとして使用できます。 lの滑らかさとrの強い凸性に従って、ターゲットl(u)+r(u)をOAまたはOBにマッピングできます。

各ケースの代表的な例は、Elastic Net Regression がケース I、Lasso がケース II、SVM がケース III です。ここではノックダウンのプロセスは省略します。

3. CoCoAフレームワーク

データが K 台のマシンに分散されている場合にターゲット OA を最小限に抑えるには、計算を K 個のローカル サブサンプルに分散し、各グローバル反復中に K 個のローカル更新を組み合わせる必要があります。まず、データ マトリックス A の列が K 個のデータ パーティションに分割されます。各ワーカーマシン k について、i∈Pk の場合は 、それ以外の場合は を定義します。この表現はデータの分布方法とは関係がないことに注意してください。データ マトリックスの次元 n と d はそれぞれ、特徴の数またはデータ ポイントの数を表すことができます。この互換性は CoCoA の大きな利点です。CoCoA は、どちらが大きいか、どのアルゴリズムが使用されているかに応じて、特徴またはデータ ポイントごとにデータを柔軟に分割する方法を提供します。

分布g(α)は分離可能であるため単純である。しかし、f(Aα)を分配するには、その二次近似を最小化する必要があります。データのローカル サブサンプルのみを読み取る次のローカル二次サブ問題を定義します。

マシンk上の列の集合を表します。これは、前の反復からの共有ベクトルに似ており、すべてのi∈Pk上のローカル変数αiの変化を表し、i∉Pkの場合はゼロになります。このサブ問題は、固定された v の周りの近傍 f の線形化であり、最も効率的な二次最適化ソルバーによって解決できます。直感的にわかるように、これはローカルな変動を考慮に入れてグローバルなターゲット OA に非常に近い値に近似しようとします。各ローカルサブ問題が最適に解決できる場合、REDUCE K 更新は、OA の f 部分のデータに依存しない、ブロックに依存しない近似のステップとして解釈できます。ただし、従来の近似法とは異なり、CoCoA では正確な局所解は必要ありません。代わりに、局所的な準最適性（最適値からの予想される絶対偏差として定義される）を許容し、それを収束境界に組み込みます。これについては以下で説明します。これは、特定の問題、データセット、およびマシン構成に合わせて最適化された単一の既存のソルバーを再利用したい実務者にとって大きな利点となります。

完全なアルゴリズムは次のとおりです。

調整可能なハイパーパラメータが 2 つあります。γ はワーカー マシンからの更新を組み合わせる方法を制御し、σ' はデータ分割の難易度を表します。実際には、与えられた γ∈(0,1] に対して、σ′:=γK と設定します。γ=1 および σ′=K は最も速い収束を保証しますが、理論的にはどれでも十分なはずです。詳細な証明については、元の論文を参照してください。

CoCoA のプライマル・デュアル柔軟性は大きな利点です。私たちは常に OA を解決しているという事実にもかかわらず、それを OA の根本または二重として見ることは自由です。つまり、根本的な問題を OA にマッピングすると、OA が根本になります。これを OB にマッピングすると、OA は双対になります。 OA をプリミティブとして扱うことで、Lasso のような非強凸正規化項を解くことができます。これは通常、データがデータ ポイントではなく特徴によって分散されている場合に当てはまります。これは、Lasso、スパース ロジスティック回帰、または L1 のような他のスパース性を誘導する事前分布でうまく機能します。 CoCoA のこの単純な変種を解決するには、グローバル反復ごとに O(データ ポイントの数) の通信コストがかかります。一方、OA をデュアルとして見ると、SVM のヒンジ損失や絶対偏差損失などの非滑らかな損失を考慮することができ、データが特徴ではなくデータ ポイントの観点から分散されている場合に最適に機能します。このバリアントでは、グローバル反復ごとに O(機能の数) の通信コストがかかります。 2 つの CoCoA バリアントの概要は次のとおりです。

上記の表を再利用すると、次のようになります。

次の表は、CoCoA フレームワークで構築される一般的なモデルの例を示しています。

元の設定（アルゴリズム 2）では、ローカル サブ問題はローカル データ パッチ上の 2 次問題となり、ローカル データ パッチのみが正規化されます。デュアル設定（アルゴリズム 3）では、経験的損失は、2 次項で近似された正規化項を使用して、ローカルにのみ適用されます。

4. 収束分析

議論を混乱させる技術的な議論を避けるため、ここでは主要な結果のみを示します。興味のある読者は、詳細については原文論文を参照してください。

デモンストレーションを簡略化するために、主な前提を 3 つ示します。

1. データは K 台のマシンに均等に分散されます。
2. データ行列Aの列は||xi||≤1を満たします。
3. ここでは、収束が保証され、分散環境で収束速度が最も速い、γ = 1 かつ σ' = K の場合のみを検討します。

最初の収束結果には、gi または L-Lipschitz の一般的な凸性の使用が含まれます (これら 2 つの条件は同等です)。

L 有界サポートと - 滑らかな定義については、元の論文を参照してください。この定理は、非強凸正則化子 (Lasso やスパース ロジスティック回帰など) を持つモデル、または非滑らかな損失 (SVM のヒンジ損失など) を持つモデルをカバーします。

また、強く凸または滑らかな gi (これら 2 つの条件も同等) では線形収束が速くなることも示せます。これは、弾性ネット回帰とロジスティック回帰をカバーします。

同様に、μ 強凸性の定義も元の論文に記載されています。

どちらの定理も、局所解 Θ の品質の定義として次の仮定を参照します。

この仮定は本質的に、局所二次問題の経験的絶対偏差の前に Θ を乗法定数として定義します。実際には、並列ローカル計算に割り当てられる時間は、すべての K ワーカー間で更新をプールするための合計通信時間コストとほぼ等しくなります。

これらの収束定理を前のカテゴリーに関連付けると次のようになります。

V. 実験

CoCoA を、Lasso、Elastic Net Regression、SVM 向けのいくつかの最先端の汎用大規模分散最適化アルゴリズムと比較します。

1. MB-SGD: ミニバッチ確率的勾配降下法。 Lasso については、L1-prox 上の MB-SGD と比較します。 Apache Spark MLlib v1.5.0 で実装し、最適化しました。
2. GD: 完全勾配降下法。 Lasso には、近似バージョンの PROX-GD を使用しました。 Apache Spark MLlib v1.5.0 で実装し、最適化しました。
3. L-BFGS: 有限メモリの準ニュートン法。 Lasso には、OWL-QN (直交座標限定準ニュートン法) を使用しました。 Apache Spark MLlib v1.5.0 で実装し、最適化しました。
4. ADMM: 乗数の交互方向法。 Lasso では共役勾配を使用しました。 SVMにはSDCA（Stochastic Dual Coordinate Ascent）を使用しました。
5. MB-CD: ミニバッチ並列化座標降下法。 SVMにはMB-SDCAを使用しました。

トラブルを避けるため、比較に関係する各方法のパラメータ調整の詳細については説明しません。興味のある読者は、論文の結果を再現するために元の論文を参照してください。 CoCoA の場合、すべての実験で、単一マシン上のローカル ソルバーとして確率的座標降下法が使用されました。もちろん、より洗練されたソルバーを使用すれば、パフォーマンス レベルをさらに向上させることも可能です。このオープンな実践は、興味のある読者が探求できるように残されています。

比較する指標は、元の最適性からの距離です。私たちは、大きな進歩が見られなくなるまですべての方法を多数の反復で実行し、最小の元の値を選択することでこれを行いました。使用されるデータセットは次のとおりです。

すべてのコードは Apache Spark で記述され、Amazon EC2 m3.xlarge インスタンス (マシンごとに 1 つのコア) で実行されました。コードは GitHub に公開されています:

www.github.com/gingsmith/proxcocoa。

元の設定では、確率的座標降下法をローカル ソルバーとして使用し、反復の総数 H でローカル ソリューションの品質 Θ を調整して、CoCoA を適用し、上記の各データセットに Lasso モデルを適合させます。極端な例として、マルチコア SHOTGUN も含めます。 MB-CD、SHOTGUN、オリジナルの CoCoA の場合、データセットは特徴ごとに分散されます。 MB-SGD、PROX-GD、OWL​​-QN、ADMM の場合、データセットはデータ ポイントごとに分散されます。生の準最適性を秒単位でプロットすると、次のようになります。

明らかに、比較した最良の方法である OWL-QN と比較しても、CoCoA は 50 倍以上速く収束し、Lasso がよく使用される多数の特徴を持つデータセットで最高のパフォーマンスを発揮します。

デュアル設定では、SVM のフィッティングを検討します。 CoCoA は、ローカル ソルバーとして確率的デュアル座標上昇法を使用します。すべての方法では、データがポイントごとに配布されます。明らかに、CoCoA は他の方法よりも大幅に優れています。

CoCoA の主双対互換性を理解するために、両方のバリアントに弾性ネット回帰モデルを適合させ、座標降下法をローカル ソルバーとして使用しました。

オリジナルの CoCoA は、データセットにデータ ポイントではなく多数の特徴がある場合にパフォーマンスが向上し、強い凸性の劣化に対して堅牢です。一方、データセットに特徴ではなく多数のデータ ポイントがある場合、デュアル CoCoA のパフォーマンスは向上しますが、強い凸性損失に対する堅牢性の点ではそれほど優れていません。これは、異なる問題設定に直面したときに、異なる CoCoA バリアント (アルゴリズム 2 またはアルゴリズム 3) を使用する必要があることを実践者に思い出させます。

オリジナルの論文では、オリジナルの CoCoA はローカルスパース性を保持でき、最終的にはそれをグローバルスパース性に引き継ぐなど、さらに興味深い発見も報告されています。 H を調整して Θ を制御することで、機械学習システムの設計者は「計算と通信」のトレードオフ曲線を徹底的に調査し、現在のシステムに最適なバランスを決定できます。

VI.結論

CoCoA は、分散クラスター内で通信​​効率の高い主二重最適化を可能にする一般的な分散最適化フレームワークです。これは、双対性を利用してグローバル目標をローカル二次近似サブ問題に分解することで実現します。これらのサブ問題は、アーキテクトが選択した最先端の単一マシン ソルバーを使用して、任意の精度で並列に解決できます。 CoCoA の柔軟性により、機械学習システムの設計者やアルゴリズム開発者は、分散システムの計算と通信のトレードオフ曲線を簡単に調査し、特定のハードウェア構成と計算負荷に最適なバランスを選択できます。実験的には、CoCoA はこの選択を単一の調整可能なハイパーパラメータ H (反復の合計数) にまとめ、その間接的な同等物 Θ (ローカル ソリューションの品質) は、主 CoCoA とデュアル CoCoA の収束率に関する 2 つの重要な理論的証明に反映されます。実験結果によると、CoCoA は現在の最先端の分散最適化手法よりも 50 倍優れたパフォーマンスを発揮します。

[この記事は51CTOコラム「Machine Heart」、WeChatパブリックアカウント「Machine Heart（id: Almosthuman2014）」からのオリジナル記事です]

この著者の他の記事を読むにはここをクリックしてください