論文の概要: Tight High Probability Bounds for Linear Stochastic Approximation with
Fixed Stepsize
- arxiv url: http://arxiv.org/abs/2106.01257v1
- Date: Wed, 2 Jun 2021 16:10:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-03 18:19:03.572794
- Title: Tight High Probability Bounds for Linear Stochastic Approximation with
Fixed Stepsize
- Title（参考訳）: ステップサイズを固定した線形確率近似の高次確率境界
- Authors: Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin
Scaman, Hoi-To Wai
- Abstract要約: 本稿では,線形近似 (LSA) アルゴリズムの漸近的解析を行う。
我々は、より弱い条件下での LSA の性能に高い確率境界を導出する:$(bf A_n, bf b_n): n in mathbbN*$。
bf A_n: n in mathbbN*$ {\displaystyle \mathbbN*=} の列について追加の仮定なしでは、我々の結論は改善できないことを示す。
- 参考スコア（独自算出の注目度）: 41.38162218102825
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper provides a non-asymptotic analysis of linear stochastic
approximation (LSA) algorithms with fixed stepsize. This family of methods
arises in many machine learning tasks and is used to obtain approximate
solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and
$\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf
b}_n): n \in \mathbb{N}^*\}$. Our analysis is based on new results regarding
moments and high probability bounds for products of matrices which are shown to
be tight. We derive high probability bounds on the performance of LSA under
weaker conditions on the sequence $\{({\bf A}_n, {\bf b}_n): n \in
\mathbb{N}^*\}$ than previous works. However, in contrast, we establish
polynomial concentration bounds with order depending on the stepsize. We show
that our conclusions cannot be improved without additional assumptions on the
sequence of random matrices $\{{\bf A}_n: n \in \mathbb{N}^*\}$, and in
particular that no Gaussian or exponential high probability bounds can hold.
Finally, we pay a particular attention to establishing bounds with sharp order
with respect to the number of iterations and the stepsize and whose leading
terms contain the covariance matrices appearing in the central limit theorems.
- Abstract（参考訳）: 本稿では,線形確率近似 (lsa) アルゴリズムの非漸近的解析について述べる。
この手法の族は、多くの機械学習タスクに現れ、線型システムの近似解を得るために使われる: $\bar{A}\theta = \bar{b}$ for that $\bar{A}$ and $\bar{b}$ can only access through random estimates $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$。
本解析は,タイトであることが示される行列の積に対するモーメントと高確率境界に関する新しい結果に基づいている。
従来より弱い条件下での lsa の性能に関する高い確率境界を導出する。 $\{({\bf a}_n, {\bf b}_n): n \in \mathbb{n}^*\}$ である。
しかし,それとは対照的に,多項式濃度境界をステップ化によって順序付きで定めている。
我々の結論は、ランダム行列の列$\{{\bf A}_n: n \in \mathbb{N}^*\}$に関する追加の仮定なしでは改善できないことを示し、特にガウス的あるいは指数関数的な高確率境界は保持できない。
最後に、我々は、反復の数とステップ化に関してシャープな順序で境界を確立することに特に注意し、その主項は中央極限定理に現れる共分散行列を含む。
関連論文リスト
- Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳（メタデータ） (2023-05-11T16:07:47Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳（メタデータ） (2022-07-10T14:36:04Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。