論文の概要: Communication Complexity of Universal Features

• arxiv url: http://arxiv.org/abs/2610.27402v1
• Date: Mon, 19 Oct 2026 23:50:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-21 21:58:47.55344
• Title: Communication Complexity of Universal Features
• Title（参考訳）: 普遍的特徴の通信複雑性
• Abstract要約: 機械学習の機能の概念に触発され、特定の関数群で評価できるデータを表現する複雑さについて研究する。 我々は、$Xsim D$を観察し、タスクの前に有限エンコーディングを生成する決定論的エンコーダを考える。 エンコーダによって達成される表現長が、すべての$d* ge 1$と$varepsilon 1/4$に対して、最悪のケース最適であることを示す下限を示す。
• 参考スコア（独自算出の注目度）: 11.783485908331379
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.
• Abstract（参考訳）: 機械学習の機能の概念に触発され、特定の関数群で評価できるデータを表現する複雑さについて研究する。 具体的には、$X\sim D$ を観察し、タスク $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ が指定される前に有限エンコーディングを生成する決定論的エンコーダを考える。 それぞれのタスクに対して、デコーダは$f(X)$でエラーを最大$\varepsilon$で予測しなければならない。 我々は、$O(d^{*}\log(1/\varepsilon))$ bitsで表現を出力するエンコーダを構築し、$d^{*}$は$\mathcal{F}$の二重VC次元である。 我々のエンコーダは、クラスから$O((d^{*}/\varepsilon)\log(1/\varepsilon)$関数を選択し、それらのジョイントラベルパターンを使用してエンコードを生成する。 上界における鍵となるアイデアは、各グリーディ選択から得られるエントロピーと二重VC次元で許されるパターンの数を比較する、新しいポテンシャル関数論である。 エンコーダによって達成される表現長が、すべての$d^* \ge 1$ と $\varepsilon < 1/4$ に対して最悪のケース最適であることを示し、すべての族に対して$\mathcal{F}$ を$O(\log(1/\varepsilon)$因子までインスタンスワイズ最適とする。 ラベルのないサンプルから表現を学習する2つの方法を提供し、表現サイズとサンプルの複雑さについて異なる保証を与える。 実験により,グリーディ構成の精度と大きさのトレードオフを検証し,ニューラルスパースオートエンコーダとの接続性を検討した。

関連論文リスト

• Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals [0.0]
  2つの独立したサンプルと1つの共有シードは、同じ関数を生成する必要がある。 for $varepsilon===10-4$, the worst case over $|H|le M$ is $(log M)2)$, without iterated logarithms. for $dge1$, $0varepsilonle1/16$, $0,le10-3$, every randomized, potentially unroper learner valid across a explicit anchored realizable family requires $(d2/(varepsilon2)$ sample
  論文  参考訳（メタデータ） (2026-10-18T05:17:14Z)
• Stochastic Autoregressive Learning [14.292982828097465]
  連立自己回帰学習のためのPAC学習モデルを提案する。 自己回帰学習が決定論的理論と根本的に異なることを示す。
  論文  参考訳（メタデータ） (2026-08-07T13:40:17Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
  対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
  論文  参考訳（メタデータ） (2026-06-18T11:00:03Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Phase Transitions in Rate Distortion Theory and Deep Learning [5.145741425164946]
  もし$mathcalS$をエンコードするために$mathcalO(R-s)$のエラーを達成できれば、$mathcalS$は$s$で圧縮できると言う。 ある"ニッチ"信号クラスに対して、$mathcalS$が相転移を起こすことを示す。
  論文  参考訳（メタデータ） (2020-08-03T16:48:49Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
  本稿では,表現学習による少数ショット学習について検討する。 1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
  論文  参考訳（メタデータ） (2020-02-21T17:30:00Z)

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

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