論文の概要: Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime
- arxiv url: http://arxiv.org/abs/2302.14154v1
- Date: Mon, 27 Feb 2023 21:19:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 18:49:51.324783
- Title: Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime
- Title（参考訳）: 実現可能領域におけるプライベートオンライン最適化のための近似最適化アルゴリズム
- Authors: Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
- Abstract要約: オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 74.52487417350221
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider online learning problems in the realizable setting, where there
is a zero-loss solution, and propose new Differentially Private (DP) algorithms
that obtain near-optimal regret bounds. For the problem of online prediction
from experts, we design new algorithms that obtain near-optimal regret ${O}
\big( \varepsilon^{-1} \log^{1.5}{d} \big)$ where $d$ is the number of experts.
This significantly improves over the best existing regret bounds for the DP
non-realizable setting which are ${O} \big( \varepsilon^{-1} \min\big\{d,
T^{1/3}\log d\big\} \big)$. We also develop an adaptive algorithm for the
small-loss setting with regret $O(L^\star\log d + \varepsilon^{-1}
\log^{1.5}{d})$ where $L^\star$ is the total loss of the best expert.
Additionally, we consider DP online convex optimization in the realizable
setting and propose an algorithm with near-optimal regret $O
\big(\varepsilon^{-1} d^{1.5} \big)$, as well as an algorithm for the smooth
case with regret $O \big( \varepsilon^{-2/3} (dT)^{1/3} \big)$, both
significantly improving over existing bounds in the non-realizable regime.
- Abstract（参考訳）: 本稿では,ゼロロス解が存在するような実現可能な環境でのオンライン学習問題を考察し,ほぼ最適の後悔境界を求める新たな差分プライベート(DP)アルゴリズムを提案する。
専門家によるオンライン予測の問題に対して、我々は、ほぼ最適に後悔する${O} \big( \varepsilon^{-1} \log^{1.5}{d} \big)$を得る新しいアルゴリズムを設計する。
これは、${O} \big( \varepsilon^{-1} \min\big\{d, T^{1/3}\log d\big\} \big)$ である DP の既約集合に対する最良の後悔境界よりも大幅に改善される。
また, 後悔する$O(L^\star\log d + \varepsilon^{-1} \log^{1.5}{d})$に対して, L^\star$は最高の専門家の総損失である。
さらに, dpオンライン凸最適化を実現可能な設定で検討し, ほぼ最適に後悔する$o \big(\varepsilon^{-1} d^{1.5} \big)$ と, 後悔$o \big( \varepsilon^{-2/3} (dt)^{1/3} \big)$ を持つ滑らかな場合のアルゴリズムを提案する。
関連論文リスト
- 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) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。
凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文 参考訳（メタデータ） (2021-07-12T17:06:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。