論文の概要: Private online learning and prediction for Littlestone classes

• arxiv url: http://arxiv.org/abs/2610.06822v1
• Date: Mon, 05 Oct 2026 17:56:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 22:23:30.535454
• Title: Private online learning and prediction for Littlestone classes
• Title（参考訳）: プライベートオンライン学習とLittlestoneクラスの予測
• Abstract要約: 本研究では,難解な現実的敵の下で,個人によるオンライン学習とオンライン予測の誤り境界について検討する。 オンライン学習では、学習者は各段階で仮説を公表する必要があるが、オンライン予測では、学習者は仮説を公表せずに予測を行う必要がある。
• 参考スコア（独自算出の注目度）: 16.396430686633767
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension $d$. First, we prove that every $\br{ε,δ}$-private online learner has a deterministic realisable stream of length $T$ on which the mistake bound is at least $\bE\bs{M_T}=\Om{\frac dε\log\br{ T}^{2/3}}$. In particular, this is the first non-trivial lower in the range $1/T<δ<1/\log T)$ left open in earlier works[SR22,DSS24,LWY24]. Second, we prove that for every class of of Littlestone dimension $d$, there exists an $(ε,δ)$-jointly private predictor with at most $2^{2^{cd^2}}ε^{-2}\log^2\br{2/\br{εδ}}$ expected mistakes, independently of $T$, for some absolute constant $c>0$. Thus, for every fixed class of finite Littlestone dimension when $δ=Θ\br{1/\log T}$, private learning requires $\Om{\br{\log T}^{2/3}}$ expected mistakes, whereas private prediction admits $\bigO{\br{\log\log T}^2}$.
• Abstract（参考訳）: 本研究では,難解な現実的敵の下で,個人によるオンライン学習とオンライン予測の誤り境界について検討する。 オンライン学習では、学習者は各段階で仮説を公表する必要があるが、オンライン予測では、学習者は仮説を公表せずに予測を行う必要がある。 プライベートオンライン学習のための新しい下位境界と、プライベート予測のための上位境界を用いて、これらの2つの問題のサンプルの複雑さは、有限リトルストーン次元$d$のクラスごとに時間的地平線とともに成長する因子によって分離されることを示す。 まず、すべての$\br{ε,δ}$-privateオンライン学習者は、誤り境界が少なくとも$\bE\bs{M_T}=\Om{\frac dε\log{T}^{2/3}}$である長さ$T$の決定論的現実的ストリームを持つことを証明する。 特に、これは 1/T<δ<1/\log T)$ left in early works[SR22,DSS24,LWY24] における最初の非自明な下限である。 第二に、Littlestone 次元のすべてのクラスの $d$ に対して、ある絶対定数 $c>0$ に対して$(ε,δ)$-jointly private predictor が存在し、少なくとも $2^{2^{cd^2}}ε^{-2}\log^2\br{2/\br{εδ}}$ 期待される誤りが存在することを証明している。 したがって、有限リトルストーン次元の任意の固定クラスに対して、$δ= \br{1/\log T}$ のとき、プライベートラーニングは $\Om{\br{\log T}^{2/3}}$ の誤りを必要とするが、プライベート予測は $\bigO{\br{\log T}^2}$ を許容する。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings [13.129167404736137]
  我々は、学習者がT$のデータポイントのシーケンスを受け取り、仮説の段階ごとに応答しなければならない、プライベートオンライン学習の問題を再考する。 出力仮説全体のストリームは、差分プライバシーを満たすべきである。 一般的なLittlestoneクラスに対して$tildeO_d(sqrtT)$のサブ線形後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-01T06:53:57Z)
• Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries [31.339322747660635]
  我々は、$Omegaleft(minn,log Tright)$の新しい下限を示す。 また、我々の低い境界は"オンラインしきい値問題"にまで拡張され、そこでは、多くの"量子クエリ"をプライベートに答えることが目標であることも示しています。
  論文  参考訳（メタデータ） (2024-02-28T16:45:54Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)

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

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