論文の概要: First-order methods for stochastic and finite-sum convex optimization with deterministic constraints
- arxiv url: http://arxiv.org/abs/2506.20630v1
- Date: Wed, 25 Jun 2025 17:26:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-26 21:00:42.8784
- Title: First-order methods for stochastic and finite-sum convex optimization with deterministic constraints
- Title（参考訳）: 決定論的制約を伴う確率的および有限サム凸最適化の一階法
- Authors: Zhaosong Lu, Yifeng Xiao,
- Abstract要約: 決定論的制約を伴う有限サム凸最適化問題のクラスについて検討する。
本稿では,$epsilon$-$surely feasible optimal$$(epsilon$-SFSO) を求める一階法を提案する。
副生成物として、$epsilon$-SFSOの計算におけるサンプル平均近似法の1次オラクル複雑性結果も導出する。
- 参考スコア（独自算出の注目度）: 1.411894456054802
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an $\epsilon$-$expectedly\ feasible\ stochastic\ optimal$ solution, in which the expected constraint violation and expected optimality gap are both within a prescribed tolerance $\epsilon$. However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an $\epsilon$-$surely\ feasible\ stochastic\ optimal$ ($\epsilon$-SFSO) solution, where the constraint violation is deterministically bounded by $\epsilon$ and the expected optimality gap is at most $\epsilon$. Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme $only\ once$ to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an $\epsilon$-SFSO solution. As a byproduct, we also derive first-order oracle complexity results for sample average approximation method in computing an $\epsilon$-SFSO solution of the stochastic optimization problem using our proposed methods to solve the sample average problem.
- Abstract（参考訳）: 本稿では,決定論的制約を伴う確率および有限サム凸最適化問題のクラスについて検討する。
既存のメソッドは通常、期待される制約違反と期待される最適性ギャップの両方が所定の許容範囲$\epsilon$内にあるような、$\epsilon$-$expectedly\ feasible\ stochastic\ optimal$ソリューションを見つけることを目的としています。
しかし、多くの実践的応用において、制約は確実性にほぼ満足していなければならず、重大な違反のリスクがあるため、そのような解決策は適さない可能性がある。
この問題に対処するために、制約違反が決定的に$\epsilon$で有界であり、期待される最適性ギャップが最大$\epsilon$であるような、$\epsilon$-$surely\ feasible\ stochastic\ optimal$$$\epsilon$-SFSO) ソリューションを見つけるための確率的一階法を提案する。
本手法では, 適応型確率勾配法(ASG)や修正型分散還元型ASGスキーム$only\ once$を, 適切に選択されたペナルティパラメータを持つ2次ペナルティサブプロブレムの列に適用する。
我々は$\epsilon$-SFSOソリューションの計算における提案手法の1次オラクル複雑性境界を確立する。
副産物として,提案手法を用いて確率最適化問題の$\epsilon$-SFSOを計算し,サンプル平均問題の解法を導出する。
関連論文リスト
- A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [17.25924791071807]
複雑な制約に対する新しい種類の下次アルゴリズムを提案する。
提案手法は, 2-of-the-artアルゴリズムよりもはるかに高速であることを示す。
論文 参考訳（メタデータ） (2025-01-31T15:18:52Z) - Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [1.2562458634975162]
既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。
多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
論文 参考訳（メタデータ） (2024-09-16T00:26:42Z) - 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) - 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) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - 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) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z) - 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) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-12T16:44:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。