論文の概要: Private Stochastic Convex Optimization: Optimal Rates in Linear Time

• arxiv url: http://arxiv.org/abs/2005.04763v1
• Date: Sun, 10 May 2020 19:52:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-05 01:37:28.872678
• Title: Private Stochastic Convex Optimization: Optimal Rates in Linear Time
• Title（参考訳）: プライベート確率凸最適化:線形時間における最適速度
• Authors: Vitaly Feldman, Tomer Koren, Kunal Talwar
• Abstract要約: 本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
• 参考スコア（独自算出の注目度）: 74.47681868973598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study differentially private (DP) algorithms for stochastic convex optimization: the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. (2019) has established the optimal bound on the excess population loss achievable given $n$ samples. Unfortunately, their algorithm achieving this bound is relatively inefficient: it requires $O(\min\{n^{3/2}, n^{5/2}/d\})$ gradient computations, where $d$ is the dimension of the optimization problem. We describe two new techniques for deriving DP convex optimization algorithms both achieving the optimal bound on excess loss and using $O(\min\{n, n^2/d\})$ gradient computations. In particular, the algorithms match the running time of the optimal non-private algorithms. The first approach relies on the use of variable batch sizes and is analyzed using the privacy amplification by iteration technique of Feldman et al. (2018). The second approach is based on a general reduction to the problem of localizing an approximately optimal solution with differential privacy. Such localization, in turn, can be achieved using existing (non-private) uniformly stable optimization algorithms. As in the earlier work, our algorithms require a mild smoothness assumption. We also give a linear-time algorithm achieving the optimal bound on the excess loss for the strongly convex case, as well as a faster algorithm for the non-smooth case.
• Abstract（参考訳）: 確率的凸最適化のための微分プライベート (dp) アルゴリズムについて検討した: 凸損失関数上の分布からのi.i.d.サンプルによる人口減少を最小化する問題。 Bassily et al. (2019) の最近の研究は、$n$のサンプルを与えられた過剰な人口損失に最適な上限を定めている。 残念ながら、この境界に達するアルゴリズムは比較的非効率である: $o(\min\{n^{3/2}, n^{5/2}/d\})$勾配計算が必要であり、ここで$d$は最適化問題の次元である。 本稿では,DP凸最適化アルゴリズムの最適化手法を2つの新しい手法で導出し,損失の最適境界を達成するとともに,$O(\min\{n, n^2/d\})$グラデーション計算を用いる。 特に、アルゴリズムは最適な非プライベートアルゴリズムの実行時間と一致する。 最初のアプローチは、可変バッチサイズの使用に依存しており、feldman et al.(2018)のイテレーションテクニックによるプライバシ増幅を用いて分析される。 第2のアプローチは、差分プライバシーを持つ近似最適解の局所化という問題への一般化に基づいている。 このようなローカライゼーションは、既存の(プライベートでない)一様安定最適化アルゴリズムを用いて達成できる。 初期の研究と同様に、我々のアルゴリズムは軽度な滑らかさの仮定を必要とする。 また, 強い凸の場合の余剰損失に対する最適境界を達成する線形時間アルゴリズムや, 非滑らかの場合の高速アルゴリズムも提案する。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning [0.0]
  ランジュバンアルゴリズムは付加ノイズを持つ手法である。 ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた 学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
  論文  参考訳（メタデータ） (2020-12-22T16:19:20Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• 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)

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

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