論文の概要: A Tight Lower Bound for Uniformly Stable Algorithms

• arxiv url: http://arxiv.org/abs/2012.13326v2
• Date: Sun, 24 Jan 2021 22:46:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-25 08:27:45.609851
• Title: A Tight Lower Bound for Uniformly Stable Algorithms
• Title（参考訳）: 一様安定アルゴリズムの厳密な下限
• Authors: Qinghua Liu, Zhou Lu
• Abstract要約: アルゴリズムの安定性を利用して鋭い一般化境界を導出することは、学習理論における古典的かつ強力なアプローチである。 順序 $omega(gamma+fraclsqrtn)$ の厳密な一般化を証明し、これは最もよく知られた上限値から対数因子に一致する。
• 参考スコア（独自算出の注目度）: 6.331019775653315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Leveraging algorithmic stability to derive sharp generalization bounds is a classic and powerful approach in learning theory. Since Vapnik and Chervonenkis [1974] first formalized the idea for analyzing SVMs, it has been utilized to study many fundamental learning algorithms (e.g., $k$-nearest neighbors [Rogers and Wagner, 1978], stochastic gradient method [Hardt et al., 2016], linear regression [Maurer, 2017], etc). In a recent line of great works by Feldman and Vondrak [2018, 2019] as well as Bousquet et al. [2020b], they prove a high probability generalization upper bound of order $\tilde{\mathcal{O}}(\gamma +\frac{L}{\sqrt{n}})$ for any uniformly $\gamma$-stable algorithm and $L$-bounded loss function. Although much progress was achieved in proving generalization upper bounds for stable algorithms, our knowledge of lower bounds is rather limited. In fact, there is no nontrivial lower bound known ever since the study of uniform stability [Bousquet and Elisseeff, 2002], to the best of our knowledge. In this paper we fill the gap by proving a tight generalization lower bound of order $\Omega(\gamma+\frac{L}{\sqrt{n}})$, which matches the best known upper bound up to logarithmic factors
• Abstract（参考訳）: アルゴリズムの安定性を利用して鋭い一般化境界を導出することは、学習理論において古典的かつ強力なアプローチである。 Vapnik と Chervonenkis [1974] が最初に SVM の解析のアイデアを定式化して以来、多くの基本的な学習アルゴリズムの研究に利用されてきた(例えば、$k$-nearest neighbors [Rogers and Wagner, 1978]、確率勾配法 [Hardt et al., 2016]、線形回帰 (Maurer, 2017) など)。 feldman and vondrak [2018, 2019] と bousquet et al による最近の偉大な作品のラインで。 [2020b] は、任意の均一な$\gamma$-stableアルゴリズムと$L$-bounded loss関数に対して、位数 $\tilde{\mathcal{O}}(\gamma +\frac{L}{\sqrt{n}})$ の確率一般化上界を証明する。 安定アルゴリズムの一般化上界の証明には多くの進歩があったが、下界の知識は比較的限られている。 実際、一様安定性の研究 (Bousquet and Elisseeff, 2002) 以来、我々の知る限りでは、非自明な下界は知られていない。 本稿では,最もよく知られた上限値から対数因子に一致する順序 $\omega(\gamma+\frac{l}{\sqrt{n}})$ の厳密な一般化を証明し,そのギャップを埋める。

関連論文リスト

• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。 提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。 また、あるSGDの変種に対する新しい境界を得ることもできる。
  論文  参考訳（メタデータ） (2022-05-27T07:23:01Z)
• Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity [70.65867695317633]
  本稿では,2つの単純な加速勾配法,再発進勾配降下法(AGD)と再発進球法(HB)を提案する。 我々は、我々の手法が$frac1epsilon)$の勾配反復数を達成することを確証する。 我々のアルゴリズムは、ネストフの古典的なAGDオークのHBと再起動機構のみからなるという意味では単純である。
  論文  参考訳（メタデータ） (2022-01-27T10:04:04Z)
• Stability Based Generalization Bounds for Exponential Family Langevin Dynamics [21.26469220896393]
  安定性の概念に基づくノイズの多いミニバッチ反復アルゴリズムの一般化境界について検討する。 本研究では,SGLDの相当な一般化である指数型ファミリーランゲヴィンダイナミクス(EFLD)を導入し,指数型ファミリーノイズを勾配降下で利用できるようにする。 第3に,ベルヌーイ雑音を用いた信号SGDを-1,+1で拡張するノイズシグ-SGDという,EFLDの重要な特殊なケースを考える。
  論文  参考訳（メタデータ） (2022-01-09T18:15:22Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation [2.294014185517203]
  本稿では、収束理論を準確率近似に拡張することを目的とする。 強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
  論文  参考訳（メタデータ） (2020-09-30T04:44:45Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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