論文の概要: Optimally compressing VC classes

• arxiv url: http://arxiv.org/abs/2201.04131v2
• Date: Wed, 12 Jan 2022 21:40:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-14 12:40:02.911220
• Title: Optimally compressing VC classes
• Title（参考訳）: 最適圧縮VCクラス
• Authors: Zachary Chase
• Abstract要約: Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Resolving a conjecture of Littlestone and Warmuth, we show that any concept class of VC-dimension $d$ has a sample compression scheme of size $d$.
• Abstract（参考訳）: Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。

関連論文リスト

• Style-Compress: An LLM-Based Prompt Compression Framework Considering Task-Specific Styles [49.65811277223873]
  Style-Compressは、より小さな言語モデルを適用して、新たなタスクでより大きなモデルのプロンプトを、追加のトレーニングなしで圧縮する軽量フレームワークである。 提案手法は,実効圧縮プロンプトを,スタイルのバリエーションやコンテキスト内学習を通じて,タスク固有の実演として反復的に生成し,選択する。 Style-Compressは、オリジナルのプロンプト再構成、テキスト要約、マルチホップQA、CoT推論の4つのタスクで2つのベースライン圧縮モデルを上回っている。
  論文  参考訳（メタデータ） (2024-10-17T21:35:49Z)
• Sample Compression Scheme Reductions [17.389446817000945]
  本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。 我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
  論文  参考訳（メタデータ） (2024-10-16T20:14:02Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Dual VC Dimension Obstructs Sample Compression by Embeddings [25.63430474763066]
  本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。 すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。 この結果は学習理論において重要な意味を持ち、長期にわたるサンプル圧縮予想に対処するための最も広範囲に研究されたアプローチの1つの基本的限界を明らかにする。
  論文  参考訳（メタデータ） (2024-05-27T12:38:25Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
  論文  参考訳（メタデータ） (2022-12-24T01:56:02Z)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
  論文  参考訳（メタデータ） (2022-10-11T13:54:41Z)
• 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)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)
• Agnostic Sample Compression Schemes for Regression [30.539063844697772]
  他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。 $ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
  論文  参考訳（メタデータ） (2018-10-03T11:46:59Z)

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

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