論文の概要: Private Online Prediction from Experts: Separations and Faster Rates
- arxiv url: http://arxiv.org/abs/2210.13537v1
- Date: Mon, 24 Oct 2022 18:40:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 14:13:57.185264
- Title: Private Online Prediction from Experts: Separations and Faster Rates
- Title（参考訳）: 専門家によるプライベートオンライン予測:分離と高速化
- Authors: Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
- Abstract要約: 専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
- 参考スコア（独自算出の注目度）: 74.52487417350221
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online prediction from experts is a fundamental problem in machine learning
and several works have studied this problem under privacy constraints. We
propose and analyze new algorithms for this problem that improve over the
regret bounds of the best existing algorithms for non-adaptive adversaries. For
approximate differential privacy, our algorithms achieve regret bounds of
$\tilde{O}(\sqrt{T \log d} + \log d/\varepsilon)$ for the stochastic setting
and $\tilde O(\sqrt{T \log d} + T^{1/3} \log d/\varepsilon)$ for oblivious
adversaries (where $d$ is the number of experts). For pure DP, our algorithms
are the first to obtain sub-linear regret for oblivious adversaries in the
high-dimensional regime $d \ge T$. Moreover, we prove new lower bounds for
adaptive adversaries. Our results imply that unlike the non-private setting,
there is a strong separation between the optimal regret for adaptive and
non-adaptive adversaries for this problem. Our lower bounds also show a
separation between pure and approximate differential privacy for adaptive
adversaries where the latter is necessary to achieve the non-private
$O(\sqrt{T})$ regret.
- Abstract（参考訳）: 専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
我々は,非適応的敵に対する最善の既存アルゴリズムの後悔の限界を克服する新しいアルゴリズムを提案し,解析する。
近似微分プライバシーのために、我々のアルゴリズムは、確率的な設定に対して$\tilde{O}(\sqrt{T \log d} + \log d/\varepsilon)$と、不快な敵に対して$\tilde O(\sqrt{T \log d} + T^{1/3} \log d/\varepsilon)$の後悔境界を達成する。
純粋なDPに対して、我々のアルゴリズムは、高次元のアレンジメント$d \ge T$において、不愉快な敵に対して、初めてサブ線形後悔を得る。
さらに,適応的敵に対する新しい下限を証明した。
この結果から,非私的設定とは違い,適応的かつ適応的でない敵に対する最適な後悔と,この問題に対する非適応的対立との間には強い相違があることが示唆された。
我々の下限はまた、非プライベートな$o(\sqrt{t})$ regretを達成するために後者が必要となる適応的敵に対する純粋な微分プライバシーと近似微分プライバシーの分離を示す。
関連論文リスト
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups [6.925352969721467]
本研究では, 敵・敵双方に対する専門家による個人別オンライン予測の問題点について検討する。
本稿では,Fed-DP-OPE-Stochアルゴリズムを提案する。
難解な敵によって、クライアント間のコラボレーションが後悔のスピードアップに繋がらないことを示す非自明な下位境界を確立します。
論文 参考訳（メタデータ） (2024-09-27T18:43:24Z) - Private Online Learning via Lazy Algorithms [52.772510023828744]
我々は,オンライン学習の問題,特に専門家によるオンライン予測(OPE)とオンライン凸最適化(OCO)について検討する。
遅延オンライン学習アルゴリズムをプライベートアルゴリズムに変換する新しい変換を提案する。
論文 参考訳（メタデータ） (2024-06-05T20:43:05Z) - DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。
我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。
我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
論文 参考訳（メタデータ） (2024-03-22T09:02:12Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - 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) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - 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) - Output Perturbation for Differentially Private Convex Optimization with
Improved Population Loss Bounds, Runtimes and Applications to Private
Adversarial Training [12.386462516398469]
強力な過剰なリスク境界を提供する効率的で実装が容易な差分プライベート(DP)アルゴリズムを見つけることは、現代の機械学習において重要な問題である。
我々は、滑らかさと強い凸性の存在下で、最もよく知られた$(epsilon, 0)$-DP人口損失境界と最速ランタイムを提供する。
我々はこの理論を2つの学習フレームワーク、傾きERMと逆学習フレームワークに適用する。
論文 参考訳（メタデータ） (2021-02-09T08:47:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。