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

开发有效的非凸非平滑优化算法及其在机器学习中的应用

• 批准号: 19H04069
• 负责人: 武田 朗子
• 金额: $ 9.48万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19H04069/
• 关键词: 非凸非平滑最適化; 錐最適化問題; ランダム行列理論; ２段階最適化問題; 機械学習; ホモトピー法; ペナルティ法; 確率的DCアルゴリズム; 低ランクスパース最適化; 非凸非平滑最適化; 錐最適化問題; ランダム行列理論; ２段階最適化問題; 機械学習; ホモトピー法; ペナルティ法; 確率的DCアルゴリズム; 低ランクスパース最適化

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

我们主要解决了以下三个主题：[开发SDCA同型方法以获取接近全球最佳解决方案的解决方案]到目前为止，许多非线性优化方法都开发了，使用梯度信息是用于找到悬浮解决方案的解决方案，而SDCA也是类似的解决方案。将SDCA应用于非凸的稀疏优化问题证实，通过该算法的初始解决方案获得的中断解决方案显着差异。因此，我们考虑了将SDCA与同型方法组合在一起，目前正在创建有效的解决方案。具体而言，该解决方案涉及引入一个参数，并不断地从简单的凸优化问题转换为应求解的非凸优化问题，同时遵循停止点的路径。在今年，我们考虑了同时实施参数并实施迭代解决方案以找到停止点以提高计算效率。尽管同时更改参数使理论保证变得困难，但通过限制要研究的优化问题，我们能够为从建议的解决方案中得出的解决方案提供理论保证。 [概率SDCA方法的建议，该方法结合了概率梯度和Hessian矩阵计算]在机器学习领域中，常见的做法是基于梯度计算以解决方案进行梯度计算以处理大规模数据。根据今年研究的结果，我们证实了在SDCA梯度计算中使用随机梯度的效果。此外，我们确认使用随机梯度构建近似的黑森矩阵并在溶液中使用它，可以实现更快的溶液。 [将SDCA应用于优化问题在二次和半阳性的确定锥和收敛分析上]现在，对SDCA的一系列研究已扩展到解决非convex的非凸线非平滑优化问题。以前，我们一直在研究使用欧几里得代数在内的优化问题的有效SDCA解决方案，包括二次和半阳性的确定锥。