論文の概要: Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization

• arxiv url: http://arxiv.org/abs/2205.12751v3
• Date: Mon, 25 Nov 2024 10:47:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:14:10.983906
• Title: Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization
• Title（参考訳）: 並列化下での高速確率的合成最小化と加速フランクウルフアルゴリズム
• Authors: Benjamin Dubois-Taine, Francis Bach, Quentin Berthet, Adrien Taylor,
• Abstract要約: 2つの凸関数の和を最小化する問題を考える。 1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。 我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
• 参考スコア（独自算出の注目度）: 7.197233473373693
• License:
• Abstract: We consider the problem of minimizing the sum of two convex functions. One of those functions has Lipschitz-continuous gradients, and can be accessed via stochastic oracles, whereas the other is "simple". We provide a Bregman-type algorithm with accelerated convergence in function values to a ball containing the minimum. The radius of this ball depends on problem-dependent constants, including the variance of the stochastic oracle. We further show that this algorithmic setup naturally leads to a variant of Frank-Wolfe achieving acceleration under parallelization. More precisely, when minimizing a smooth convex function on a bounded domain, we show that one can achieve an $\epsilon$ primal-dual gap (in expectation) in $\tilde{O}(1/ \sqrt{\epsilon})$ iterations, by only accessing gradients of the original function and a linear maximization oracle with $O(1/\sqrt{\epsilon})$ computing units in parallel. We illustrate this fast convergence on synthetic numerical experiments.
• Abstract（参考訳）: 2つの凸関数の和を最小化する問題を考える。 これらの関数の1つはリプシッツ連続勾配を持ち、確率的オラクルを通してアクセスすることができるが、もう1つは「単純」である。 最小値を含む球に対する関数値の収束を高速化したブレグマン型アルゴリズムを提案する。 このボールの半径は確率オラクルの分散を含む問題依存定数に依存する。 さらに、このアルゴリズムが並列化の下で加速を達成するFrank-Wolfeの変種を自然に導くことを示す。 より正確には、有界領域上の滑らかな凸函数を最小化するとき、元の関数の勾配にのみアクセスし、O(1/\sqrt{\epsilon})$計算単位を並列に計算することで、$\epsilon$primal-dual gap(期待)を$\tilde{O}(1/ \sqrt{\epsilon})$イテレーションで達成できることが示される。 合成数値実験におけるこの高速収束について説明する。

関連論文リスト

• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• On the Complexity of Finding Small Subgradients in Nonsmooth Optimization [31.714928102950584]
  決定論的アルゴリズムにより次元自由度を達成できないことを示す。 関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
  論文  参考訳（メタデータ） (2022-09-21T13:30:00Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
  我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。 この2つを同時に実現したのは初めてである。
  論文  参考訳（メタデータ） (2021-01-30T15:05:34Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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