論文の概要: Unconstrained optimisation on Riemannian manifolds
- arxiv url: http://arxiv.org/abs/2008.11091v2
- Date: Mon, 31 Aug 2020 11:00:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 03:45:08.433885
- Title: Unconstrained optimisation on Riemannian manifolds
- Title（参考訳）: リーマン多様体上の非制約最適化
- Authors: Tuyen Trung Truong
- Abstract要約: 本稿では, (Local-) Backtracking Gradient Descent と New Q-Newton の手法について記述する。
また、対称正方行列の最小固有値を計算するための明示的な計算を行う。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we give explicit descriptions of versions of (Local-)
Backtracking Gradient Descent and New Q-Newton's method to the Riemannian
setting.Here are some easy to state consequences of results in this paper,
where X is a general Riemannian manifold of finite dimension and
$f:X\rightarrow \mathbb{R}$ a $C^2$ function which is Morse (that is, all its
critical points are non-degenerate).
{\bf Theorem.} For random choices of the hyperparameters in the Riemanian
Local Backtracking Gradient Descent algorithm and for random choices of the
initial point $x_0$, the sequence $\{x_n\}$ constructed by the algorithm either
(i) converges to a local minimum of $f$ or (ii) eventually leaves every compact
subsets of $X$ (in other words, diverges to infinity on $X$). If $f$ has
compact sublevels, then only the former alternative happens. The convergence
rate is the same as in the classical paper by Armijo.
{\bf Theorem.} Assume that $f$ is $C^3$. For random choices of the
hyperparametes in the Riemannian New Q-Newton's method, if the sequence
constructed by the algorithm converges, then the limit is a critical point of
$f$. We have a local Stable-Center manifold theorem, near saddle points of $f$,
for the dynamical system associated to the algorithm. If the limit point is a
non-degenerate minimum point, then the rate of convergence is quadratic. If
moreover $X$ is an open subset of a Lie group and the initial point $x_0$ is
chosen randomly, then we can globally avoid saddle points.
As an application, we propose a general method using Riemannian Backtracking
GD to find minimum of a function on a bounded ball in a Euclidean space, and do
explicit calculations for calculating the smallest eigenvalue of a symmetric
square matrix.
- Abstract（参考訳）: 本稿では、 (Local-) Backtracking Gradient Descent and New Q-Newton's method to the Riemannian set. ここでは、X が有限次元の一般リーマン多様体であり、$f:X\rightarrow \mathbb{R}$ a $C^2$ function that is Morse (つまり、すべての臨界点は非退化である)であるような結果のいくつかを簡単に述べることができる。
bf定理。
} リーマン局所追跡勾配Descentアルゴリズムにおけるハイパーパラメータのランダムな選択と初期点$x_0$のランダムな選択に対して、このアルゴリズムによって構築されたシーケンス$\{x_n\}$
(i)最低額のf$に収束する
(ii) 最終的にすべてのコンパクト部分集合は $x$ となる(言い換えれば、$x$ の無限大に発散する)。
もし$f$ がコンパクトな部分レベルを持つなら、以前の選択肢のみが生じる。
収束率は、Armijoの古典的な論文と同じである。
bf定理。
f$が$C^3$であると仮定する。
リーマンの新しいq-ニュートン法における超パラメータのランダムな選択に対して、アルゴリズムによって構築された列が収束すると、極限は$f$の臨界点となる。
アルゴリズムに付随する力学系に対して、局所安定・中心多様体定理、つまり、$f$のサドル点に近いものが存在する。
極限点が非退化最小点であれば、収束の速度は二次的である。
さらに、x$ がリー群の開部分集合であり、初期点 $x_0$ がランダムに選択されるなら、サドル点をグローバルに避けることができる。
本稿では、リーマン逆追跡gdを用いてユークリッド空間内の有界球上の関数の最小値を求める一般的な方法を提案し、対称正方行列の最小固有値を計算するための明示的な計算を行う。
関連論文リスト
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded
Geometric Penalties [21.141544548229774]
我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。
我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
論文 参考訳（メタデータ） (2023-05-25T15:43:07Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - A fast and simple modification of Newton's method helping to avoid
saddle points [0.0]
この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
論文 参考訳（メタデータ） (2020-06-02T10:38:00Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。