論文の概要: 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$ であることを示す。
関連論文リスト
- Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。
サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
論文 参考訳(メタデータ) (2023-08-12T00:26:08Z) - 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) - Unrolled Compressed Blind-Deconvolution [77.88847247301682]
sparse multi channel blind deconvolution (S-MBD) はレーダー/ソナー/超音波イメージングなどの多くの工学的応用で頻繁に発生する。
そこで本研究では,受信した全信号に対して,はるかに少ない測定値からブラインドリカバリを可能にする圧縮手法を提案する。
論文 参考訳(メタデータ) (2022-09-28T15:16:58Z) - COMISR: Compression-Informed Video Super-Resolution [76.94152284740858]
ウェブやモバイルデバイスのほとんどのビデオは圧縮され、帯域幅が制限されると圧縮は厳しい。
圧縮によるアーティファクトを導入せずに高解像度コンテンツを復元する圧縮インフォームドビデオ超解像モデルを提案する。
論文 参考訳(メタデータ) (2021-05-04T01:24:44Z) - Eluder Dimension and Generalized Rank [48.27338656415236]
eluder次元は$sigma$-rankよりも指数関数的に大きいことが分かる。
sigma$ が $mathrmrelu$ の活性化であるとき、 eluder 次元は $sigma$-rank よりも指数関数的に大きいことが示される。
論文 参考訳(メタデータ) (2021-04-14T16:53:13Z) - 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) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳(メタデータ) (2020-08-06T09:50:29Z) - Private Query Release Assisted by Public Data [96.6174729958211]
本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。
我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
論文 参考訳(メタデータ) (2020-04-23T02:46:37Z) - The VC-dimension of k-vertex d-polytopes [1.0660480034605242]
我々は、$mathbb Rd$ の $k$-vertex polytopes クラスの VC 次元は、少なくとも 8d2klogk$ であり、Long と Warmuth の古い疑問に答える。
論文 参考訳(メタデータ) (2020-04-09T23:00:08Z) - Agnostic Sample Compression Schemes for Regression [30.539063844697772]
他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。
$ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
論文 参考訳(メタデータ) (2018-10-03T11:46:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。