論文の概要: Near-Optimal List Replicability from Littlestone Dimension

• arxiv url: http://arxiv.org/abs/2610.32853v1
• Date: Fri, 23 Oct 2026 16:25:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.606077
• Title: Near-Optimal List Replicability from Littlestone Dimension
• Title（参考訳）: リトルストーン次元からの準最適リスト再現性
• Abstract要約: Littlestone 次元 $d$ と双対 VC 次元 $v*$ を満たす可算領域上のすべての概念クラス $H$ を証明します。 これは指数の対数係数まで$2(d)$の最悪の下限と一致し、前回の最高上限である$mathrmLR(H)le 22O(d)$ of Bun, Livni,
• 参考スコア（独自算出の注目度）: 0.8749675983608171
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{Ω(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_ε(d^2)}$ for fixed accuracy $ε>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $ε$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.
• Abstract（参考訳）: 実現可能なPAC学習フレームワークにおけるリストの複製数を調べ、Littlestone 次元 $d$ と dual VC 次元 $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})} を持つ可算領域上の任意の概念クラス $H$ が証明される。 これは指数の対数係数まで$2^{Ω(d)} の最悪の下限と一致し、以前の最高上限である$\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020] を指数関数的に改善する。 Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] と Lyu (STOC 2026] の作業によって導かれる固定精度$ε>0$に対して、以前の2^{O_ε(d^2)}$のバウンダリとは異なり、我々のバウンダリは$ε$とは独立である。 $2^{O(d\log d)}$boundは、最近の微分プライベートラーニングからの既約性の概念に基づく、リストの複製性の境界付けのための新しい帰納的フレームワークに従う。 $2^{O(dv^*)}$boundは、複数の経験的リスク最小化器の過半数を採決する単純なグローバルな学習者から導かれる。

関連論文リスト

• Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection [10.37026246853005]
  Shamirシークレット共有のための局所漏洩抵抗性とOPI(Optimal Polynomial Intersection)の2つの問題 我々は、これらの2つの問題(Sun、Wooters 2026)の間の最近の接続を使って、両方の問題の最先端を改善します。 LLR に対して、ある定数 $> 0$ が存在して、$R := k/n geq 1/2 - $ である限り、シャミールの秘密共有は局所的に1ビットレジリエントである。 これがいわゆる「一」を破る最初の結果である
  論文  参考訳（メタデータ） (2026-10-08T17:23:04Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Optimistic Rates for Multiclass PAC Learning [39.91890433860882]
  最悪のマルチクラス境界は、最高の分類器が既にほぼ正しいときに小さくならない。 ナタラジャン次元のクラス $d_N$ と Daniely-Shalev-Shwartz 次元 $d_DS$ に対して、最適余剰リスクは2つのエンドポイントで知られている。 固定オラクルリスクが$Lstar$であれば、最適な過剰リスクは$widetilde(sqrtLstar d_N/n+d_DS/n)$で、アルファベットサイズは一様である。
  論文  参考訳（メタデータ） (2026-08-11T12:46:03Z)
• A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
  Lipschitz-of-$nabla f$ $mathcalS_k|p$。 $mathcalS_k|p$。 $nabla f$. $mathcalS_k|p$。
  論文  参考訳（メタデータ） (2024-09-28T18:16:32Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)

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

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