論文の概要: Limitations of Membership Queries in Testable Learning
- arxiv url: http://arxiv.org/abs/2512.02279v1
- Date: Mon, 01 Dec 2025 23:50:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-03 21:04:45.650518
- Title: Limitations of Membership Queries in Testable Learning
- Title（参考訳）: テスト可能な学習におけるメンバシップクエリの制限
- Authors: Jane Lange, Mingda Qiao,
- Abstract要約: テスト可能な学習アルゴリズムでは,メンバシップクエリが時間の複雑さを低減できないことを示す。
テスト可能な学習モデルでは、学習者は、データが所望のプロパティを満たすたびに仮説を出力しなければならない。
本稿では,このクラスにおけるTL-Qアルゴリズムが統計的難読化および学習アルゴリズムを効率的に行うことを示す。
- 参考スコア（独自算出の注目度）: 8.837640805363316
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the \emph{testable learning} model of Rubinfeld and Vasilyan [RV23], membership queries cannot decrease the time complexity of testable learning algorithms beyond the complexity of sample-only distribution-specific learning. In the testable learning model, the learner must output a hypothesis whenever the data distribution satisfies a desired property, and if it outputs a hypothesis, the hypothesis must be near-optimal. We give a general reduction from sample-based \emph{refutation} of boolean concept classes, as presented in [Vadhan17, KL18], to testable learning with queries (TL-Q). This yields lower bounds for TL-Q via the reduction from learning to refutation given in [KL18]. The result is that, relative to a concept class and a distribution family, no $m$-sample TL-Q algorithm can be super-polynomially more time-efficient than the best $m$-sample PAC learner. Finally, we define a class of ``statistical'' MQ algorithms that encompasses many known distribution-specific MQ learners, such as those based on influence estimation or subcube-conditional statistical queries. We show that TL-Q algorithms in this class imply efficient statistical-query refutation and learning algorithms. Thus, combined with known SQ dimension lower bounds, our results imply that these efficient membership query learners cannot be made testable.
- Abstract（参考訳）: メンバシップクエリ(MQ)は、特に分散固有の設定において、学習タスクのスピードアップをもたらすことが多い。
本稿では,Rubinfeld と Vasilyan [RV23] の \emph{testable learning} モデルにおいて,テスト可能な学習アルゴリズムの時間的複雑さを,サンプルのみの分布型学習の複雑さを超えて減少させることは不可能であることを示す。
テスト可能な学習モデルでは、学習者は、データ分布が所望の特性を満たすたびに仮説を出力し、仮説を出力した場合、仮説はほぼ最適でなければならない。
本稿では,[Vadhan17, KL18] に示されるブールの概念クラスのサンプルベース \emph{refutation} から,クエリによるテスト可能な学習 (TL-Q) への一般化について述べる。
これにより[KL18]で与えられる学習から難読化への還元により、TL-Qの低い境界が得られる。
その結果、概念クラスと分布ファミリと比較して、$m$sample TL-Qアルゴリズムは、最高の$m$sample PAC学習者よりも極端に時間効率が高い。
最後に、影響推定やサブキューブ条件の統計クエリなど、多くの既知の分布固有のMQ学習者を包含する「統計的」MQアルゴリズムのクラスを定義する。
本稿では,このクラスにおけるTL-Qアルゴリズムが,統計的クエリの難読化と学習アルゴリズムを効率的に行うことを示す。
したがって、既知のSQ次元の低境界と組み合わせることで、これらの効率的なメンバシップクエリ学習者が検証できないことを示す。
関連論文リスト
- Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
ハーフスペースの交叉学習は計算学習理論における中心的な問題である。
たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。
本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-13T00:28:24Z) - Provably Efficient and Agile Randomized Q-Learning [35.14581235983678]
我々は、サンプリングベースの探索をアジャイル、ステップワイド、ポリシー更新と統合した新しいQ-ラーニングアルゴリズムをRandomizedQと呼ぶ。
経験的に、RandomizedQは、ボーナスベースとベイズベースで標準ベンチマークを探索する既存のQラーニングモデルと比較して、優れたパフォーマンスを示している。
論文 参考訳（メタデータ） (2025-06-30T16:08:29Z) - Sample, Don't Search: Rethinking Test-Time Alignment for Language Models [55.2480439325792]
新しいテストタイムアライメントアプローチであるQAlignを紹介します。
テスト時間計算をスケールする際、QAlignは各プロンプトの最適配向分布からのサンプリングに収束する。
マルコフ連鎖モンテカルロのテキスト生成における最近の進歩を取り入れることで、基礎となるモデルを変更したり、ロジットアクセスを必要とせずに、より良い整合出力を可能にする。
論文 参考訳（メタデータ） (2025-04-04T00:41:40Z) - CoT-UQ: Improving Response-wise Uncertainty Quantification in LLMs with Chain-of-Thought [10.166370877826486]
大規模言語モデル(LLM)は多くのタスクで優れるが、生成された応答の不確かさを正確に定量化するのに苦労する。
LLMの既存の不確実量化法(UQ)は、応答性よりも応答性の方が早い。
応答型UQフレームワークであるCoT-UQを提案する。
論文 参考訳（メタデータ） (2025-02-24T14:48:06Z) - LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
大規模言語モデル(LLM)におけるインテリジェンス(インテリジェンス)の出現は、オートマチックラーニングへの統合に関する調査にインスピレーションを与えている。
本稿では,pMAT (probabilistic Minimally Adequate Teacher) の定式化について紹介する。
我々は,解答精度を向上し,学習したオートマタの正確性を確保する技術を開発した。
論文 参考訳（メタデータ） (2024-08-06T07:12:09Z) - Benchmarking Uncertainty Quantification Methods for Large Language Models with LM-Polygraph [83.90988015005934]
不確実性定量化は機械学習アプリケーションにおいて重要な要素である。
最新のUQベースラインの集合を実装した新しいベンチマークを導入する。
我々は、11タスクにわたるUQと正規化技術に関する大規模な実証的研究を行い、最も効果的なアプローチを特定した。
論文 参考訳（メタデータ） (2024-06-21T20:06:31Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-28T16:53:41Z) - A Moment-Matching Approach to Testable Learning and a New
Characterization of Rademacher Complexity [15.746613321517282]
我々は、モーメントマッチングやメートル法非依存のツールを用いて、テスト可能な学習アルゴリズムを開発するための強力な新しいアプローチを提案する。
意外なことに、テスト可能な学習における情報理論の複雑さは、概念クラスのRademacher複雑さによって強く特徴づけられている。
論文 参考訳（メタデータ） (2022-11-23T21:29:51Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。