論文の概要: A Sharp Dynamic Haussler Lemma

• arxiv url: http://arxiv.org/abs/2610.29898v1
• Date: Wed, 21 Oct 2026 15:40:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.393324
• Title: A Sharp Dynamic Haussler Lemma
• Title（参考訳）: シャープ動的ハウスラーレンマ
• Abstract要約: ハウスの被覆補題 (JCTA 1995) は、正規化$ell$距離の下で二進VCクラスに対してシャープな$(C/)d$計量エントロピー境界を与える。 正規化された$ell_p$ の有界実数値類に対して、1le pinfty$ ごとに鋭い大域的動的類似を証明した。
• 参考スコア（独自算出の注目度）: 53.21205120247118
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Haussler's covering lemma (JCTA 1995) gives the sharp $(C/δ)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\varepsilon<1/4$, a matching worst-case lower bound $(c/\varepsilon)^{pd}$ holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of $p$. For $p=2$, this resolves the horizon-independent sequential $\ell_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C/δ)^{\operatorname{Ldim}(\mathcal H)}$ global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.
• Abstract（参考訳）: Haussler's cover lemma (JCTA 1995) は、正規化された$\ell_1$ 距離の下で二進VCクラスに対して、シャープな$(C/δ)^d$ 計量エントロピー境界を与える。 正規化された$\ell_p$ の有界実数値類に対して 1 ドル p<\infty$ に対して鋭い大域的動的類似性を証明する。 d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$ と書くと、すべての地平線に対して最大$(C/\varepsilon^p)^d$ と$0<\varepsilon<1/2$ のグローバルな動的被覆が得られる。 ここでは、インスタンスシーケンスとは独立に固定された決定論的因果の専門家の1つのファミリーが、各シーケンスのすべてのターゲットをカバーする。 0<\varepsilon<1/4$の場合、一致した最悪のケースの低いバウンド$(c/\varepsilon)^{pd}$は、1つの固定シーケンス上のバイナリクラスに対して既に保持される。 定数は普遍的であり、$p$とは独立である。 p=2$の場合、これは、ラフリン、スリダーラン、テワリ(PTRF 2015)の地平線に依存しないシーケンシャルな$\ell_2$被覆問題をより強いグローバルな形で解決する。 例えば、$p=1$の場合、シャープな$(C/δ)^{\operatorname{Ldim}(\mathcal H)}$大域的動的被覆を与え、Alon, Ben-Eliezer, Dagan, Moran, Naor, Yogev (STOC 2021) と Malliaris and Moran (Trans. AMS 2024) の問題を解く。 本証明では, 精度の低い修正スケジュールと正確なサンプルプレフィックスを, 目標同定後の正確な継続と組み合わせた。 共有ペアレントルーティングは、これらの継続を許容プレフィックスに分散し、対数オーバーヘッドを排除します。

関連論文リスト

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
  クラスごとの分解$I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$を介して、Side-Channel Existence Theoremを$k$クラスに拡張します。 以下の3つの結果が従う: (1) 活性クラス全体の和形式 MI の下限、(2) カスケード臨界コスト定理と、一様予算境界が消滅する非ゼロ、(3) 精度 $mathrmAcc*
  論文  参考訳（メタデータ） (2026-09-06T00:48:40Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  1つの暗黙のDDIM反転ステップは、事前訓練された拡散モデルが局所多様体幾何学を符号化するかどうかの最も安価なプローブである。 フェルミ窓はモデルのトレーニングサポートと3.6$-$5.6times$で対立し、ヘッセン=リプシッツ定数は法が読み取る曲率の2-$12%である。 最後の条件付き天井 $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  論文  参考訳（メタデータ） (2026-08-24T11:01:54Z)
• The Physical Cutoff Does Not Restore Homogenization: Phase-Dependent Burning in the Strain G-Equation [2.538209532048867]
  C2$非圧縮性周期フローに対して、すべての$varepsilon$-ward barrier certificateが半径を少なくとも2dvarepsilon$でカバーしていることを証明している。
  論文  参考訳（メタデータ） (2026-08-15T17:41:14Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Optimal Temporal Hiding in Correlated Quantum Reference-Frame Processes [0.0]
  $[n,k]_q$コードの一様コセット法則は、$d(Cperp)$スロット以下のすべての集合で同一である。 ネストされたコードに対して$Csubset D$、ペイロード$R=dim D-dim C$、見えない深さ$t=d_mathrmrel(Cperp,Dperp)-1$、セクター距離$d_mathrmrel(D,C)-1leq n$。
  論文  参考訳（メタデータ） (2026-08-06T06:27:12Z)
• The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences [4.588028371034407]
  我々は,データ分布の逆摂動が Cressie-Read divergence of order $k>1$ and radius $geq 0$ で制約されるような$0$--1$-lossのPAC学習について検討した。 VC次元が$d$の仮説クラスに対して、実現可能かつ非依存的なサンプル-複雑性は定数および対数的因子に密接な境界を定めている。
  論文  参考訳（メタデータ） (2026-08-05T10:53:13Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• 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)

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

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