論文の概要: A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization
- arxiv url: http://arxiv.org/abs/2608.12665v1
- Date: Wed, 12 Aug 2026 23:55:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-14 18:29:38.349793
- Title: A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization
- Title（参考訳）: 非凸等式制約最適化のための局所線形収束アルゴリズム
- Abstract要約: 勾配固有ステップアルゴリズムを用いて任意の出発点から近似した2階定常点を求める。
このアルゴリズムは、プログレッシブサンプリング戦略の文脈で効率的なサブプロブレム解法として利用できる。
フルサンプルの問題を直接解決するアプローチと比較して、最悪のサンプルの複雑さが改善されたアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 4.8718671103376865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.
- Abstract（参考訳）: 非凸等式制約最適化問題を解くため、GoyensらによるGradient-Eigenstep Algorithmはフレッチャーの拡張ラグランジアン関数を最小化し、任意の出発点から近似二階定常点を求める反復効率のアルゴリズムである。
本稿では,このアルゴリズムを拡張し,2倍のコントリビューションを提供する。
まず,2階定常点に十分に接近して十分に小さいステップサイズパラメータと十分に大きなペナルティパラメータを用いると,局所的な収束率が得られることを示した。
この場合、アルゴリズムはフレッチャーの拡張ラグランジアンを最小化する勾配降下アルゴリズムに還元される。
第二に、第一結果の特に有用な応用として、目的関数と制約関数が大きなサンプル平均で定義される場合の等式制約付き最適化問題を解くためのプログレッシブサンプリング戦略の文脈において、反復効率の低いサブプロブレム解法としてグラディエント・固有ステップアルゴリズムが利用可能であることが示され、最終的には全サンプル問題を直接解いたアプローチと比較して、最悪のサンプルの複雑さが向上したアルゴリズムが提供される。
関連論文リスト
- Dynamic Proximal Gradient Algorithms for Schatten-$p$ Quasi-Norm Regularized Problems [4.456078319832753]
本稿では,[0,1]$に$pを持つ半ノルム正規化問題の数値解法について検討する。
本稿では,各反復における計算コストのかかる特異値の分解を回避する動的勾配反復アルゴリズムを提案する。
予備的な数値計算により,提案アルゴリズムの計算効率が向上した。
論文 参考訳（メタデータ） (2026-02-27T22:04:25Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Follower Agnostic Methods for Stackelberg Games [14.143502615941648]
我々は,複数のフォロワーを対象とするオンラインStackelbergゲームにおいて,フォロワーに依存しない方法で効率よく解決するアルゴリズムを提案する。
私たちのアプローチは、リーダがフォロワーのユーティリティ機能や戦略空間について知識を持っていない場合でも機能します。
論文 参考訳（メタデータ） (2023-02-02T21:21:14Z) - Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Reinforcement Learning with Unbiased Policy Evaluation and Linear
Function Approximation [11.345796608258434]
マルコフ決定プロセスを制御するためのシミュレーションベースのポリシーイテレーションの変種に対して,性能保証を提供する。
第一のアルゴリズムは最小二乗アプローチを伴い、各反復において、特徴ベクトルに関連する新しい重みの集合が少なくとも二乗によって得られる。
第2のアルゴリズムは、最小二乗解への勾配降下を数ステップ行う2段階の近似アルゴリズムを含む。
論文 参考訳（メタデータ） (2022-10-13T20:16:19Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳（メタデータ） (2022-09-01T11:05:26Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。