論文の概要: Faster Riemannian Newton-type Optimization by Subsampling and Cubic
Regularization
- arxiv url: http://arxiv.org/abs/2302.11076v1
- Date: Wed, 22 Feb 2023 00:37:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 16:46:30.405092
- Title: Faster Riemannian Newton-type Optimization by Subsampling and Cubic
Regularization
- Title(参考訳): 部分サンプリングと立方正則化による高速リーマンニュートン型最適化
- Authors: Yian Deng, Tingting Mu
- Abstract要約: この研究は、制約集合が多様体構造を意味するような制約付き大規模非制約最適化に関するものである。
本稿では,収束性の向上と計算コストの削減を目的とした2階サドル最適化アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 3.867143522757309
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work is on constrained large-scale non-convex optimization where the
constraint set implies a manifold structure. Solving such problems is important
in a multitude of fundamental machine learning tasks. Recent advances on
Riemannian optimization have enabled the convenient recovery of solutions by
adapting unconstrained optimization algorithms over manifolds. However, it
remains challenging to scale up and meanwhile maintain stable convergence rates
and handle saddle points. We propose a new second-order Riemannian optimization
algorithm, aiming at improving convergence rate and reducing computational
cost. It enhances the Riemannian trust-region algorithm that explores curvature
information to escape saddle points through a mixture of subsampling and cubic
regularization techniques. We conduct rigorous analysis to study the
convergence behavior of the proposed algorithm. We also perform extensive
experiments to evaluate it based on two general machine learning tasks using
multiple datasets. The proposed algorithm exhibits improved computational speed
and convergence behavior compared to a large set of state-of-the-art Riemannian
optimization algorithms.
- Abstract(参考訳): この仕事は、制約集合が多様体構造を意味するような制約付き大規模非凸最適化に関するものである。
このような問題を解決することは、多くの基本的な機械学習タスクにおいて重要である。
リーマン最適化の最近の進歩は、多様体上の制約のない最適化アルゴリズムを適用することで、解の便利な回復を可能にした。
しかし、スケールアップし、安定した収束率を維持し、サドルポイントを扱うことは依然として困難である。
本稿では,収束率の向上と計算コストの低減を目的とした2次リーマン最適化アルゴリズムを提案する。
リーマン信頼領域アルゴリズムは、サブサンプリングと立方正則化技術の混合により、鞍点から逃れるために曲率情報を探索する。
提案するアルゴリズムの収束挙動を研究するため,厳密な解析を行う。
また、複数のデータセットを用いて2つの一般的な機械学習タスクに基づいて評価を行う。
提案アルゴリズムは,最先端リーマン最適化アルゴリズムに比べて計算速度と収束挙動が向上した。
関連論文リスト
- Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms [19.99781875916751]
textttZo-RASAは$epsilon$-approximation 1次定常解を生成するのに最適なサンプル複雑性を実現する。
指数写像や並列輸送の代わりに幾何とベクトル輸送を用いることで,アルゴリズムの実用性を向上させる。
論文 参考訳(メタデータ) (2023-09-25T20:13:36Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳(メタデータ) (2022-06-22T23:57:40Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳(メタデータ) (2022-06-04T18:53:44Z) - Accelerated Algorithms for Convex and Non-Convex Optimization on
Manifolds [9.632674803757475]
距離における凸問題と非最適化問題の解法を提案する。
提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
論文 参考訳(メタデータ) (2020-10-18T02:48:22Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic
Optimization Problems [12.010310883787911]
我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。
実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
論文 参考訳(メタデータ) (2020-05-19T07:44:52Z) - A Riemannian Primal-dual Algorithm Based on Proximal Operator and its
Application in Metric Learning [3.511851311025242]
一次変数と双対変数を反復的に最適化する原始双対アルゴリズムを提案する。
提案アルゴリズムの収束を証明し,その非漸近収束率を示す。
ファンドマネージメントにおける最適ファンド選択問題に関する予備実験の結果,有効性が確認された。
論文 参考訳(メタデータ) (2020-05-19T03:31:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。