論文の概要: Publicly-Verifiable Certificates for Statistical Algorithms

• arxiv url: http://arxiv.org/abs/2607.15528v1
• Date: Fri, 17 Jul 2026 00:32:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-20 17:56:52.722093
• Title: Publicly-Verifiable Certificates for Statistical Algorithms
• Title（参考訳）: 統計的アルゴリズムのための公開検証証明書
• Abstract要約: 我々は、新しい概念を定義し、研究する: 統計的妥当性の公検証証明(pvCSVs) pvCSVは、学習アルゴリズムの結果が有効であることを示す、パブリックかつ分散ロバストな認証を可能にする。 本研究では,SQモデルにおける学習の証明システムについて検討し,モデルの強みと限界を実証する。
• 参考スコア（独自算出の注目度）: 2.502327145375967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis $h$ and corresponding certificate $π$; then, any user, who holds a user-specific distribution, can read the pair $(h,π)$ and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes $k$ adaptive queries, we construct pvCSVs where the sample complexity scales with $O(\log k)$, whereas the sample complexity of the best learning algorithms scale with $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.
• Abstract（参考訳）: Goldwasser氏、Rothblum氏、Shafer氏、Yehudayoff氏は、対話型学習証明(ITCS'21)のフレームワークを定義した上で、非対話型学習証明の研究を開始した。 我々は,新しい概念を定義し,研究する。pvCSV(Publicly-Verible Certificates of Statistical Validity)。 pvCSVでは、学習者が仮説$h$とそれに対応する証明書$π$をパブリッシュし、ユーザ固有の分布を持つ任意のユーザがペア$(h,π)$を読み取ることができ、その仮説がユーザ固有の分布に従って有効かどうかを効率的に決定することができる。 適応統計クエリ(SQ)アルゴリズムの文脈でpvCSVを構築する。 適応クエリを$kで作成するSQアルゴリズムを認証するために、サンプル複雑性が$O(\log k)$でスケールするpvCSVを構築し、最高の学習アルゴリズムのサンプル複雑性は$\tilde{O}(\sqrt{k})$でスケールする。 より一般に、SQモデルにおける学習の証明システムについて研究し、モデルの強みと限界を実証する。

関連論文リスト

• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。 SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。 また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
  論文  参考訳（メタデータ） (2026-08-05T17:51:25Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$は、効率的なペアワイドランキングを通じて生成と検証を統合するフレームワークである。 V_$-Inferはポイントワイド検証でPass@1を最大10%改善する。 V_$-PairRLは、標準のRLとポイントワイドのジョイントトレーニングよりも、テストタイムのスケーリングが7ドル--9%で向上する。
  論文  参考訳（メタデータ） (2026-03-04T17:22:16Z)
• Limitations of Membership Queries in Testable Learning [8.837640805363316]
  テスト可能な学習アルゴリズムでは,メンバシップクエリが時間の複雑さを低減できないことを示す。 テスト可能な学習モデルでは、学習者は、データが所望のプロパティを満たすたびに仮説を出力しなければならない。 本稿では,このクラスにおけるTL-Qアルゴリズムが統計的難読化および学習アルゴリズムを効率的に行うことを示す。
  論文  参考訳（メタデータ） (2025-12-01T23:50:20Z)
• 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)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• Symmetric Equilibrium Learning of VAEs [56.56929742714685]
  可変オートエンコーダ(VAE)をデコーダ-エンコーダペアとみなし,データ空間内の分布を潜在空間内の分布にマッピングする。 本研究では,エンコーダとデコーダに対して対称なナッシュ均衡学習手法を提案し,データと潜伏分布の両方がサンプリングによってのみアクセス可能な状況下でのVAEの学習を可能にする。
  論文  参考訳（メタデータ） (2023-07-19T10:27:34Z)
• Offline RL with No OOD Actions: In-Sample Learning via Implicit Value Regularization [90.9780151608281]
  インサンプルラーニング(IQL)は、データサンプルのみを使用して、定量的回帰によってポリシーを改善する。 サンプル内学習のパラダイムがtextitImplicit Value Regularization (IVR) フレームワークの下で生まれることを確認する。 Sparse $Q$-learning (EQL)とExponential $Q$-learning (EQL)の2つの実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-28T08:30:01Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Linear Algorithms for Nonparametric Multiclass Probability Estimation [0.0]
  アンサンブル学習によってクラス確率を推定するために,サポートベクトルマシン (wSVM) が開発された。 計算効率と推定精度の面でwSVMをさらに向上するために,ベースライン学習とOVA学習という2つの新しい学習手法を提案する。
  論文  参考訳（メタデータ） (2022-05-25T03:15:22Z)
• Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
  構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。 我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
  論文  参考訳（メタデータ） (2022-05-03T11:00:59Z)

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

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