論文の概要: Bregman Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Zeroth-order Optimization

• arxiv url: http://arxiv.org/abs/2504.09409v1
• Date: Sun, 13 Apr 2025 02:44:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:49:16.258589
• Title: Bregman Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Zeroth-order Optimization
• Title（参考訳）: 非凸制約確率ゼロ階最適化のためのブラグマン線形化ラグランジアン法
• Authors: Qiankun Shi, Xiao Wang, Hao Wang,
• Abstract要約: 本稿では,0階推定器と分散手法を組み合わせたBregman線形化ラグランジアン法を提案する。 その結果,提案手法の複雑性は,必要条件(O(d))よりも低次元依存性を実現することができることがわかった。
• 参考スコア（独自算出の注目度）: 9.482573620753442
• License:
• Abstract: In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems, for which we have access to exact information of constraints and noisy function values of the objective. We propose a Bregman linearized augmented Lagrangian method that utilizes stochastic zeroth-order gradient estimators combined with a variance reduction technique. We analyze its oracle complexity, in terms of the total number of stochastic function value evaluations required to achieve an \(\epsilon\)-KKT point in \(\ell_p\)-norm metrics with \(p \ge 2\), where \(p\) is a parameter associated with the selected Bregman distance. In particular, starting from a near-feasible initial point and using Rademacher smoothing, the oracle complexity is in order \(O(p d^{2/p} \epsilon^{-3})\) for \(p \in [2, 2 \ln d]\), and \(O(\ln d \cdot \epsilon^{-3})\) for \(p > 2 \ln d\), where \(d\) denotes the problem dimension. Those results show that the complexity of the proposed method can achieve a dimensional dependency lower than \(O(d)\) without requiring additional assumptions, provided that a Bregman distance is chosen properly. This offers a significant improvement in the high-dimensional setting over existing work, and matches the lowest complexity order with respect to the tolerance \(\epsilon\) reported in the literature. Numerical experiments on constrained Lasso and black-box adversarial attack problems highlight the promising performances of the proposed method.
• Abstract（参考訳）: 本稿では,制約の厳密な情報と目的の雑音関数値にアクセス可能な非凸制約の確率的ゼロ階最適化問題について検討する。 本稿では,確率的ゼロ階勾配推定器と分散低減手法を組み合わせたBregman線形化ラグランジアン法を提案する。 我々は,そのオラクルの複雑性を,選択したブレグマン距離に関連付けられたパラメータである \(p \ge 2\)-ノルム測度における \(\epsilon\)-KKT 点を達成するために必要な確率関数値の総数の観点から解析する。 特に、ほぼ実現可能な初期点から始まり、ラデマッハ滑らか化(英語版)(Rademacher smoothing)を使い、オラクルの複雑性は、(p \in [2, 2 \ln d]\) に対して \(O(p d^{2/p} \epsilon^{-3})\) および(p > 2 \ln d\) に対して \(O(\ln d \cdot \epsilon^{-3})\) である。 これらの結果から,Bregman距離が適切に選択された場合,提案手法の複雑さは,追加の仮定を必要とせずに,(O(d)\)よりも低次元の依存性を達成できることが示唆された。 これは、既存の作業よりも高次元的な設定を大幅に改善し、文献で報告されている寛容(\epsilon\)に関して、最も低い複雑さの順序と一致する。 制約付きラッソとブラックボックスの対向攻撃問題に関する数値実験は,提案手法の有望な性能を浮き彫りにした。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• 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)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• 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 Bregman Coordinate Descent Methods for Non-Lipschitz Optimization [31.474280642125734]
  そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。 提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
  論文  参考訳（メタデータ） (2020-01-15T09:57:38Z)

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

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