論文の概要: Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching

• arxiv url: http://arxiv.org/abs/2305.18379v1
• Date: Sun, 28 May 2023 06:33:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 22:04:56.703972
• Title: Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching
• Title（参考訳）: 完全拡張ラグランジアンおよびランダム化反復スケッチによる制約付き最適化
• Authors: Ilgee Hong, Sen Na, Michael W. Mahoney, Mladen Kolar
• Abstract要約: 等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
• 参考スコア（独自算出の注目度）: 55.28394191394675
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider solving equality-constrained nonlinear, nonconvex optimization problems. This class of problems appears widely in a variety of applications in machine learning and engineering, ranging from constrained deep neural networks, to optimal control, to PDE-constrained optimization. We develop an adaptive inexact Newton method for this problem class. In each iteration, we solve the Lagrangian Newton system inexactly via a randomized iterative sketching solver, and select a suitable stepsize by performing line search on an exact augmented Lagrangian merit function. The randomized solvers have advantages over deterministic linear system solvers by significantly reducing per-iteration flops complexity and storage cost, when equipped with suitable sketching matrices. Our method adaptively controls the accuracy of the randomized solver and the penalty parameters of the exact augmented Lagrangian, to ensure that the inexact Newton direction is a descent direction of the exact augmented Lagrangian. This allows us to establish a global almost sure convergence. We also show that a unit stepsize is admissible locally, so that our method exhibits a local linear convergence. Furthermore, we prove that the linear convergence can be strengthened to superlinear convergence if we gradually sharpen the adaptive accuracy condition on the randomized solver. We demonstrate the superior performance of our method on benchmark nonlinear problems in CUTEst test set, constrained logistic regression with data from LIBSVM, and a PDE-constrained problem.
• Abstract（参考訳）: 等式制約付き非線形非凸最適化問題を解くことを検討する。 このタイプの問題は、制約付きディープニューラルネットワークから最適制御、PDE制約付き最適化まで、機械学習とエンジニアリングの様々な応用に広く見られる。 この問題クラスに対して適応的不適合ニュートン法を開発した。 各イテレーションでは、ランダム化反復スケッチ解法を用いてラグランジアンニュートン系を非現実的に解き、正確に拡張されたラグランジアンメリット関数で行探索を行うことで、適切なステップを選択する。 ランダム化された解法は、適切なスケッチ行列を備える場合、解法あたりのフロップの複雑性と保存コストを著しく低減し、決定論的線形系解法よりも有利である。 本手法は,ランダム化ソルバの精度と正確な拡張ラグランジアンのペナルティパラメータを適応的に制御し,不正確なニュートン方向が正確な拡張ラグランジアンの降下方向であることを保証する。 これにより、ほぼ確実にグローバルな収束を確立することができます。 また, 単位ステップ化は局所的に許容されるので, 局所線形収束を示す。 さらに, ランダム化解器の適応精度条件を徐々に鋭くすれば, 線形収束を超線形収束に強化できることを示す。 CUTEstテストセットにおけるベンチマーク非線形問題,LIBSVMのデータによる制約付きロジスティック回帰,PDE制約問題に対する本手法の優れた性能を示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• Over-the-Air Computation Aided Federated Learning with the Aggregation of Normalized Gradient [12.692064367193934]
  オーバー・ザ・エア(Over-the-air)は、フェデレートラーニング(FL)のための通信効率のよい解である。 このようなシステムでは、プライベート損失関数の反復手順を更新し、すべてのモバイルデバイスで送信する。 この問題を回避するため,局所勾配を正規化して増幅する手法を提案する。
  論文  参考訳（メタデータ） (2023-08-17T16:15:47Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming [17.9230793188835]
  客観的・決定論的等式と不等式制約を用いた非線形最適化問題について検討する。 本稿では,有理関数として微分可能な拡張ラグランジアンを用いて,能動型逐次適応型プログラミングアルゴリズムを提案する。 アルゴリズムは、拡張ラグランジアンのパラメータを適応的に選択し、行探索を行い、ステップサイズを決定する。
  論文  参考訳（メタデータ） (2021-09-23T17:12:17Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)

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

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