論文の概要: Improved Inapproximability of VC Dimension and Littlestone's Dimension
via (Unbalanced) Biclique
- arxiv url: http://arxiv.org/abs/2211.01443v1
- Date: Wed, 2 Nov 2022 19:23:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-04 14:10:12.235677
- Title: Improved Inapproximability of VC Dimension and Littlestone's Dimension
via (Unbalanced) Biclique
- Title（参考訳）: VC次元とリトルストーン次元の(不均衡)二軸による不適応性の改善
- Authors: Pasin Manurangsi
- Abstract要約: 我々は、VC次元とリトルストーン次元を近似するために、最大(アンバランス)双立問題から簡単な還元を与える。
この接続により、近似結果と時間的下界のランニングの難易度を導出する。
- 参考スコア（独自算出の注目度）: 28.57552551316786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of computing (and approximating) VC Dimension and
Littlestone's Dimension when we are given the concept class explicitly. We give
a simple reduction from Maximum (Unbalanced) Biclique problem to approximating
VC Dimension and Littlestone's Dimension. With this connection, we derive a
range of hardness of approximation results and running time lower bounds. For
example, under the (randomized) Gap-Exponential Time Hypothesis or the
Strongish Planted Clique Hypothesis, we show a tight inapproximability result:
both dimensions are hard to approximate to within a factor of $o(\log n)$ in
polynomial-time. These improve upon constant-factor inapproximability results
from [Manurangsi and Rubinstein, COLT 2017].
- Abstract（参考訳）: 我々は,計算(および近似)のVC次元とLittlestoneの次元の複雑さを,概念クラスを明示的に与えられたときに研究する。
我々は、VC次元とリトルストーン次元を近似するために、最大(アンバランス)双立問題から簡単な還元を与える。
この接続により、近似結果の硬度範囲と実行時間下限を導出する。
例えば、(ランダム化された)ギャップ-指数時間仮説や強いプランテッド・クリッド仮説の下では、どちらの次元も多項式時間において$o(\log n)$の係数で近似することが困難である、厳密な不近似結果を示す。
これらは[Manurangsi と Rubinstein, COLT 2017] による定数不適合性を改善する。
関連論文リスト
- On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文 参考訳（メタデータ） (2024-11-16T12:09:37Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Applications of Littlestone dimension to query learning and to
compression [1.9336815376402723]
我々は、ランダムな反例を持つ同値クエリによる学習のために、2017年のシアングルインのモデルを拡張した。
第二に、このモデルを無作為性のある無限の概念クラスに拡張する。
第三に、Littlestone次元と拡張$d$-compressionスキームを持つクラスとの関係に関する改善された結果を与える。
論文 参考訳（メタデータ） (2023-10-07T14:04:18Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。
ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。
また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
論文 参考訳（メタデータ） (2021-10-18T02:57:25Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - 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) - Near-tight closure bounds for Littlestone and threshold dimensions [59.245101116396555]
二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
論文 参考訳（メタデータ） (2020-07-07T17:56:06Z) - Interpolation and Learning with Scale Dependent Kernels [91.41836461193488]
非パラメトリックリッジレス最小二乗の学習特性について検討する。
スケール依存カーネルで定義される推定器の一般的な場合を考える。
論文 参考訳（メタデータ） (2020-06-17T16:43:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。