論文の概要: Some convergent results for Backtracking Gradient Descent method on
Banach spaces
- arxiv url: http://arxiv.org/abs/2001.05768v2
- Date: Wed, 22 Jan 2020 13:40:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 00:14:05.529255
- Title: Some convergent results for Backtracking Gradient Descent method on
Banach spaces
- Title(参考訳): バナッハ空間における逆追跡勾配降下法の収束結果
- Authors: Tuyen Trung Truong
- Abstract要約: bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。
$mathcalC$ を $f$ の臨界点の集合とする。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Our main result concerns the following condition:
{\bf Condition C.} Let $X$ be a Banach space. A $C^1$ function
$f:X\rightarrow \mathbb{R}$ satisfies Condition C if whenever $\{x_n\}$ weakly
converges to $x$ and $\lim _{n\rightarrow\infty}||\nabla f(x_n)||=0$, then
$\nabla f(x)=0$.
We assume that there is given a canonical isomorphism between $X$ and its
dual $X^*$, for example when $X$ is a Hilbert space.
{\bf Theorem.} Let $X$ be a reflexive, complete Banach space and
$f:X\rightarrow \mathbb{R}$ be a $C^2$ function which satisfies Condition C.
Moreover, we assume that for every bounded set $S\subset X$, then $\sup _{x\in
S}||\nabla ^2f(x)||<\infty$. We choose a random point $x_0\in X$ and construct
by the Local Backtracking GD procedure (which depends on $3$ hyper-parameters
$\alpha ,\beta ,\delta _0$, see later for details) the sequence
$x_{n+1}=x_n-\delta (x_n)\nabla f(x_n)$. Then we have:
1) Every cluster point of $\{x_n\}$, in the {\bf weak} topology, is a
critical point of $f$.
2) Either $\lim _{n\rightarrow\infty}f(x_n)=-\infty$ or $\lim
_{n\rightarrow\infty}||x_{n+1}-x_n||=0$.
3) Here we work with the weak topology. Let $\mathcal{C}$ be the set of
critical points of $f$. Assume that $\mathcal{C}$ has a bounded component $A$.
Let $\mathcal{B}$ be the set of cluster points of $\{x_n\}$. If
$\mathcal{B}\cap A\not= \emptyset$, then $\mathcal{B}\subset A$ and
$\mathcal{B}$ is connected.
4) Assume that $X$ is separable. Then for generic choices of $\alpha ,\beta
,\delta _0$ and the initial point $x_0$, if the sequence $\{x_n\}$ converges -
in the {\bf weak} topology, then the limit point cannot be a saddle point.
- Abstract(参考訳): 我々の主な結果は以下の条件に関するものである。
X$ をバナッハ空間とする。
c^1$ 関数 $f:x\rightarrow \mathbb{r}$ が条件 c を満たすとき、$\{x_n\}$ が弱く収束すると $x$ と $\lim _{n\rightarrow\infty}|||\nabla f(x_n)||=0$ となると、$\nabla f(x)=0$ となる。
我々は、例えば$X$がヒルベルト空間であるとき、$X$とその双対な$X^*$の間に正準同型が与えられると仮定する。
bf定理。
さらに、すべての有界集合 $S\subset X$ に対して、$\sup _{x\in S}||\nabla ^2f(x)||<\infty$ が成り立つと仮定する。
ランダムな点 $x_0\in x$ を選択し、ローカルなバックトラッキング gd 手順によって構成する($\alpha ,\beta ,\delta _0$,詳細は後で参照) シーケンス $x_{n+1}=x_n-\delta (x_n)\nabla f(x_n)$。
1) $\{x_n\}$ のすべてのクラスタポイントは {\bf weak} 位相において、$f$ の臨界点である。
2) $\lim _{n\rightarrow\infty}f(x_n)=-\infty$ または $\lim _{n\rightarrow\infty}||x_{n+1}-x_n||=0$ のいずれか。
3) ここでは弱トポロジーを扱う。
$\mathcal{C}$ を $f$ の臨界点の集合とする。
もし$\mathcal{c}$ が有界成分 $a$ を持つと仮定する。
ここで、$\mathcal{b}$ を$\{x_n\}$ のクラスタ点の集合とする。
もし$\mathcal{B}\cap A\not= \emptyset$ なら、$\mathcal{B}\subset A$ と $\mathcal{B}$ は連結である。
4)$x$が分離可能であると仮定する。
すると、$\alpha ,\beta ,\delta _0$ と初期点 $x_0$ の一般選択に対して、シーケンス $\{x_n\}$ が {\bf weak} 位相に収束するならば、極限点は鞍点にはならない。
関連論文リスト
- Sparsifying Suprema of Gaussian Processes [6.638504164134713]
我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。
また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
論文 参考訳(メタデータ) (2024-11-22T01:43:58Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳(メタデータ) (2024-06-07T08:26:31Z) - Online Learning of Smooth Functions [0.35534933448684125]
隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。
定数係数までシャープな$textopt_p(mathcal F_q)$の新たなバウンダリを見つける。
マルチ変数のセットアップでは、$textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$に関連する不等式を確立し、$textopt_p(mathcal F)$を示す。
論文 参考訳(メタデータ) (2023-01-04T04:05:58Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳(メタデータ) (2021-09-21T13:19:04Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳(メタデータ) (2021-06-25T19:14:45Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳(メタデータ) (2021-03-17T00:59:33Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z) - Backtracking Gradient Descent allowing unbounded learning rates [0.0]
ユークリッド空間上の非制約最適化では、勾配 Descent process (GD) $x_n+1=x_n-delta _n nabla f(x_n)$ の収束を証明するために、通常、学習レート $delta _n$'s が有界であることが要求される。
本稿では,学習率$delta _n$を非有界にする。
この$h$の成長率は、シーケンスの$x_n$の収束を望んでいれば最善であることが示される。
論文 参考訳(メタデータ) (2020-01-07T12:52:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。