Development of nonlinear semidefinite optimization theory and application to machine learning

非线性半定优化理论的发展及其在机器学习中的应用

基本信息

批准号：
20K19748
负责人：
奥野貴之
金额：
$ 2.66万
依托单位：
Seikei University (2022)Institute of Physical and Chemical Research (2020-2021)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

2022年度では, 非線形最適化問題の最重要クラスの一つである最小２乗問題に着目し、とくにその問題に対する数値解法の一つであるレーベンバーグ・マルカート法（以下、LM法）のアルゴリズムの改良型について以下２点の研究を行い、いすれも最適化の国際論文誌に投稿中である。なお、新たに開発した両アルゴリズムとも本研究課題の対象である半正定値錐上の最小２乗問題に適用可能である。１. 加速勾配法に基づいた一般化LM法とそのオラクル計算量保証と２次収束性保証の両立２．リーマン多様体上のLM法の開発と理論保証まず１についてであるが、LM法は或る強凸最適化問題を部分問題として繰返し近似的に解くことで元問題の解へ収束する点列を生成するアルゴリズムである。その近似精度と元問題の解への２次収束性の関係、全体の計算量の見積もりと近似精度の関係は各々知られているものの、両性質を担保できる近似精度の設定は不明だった。提案LM法では、２次収束性と全体の計算量の保証が両方可能な近似精度の設定方法を明らかにした。なお、本LM法は最小２乗問題だけでなく、より一般的なクラスである最小化問題に適用可能である。２の研究ではユークリッド空間上のみで論じられてきたLM法をより一般的な空間であるリーマン多様体に拡張した。本LM法に対して、大域的収束性に加えエラーバウンド条件という緩い条件下で２次収束性を証明した。両手法とも機械学習などで現れる問題に対して適用し、既存のLM法やニュートン法などと比較して優れた性能を発揮することを確認した。

在2022年，我们专注于最小二乘问题，这是最重要的非线性优化问题之一，并在Levenberg-Marquatt方法的改进算法上进行了两个研究点（以下简称以下简称LM方法），这是对问题的数值解决方案之一，并已将其用于国际论文。两种新开发的算法都可以应用于半正面确定锥体上的最小二乘问题，这是本研究主题的主题。 1。基于加速梯度方法及其在保证甲骨文计算量和保证二阶收敛量之间的平衡2。首先，LM方法对RIEMANN流形的开发和理论保证，首先是1，LM方法是一种算法，该算法是一种通过重复求解的点，从而使点的序列融合了一个点的序列，可以重复求解某个序列，以重复求解一个强大的解决方案。尽管近似准确性与二次收敛与原始问题解决方案之间的关系，但已知总计算复杂性估计与近似精度之间的关系，但可以保证这两种属性的近似准确性的设置尚不清楚。提出的LM方法揭示了一种设置近似精度的方法，该方法既可以确保二次收敛和总体计算复杂性。此外，这种LM方法不仅可以应用于最小二乘问题，还可以应用于更一般的最小化问题类别。在第二项研究中，仅在欧几里得空间中进行了讨论的LM方法已扩展到更一般的空间，Riemann歧管。在这种LM方法中，我们已经证明，在误差结合条件的松散条件以及全局收敛条件下，它是二次收敛。两种方法都应用于机器学习和其他领域中出现的问题，并且与现有的LM和牛顿方法相比，确认可以提供出色的性能。