論文の概要: Gradient-Free Method for Heavily Constrained Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2409.00459v1
- Date: Sat, 31 Aug 2024 13:46:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-06 14:39:09.473555
- Title: Gradient-Free Method for Heavily Constrained Nonconvex Optimization
- Title（参考訳）: 重み付き非凸最適化のための勾配自由法
- Authors: Wanli Shi, Hongchang Gao, Bin Gu,
- Abstract要約: ゼロ階数(ZO)法は,制約の明示的表現が困難あるいは実現不可能な最適化問題を解くための強力な手法であることが示されている。
本稿では,運動量適応的なステップサイズを持つ2次勾配ゼロ階法(DS)を提案する。
- 参考スコア（独自算出の注目度）: 43.941106371683766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Zeroth-order (ZO) method has been shown to be a powerful method for solving the optimization problem where explicit expression of the gradients is difficult or infeasible to obtain. Recently, due to the practical value of the constrained problems, a lot of ZO Frank-Wolfe or projected ZO methods have been proposed. However, in many applications, we may have a very large number of nonconvex white/black-box constraints, which makes the existing zeroth-order methods extremely inefficient (or even not working) since they need to inquire function value of all the constraints and project the solution to the complicated feasible set. In this paper, to solve the nonconvex problem with a large number of white/black-box constraints, we proposed a doubly stochastic zeroth-order gradient method (DSZOG) with momentum method and adaptive step size. Theoretically, we prove DSZOG can converge to the $\epsilon$-stationary point of the constrained problem. Experimental results in two applications demonstrate the superiority of our method in terms of training time and accuracy compared with other ZO methods for the constrained problem.
- Abstract（参考訳）: ゼロ階数(ZO)法は、勾配の明示的な表現が困難あるいは得られ難い最適化問題を解くための強力な方法であることが示されている。
近年、制約された問題の実用的価値のため、ZO Frank-Wolfe法や投影ZO法が多数提案されている。
しかし、多くのアプリケーションにおいて、非常に多くの非凸なホワイト/ブラックボックス制約が存在するため、既存のゼロ階法は、すべての制約の関数値を求め、複雑な実現可能な集合への解を投影する必要があるため、非常に非効率である(あるいは動作しない)。
本稿では,多数の白黒ボックス制約を伴って非凸問題を解くために,運動量法と適応ステップサイズを備えた2次確率ゼロ階勾配法(DSZOG)を提案する。
理論的には、DSZOG は制約された問題の $\epsilon$-stationary 点に収束できる。
実験結果から, 制約問題に対する他のZO法と比較して, 学習時間と精度の点で, 提案手法の優位性を実証した。
関連論文リスト
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization [31.28781889710351]
再帰的仮定を使わずに,非滑らかな暗黙関数定理を応用したLCBOの新しい過次関数を提案する。
さらに,2重モーメント法と適応ステップサイズ法に基づいて,テキスト入力ループのシングルタイムスケール反復アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-25T09:05:22Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity [34.84170466506512]
本稿では,新しいランダムサンプリングを用いた一般ZO勾配推定器を用いたゼロ階ハードスレッディング(SZOHT)アルゴリズムを提案する。
SZOHTの問合せ複雑性は, 異なる条件下での次元性に依存しないか, あるいは弱く依存していることが判明した。
論文 参考訳（メタデータ） (2022-10-11T09:23:53Z) - l1-Norm Minimization with Regula Falsi Type Root Finding Methods [81.55197998207593]
Regula Falsiルートフィンディング技術を使用して、非可能性に対する効率的なアプローチを開発します。
実用的性能は l1 正規化クラス t を用いて示される。
論文 参考訳（メタデータ） (2021-05-01T13:24:38Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints [8.643249539674612]
本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。
まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
論文 参考訳（メタデータ） (2020-06-30T23:49:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。