論文の概要: Almost Sure Convergence Rates of Stochastic Zeroth-order Gradient
Descent for \L ojasiewicz Functions
- arxiv url: http://arxiv.org/abs/2210.16997v1
- Date: Mon, 31 Oct 2022 00:53:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 19:32:57.545886
- Title: Almost Sure Convergence Rates of Stochastic Zeroth-order Gradient
Descent for \L ojasiewicz Functions
- Title(参考訳): l ojasiewicz関数に対する確率的零次勾配降下のほぼ確実収束率
- Authors: Tianyu Wang
- Abstract要約: L ojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの収束率をほぼ確実に証明する。
滑らかな L ojasiewicz 函数に対して、列 $ x_t _tinmathbbN$ は有界点 $x_infty$ にほぼ確実に収束する。
本稿は、L ojasiewicz関数のゼロ次アルゴリズムに対して、最も確実な収束率保証を提供する。
- 参考スコア(独自算出の注目度): 5.7569764948783355
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove \emph{almost sure convergence rates} of Zeroth-order Gradient
Descent (SZGD) algorithms for \L ojasiewicz functions. The SZGD algorithm
iterates as \begin{align*}
x_{t+1} = x_t - \eta_t \widehat{\nabla} f (x_t), \qquad t = 0,1,2,3,\cdots ,
\end{align*} where $f$ is the objective function that satisfies the \L
ojasiewicz inequality with \L ojasiewicz exponent $\theta$, $\eta_t$ is the
step size (learning rate), and $ \widehat{\nabla} f (x_t) $ is the approximate
gradient estimated using zeroth-order information. We show that, for {smooth}
\L ojasiewicz functions, the sequence $\{ x_t \}_{t\in\mathbb{N}}$ governed by
SZGD converges to a bounded point $x_\infty$ almost surely, and $x_\infty$ is a
critical point of $f$. If $\theta \in (0,\frac{1}{2}]$, $ f (x_t) - f
(x_\infty) $, $ \sum_{s=t}^\infty \| x_s - x_\infty \|^2$ and $ \| x_t -
x_\infty \| $ ($\| \cdot \|$ is the Euclidean norm) converge to zero
\emph{linearly almost surely}. If $\theta \in (\frac{1}{2}, 1)$, then $ f (x_t)
- f (x_\infty) $ (and $ \sum_{s=t}^\infty \| x_{s+1} - x_s \|^2 $) converges to
zero at rate $o \left( t^{\frac{1}{1 - 2\theta}} \log t \right) $ almost
surely; $ \| x_{t} - x_\infty \| $ converges to zero at rate $o \left(
t^{\frac{1-\theta}{1-2\theta}} \log t \right) $ almost surely. To the best of
our knowledge, this paper provides the first \emph{almost sure convergence
rate} guarantee for stochastic zeroth order algorithms for \L ojasiewicz
functions.
- Abstract(参考訳): L ojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの 'emph{almost sure convergence rate} を証明する。
x_{t+1} = x_t - \eta_t \widehat{\nabla} f (x_t), \qquad t = 0,1,2,3,\cdots , \end{align*} ここで、$f$ は \l ojasiewicz の不等式を満たす目的関数であり、 \l ojasiewicz exponent $\theta$, $\eta_t$ はステップサイズ(学習率)、$ \widehat{\nabla} f (x_t) $ はゼロ次情報を用いて推定される近似勾配である。
我々は、 {smooth} \L ojasiewicz 関数に対して、SZGD が支配する列 $\{ x_t \}_{t\in\mathbb{N}}$ が有界点 $x_\infty$ にほぼ確実に収束し、$x_\infty$ は$f$ の臨界点であることを示す。
もし$\theta \in (0,\frac{1}{2}]$, $ f (x_t) - f (x_\infty) $, $ \sum_{s=t}^\infty \| x_s - x_\infty \|^2$ and $ \| x_tx_\infty \| $$$\| \cdot \|$ is the Euclidean norm) が 0 \emph{linearlyly} に収束する。
もし$\theta \in (\frac{1}{2}, 1)$, $ f (x_t) - f (x_\infty) $ (and $ \sum_{s=t}^\infty \| x_{s+1} - x_s \|^2 $) $o \left( t^{\frac{1}{1 - 2\theta}} \log t \right) $ ほぼ確実に$ \| x_{t} - x_\infty \| $ が 0 に収束すると、$ $o \left( t^{\frac{1-\theta}{1-2\theta}} \log t \right) $ はほぼ確実に 0 に収束する。
我々の知識を最大限に活用するために、この論文は \L ojasiewicz 関数に対する確率零次アルゴリズムに対する最初の \emph{almost sure convergence rate} 保証を提供する。
関連論文リスト
- Exact objectives of random linear programs and mean widths of random
polyhedrons [0.0]
我々は、エンフレアンドム最適化問題(rops)のサブクラスとして、エンフレアンドム線形プログラム(rlps)を考える。
我々の特に焦点は、rpsをランダムなポリヘドロン/ポリトープの平均幅に接続する適切な線形目的性である。
論文 参考訳(メタデータ) (2024-03-06T11:51:52Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic
Optimization [14.960834297685366]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。
最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文 参考訳(メタデータ) (2023-01-16T13:33:37Z) - $L^p$ sampling numbers for the Fourier-analytic Barron space [0.0]
f(x) = int_mathbbRd F(xi), e2 pi i langle x, xi rungle, d xi quad text with quad int_mathbbRd |F(xi)| cdot (1 + |xi|)sigma, d xi infty。
$ (複数形 $s)
論文 参考訳(メタデータ) (2022-08-16T08:41:48Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss
Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
$mathcalM$ を $mathbbRN$ のコンパクト $d$-次元部分多様体とし、リーチ $tau$ とボリューム $V_mathcal M$ とする。
非線形関数 $f: mathbbRN rightarrow mathbbRmm が存在し、$m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math が存在することを証明します。
論文 参考訳(メタデータ) (2022-06-07T15:10:46Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳(メタデータ) (2021-10-12T09:36:41Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳(メタデータ) (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。