論文の概要: The One-Inclusion Graph Algorithm is not Always Optimal

• arxiv url: http://arxiv.org/abs/2212.09270v1
• Date: Mon, 19 Dec 2022 06:49:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-20 19:00:37.661291
• Title: The One-Inclusion Graph Algorithm is not Always Optimal
• Title（参考訳）: 独占グラフアルゴリズムは必ずしも最適とは限らない
• Authors: Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy
• Abstract要約: 本稿では,Vapnik-Chervonenkisクラスに対する探索的一括グラフアルゴリズムを提案する。 我々は,近年の予測手法により,同じ低い高確率性能が継承されていることを示す。
• 参考スコア（独自算出の注目度）: 11.125968799758436
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first COLT open problems, Warmuth conjectured that this prediction strategy always implies an optimal high probability bound on the risk, and hence is also an optimal PAC algorithm. We refute this conjecture in the strongest sense: for any practically interesting Vapnik-Chervonenkis class, we provide an in-expectation optimal one-inclusion graph algorithm whose high probability risk bound cannot go beyond that implied by Markov's inequality. Our construction of these poorly performing one-inclusion graph algorithms uses Varshamov-Tenengolts error correcting codes. Our negative result has several implications. First, it shows that the same poor high-probability performance is inherited by several recent prediction strategies based on generalizations of the one-inclusion graph algorithm. Second, our analysis shows yet another statistical problem that enjoys an estimator that is provably optimal in expectation via a leave-one-out argument, but fails in the high-probability regime. This discrepancy occurs despite the boundedness of the binary loss for which arguments based on concentration inequalities often provide sharp high probability risk bounds.
• Abstract（参考訳）: Haussler, Littlestone, Warmuth の 1-inclusion graph アルゴリズムは、標準的なPAC分類設定に縛られた最適な予測内リスクを達成する。 最初のcoltオープン問題の1つで、ウォーマスは、この予測戦略が常にリスクに縛られる最適な高い確率を意味し、したがって最適なpacアルゴリズムでもあると推測した。 実際に興味深いVapnik-Chervonenkisクラスに対して、高い確率リスク境界がマルコフの不等式によって示唆されるものを超えない、予測できない最適な1-包含グラフアルゴリズムを提供する。 本稿では,Varshamov-Tenengolts 誤り訂正符号を用いた1-inclusion グラフアルゴリズムの構築を行った。 私たちの否定的な結果はいくつかの意味を持つ。 まず, 1-inclusion graphアルゴリズムの一般化に基づく近年の予測戦略により, 予測精度の低さが受け継がれていることを示す。 第2に, 本解析では, 期待値が絶対的に最適である場合, 高確率法では失敗する場合と, 予測値が最適である場合の統計学的問題を示す。 この差は、濃度の不等式に基づく議論がしばしば鋭い高い確率リスク境界をもたらす二項損失の境界性にもかかわらず生じる。

関連論文リスト

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments [10.889739958035536]
  本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。 平均値の中央値は近傍最適であり, 一定の要因が得られている。 定数係数のずれのない近傍分離推定器を見つけることは自由である。
  論文  参考訳（メタデータ） (2023-11-21T18:50:38Z)
• Zero-Regret Performative Prediction Under Inequality Constraints [5.513958040574729]
  本稿では不等式制約下での性能予測について検討する。 我々は,ある程度の精度しか必要としない頑健な原始双対フレームワークを開発する。 次に、位置ファミリに対する適応的原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-22T04:54:26Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
  両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。 本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。 提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
  論文  参考訳（メタデータ） (2022-01-12T13:38:33Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。 混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2020-06-19T22:49:42Z)
• The estimation error of general first order methods [12.472245917779754]
  我々は,高次元回帰と低次元行列推定という2種類の推定問題を考察する。 我々は、観測数とパラメータ数の両方が分岐する高次元最適値の誤差を下界に導出する。 これらの下界は、推定誤差が下界とわずかに無視可能な項に一致するアルゴリズムが存在することを意味している。
  論文  参考訳（メタデータ） (2020-02-28T18:13:47Z)

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

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