論文の概要: Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates

• arxiv url: http://arxiv.org/abs/2408.09891v1
• Date: Mon, 19 Aug 2024 11:07:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-20 16:35:11.021985
• Title: Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
• Title（参考訳）: 重み付きデータを用いた微分的私的確率最適化:最適速度を目指して
• Authors: Puning Zhao, Jiafei Wu, Zhe Liu, Chong Wang, Rongfei Fan, Qingming Li,
• Abstract要約: 重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。 その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 15.27596975662702
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study convex optimization problems under differential privacy (DP). With heavy-tailed gradients, existing works achieve suboptimal rates. The main obstacle is that existing gradient estimators have suboptimal tail properties, resulting in a superfluous factor of $d$ in the union bound. In this paper, we explore algorithms achieving optimal rates of DP optimization with heavy-tailed gradients. Our first method is a simple clipping approach. Under bounded $p$-th order moments of gradients, with $n$ samples, it achieves $\tilde{O}(\sqrt{d/n}+\sqrt{d}(\sqrt{d}/n\epsilon)^{1-1/p})$ population risk with $\epsilon\leq 1/\sqrt{d}$. We then propose an iterative updating method, which is more complex but achieves this rate for all $\epsilon\leq 1$. The results significantly improve over existing methods. Such improvement relies on a careful treatment of the tail behavior of gradient estimators. Our results match the minimax lower bound in \cite{kamath2022improved}, indicating that the theoretical limit of stochastic convex optimization under DP is achievable.
• Abstract（参考訳）: 差分プライバシー(DP)下での凸最適化問題について検討する。 重み付き勾配では、既存の作業は最適以下の速度を達成する。 主な障害は、既存の勾配推定器が準最適尾部特性を持ち、結果としてユニオン境界における超流動係数が$d$となることである。 本稿では,重み付き勾配を用いたDP最適化のアルゴリズムについて検討する。 最初の方法は単純なクリッピングアプローチです。 勾配の有界な$p$-次モーメントの下で、$n$サンプルを持ち、$\tilde{O}(\sqrt{d/n}+\sqrt{d}(\sqrt{d}/n\epsilon)^{1-1/p})$ 人口リスク$$\epsilon\leq 1/\sqrt{d}$を達成する。 次に、より複雑な反復更新法を提案するが、これはすべての$\epsilon\leq 1$に対してこの率を達成する。 その結果、既存の手法よりも大幅に改善された。 このような改善は勾配推定器のテール挙動を慎重に扱うことに依存している。 この結果は, DP下での確率凸最適化の理論的限界が達成可能であることを示す。

関連論文リスト

• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。 Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-04T21:26:29Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Variance-reduced Clipping for Non-convex Optimization [24.765794811146144]
  グラディエント・クリッピング(Gradient clipping)は、大規模言語モデリングのようなディープラーニングアプリケーションで用いられる技法である。 最近の実験的な訓練は、秩序の複雑さを緩和する、非常に特別な振る舞いを持っている。
  論文  参考訳（メタデータ） (2023-03-02T00:57:38Z)
• DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning [58.79085525115987]
  以前の研究でよく知られたユーティリティ境界は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3)$である。 本稿では,差分プライベートフレームワークを構築した mphDIFF2 (DIFFerential private via DIFFs) という新しい差分プライベートフレームワークを提案する。 大域的な降下を持つ$mphDIFF2は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3の効用を達成する
  論文  参考訳（メタデータ） (2023-02-08T05:19:01Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Never Go Full Batch (in Stochastic Convex Optimization) [42.46711831860667]
  凸最適化のための$textfull-batch$最適化アルゴリズムの一般化性能について検討する。 我々は、勾配降下のようなアルゴリズムが人口リスクを$O(1/epsilon2)$の後に$epsilon$に一般化し、最適化する一方で、フルバッチ法は少なくとも$Omega(1/epsilon4)$の反復を必要とするか、あるいは次元依存的なサンプル複雑性を示すことを示した。
  論文  参考訳（メタデータ） (2021-06-29T16:07:50Z)
• Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
  モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
  論文  参考訳（メタデータ） (2021-06-17T13:33:05Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。