論文の概要: Optimal Algorithms for Private Online Learning in a Stochastic
Environment
- arxiv url: http://arxiv.org/abs/2102.07929v1
- Date: Tue, 16 Feb 2021 02:48:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 15:01:19.259703
- Title: Optimal Algorithms for Private Online Learning in a Stochastic
Environment
- Title(参考訳): 確率環境下でのプライベートオンライン学習のための最適アルゴリズム
- Authors: Bingshan Hu and Zhiming Huang and Nishant A. Mehta
- Abstract要約: プライベートオンライン学習の2つのバリエーションを検討します。
第1の変種は差分プライベート・バンディットである。
最適な後悔境界を達成できる任意の UCB ベースのアルゴリズムを提案する。
第2の変種は、プライベートオンライン学習の完全な情報バージョンである。
- 参考スコア(独自算出の注目度): 5.489507031856551
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider two variants of private stochastic online learning. The first
variant is differentially private stochastic bandits. Previously, Sajed and
Sheffet (2019) devised the DP Successive Elimination (DP-SE) algorithm that
achieves the optimal $ O \biggl(\sum\limits_{1\le j \le K: \Delta_j >0} \frac{
\log T}{ \Delta_j} + \frac{ K\log T}{\epsilon} \biggr)$ problem-dependent
regret bound, where $K$ is the number of arms, $\Delta_j$ is the mean reward
gap of arm $j$, $T$ is the time horizon, and $\epsilon$ is the required privacy
parameter. However, like other elimination style algorithms, it is not an
anytime algorithm. Until now, it was not known whether UCB-based algorithms
could achieve this optimal regret bound. We present an anytime, UCB-based
algorithm that achieves optimality. Our experiments show that the UCB-based
algorithm is competitive with DP-SE. The second variant is the full information
version of private stochastic online learning. Specifically, for the problems
of decision-theoretic online learning with stochastic rewards, we present the
first algorithm that achieves an $ O \left( \frac{ \log K}{ \Delta_{\min}} +
\frac{ \log K}{\epsilon} \right)$ regret bound, where $\Delta_{\min}$ is the
minimum mean reward gap. The key idea behind our good theoretical guarantees in
both settings is the forgetfulness, i.e., decisions are made based on a certain
amount of newly obtained observations instead of all the observations obtained
from the very beginning.
- Abstract(参考訳): 私たちは、プライベート確率オンライン学習の2つのバリエーションを検討します。
最初の変種は、差動的にプライベートな確率的バンドである。
Sajed and Sheffet (2019)はDP-SEアルゴリズムを考案し、O \biggl(\sum\limits_{1\le j \le K: \Delta_j >0} \frac{ \log T}{ \Delta_j} + \frac{ K\log T}{\epsilon} \biggr)$ problem-dependent regret bound, where $K$ is the number of arms, $\Delta_j$ is the mean reward gap of arm $j$, $T$ is the time horizon, $\epsilon$ is the privacy parameter。
しかし、他の除去スタイルアルゴリズムと同様に、これは時限アルゴリズムではない。
これまで、UCBベースのアルゴリズムがこの最適な後悔の限界を達成できるかどうかは分かっていなかった。
最適性を実現するUCBベースのアルゴリズムを随時発表します。
実験の結果,本アルゴリズムはdp-seと競合することがわかった。
第二の変種は、プライベート確率オンライン学習の完全な情報バージョンです。
具体的には、確率的報酬による決定理論的オンライン学習の問題に対して、$ O \left( \frac{ \log K}{ \Delta_{\min}} + \frac{ \log K}{\epsilon} \right)$ 後悔有界($\Delta_{\min}$ が最小平均報酬ギャップである)を実現する最初のアルゴリズムを提示する。
両方の設定における私たちの良い理論的保証の背後にある重要なアイデアは、忘れること、すなわち、最初に得られたすべての観察ではなく、一定量の新しく得られた観測に基づいて決定が行われます。
関連論文リスト
- Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳(メタデータ) (2023-12-24T08:27:30Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳(メタデータ) (2023-10-17T19:43:37Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-27T21:19:24Z) - Counterfactual Optimism: Rate Optimal Regret for Stochastic Contextual
MDPs [48.98020692698762]
我々は, UC$3$RL アルゴリズムを用いて, 残酷な文脈的 MDP (CMDPs) を提案する。
我々のアルゴリズムは効率的な(効率的なオフライン回帰オラクルを仮定すると)、$widetildeO(H3 sqrtT |S| |A|(log (|mathcalF|/delta) + log (|mathcalP|/delta) )$ regret guarantee。
論文 参考訳(メタデータ) (2022-11-27T20:38:47Z) - UniRank: Unimodal Bandit Algorithm for Online Ranking [0.0]
We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。
いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
論文 参考訳(メタデータ) (2022-08-02T15:01:33Z) - Unimodal Mono-Partite Matching in a Bandit Setting [0.0]
We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。
いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
論文 参考訳(メタデータ) (2022-08-02T14:55:50Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2021-06-05T14:11:01Z) - 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) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。