論文の概要: Optimal Anytime-Valid Tests for Composite Nulls
- arxiv url: http://arxiv.org/abs/2512.20039v1
- Date: Tue, 23 Dec 2025 04:14:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-24 19:17:49.74204
- Title: Optimal Anytime-Valid Tests for Composite Nulls
- Title（参考訳）: 複合核の最適時変試験
- Authors: Shubhanshu Shekhar,
- Abstract要約: 合成ヌルに対する最適レベル-$$パワーワンテストの設計問題を考察する。
まず、有限アルファベットのケース($|mathcalX| = m infty$)を考えると、インフニバーサル$e$-プロセスに基づくテストが最適であることを示す。
- 参考スコア（独自算出の注目度）: 12.048034578791954
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of designing optimal level-$α$ power-one tests for composite nulls. Given a parameter $α\in (0,1)$ and a stream of $\mathcal{X}$-valued observations $\{X_n: n \geq 1\} \overset{i.i.d.}{\sim} P$, the goal is to design a level-$α$ power-one test $τ_α$ for the null $H_0: P \in \mathcal{P}_0 \subset \mathcal{P}(\mathcal{X})$. Prior works have shown that any such $τ_α$ must satisfy $\mathbb{E}_P[τ_α] \geq \tfrac{\log(1/α)}{γ^*(P, \mathcal{P}_0)}$, where $γ^*(P, \mathcal{P}_0)$ is the so-called $\mathrm{KL}_{\inf}$ or minimum divergence of $P$ to the null class. In this paper, our objective is to develop and analyze constructive schemes that match this lower bound as $α\downarrow 0$. We first consider the finite-alphabet case~($|\mathcal{X}| = m < \infty$), and show that a test based on \emph{universal} $e$-process~(formed by the ratio of a universal predictor and the running null MLE) is optimal in the above sense. The proof relies on a Donsker-Varadhan~(DV) based saddle-point representation of $\mathrm{KL}_{\inf}$, and an application of Sion's minimax theorem. This characterization motivates a general method for arbitrary $\mathcal{X}$: construct an $e$-process based on the empirical solutions to the saddle-point representation over a sufficiently rich class of test functions. We give sufficient conditions for the optimality of this test for compact convex nulls, and verify them for Hölder smooth density models. We end the paper with a discussion on the computational aspects of implementing our proposed tests in some practical settings.
- Abstract（参考訳）: 合成ヌルに対する最適レベル-$α$パワーワンテストの設計問題を考察する。
パラメータ $α\in (0,1)$ と $\mathcal{X}$-valued observed $\{X_n: n \geq 1\} \overset{i.i.d.}{\sim} P$ が与えられた場合、目標は、null $H_0: P \in \mathcal{P}_0 \subset \mathcal{P}(\mathcal{X})$ に対して、レベル-$α$のパワーワンテスト $τ_α$ を設計することである。
そのような$τ_α$ は $\mathbb{E}_P[τ_α] \geq \tfrac{\log(1/α)}{γ^*(P, \mathcal{P}_0)}$, ここで $γ^*(P, \mathcal{P}_0)$ は、いわゆる $\mathrm{KL}_{\inf}$ である。
本稿では,この下界を$α\downarrow 0$とする構成スキームの開発と解析を行う。
まず、有限アルファベットの場合~($|\mathcal{X}| = m < \infty$)を考えると、上記の意味では \emph{universal} $e$-process~(普遍予測器と実行中のヌルMLEの比で生成される)に基づくテストが最適であることを示す。
この証明は、$\mathrm{KL}_{\inf}$のDonsker-Varadhan~(DV)ベースのサドル点表現と、シオンのミニマックス定理の適用に依存する。
この特徴付けは、任意の$\mathcal{X}$: 十分にリッチなテスト関数のクラス上のサドルポイント表現に対する経験的解に基づいて$e$-プロセスを構築するための一般的なメソッドを動機付けている。
コンパクト凸零点に対するこのテストの最適性について十分な条件を与え、ヘルダー滑らか密度モデルに対して検証する。
本稿は,提案した試験を実践的な環境で実施する際の計算的側面について論じる。
関連論文リスト
- A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
我々は,分散レベルと出力レベルの両方でエラーを定量化する,Top-$$ attention truncationという統一フレームワークを開発した。
総偏差距離は捨てられたソフトマックスのテール質量と一致し,$mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$を満たすことを示す。
論文 参考訳（メタデータ） (2025-12-08T15:36:41Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳（メタデータ） (2025-09-15T14:26:11Z) - Revisiting Agnostic PAC Learning [30.67561230812141]
PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。
経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。
私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
論文 参考訳（メタデータ） (2024-07-29T08:20:49Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - 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) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Minimax Optimal Regression over Sobolev Spaces via Laplacian
Regularization on Neighborhood Graphs [25.597646488273558]
非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。
ラプラシアン滑らか化が多様体適応であることを証明する。
論文 参考訳（メタデータ） (2021-06-03T01:20:41Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。