論文の概要: Private Online Prediction from Experts with Small Losses
- arxiv url: http://arxiv.org/abs/2610.29575v1
- Date: Wed, 21 Oct 2026 11:18:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-23 00:40:06.320379
- Title: Private Online Prediction from Experts with Small Losses
- Title（参考訳）: 小さな損失を持つ専門家からのプライベートオンライン予測
- Abstract要約: 既存のプライベートアルゴリズムは、ほぼ最適に後悔する$tildeO(sqrtT)$を達成する。
我々は,低損失構造を著しく改善した,後悔の$tildeO(sqrtLstar)$の最初の微分プライベートアルゴリズムを提示する。
- 参考スコア（独自算出の注目度）: 11.73777775485126
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret $\tilde{O}(\sqrt{T})$, where $T$ is the time horizon. However, this bound becomes suboptimal when $L^\star$, the cumulative loss of the best expert, is significantly less than $T$. In this work, we present the first differentially private algorithm with regret $\tilde{O}(\sqrt{L^\star})$, offering a substantial improvement in the low-loss regime. Our regret bound matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, demonstrating that privacy incurs only a small cost in this setting. Our result assumes that the input sequence is oblivious, i.e., it is fixed in advance and independent of the algorithm's outputs. We also prove that an $\tildeΩ(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.
- Abstract（参考訳）: 我々は、機械学習の基本的な問題である専門家からのオンライン予測を、差分プライバシー制約の下で検討する。
既存のプライベートアルゴリズムは、ほぼ最適に後悔する$\tilde{O}(\sqrt{T})$を達成する。
しかし、最高の専門家の累積損失である$L^\star$が$T$よりもはるかに小さいとき、この境界は準最適となる。
本研究では,低損失状態において有意な改善をもたらす,後悔$\tilde{O}(\sqrt{L^\star})$の微分プライベートアルゴリズムを初めて提示する。
私たちの後悔は、プライバシーパラメーターを一定に設定するために、プライベートでない要素に縛られることと一致しており、この設定ではプライバシーがわずかなコストしか発生しないことを示している。
この結果は、入力シーケンスが不明確である、すなわち、前もって固定され、アルゴリズムの出力とは独立である、と仮定する。
また、$L^\star = 0$であっても、適応的に生成された入力に対して$\tildeΩ(\sqrt{T})$後悔は避けられないことを証明している。
関連論文リスト
- Towards Optimal Differentially Private Regret Bounds in Linear MDPs [0.0]
我々は、LSVI-UCB++を民営化し、オフラインRLから分散認識解析に適応させることにより、新しい微分プライベートアルゴリズムを設計する。
我々のアルゴリズムは、$widetildeO(d sqrtH3 K + H15/4 d7/6 K1/2 / epsilon)$の後悔の限界を達成し、従来のプライベートメソッドよりも改善した。
論文 参考訳（メタデータ） (2025-04-12T20:51:51Z) - Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳（メタデータ） (2024-11-27T00:48:48Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Differentially Private Stochastic Linear Bandits: (Almost) for Free [17.711701190680742]
中心的なモデルでは、最適な非プライベートなアルゴリズムとほとんど同じ後悔を実現しています。
シャッフルモデルでは、中央の場合のように$tildeO(sqrtT+frac1epsilon)$ % for small $epsilon$を後悔する一方、最もよく知られたアルゴリズムは$tildeO(frac1epsilonT3/5)$を後悔する。
論文 参考訳（メタデータ） (2022-07-07T17:20:57Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。