論文の概要: Sign-Rank, Index, and List Replicability: Connections and Separations
- arxiv url: http://arxiv.org/abs/2606.18236v1
- Date: Tue, 16 Jun 2026 17:57:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.593106
- Title: Sign-Rank, Index, and List Replicability: Connections and Separations
- Title（参考訳）: Sign-Rank, Index, List Replicability: 接続と分離
- Authors: Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak,
- Abstract要約: この問題に対する2つのアプローチは、$mathbbZ$-indexとリストの複製可能性数という、分析し易い尺度によって、符号ランクの低い境界を確立する。
我々は、$mathbbZ$-index がリストの複製率の線型関数によって上界であることが示している。
また、2つの概念クラスの積が2つの概念クラスのリスト複製可能性数の和で束縛されたリスト複製性数を持つことを示す、基本的な構成結果も証明する。
- 参考スコア（独自算出の注目度）: 0.815557531820863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and $\mathbb{Z}_2$-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.
- Abstract（参考訳）: 学習理論において、二項概念クラスの符号ランクは、点と半空間で表現できる最小の次元を捉えている。
非常に興味をそそられるが、標識のランクの低い境界は見つからないことで有名である。
この問題に対する最近の2つのアプローチは、$\mathbb{Z}_2$-index(英語版)とリストの複製可能性数(英語版)という、解析し易い測度による符号階の下位境界を確立する。
これらの測度を順序付け、$\mathbb{Z}_2$-index がリストの複製可能性数の線型関数によって上界であることが示される。
その結果、符号ランクと$\mathbb{Z}_2$-index を強く分離し、フリック、ホセイニ、ヴァシレスキの問題を解く。
これは2つの下界測度よりも強いリストの複製性について、徹底的な研究を動機付けている。
我々は、リストの複製率の上限を、高さと最小の星数という2つの組合せ測度で定めている。
また、2つの概念クラスの積が2つの概念クラスのリスト複製可能性数の和で束縛されたリスト複製性数を持つことを示す、基本的な構成結果も証明する。
関連論文リスト
- Tight list replicability bounds via a novel sphere covering theorem [0.815557531820863]
大域半空間に対して、マージンが大きすぎると、最適リストサイズは周囲次元に等しいことを示す。
また、大マージン半空間の場合、マージンが大きすぎると、最適リストサイズは周囲次元に等しいことを示す。
論文 参考訳（メタデータ） (2026-06-04T13:24:05Z) - Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
$dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか?
この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
論文 参考訳（メタデータ） (2026-05-06T17:53:20Z) - Entanglement-Rank Duality in Quadratic Phase Quantum States [0.0]
二次相量子状態のクラスにおける多部交絡の基礎となる有限体階構造を同定する。
絡み合い構造は、中国語のRemainder Theoremを介して独立した素体寄与に分解されることを示す。
論文 参考訳（メタデータ） (2026-05-06T17:34:42Z) - Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。
関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。
また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
論文 参考訳（メタデータ） (2025-01-22T16:30:58Z) - AGRaME: Any-Granularity Ranking with Multi-Vector Embeddings [53.78802457488845]
我々は,多ベクトル埋め込みを利用して粒度の異なるレベルにランク付けする,任意の粒度ランキングの考え方を紹介した。
検索強化世代におけるポストホック励振付加への命題レベルのランク付けの適用を実証する。
論文 参考訳（メタデータ） (2024-05-23T20:04:54Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Discreteness of asymptotic tensor ranks [7.378597079944368]
置換ランクとスライスランクは累積点を持たず、複素数に対してスライスランクは累積点を持たないことを示す。
我々のアプローチの中心はテンソルのサブランク上の2つの新しい一般下界であり、テンソルがどれだけ対角化できるかを測定する。
行列部分空間における最大階数に対する新しい下界は、3つの異なる方向に3つのテンソルをスライスすることで得られる。
論文 参考訳（メタデータ） (2023-06-02T17:42:39Z) - Learning List-Level Domain-Invariant Representations for Ranking [59.3544317373004]
リストレベルのアライメント -- より高いレベルのリストでドメイン不変表現を学習する。
利点は2つある: これは、ランク付けに縛られる最初のドメイン適応の一般化をもたらし、その結果、提案法に対する理論的支援を提供する。
論文 参考訳（メタデータ） (2022-12-21T04:49:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。