論文の概要: Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks

• arxiv url: http://arxiv.org/abs/2302.09699v1
• Date: Mon, 20 Feb 2023 00:11:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-21 17:05:56.886428
• Title: Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks
• Title（参考訳）: プライベート(確率的)非凸最適化の再検討:2次定常点と余剰リスク
• Authors: Arun Ganesh, Daogao Liu, Sewoong Oh, Abhradeep Thakurta
• Abstract要約: 2つの異なる種類のオラクルを利用する新しいフレームワークを導入する。 指数的メカニズムは高い集団リスクバウンドを達成でき、ほぼ一致する低いバウンドを提供することを示す。
• 参考スコア（独自算出の注目度）: 34.79650838578354
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of minimizing a non-convex objective while preserving the privacy of the examples in the training data. Building upon the previous variance-reduced algorithm SpiderBoost, we introduce a new framework that utilizes two different kinds of gradient oracles. The first kind of oracles can estimate the gradient of one point, and the second kind of oracles, less precise and more cost-effective, can estimate the gradient difference between two points. SpiderBoost uses the first kind periodically, once every few steps, while our framework proposes using the first oracle whenever the total drift has become large and relies on the second oracle otherwise. This new framework ensures the gradient estimations remain accurate all the time, resulting in improved rates for finding second-order stationary points. Moreover, we address a more challenging task of finding the global minima of a non-convex objective using the exponential mechanism. Our findings indicate that the regularized exponential mechanism can closely match previous empirical and population risk bounds, without requiring smoothness assumptions for algorithms with polynomial running time. Furthermore, by disregarding running time considerations, we show that the exponential mechanism can achieve a good population risk bound and provide a nearly matching lower bound.
• Abstract（参考訳）: 本稿では,非凸目標を最小化しつつ,サンプルのプライバシをトレーニングデータに保持する問題を考える。 従来の分散還元アルゴリズムであるSpiderBoostに基づいて、2種類の勾配オラクルを利用する新しいフレームワークを導入する。 1つ目の種類のオラクルは1つのポイントの勾配を見積もることができ、2番目の種類のオラクルはより正確でコスト効率が良いので、2つのポイント間の勾配差を見積もることができる。 spiderboostは定期的に、数ステップに一度だけ、最初の種類のoracleを使用しますが、私たちのフレームワークでは、全体のドリフトが大きくなり、2番目のoracleに依存するたびに、最初のoracleを使うように提案しています。 この新しいフレームワークは、勾配推定が常に正確であることを保証するため、2次静止点を見つけるための速度が向上する。 さらに, 指数関数機構を用いて非凸対象のグローバルミニマを探索するより困難な課題に対処した。 本研究は, 多項式実行時間を持つアルゴリズムのスムーズな仮定を必要とせず, 従来の経験的, 集団的リスク境界と密に一致できることを示唆する。 さらに, ランニングタイムの考慮を無視することにより, 指数的メカニズムが良好な集団リスクバウンドを実現し, ほぼ一致する低いバウンドを提供できることを示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Stochastic Gradient Succeeds for Bandits [64.17904367852563]
  エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。 興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
  論文  参考訳（メタデータ） (2024-02-27T06:05:01Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods [0.6554326244334866]
  シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。 シャープネスは、通常不明な問題固有の定数を伴い、再起動スキームは通常収束率を減少させる。 対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
  論文  参考訳（メタデータ） (2023-01-05T19:01:41Z)
• Non-Convergence and Limit Cycles in the Adam optimizer [0.0]
  本稿では,2周期の極限周期が2次目的関数のバッチモードに存在することを示す。 これらの極限周期の安定性を解析し、近似収束が示される他の結果と分析を関連付ける。
  論文  参考訳（メタデータ） (2022-10-05T07:44:33Z)
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
  最適化問題の解法として,新しい2段階勾配法を提案する。 最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。 我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
  論文  参考訳（メタデータ） (2021-09-29T23:15:23Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• On Limited-Memory Subsampling Strategies for Bandits [0.0]
  本稿では,Budry et al. (2020) の最近の研究で提案されている単純な決定論的部分サンプリング則が,一次元指数関数族において最適であることを示す。 また、これらの保証は、アルゴリズムメモリを時間軸の多対数関数に制限する場合にも有効であることを示す。 本稿では,近年の観測結果のみをサブサンプリングに用い,既知の急激な変化を前提とした最適後悔保証を実現するアルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2021-06-21T09:11:22Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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