Fugu-MT 論文翻訳(概要): Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems

論文の概要: Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems

arxiv url: http://arxiv.org/abs/2401.15890v1
Date: Mon, 29 Jan 2024 05:05:03 GMT
ステータス: 処理完了
システム内更新日: 2024-01-30 15:48:37.413772
Title: Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems
Title（参考訳）: 非凸有限問題における確率的再帰勾配の確率的保証
Authors: Yanjie Zhong, Jiaqi Li, Soumendra Lahiri
Abstract要約: 本稿では,ランダムな個人境界を持つマーチンゲール差分列のノルムに基づく,次元自由なアゴホフディング型を新たに開発する。本稿では,提案アルゴリズムであるProb-SARAHにおける勾配ノルム推定器の高確率境界について述べる。
参考スコア（独自算出の注目度）: 1.5586874069708228
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper develops a new dimension-free Azuma-Hoeffding type bound on summation norm of a martingale difference sequence with random individual bounds. With this novel result, we provide high-probability bounds for the gradient norm estimator in the proposed algorithm Prob-SARAH, which is a modified version of the StochAstic Recursive grAdient algoritHm (SARAH), a state-of-art variance reduced algorithm that achieves optimal computational complexity in expectation for the finite sum problem. The in-probability complexity by Prob-SARAH matches the best in-expectation result up to logarithmic factors. Empirical experiments demonstrate the superior probabilistic performance of Prob-SARAH on real datasets compared to other popular algorithms.
Abstract（参考訳）: 本稿では,ランダムな個人境界を持つマーチンゲール差分列の和ノルムに基づく次元自由なアゴホフディング型を開発する。この新たな結果により、有限和問題に対する期待値の計算複雑性を最適に達成する最先端分散化アルゴリズムであるStochAstic Recursive grAdient algoritHm (SARAH) の修正版である提案アルゴリズムProb-SARAHにおいて、勾配ノルム推定器の高確率境界を提供する。 Prob-SARAHによる確率の複雑さは、対数的因子による最良の観測結果と一致する。実証実験では、prob-sarahが実際のデータセット上で他の一般的なアルゴリズムよりも優れた確率的性能を示す。

関連論文リスト

High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文参考訳（メタデータ） (2023-02-02T10:37:23Z)
A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。 1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
論文参考訳（メタデータ） (2023-01-01T21:46:50Z)
Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。決定集合の低次元構造を高次元問題に活用する。
論文参考訳（メタデータ） (2022-11-21T18:31:43Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
Selection of the Most Probable Best [2.1095005405219815]
予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
論文参考訳（メタデータ） (2022-07-15T15:27:27Z)
Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文参考訳（メタデータ） (2021-09-20T21:48:19Z)
High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文参考訳（メタデータ） (2021-06-10T17:54:21Z)
Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization [21.81837334970773]
本稿では,予測最大化(EM)アルゴリズムへのパス付き微分エスティマの拡張を提案する。 SPIDER-EM-IDERと同じ状態アート境界をサポートし,その結果を得た。
論文参考訳（メタデータ） (2020-11-24T21:20:53Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文参考訳（メタデータ） (2020-06-11T19:40:38Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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