論文の概要: Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
- arxiv url: http://arxiv.org/abs/2510.00574v1
- Date: Wed, 01 Oct 2025 06:53:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 16:59:20.427793
- Title: Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
- Title（参考訳）: 適応的相手に対するプライベートオンライン学習:実現可能で不可知的な設定
- Authors: Bo Li, Wei Wang, Peng Ye,
- Abstract要約: 我々は、学習者がT$のデータポイントのシーケンスを受け取り、仮説の段階ごとに応答しなければならない、プライベートオンライン学習の問題を再考する。
出力仮説全体のストリームは、差分プライバシーを満たすべきである。
一般的なLittlestoneクラスに対して$tildeO_d(sqrtT)$のサブ線形後悔を実現するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 13.129167404736137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of private online learning, in which a learner receives a sequence of $T$ data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [2021] established that every concept class $\mathcal{H}$ with finite Littlestone dimension $d$ is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an $O_{d}(\log T)$ mistake bound against an oblivious adversary. However, their approach yields a suboptimal $\tilde{O}_{d}(\sqrt{T})$ bound against an adaptive adversary. In this work, we present a new algorithm with a mistake bound of $O_{d}(\log T)$ against an adaptive adversary, closing this gap. We further investigate the problem in the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of $\tilde{O}_d(\sqrt{T})$ for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.
- Abstract（参考訳）: 我々は、学習者がT$のデータポイントのシーケンスを受け取り、仮説の段階ごとに応答しなければならない、プライベートオンライン学習の問題を再考する。
出力仮説全体のストリームは、差分プライバシーを満たすべきである。
Golowich と Livni [2021] の以前の研究は、有限のLittlestone次元を持つすべての概念クラス $\mathcal{H}$ が、実現可能な環境でプライベートに学習可能であることを証明した。
特に、不愉快な相手に縛られた$O_{d}(\log T)$ミスを達成するアルゴリズムを提案した。
しかし、それらのアプローチは、適応的敵に対して有界な $\tilde{O}_{d}(\sqrt{T})$ となる。
本研究では,適応的逆数に対して$O_{d}(\log T)$の誤り境界を持つ新しいアルゴリズムを提示し,このギャップを埋める。
さらに、データに仮定を課さないため、実現可能な設定よりも一般的である不可知設定の問題についても検討する。
我々は、一般的なLittlestoneクラスに対して$\tilde{O}_d(\sqrt{T})$のサブ線形後悔を求めるアルゴリズムを提示し、それらが無知環境でプライベートに学習可能であることを示す。
関連論文リスト
- Private Learning of Littlestone Classes, Revisited [2.1043427184533035]
偏微分プライバシーの制約を考慮したLittlestoneクラスのオンライン学習とPAC学習について考察する。
我々の主な成果は、オンラインで学習するLittlestoneクラスに対して、$tildeO(d9.5cdot log(T))$の誤りを許容可能なケースで与える、プライベートな学習者です。
これは最先端[GL'21]に対する2倍の指数的改善であり、このタスクの下位境界に近づきます。
論文 参考訳（メタデータ） (2025-09-30T01:22:40Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games [36.969021834291745]
本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。
この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。
実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
論文 参考訳（メタデータ） (2021-11-17T05:24:21Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。