論文の概要: 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} 保証を提供する。
関連論文リスト
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-11-11T03:43:52Z) - In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。
グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
論文 参考訳（メタデータ） (2024-09-13T12:28:42Z) - Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles [38.45952947660789]
本稿では,$(alpha,tau,mathcal)$-projected-dominanceプロパティの下で関数を最小化する一階法の性能限界について検討する。
論文 参考訳（メタデータ） (2024-08-03T18:34:23Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。