論文の概要: Query Complexity of Learning Axis-Aligned Partitions

• arxiv url: http://arxiv.org/abs/2610.35495v1
• Date: Mon, 26 Oct 2026 14:25:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:14.027573
• Title: Query Complexity of Learning Axis-Aligned Partitions
• Title（参考訳）: 軸アライズされた部分の学習における問合せ複雑性
• Abstract要約: この研究は、正確なクエリ学習設定において、高次元のボックスを学習する際のクエリ複雑性を確立する。 古典的な能動学習アルゴリズムであるCALは、クエリの複雑さが$(kd log (n/kd))$であるミニマックス最適化であることを示す。
• 参考スコア（独自算出の注目度）: 22.50066675944677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $Θ(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $Θ(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.
• Abstract（参考訳）: この研究は、正確なクエリ学習設定において、高次元のボックスを学習する際のクエリ複雑性を確立する。 X \subset \mathbb{R}^d$ を$n$ の点の集合とし、$k$ の箱の集合でラベル付けする。 学習者は、ラベルのオラクルへの所定のアクセスに対して$X$ですべてのポイントのラベルを正確に復元することを目的としている。 より構造化された3つの設定を考えます。 最も一般的な設定では、ボックスに条件はなく、重複する可能性がある。 古典的能動学習アルゴリズムであるCAL (Cohn-Atlas-Ladner 1994) は,クエリの複雑さを$ >(kd \log (n/kd))$ で最小最適であることを示す。 箱が切り離されたとき、我々は2つの制度を調べる。 大規模なk$体制では、CALは最小限の最適化のままである。 定数=k$レジームでは、ハルヴィングアルゴリズムの最適化された変種(ヘーゲデュース1995)が$\log(d)$因子でCALを破ることができる。 最後に、最も構造化された設定では、ボックスは一定サイズの決定木の葉に対応する。 我々は、最近の結果(Black-Larsen-Mazumdar-Saha-So 2026)を一般化して、$d$ と $\log n$ の加法である$(d + \log n)$ の厳密なクエリ複雑性を証明し、学習決定切り株のクエリ複雑性を確立する。

関連論文リスト

• Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables [55.952069550106906]
  複雑クエリアンサーリング(CQA)は、不完全知識グラフ(KG)上の基本的な知識表現と推論タスクである ここで$mathcalEk$はKGのエンティティセットを表す。 既存のベンチマークとメソッドは、個々の変数よりも限界ランクに依存している。 我々は、$mathcalEk$を列挙することなく、共同ランキングを近似するフレームワークであるNeural Scalable Symbolic Search (NS3)を提案する。
  論文  参考訳（メタデータ） (2026-05-25T16:04:57Z)
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。 驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
  論文  参考訳（メタデータ） (2026-04-17T14:47:52Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• Quantum Search on Computation Trees [0.0]
  モンタナロ(ToC)によるバックトラック木探索のための量子ウォークアルゴリズムの一般化を示す。 このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
  論文  参考訳（メタデータ） (2025-05-28T14:35:18Z)
• Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
  未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。 非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。 我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
  論文  参考訳（メタデータ） (2025-05-08T07:27:29Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)

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

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