論文の概要: Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L
ojasiewicz Functions
- arxiv url: http://arxiv.org/abs/2210.16997v6
- Date: Wed, 19 Apr 2023 12:20:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 17:38:56.102865
- Title: Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L
ojasiewicz Functions
- Title(参考訳): L ojasiewicz関数に対する確率ゼロ階勾配の収束速度
- Authors: Tianyu Wang and Yasong Feng
- Abstract要約: Lojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの収束率を証明する。
その結果, mathbbN $ における f (mathbfx_t) - f (mathbfx_infty) _t は $ | mathbfx_infty よりも早く収束できることがわかった。
- 参考スコア(独自算出の注目度): 6.137707924685666
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove convergence rates of Stochastic Zeroth-order Gradient Descent (SZGD)
algorithms for Lojasiewicz functions. The SZGD algorithm iterates as
\begin{align*}
\mathbf{x}_{t+1} = \mathbf{x}_t - \eta_t \widehat{\nabla} f (\mathbf{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
(\mathbf{x}_t) $ is the approximate gradient estimated using zeroth-order
information only.
Our results show that $ \{ f (\mathbf{x}_t) - f (\mathbf{x}_\infty) \}_{t \in
\mathbb{N} } $ can converge faster than $ \{ \| \mathbf{x}_t -
\mathbf{x}_\infty \| \}_{t \in \mathbb{N} }$, regardless of whether the
objective $f$ is smooth or nonsmooth.
- Abstract(参考訳): Lojasiewicz関数に対する確率ゼロ階勾配Descent(SZGD)アルゴリズムの収束率を証明した。
szgdアルゴリズムは、 \begin{align*} \mathbf{x}_{t+1} = \mathbf{x}_t - \eta_t \widehat{\nabla} f (\mathbf{x}_t), \qquad t = 0,1,2,3,\cdots , \end{align*} ここで、$f$ は \l ojasiewicz の不等式を満たす目的関数であり、 \l ojasiewicz exponent $\theta$, $\eta_t$ はステップサイズ(学習率)であり、$ \widehat{\nabla} f (\mathbf{x}_t)$ はゼロ次情報のみを用いた近似勾配である。
その結果、$f$ が滑らかであるか否かに関わらず、$ \{f (\mathbf{x}_t) - f (\mathbf{x}_\infty) \}_{t \in \mathbb{n} } $ は$ \{ \| \mathbf{x}_t\mathbf{x}_\infty \| \}_{t \in \mathbb{n} }$ よりも高速に収束することが示された。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。