論文の概要: A Note on High-Probability Analysis of Algorithms with Exponential,
Sub-Gaussian, and General Light Tails
- arxiv url: http://arxiv.org/abs/2403.02873v1
- Date: Tue, 5 Mar 2024 11:38:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 15:07:49.488528
- Title: A Note on High-Probability Analysis of Algorithms with Exponential,
Sub-Gaussian, and General Light Tails
- Title（参考訳）: 指数, サブガウス, 一般ライトテールを用いたアルゴリズムの高確率解析に関する研究
- Authors: Amit Attia, Tomer Koren
- Abstract要約: このようなアルゴリズムの解析はブラックボックス方式で削減でき、対数係数の損失はわずかである。
このアプローチは指数関数、準ガウス分布、より一般的な高速分解分布を含む任意の光尾ランダム化にも同時に適用される。
- 参考スコア（独自算出の注目度）: 34.465259431606405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This short note describes a simple technique for analyzing probabilistic
algorithms that rely on a light-tailed (but not necessarily bounded) source of
randomization. We show that the analysis of such an algorithm can be reduced,
in a black-box manner and with only a small loss in logarithmic factors, to an
analysis of a simpler variant of the same algorithm that uses bounded random
variables and often easier to analyze. This approach simultaneously applies to
any light-tailed randomization, including exponential, sub-Gaussian, and more
general fast-decaying distributions, without needing to appeal to specialized
concentration inequalities. Analyses of a generalized Azuma inequality and
stochastic optimization with general light-tailed noise are provided to
illustrate the technique.
- Abstract（参考訳）: この短い注記は、ランダム化のライトテール(しかし必ずしも有界ではない)ソースに依存する確率的アルゴリズムを解析するための単純な技術について記述している。
このようなアルゴリズムの解析は、有界確率変数を使い、解析が容易な同じアルゴリズムのより単純な変種を解析するために、ブラックボックス方式で、対数係数のわずかな損失だけを削減できることを示す。
このアプローチは指数関数、準ガウス分布、より一般的な高速分解分布を含む任意の光尾ランダム化に適用される。
一般化された東の不等式と一般光尾雑音による確率的最適化の分析を行い,その手法を解説した。
関連論文リスト
- Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。
本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-10T06:16:24Z) - Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequality [1.1510009152620668]
我々は、ユークリッド空間上の交互最小化アルゴリズムを理解するためによく用いられる分析手法を、期待最大化(EM)アルゴリズムに拡張する。
対数ソボレフ不等式の自然な一般化の下で有限サンプル誤差境界とEMアルゴリズムの指数収束を求める。
論文 参考訳（メタデータ） (2024-07-25T11:08:53Z) - A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
中心行列および非標準行列に対するフロベニウスノルムにおける低ランク近似誤差の解析のための枠組みを提案する。
最小限の仮定の下では、期待と確率の正確な境界を導出する。
私たちの境界には、プロパティを導出し、実践的な選択を動機付けるための明確な解釈があります。
論文 参考訳（メタデータ） (2024-05-08T04:51:56Z) - Connection between single-layer Quantum Approximate Optimization
Algorithm interferometry and thermal distributions sampling [0.0]
固有状態の振幅と単層QAOAによって生成されるボルツマン分布の理論的導出を拡張する。
我々はまた、この行動が実践的および基本的視点の両方から持つ意味についてもレビューする。
論文 参考訳（メタデータ） (2023-10-13T15:06:58Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Quantization-Based Optimization: Alternative Stochastic Approximation of
Global Optimization [0.0]
NP-hard問題における目的関数のエネルギーレベルを定量化するための大域的最適化アルゴリズムを提案する。
数値実験により,提案アルゴリズムはNP-ハード最適化問題の解法において従来の学習法よりも優れていた。
論文 参考訳（メタデータ） (2022-11-08T03:01:45Z) - Understanding the Generalization Performance of Spectral Clustering
Algorithms [11.025579607812167]
本稿では,一般的なスペクトルクラスタリングアルゴリズムであるEmphrelaxed RatioCutとEmphrelaxed NCutの過剰なリスク境界について検討する。
本稿では,この量をペナルライズするだけでなく,サンプル全体を再固有分解することなくサンプル外のデータをクラスタリングする2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-30T14:21:56Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳（メタデータ） (2022-04-07T00:11:05Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。