論文の概要: Complexity of Single Loop Algorithms for Nonlinear Programming with
Stochastic Objective and Constraints
- arxiv url: http://arxiv.org/abs/2311.00678v1
- Date: Wed, 1 Nov 2023 17:37:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 12:38:25.932866
- Title: Complexity of Single Loop Algorithms for Nonlinear Programming with
Stochastic Objective and Constraints
- Title（参考訳）: 確率的目的と制約を伴う非線形プログラミングのための単一ループアルゴリズムの複雑性
- Authors: Ahmet Alacaoglu and Stephen J. Wright
- Abstract要約: 単ループ2次ペナルティと拡張ヴァリガングアルゴリズムの複雑さを解析する。
目的が関数的かつ滑らかな3つの場合を考える。
- 参考スコア（独自算出の注目度）: 16.96067869451225
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the complexity of single-loop quadratic penalty and augmented
Lagrangian algorithms for solving nonconvex optimization problems with
functional equality constraints. We consider three cases, in all of which the
objective is stochastic and smooth, that is, an expectation over an unknown
distribution that is accessed by sampling. The nature of the equality
constraints differs among the three cases: deterministic and linear in the
first case, deterministic, smooth and nonlinear in the second case, and
stochastic, smooth and nonlinear in the third case. Variance reduction
techniques are used to improve the complexity. To find a point that satisfies
$\varepsilon$-approximate first-order conditions, we require
$\widetilde{O}(\varepsilon^{-3})$ complexity in the first case,
$\widetilde{O}(\varepsilon^{-4})$ in the second case, and
$\widetilde{O}(\varepsilon^{-5})$ in the third case. For the first and third
cases, they are the first algorithms of "single loop" type (that also use
$O(1)$ samples at each iteration) that still achieve the best-known complexity
guarantees.
- Abstract（参考訳）: 関数等式制約付き非凸最適化問題を解くために,単ループ二次ペナルティと拡張ラグランジアンアルゴリズムの複雑さを分析する。
対象が確率的かつ滑らかである3つの事例,すなわちサンプリングによってアクセスされる未知の分布に対する期待について考察する。
等式制約の性質は、第一のケースでは決定論的、線形、第二のケースでは決定論的、滑らかで非線形、第三のケースでは確率的、滑らかで非線形である。
ばらつき低減技術は複雑さを改善するために使われる。
1次条件である$\varepsilon$-approximate 1次条件を満たす点を見つけるには、最初の場合では$\widetilde{o}(\varepsilon^{-3})$、第2の場合$\widetilde{o}(\varepsilon^{-4})$、第3の場合$\widetilde{o}(\varepsilon^{-5})$が必要である。
第1および第3のケースでは、"シングルループ"型(各イテレーションで$O(1)$サンプルを使用する)の最初のアルゴリズムであり、最もよく知られた複雑性を保証する。
関連論文リスト
- Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文 参考訳（メタデータ） (2024-01-26T11:22:13Z) - On Penalty Methods for Nonconvex Bilevel Optimization and First-Order
Stochastic Approximation [13.813242559935732]
両レベル最適化問題の1次解法について述べる。
特に,ペナルティ関数と超目的物との間に強い関連性を示す。
その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
論文 参考訳（メタデータ） (2023-09-04T18:25:43Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。