論文の概要: Near-tight closure bounds for Littlestone and threshold dimensions
- arxiv url: http://arxiv.org/abs/2007.03668v1
- Date: Tue, 7 Jul 2020 17:56:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 19:24:47.910076
- Title: Near-tight closure bounds for Littlestone and threshold dimensions
- Title（参考訳）: リトルストーンおよびしきい値次元の近位閉包境界
- Authors: Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
- Abstract要約: 二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
- 参考スコア（独自算出の注目度）: 59.245101116396555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study closure properties for the Littlestone and threshold dimensions of
binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$
of Boolean functions with bounded Littlestone (respectively, threshold)
dimension, we establish an upper bound on the Littlestone (respectively,
threshold) dimension of the class defined by applying an arbitrary binary
aggregation rule to $\mathcal{H}_1, \ldots, \mathcal{H}_k$. We also show that
our upper bounds are nearly tight. Our upper bounds give an exponential (in
$k$) improvement upon analogous bounds shown by Alon et al. (COLT 2020), thus
answering a question posed by their work.
- Abstract（参考訳）: 二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
有界なリトルストーン次元を持つブール関数のクラス $\mathcal{h}_1, \ldots, \mathcal{h}_k$ が与えられたとき、任意の二元集計規則を$\mathcal{h}_1, \ldots, \mathcal{h}_k$ に適用して定義されるクラスのリトルストーン(respectiveively, threshold)次元の上界を確立する。
また、上界はほぼきつくなっていることも示している。
我々の上限は、alon et al. (colt 2020) によって示された類似の限界に対して指数関数的に(k$ で)改善される。
関連論文リスト
- Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。
具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
論文 参考訳（メタデータ） (2023-11-02T21:10:16Z) - Applications of Littlestone dimension to query learning and to
compression [1.9336815376402723]
我々は、ランダムな反例を持つ同値クエリによる学習のために、2017年のシアングルインのモデルを拡張した。
第二に、このモデルを無作為性のある無限の概念クラスに拡張する。
第三に、Littlestone次元と拡張$d$-compressionスキームを持つクラスとの関係に関する改善された結果を与える。
論文 参考訳（メタデータ） (2023-10-07T14:04:18Z) - Prediction, Learning, Uniform Convergence, and Scale-sensitive
Dimensions [39.97534972432276]
本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。
このアルゴリズムの絶対誤差の一般上界を証明した。
本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
論文 参考訳（メタデータ） (2023-04-21T15:51:35Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Improved Inapproximability of VC Dimension and Littlestone's Dimension
via (Unbalanced) Biclique [28.57552551316786]
我々は、VC次元とリトルストーン次元を近似するために、最大(アンバランス)双立問題から簡単な還元を与える。
この接続により、近似結果と時間的下界のランニングの難易度を導出する。
論文 参考訳（メタデータ） (2022-11-02T19:23:42Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - 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) - On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies [74.39616164169131]
雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。
Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
論文 参考訳（メタデータ） (2020-06-07T05:19:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。