論文の概要: Nearly Linear Private Learning of Littlestone Classes

• arxiv url: http://arxiv.org/abs/2610.23160v1
• Date: Fri, 16 Oct 2026 08:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 00:56:07.8368
• Title: Nearly Linear Private Learning of Littlestone Classes
• Title（参考訳）: リトルストーンクラスのニアリニアプライベートラーニング
• Abstract要約: 本稿では,適切な安定性を満足するランクを備えたデータ依存型候補集合の構造的指数関数機構を提案する。 部分空間指標のような自然のリトルストーン類では、この階数は単純な幾何学的解釈を持ち、それは余次元である。 これにより、任意のフィールド上で最大$d$の次元の部分空間に対してプライベートなPAC学習者が得られる。
• 参考スコア（独自算出の注目度）: 26.82507907585014
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism.
• Abstract（参考訳）: 異なるプライベートな学習は、個々のトレーニング例を保護しながら、データから学習することを目的としている。 二項分類において、有限リトルストーン次元は、近似プライベートPAC学習可能性(Alon et al , JACM 2022)を特徴付ける。 この次元がどのようにプライベートサンプルの複雑さを制御するかを理解することは、依然として中心的な問題である。 リトルストーン次元$d$のクラスでは、最初の一般上界はd$(Bun, Livni, Moran, FOCS 2020)の2倍指数である。 その後、これを$\widetilde O(d^6)$ (Ghazi et al , STOC 2021)、$\widetilde O(d^5)$ (Lyu, STOC 2026)へと改善した。 我々は、ほぼ線型の上界が$O(d\log d)$であることを証明する。 我々の主なアルゴリズム的貢献は、適切な安定性条件を満たすランクを備えたデータ依存候補集合の構造的指数関数機構である。 部分空間指標のような自然のリトルストーン類では、この階数は単純な幾何学的解釈を持ち、それは余次元である。 これにより、任意の体上の任意の次元上の部分空間に対して最大$d$でプライベートなPAC学習者となり、周囲次元への依存が強く、Kaplan et al (STOC 2025) の二次的依存が改善される。 モデル理論の考えに基づいて、一般のリトルストーン類に対して適切な階数を構築し、その機構が要求する数え上げ境界を確立する。

関連論文リスト

• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
  論文  参考訳（メタデータ） (2026-05-13T15:41:30Z)
• Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks [8.250374560598493]
  雑音の多い質問から階層的な特徴を持つ一層教師ネットワークを学習する際の情報理論的限界について検討する。 有効幅$k_c$付近でtextscAdam を訓練した学生が,これらの最適スケーリング法則を実現することを示す。
  論文  参考訳（メタデータ） (2026-05-11T11:39:03Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Private Learning of Littlestone Classes, Revisited [2.1043427184533035]
  偏微分プライバシーの制約を考慮したLittlestoneクラスのオンライン学習とPAC学習について考察する。 我々の主な成果は、オンラインで学習するLittlestoneクラスに対して、$tildeO(d9.5cdot log(T))$の誤りを許容可能なケースで与える、プライベートな学習者です。 これは最先端[GL'21]に対する2倍の指数的改善であり、このタスクの下位境界に近づきます。
  論文  参考訳（メタデータ） (2025-09-30T01:22:40Z)
• Private List Learnability vs. Online List Learnability [26.86418374191696]
  この研究は、PACリスト学習の文脈において、差分プライバシー(DP)とオンライン学習の関連について考察する。 有限$k$-モノトーン次元は、有限$k$-リトルストーン次元とともにDP$k$-list学習可能性の別の必要条件であることを示す。
  論文  参考訳（メタデータ） (2025-06-15T14:10:46Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)

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

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