論文の概要: 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つの一般的な機械学習タスクに基づいて評価を行う。
提案アルゴリズムは,最先端リーマン最適化アルゴリズムに比べて計算速度と収束挙動が向上した。
関連論文リスト
- Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data [23.661713049508375]
本稿では,クライアントの設定においてサブマニフォールド上で学習するアルゴリズムを提案する。
提案アルゴリズムは,新しい解析手法を用いて一階最適解の近傍に部分収束することを示す。
論文 参考訳(メタデータ) (2024-06-12T17:53:28Z) - Riemannian Bilevel Optimization [35.42472057648458]
特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。
本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。
様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
論文 参考訳(メタデータ) (2024-05-22T20:49:01Z) - 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) - 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) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Accelerated Algorithms for Convex and Non-Convex Optimization on
Manifolds [9.632674803757475]
距離における凸問題と非最適化問題の解法を提案する。
提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
論文 参考訳(メタデータ) (2020-10-18T02:48:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。