論文の概要: Differentially Private Online-to-Batch for Smooth Losses
- arxiv url: http://arxiv.org/abs/2210.06593v1
- Date: Wed, 12 Oct 2022 21:13:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-14 17:27:05.190926
- Title: Differentially Private Online-to-Batch for Smooth Losses
- Title（参考訳）: Smooth Lossesのための個人用オンラインバッチ
- Authors: Qinzi Zhang, Hoang Tran, Ashok Cutkosky
- Abstract要約: 我々は,オンライン凸最適化アルゴリズムが$O(sqrtT)$ regretを,最適収束率$tilde O(sqrtT + sqrtd/epsilon T)$で$epsilon$-differentially private convexアルゴリズムに変換することで,線形時間におけるスムーズな損失を解消する手法を開発した。
- 参考スコア（独自算出の注目度）: 38.23708749658059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a new reduction that converts any online convex optimization
algorithm suffering $O(\sqrt{T})$ regret into an $\epsilon$-differentially
private stochastic convex optimization algorithm with the optimal convergence
rate $\tilde O(1/\sqrt{T} + \sqrt{d}/\epsilon T)$ on smooth losses in linear
time, forming a direct analogy to the classical non-private "online-to-batch"
conversion. By applying our techniques to more advanced adaptive online
algorithms, we produce adaptive differentially private counterparts whose
convergence rates depend on apriori unknown variances or parameter norms.
- Abstract（参考訳）: 我々は、任意のオンライン凸最適化アルゴリズムが$O(\sqrt{T})$ regretを、最適収束率$\tilde O(1/\sqrt{T} + \sqrt{d}/\epsilon T)$で$\epsilon$-differentially private stochastic convex Optimizationアルゴリズムに変換し、線形時間におけるスムーズな損失を解消し、古典的な非プライベートな"online-to-batch"変換に直交する。
本手法をより高度な適応オンラインアルゴリズムに適用することにより, 収束率が未知分散やパラメータノルムに依存する適応微分プライベートアルゴリズムを生成する。
関連論文リスト
- Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - On Private Online Convex Optimization: Optimal Algorithms in
$\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。
また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。
提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
論文 参考訳（メタデータ） (2022-06-16T12:09:47Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。