Fugu-MT 論文翻訳(概要): Exponential Concentration of Stochastic Approximation with Non-vanishing Gradient

論文の概要: Exponential Concentration of Stochastic Approximation with Non-vanishing Gradient

arxiv url: http://arxiv.org/abs/2208.07243v3
Date: Thu, 3 Aug 2023 19:22:21 GMT
ステータス: 処理完了
システム内更新日: 2023-08-07 16:42:13.797342
Title: Exponential Concentration of Stochastic Approximation with Non-vanishing Gradient
Title（参考訳）: 非消滅勾配による確率近似の指数集中
Authors: Kody Law and Neil Walton and Shangda Yang
Abstract要約: 近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行する。非消滅マルコフを持つ射影勾配 Descent に対して、我々の結果は$O(t)$および線形収束率を証明するのに使うことができる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We analyze the behavior of stochastic approximation algorithms where iterates, in expectation, make progress towards an objective at each step. When progress is proportional to the step size of the algorithm, we prove exponential concentration bounds. These tail-bounds contrast asymptotic normality results which are more frequently associated with stochastic approximation. The methods that we develop rely on a geometric ergodicity proof. This extends a result on Markov chains due to Hajek (1982) to the area of stochastic approximation algorithms. For Projected Stochastic Gradient Descent with a non-vanishing gradient, our results can be used to prove $O(1/t)$ and linear convergence rates.
Abstract（参考訳）: 我々は,確率近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行していくことを期待する。進行がアルゴリズムのステップサイズに比例すると指数集中境界が証明される。これらのテールバウンドのコントラスト漸近正規性の結果は、より頻繁に確率近似と関連付けられる。私たちが開発する手法は幾何学的エルゴディディティ証明に依存している。これはHajek (1982) によるマルコフ連鎖上の結果を確率近似アルゴリズムの領域に拡張する。非消滅勾配の射影確率勾配 Descent に対して、この結果は$O(1/t)$と線形収束率の証明に利用できる。

関連論文リスト

Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
論文参考訳（メタデータ） (2024-03-29T21:12:25Z)
Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。本稿では,直感的に設計を記述し,設計選択について説明する。本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
論文参考訳（メタデータ） (2023-10-31T16:15:13Z)
Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文参考訳（メタデータ） (2023-08-18T05:11:50Z)
A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization [10.820943271350442]
本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
論文参考訳（メタデータ） (2022-07-30T18:50:36Z)
Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文参考訳（メタデータ） (2022-07-09T01:44:17Z)
Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文参考訳（メタデータ） (2021-11-29T15:10:09Z)
Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
StochAstic Recursive grAdientritHm (SARAH)アルゴリズムは、Gradient Descent (SGD)アルゴリズムのばらつき低減版である。本稿では,完全勾配の必要性を除去する。集約された勾配は、SARAHアルゴリズムの完全な勾配の見積もりとなる。
論文参考訳（メタデータ） (2021-11-26T06:00:44Z)
Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文参考訳（メタデータ） (2021-08-25T21:30:27Z)
Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文参考訳（メタデータ） (2021-07-21T17:10:14Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文参考訳（メタデータ） (2020-02-26T12:53:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。