論文の概要: Tracking the Best Expert Privately

• arxiv url: http://arxiv.org/abs/2503.09889v1
• Date: Wed, 12 Mar 2025 23:17:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 15:52:01.496125
• Title: Tracking the Best Expert Privately
• Title（参考訳）: 最高の専門家をプライベートに追跡する
• Authors: Aadirupa Saha, Vinod Raman, Hilal Asi,
• Abstract要約: 我々は、動的後悔の下で専門家のアドバイスで予測する問題に対して、微分プライベートなアルゴリズムを設計する。 我々の研究は3つの自然な種類の敵に対処し、変化する分布、曖昧さ、適応性を持ち、3つのケースすべてに対してサブ線形後悔を伴うアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 31.03746573619407
• License:
• Abstract: We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three natural types of adversaries, stochastic with shifting distributions, oblivious, and adaptive, and designs algorithms with sub-linear regret for all three cases. In particular, under a shifting stochastic adversary where the distribution may shift $S$ times, we provide an $\epsilon$-differentially private algorithm whose expected dynamic regret is at most $O\left( \sqrt{S T \log (NT)} + \frac{S \log (NT)}{\epsilon}\right)$, where $T$ and $N$ are the epsilon horizon and number of experts, respectively. For oblivious adversaries, we give a reduction from dynamic regret minimization to static regret minimization, resulting in an upper bound of $O\left(\sqrt{S T \log(NT)} + \frac{S T^{1/3}\log(T/\delta) \log(NT)}{\epsilon^{2/3}}\right)$ on the expected dynamic regret, where $S$ now denotes the allowable number of switches of the best expert. Finally, similar to static regret, we establish a fundamental separation between oblivious and adaptive adversaries for the dynamic setting: while our algorithms show that sub-linear regret is achievable for oblivious adversaries in the high-privacy regime $\epsilon \le \sqrt{S/T}$, we show that any $(\epsilon, \delta)$-differentially private algorithm must suffer linear dynamic regret under adaptive adversaries for $\epsilon \le \sqrt{S/T}$. Finally, to complement this lower bound, we give an $\epsilon$-differentially private algorithm that attains sub-linear dynamic regret under adaptive adversaries whenever $\epsilon \gg \sqrt{S/T}$.
• Abstract（参考訳）: 我々は、動的後悔の下で、専門家のアドバイスによる予測問題に対する差分プライベートなアルゴリズムを設計する。 本研究は,3つの自然な逆問題に対処し,分布の変化に確率的であり,不明瞭で適応的なアルゴリズムを設計し,これら3つのケースに対してサブ線形後悔を伴うアルゴリズムを設計する。 特に、分布が$S$倍にシフトする確率的逆数の下で、期待される動的後悔が最大$O\left( \sqrt{S T \log (NT)} + \frac{S \log (NT)}{\epsilon}\right)$であるような$\epsilon$-differentially private algorithmを提供する。 不可解な敵に対しては、動的後悔の最小化から静的後悔の最小化への還元を与え、その結果、$O\left(\sqrt{S T \log(NT)} + \frac{S T^{1/3}\log(T/\delta) \log(NT)}{\epsilon^{2/3}}\right)$の上限となる。 最後に、静的な後悔と同様に、動的設定に対する難解な逆数と適応的な逆数とを基本的に分離する:我々のアルゴリズムは、高民制における不愉快な逆数に対してサブ線形後悔が達成可能であることを示す一方で、任意の$(\epsilon, \delta)$-differentially private algorithmは、$\epsilon \le \sqrt{S/T}$に対して適応的逆数に対して線形的後悔をしなくてはならないことを示す。 最後に、この下界を補うために、$\epsilon$-differentially private algorithm を与える。

関連論文リスト

• Private Online Learning via Lazy Algorithms [52.772510023828744]
  我々は,オンライン学習の問題,特に専門家によるオンライン予測(OPE)とオンライン凸最適化(OCO)について検討する。 遅延オンライン学習アルゴリズムをプライベートアルゴリズムに変換する新しい変換を提案する。
  論文  参考訳（メタデータ） (2024-06-05T20:43:05Z)
• 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)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。 また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
  論文  参考訳（メタデータ） (2022-01-21T22:08:07Z)
• 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)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。 差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。 同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
  論文  参考訳（メタデータ） (2021-02-16T02:48:16Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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