論文の概要: Private Online Prediction from Experts: Separations and Faster Rates
- arxiv url: http://arxiv.org/abs/2210.13537v3
- Date: Thu, 29 Jun 2023 19:05:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-03 15:51:30.245470
- 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を達成するために後者が必要となる適応的敵に対する純粋な微分プライバシーと近似微分プライバシーの分離を示す。
関連論文リスト
- 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) - 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) - 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) - 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) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。