論文の概要: Understanding the Generalization Error of Markov algorithms through Poissonization

• arxiv url: http://arxiv.org/abs/2502.07584v1
• Date: Tue, 11 Feb 2025 14:31:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:10:03.554840
• Title: Understanding the Generalization Error of Markov algorithms through Poissonization
• Title（参考訳）: ポアソン化によるマルコフアルゴリズムの一般化誤差の理解
• Authors: Benjamin Dupuis, Maxime Haddouche, George Deligiannidis, Umut Simsekli,
• Abstract要約: マルコフアルゴリズムの一般化誤差を解析するための汎用フレームワークを提案する。 我々はまず、PAC-ベイジアン一般化境界に直結する新しいエントロピーフローを開発する。 そして、祝賀された対数的ソボレフ不等式(LSI)の修正版への新しいリンクを描く。
• 参考スコア（独自算出の注目度）: 25.946717717350047
• License:
• Abstract: Using continuous-time stochastic differential equation (SDE) proxies to stochastic optimization algorithms has proven fruitful for understanding their generalization abilities. A significant part of these approaches are based on the so-called ``entropy flows'', which greatly simplify the generalization analysis. Unfortunately, such well-structured entropy flows cannot be obtained for most discrete-time algorithms, and the existing SDE approaches remain limited to specific noise and algorithmic structures. We aim to alleviate this issue by introducing a generic framework for analyzing the generalization error of Markov algorithms through `Poissonization', a continuous-time approximation of discrete-time processes with formal approximation guarantees. Through this approach, we first develop a novel entropy flow, which directly leads to PAC-Bayesian generalization bounds. We then draw novel links to modified versions of the celebrated logarithmic Sobolev inequalities (LSI), identify cases where such LSIs are satisfied, and obtain improved bounds. Beyond its generality, our framework allows exploiting specific properties of learning algorithms. In particular, we incorporate the noise structure of different algorithm types - namely, those with additional noise injections (noisy) and those without (non-noisy) - through various technical tools. This illustrates the capacity of our methods to achieve known (yet, Poissonized) and new generalization bounds.
• Abstract（参考訳）: 連続時間確率微分方程式(SDE)を用いた確率最適化アルゴリズムは、それらの一般化能力を理解する上で有益であることが証明されている。 これらのアプローチのかなりの部分は「エントロピーフロー」と呼ばれる一般化解析を大幅に単純化した手法に基づいている。 残念なことに、ほとんどの離散時間アルゴリズムではそのようなよく構造化されたエントロピーフローは得られず、既存のSDEアプローチは特定のノイズやアルゴリズム構造に限られている。 本稿では,マルコフアルゴリズムの一般化誤差を公式近似保証付き離散時間プロセスの連続近似である 'Poissonization' を用いて解析する汎用フレームワークを導入することにより,この問題を軽減することを目的とする。 このアプローチを通じて、我々はまず、PAC-ベイズ一般化境界に直結する新しいエントロピーフローを開発する。 次に、祝賀された対数的ソボレフ不等式(LSI)の修正版に対する新しいリンクを作成し、そのようなLSIが満たされた場合を特定し、改善された境界を得る。 このフレームワークは,汎用性以外にも,学習アルゴリズムの特定の特性を活用できる。 特に、異なるアルゴリズムタイプのノイズ構造、すなわち、追加のノイズ注入(ノイズ)と非ノイズ(ノイズ)のノイズを、様々な技術ツールに組み込む。 これは、既知の(イェート、ポアソン化)および新しい一般化境界を達成する方法の能力を示す。

関連論文リスト

• Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent [30.84181129503133]
  この10年で、異なる損失関数に適用された異なるアルゴリズムに対する安定性の増大が見られた。 本稿では,最適化アルゴリズムの安定性を証明するための統一的なガイドラインを導入する。 私たちのアプローチは柔軟で、他の一般的な学習クラスにも容易に適用できます。
  論文  参考訳（メタデータ） (2023-05-20T01:49:58Z)
• On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights [0.0]
  Fazylabらによって導入されたフレームワークを再検討し、離散的かつ連続的な時間で最適化アルゴリズムのためのLyapunov関数を構築する。 滑らかで強凸な目的関数に対して、そのような構成に必要な要求を緩和する。 文献で利用できるものよりも良い収束率を証明します。
  論文  参考訳（メタデータ） (2023-05-15T14:03:16Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Distributed Value Function Approximation for Collaborative Multi-Agent Reinforcement Learning [2.7071541526963805]
  本稿では,多エージェントオフポリシー学習のための分散勾配に基づく時間差分アルゴリズムを提案する。 提案するアルゴリズムは,その形式,可視性トレースの定義,時間スケールの選択,コンセンサス反復を組み込む方法などによって異なる。 より弱い情報構造制約の下で時間差分アルゴリズムにどのように適用できるかを示す。
  論文  参考訳（メタデータ） (2020-06-18T11:46:09Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。