Developing efficient algorithms for nonconvex non smooth optimization and its application to machine learning

点击翻译按钮获取中文摘要

主に以下の3つのトピックスに取り組んだ.[大域最適解に近い解を求めるための，SDCAホモトピー法の開発] これまで開発された，勾配情報を利用した非線形最適化法の多くは停留解を求めるための解法であり，SDCAも同様の解法である．非凸スパース最適化問題にSDCAを適用すると，アルゴリズムの初期解によって得られる停留解がかなり異なることが確認される．そこで，SDCAとホモトピー法を組み合わせることを検討し，現在，効率的な解法を構築した段階である．具体的には，パラメータを1つ導入して，簡単な凸最適化問題から解くべき非凸最適化問題へと連続変形させつつ，その停留点のパスを追っていく解法である．本年度は，計算効率の向上のため，パラメータの変更と停留点を求めるための反復解法の実行を同時に行うことを検討した．同時にパラメータの変更を行うと，理論保証が難しくなるが，研究対象とする最適化問題を限定することで，提案解法より導出される解について，理論的保証を与えることができた．[確率的な勾配・ヘシアン行列計算を取り入れた確率的SDCA法の提案] 機械学習分野では，大規模データを扱うために，勾配計算に基づく解法に対して勾配計算を確率的に行うことが常套手段となっている．本年度の研究成果により，SDCAの勾配計算に確率的な勾配を用いる効果を確認した．さらに確率的勾配を用いて近似ヘシアン行列を構築し，解法で利用することにより，解法の高速化が達成されることを確認した．[SDCAの2次錐や半正定値錐上の最適化問題への適用と収束解析] SDCAに関する一連の研究は，現在は非凸非平滑最適化問題を解くまでに拡張されている．以前より，ユークリッドジョルダン代数を用いた， 2次錐や半正定値錐を含む最適化問題のための効率的SDCA解法の開発について検討を進めた．