論文の概要: Conditional gradient methods for stochastically constrained convex minimization

• arxiv url: http://arxiv.org/abs/2007.03795v1
• Date: Tue, 7 Jul 2020 21:26:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-12 19:22:57.940591
• Title: Conditional gradient methods for stochastically constrained convex minimization
• Title（参考訳）: 確率制約付き凸最小化の条件勾配法
• Authors: Maria-Luiza Vladarean, Ahmet Alacaoglu, Ya-Ping Hsieh, Volkan Cevher
• Abstract要約: 構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
• 参考スコア（独自算出の注目度）: 54.53786593679331
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, which involve a number of constraints that is polynomial in the problem dimension. The most important feature of our framework is that only a subset of the constraints is processed at each iteration, thus gaining a computational advantage over prior works that require full passes. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees. Preliminary numerical experiments are provided for illustrating the practical performance of the methods.
• Abstract（参考訳）: 線形制約を多数有する構造付き確率凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 このテンプレートの例は、問題次元の多項式である多くの制約を含む組合せ問題のSDP緩和から自然に生じる。 私たちのフレームワークの最も重要な特徴は、制約のサブセットが各イテレーションでのみ処理されるため、完全なパスを必要とする以前の作業よりも計算上の優位性を得るということです。 本アルゴリズムは,条件付き勾配ステップと併用した分散低減と平滑化に依拠し,厳密な収束保証を伴っている。 本手法の実用性を示すための予備的な数値実験を行う。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
  目的関数が弱凸あるいは弱凸である非制約最適化問題を考える。 そこで本研究では,一階調律であり,実装が容易な段階的手法について考察する。
  論文  参考訳（メタデータ） (2023-01-30T22:13:14Z)
• A conditional gradient homotopy method with applications to Semidefinite Programming [1.6369790794838281]
  ホモトピーに基づく条件勾配法による凸最適化問題の解法。 我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
  論文  参考訳（メタデータ） (2022-07-07T05:48:27Z)
• Stochastic Gradient Methods with Preconditioned Updates [47.23741709751474]
  このような問題に対するアルゴリズムはいくつかあるが、既存の手法は、スケールが悪く、あるいは条件が悪ければ、しばしばうまく機能しない。 ここではハッチンソンの対角ヘッセン近似のアプローチに基づく前提条件を含む。 我々は滑らかさとPL条件が仮定されるときの収束性を証明する。
  論文  参考訳（メタデータ） (2022-06-01T07:38:08Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints [8.643249539674612]
  本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。 まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。 さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
  論文  参考訳（メタデータ） (2020-06-30T23:49:38Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

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

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