Fugu-MT 論文翻訳(概要): Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization

論文の概要: Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization

arxiv url: http://arxiv.org/abs/2107.06534v1
Date: Wed, 14 Jul 2021 08:01:30 GMT
ステータス: 処理完了
システム内更新日: 2021-07-15 14:23:31.307005
Title: Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
Title（参考訳）: 制約付き最適化のためのゼロ・1次確率フランクウルフアルゴリズム
Authors: Zeeshan Akhtar, and Ketan Rajawat
Abstract要約: 2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
参考スコア（独自算出の注目度）: 13.170519806372075
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before, and solved using first-order stochastic FW algorithms by applying homotopy and Nesterov's smoothing techniques to the indicator function. This work improves upon these existing results and puts forth momentum-based first-order methods that yield improved convergence rates, at par with the best known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem.
Abstract（参考訳）: 本稿では, 2つの制約からなる確率的凸最適化問題について考察する: (a) 最適化変数の領域に対する決定論的制約, (b) 効率的な射影を許容する決定論的あるいは確率的制約。この形式の問題は、半定値プログラミングの文脈や、様々なNPハード問題が半定値緩和によってほぼ解決されたときに頻繁に発生する。最初の制約セットへのプロジェクションは困難であるため、確率的フランク・ウルフアルゴリズム(FW)のようなプロジェクションフリーなアルゴリズムを探索する必要がある。一方、第2の制約セットは同じ方法では処理できず、目的関数内にインジケータ関数として組み込まれなければならないため、fwメソッドの適用が複雑になる。同様の問題は以前に研究され、ホモトピーとネステロフの平滑化手法を指標関数に適用して一階確率的fwアルゴリズムを用いて解いた。この研究は、これらの既存の結果を改善し、第2の制約のない問題に対する最もよく知られたレートに匹敵する収束率を改善する運動量に基づく一階法を提示する。提案されたアルゴリズムのゼロ次変種も開発され、最先端のレート結果が再び改善される。提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。

関連論文リスト

Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文参考訳（メタデータ） (2024-09-24T04:39:47Z)
A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
論文参考訳（メタデータ） (2023-04-28T15:30:43Z)
Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文参考訳（メタデータ） (2023-04-23T20:05:09Z)
Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文参考訳（メタデータ） (2023-02-01T08:50:48Z)
A Sequential Deep Learning Algorithm for Sampled Mixed-integer Optimisation Problems [0.3867363075280544]
混合整数最適化問題に対する2つの効率的なアルゴリズムを導入,解析する。両アルゴリズムが最適解に対して有限時間収束を示すことを示す。 3つの数値実験により,これらのアルゴリズムの有効性を定量的に確立する。
論文参考訳（メタデータ） (2023-01-25T17:10:52Z)
A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。 1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
論文参考訳（メタデータ） (2023-01-01T21:46:50Z)
A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians [11.03311584463036]
滑らかな非線形等式制約最適化問題の解法として, 逐次2次最適化アルゴリズムを提案する。数値実験の結果、このアルゴリズムは一般的な代替品と比較して優れた性能を示すことが示された。
論文参考訳（メタデータ） (2021-06-24T13:46:52Z)
High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文参考訳（メタデータ） (2021-06-10T17:54:21Z)
Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文参考訳（メタデータ） (2020-08-13T08:56:24Z)
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文参考訳（メタデータ） (2020-06-11T18:49:06Z)
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)

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

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