論文の概要: Agnostic Online Learning and Excellent Sets
- arxiv url: http://arxiv.org/abs/2108.05569v3
- Date: Sun, 06 Jul 2025 09:18:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-09 14:27:11.361673
- Title: Agnostic Online Learning and Excellent Sets
- Title（参考訳）: Agnostic Online Learning and Excellent Sets
- Authors: Maryanthe Malliaris, Shay Moran,
- Abstract要約: モデル理論の意味で、$epsilon$-excellent set が任意の $epsilon frac12$ in $k$-edge 安定グラフに対して存在することを示す。
また、この設定に適した動的Sauer-Shelah-Perles lemmaのバージョンも提供します。
- 参考スコア（独自算出の注目度）: 18.557423328068122
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\epsilon$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemer\'edi's celebrated Regularity Lemma). We prove that $\epsilon$-excellent sets exist for any $\epsilon < \frac{1}{2}$ in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\epsilon < 1/{2^{2^k}}$ or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide.
- Abstract（参考訳）: 我々は、オンライン学習のアルゴリズム手法を用いて、モデル理論とコンビネータ学の交差する重要な対象を探索し、アルゴリズム手法がモデル理論の意味で安定した構造を検出し、説明し、理解を深める自然の方法を見つける。
主定理は、$\epsilon$-excellent set の存在を扱う(これは、Szemer\'edi の有名な正則性 Lemma における不規則対の出現を特徴づける、安定正則性 Lemma の鍵である)。
我々は、$\epsilon < \frac{1}{2}$ in $k$-edge stable graphs in the sense of model theory (等しくしてリトルストーン類)に対して、$\epsilon$-excellent set が存在することを証明した。
1つはオンライン学習からの遺言境界、もう1つはLittlestoneクラスのBoolean閉包特性とサンプリングである。
また、この設定に適した動的Sauer-Shelah-Perles lemmaのバージョンも提供します。
証明は、測度と次元から生じる2つの異なる自然概念が、しばしば密に一致していることを示す。
関連論文リスト
- Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。
また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
論文 参考訳（メタデータ） (2025-02-24T20:20:06Z) - The Aldous--Lyons Conjecture II: Undecidability [3.8370118222043694]
調整された非局所ゲームである$G$が与えられた場合、$G$が特別な種類の完全戦略を持つ場合と、$G$のすべての戦略が完璧ではない場合とを区別することは決定不可能である。
共役紙 [BCLV24] に導入された還元を用いて、この不決定性の結果はアルドゥス=リヨン予想に対する負の答えを意味する。
論文 参考訳（メタデータ） (2024-12-30T22:59:56Z) - Topological entanglement and number theory [0.0]
3dチャーン・サイモンズ理論の文脈における位相的多界絡みの研究の最近の発展は、絡み合い測度と数論の間の強い相互作用を示唆している。
我々は、$k から infty$ の半古典的極限において、これらのエントロピーが有限値に収束することを示す。
論文 参考訳（メタデータ） (2024-10-02T12:43:57Z) - The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
スムースブースターは任意の例にあまり重みを付けない分布を生成する。
もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
論文 参考訳（メタデータ） (2024-09-17T23:09:25Z) - A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文 参考訳（メタデータ） (2023-11-10T23:27:23Z) - Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。
具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
論文 参考訳（メタデータ） (2023-11-02T21:10:16Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and
Relaxed Assumptions [33.49807210207286]
新しい補助関数$xi$は、AdaGradsイテレーションの数値と分母の間の相関を扱う複雑さを取り除くのに役立つ。
AdaGradは,学習率がしきい値より低い限り,$(L_0)$smooth条件下での収束に成功していることを示す。
論文 参考訳（メタデータ） (2023-05-29T09:33:04Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳（メタデータ） (2022-09-16T13:59:42Z) - multiPRover: Generating Multiple Proofs for Improved Interpretability in
Rule Reasoning [73.09791959325204]
我々は、自然言語の事実と規則の形で明示的な知識を推論することを目的としている言語形式推論の一種に焦点を当てる。
PRoverという名前の最近の研究は、質問に答え、答えを説明する証明グラフを生成することによって、そのような推論を行う。
本研究では,自然言語規則ベースの推論のために複数の証明グラフを生成するという,新たな課題に対処する。
論文 参考訳（メタデータ） (2021-06-02T17:58:35Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。