論文の概要: Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems
- arxiv url: http://arxiv.org/abs/2403.02912v1
- Date: Tue, 5 Mar 2024 12:28:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 14:58:54.920261
- Title: Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems
- Title（参考訳）: 確率的サドル点差分問題に対する近次元非依存のミラーディフレッシュアルゴリズム
- Authors: Tom\'as Gonz\'alez and Crist\'obal Guzm\'an and Courtney Paquette
- Abstract要約: 多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
- 参考スコア（独自算出の注目度）: 6.431793114484429
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of differentially-private (DP) stochastic
(convex-concave) saddle-points in the polyhedral setting. We propose
$(\varepsilon, \delta)$-DP algorithms based on stochastic mirror descent that
attain nearly dimension-independent convergence rates for the expected duality
gap, a type of guarantee that was known before only for bilinear objectives.
For convex-concave and first-order-smooth stochastic objectives, our algorithms
attain a rate of $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{1/3}$,
where $d$ is the dimension of the problem and $n$ the dataset size. Under an
additional second-order-smoothness assumption, we improve the rate on the
expected gap to $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{2/5}$.
Under this additional assumption, we also show, by using bias-reduced gradient
estimators, that the duality gap is bounded by $\log(d)/\sqrt{n} +
\log(d)/[n\varepsilon]^{1/2}$ with constant success probability. This result
provides evidence of the near-optimality of the approach. Finally, we show that
combining our methods with acceleration techniques from online learning leads
to the first algorithm for DP Stochastic Convex Optimization in the polyhedral
setting that is not based on Frank-Wolfe methods. For convex and
first-order-smooth stochastic objectives, our algorithms attain an excess risk
of $\sqrt{\log(d)/n} + \log(d)^{7/10}/[n\varepsilon]^{2/5}$, and when
additionally assuming second-order-smoothness, we improve the rate to
$\sqrt{\log(d)/n} + \log(d)/\sqrt{n\varepsilon}$. Instrumental to all of these
results are various extensions of the classical Maurey Sparsification Lemma,
which may be of independent interest.
- Abstract（参考訳）: 本研究では,多面体設定におけるDP確率的サドル点の問題について検討する。
双線型目的に対してのみ既知の保証である期待双対性ギャップに対してほぼ次元独立な収束率を達成する確率的ミラー降下に基づく$(\varepsilon, \delta)$-dpアルゴリズムを提案する。
凸凸および一階スムース確率的目的に対して、このアルゴリズムは$d$が問題の次元であり、データセットサイズが$n$である場合、$\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{1/3}$となる。
さらに二階スムースネスの仮定の下で、期待されるギャップの速度を$\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{2/5}$に改善する。
この追加の仮定の下では、バイアス還元勾配推定器を用いて、双対性ギャップは一定の成功確率を持つ$\log(d)/\sqrt{n} + \log(d)/[n\varepsilon]^{1/2}$で有界であることを示す。
この結果は、アプローチのほぼ最適性の証拠となる。
最後に,本手法とオンライン学習の高速化手法を組み合わせることで,frank-wolfe法を基礎としない多面体設定におけるdp確率凸最適化の最初のアルゴリズムとなることを示す。
凸および一階スムース確率目的に対して、我々のアルゴリズムは、$\sqrt{\log(d)/n} + \log(d)^{7/10}/[n\varepsilon]^{2/5}$の余剰リスクを獲得し、さらに二階スムースネスを仮定すると、$\sqrt{\log(d)/n} + \log(d)/\sqrt{n\varepsilon}$に改善する。
これらの結果は、古典的なモーリー・スパーシフィケーション・レムマ(Maurey Sparsification Lemma)の様々な拡張である。
関連論文リスト
- Differentially Private Bilevel Optimization [4.07926531936425]
両レベル最適化のための差分プライベート(DPright)アルゴリズムを提案する。
これらは、任意の所望の経験的設定を提供することができる、このタスクのための最初のアルゴリズムである。
我々の分析は、制約のある問題や未調査の問題もカバーしている。
論文 参考訳（メタデータ） (2024-09-29T21:52:38Z) - Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。
その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
論文 参考訳（メタデータ） (2024-08-19T11:07:05Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。