論文の概要: Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees

• arxiv url: http://arxiv.org/abs/2506.08558v2
• Date: Wed, 11 Jun 2025 06:46:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-12 16:13:48.066372
• Title: Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
• Title（参考訳）: スパース支援保存セットの最適化:グローバル最適保証付き2段階投影
• Authors: William de Vazelhes, Xiao-Tong Yuan, Bin Gu,
• Abstract要約: スパース最適化では、$ell_$ pseudo-normを使ってハード制約を強制することは、制御されたスパーシリティのような利点を提供する。 多くの現実世界のアプリケーションは、余分な制約だけでなく、余分な制約も要求します。 本稿では,これらの制約をカスタマイズした2ステップのプロジェクション演算子を備えた,保存困難な反復アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 34.164821598251315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In sparse optimization, enforcing hard constraints using the $\ell_0$ pseudo-norm offers advantages like controlled sparsity compared to convex relaxations. However, many real-world applications demand not only sparsity constraints but also some extra constraints. While prior algorithms have been developed to address this complex scenario with mixed combinatorial and convex constraints, they typically require the closed form projection onto the mixed constraints which might not exist, and/or only provide local guarantees of convergence which is different from the global guarantees commonly sought in sparse optimization. To fill this gap, in this paper, we study the problem of sparse optimization with extra support-preserving constraints commonly encountered in the literature. We present a new variant of iterative hard-thresholding algorithm equipped with a two-step consecutive projection operator customized for these mixed constraints, serving as a simple alternative to the Euclidean projection onto the mixed constraint. By introducing a novel trade-off between sparsity relaxation and sub-optimality, we provide global guarantees in objective value for the output of our algorithm, in the deterministic, stochastic, and zeroth-order settings, under the conventional restricted strong-convexity/smoothness assumptions. As a fundamental contribution in proof techniques, we develop a novel extension of the classic three-point lemma to the considered two-step non-convex projection operator, which allows us to analyze the convergence in objective value in an elegant way that has not been possible with existing techniques. In the zeroth-order case, such technique also improves upon the state-of-the-art result from de Vazelhes et. al. (2022), even in the case without additional constraints, by allowing us to remove a non-vanishing system error present in their work.
• Abstract（参考訳）: スパース最適化では、$\ell_0$ pseudo-norm を使ってハード制約を強制することは凸緩和に比べて制御された空間性のような利点をもたらす。 しかし、現実世界のアプリケーションの多くは、余分な制約だけでなく、余分な制約も要求している。 従来のアルゴリズムはこの複雑なシナリオに混合組合せ制約と凸制約で対処するために開発されたが、通常は存在しないような混合制約に対する閉形式プロジェクションが必要であり、また/またはスパース最適化で求められる大域的な保証とは異なる収束の局所的な保証のみを提供する。 このギャップを埋めるために,本稿では,文献に共通する余分なサポート保存制約によるスパース最適化の問題について検討する。 混合制約に対するユークリッド射影の簡単な代替として、これらの制約をカスタマイズした2段階連続射影演算子を備えた、反復型ハードスレッショルドアルゴリズムを提案する。 空間緩和と部分最適性の間に新たなトレードオフを導入することにより、従来の制限された強凸/平滑性仮定の下で、決定論的、確率的、ゼロ次設定において、アルゴリズムの出力に対する客観的値のグローバルな保証を提供する。 実証技術における基本的な貢献として、従来の3点補題を2段階の非凸射影作用素に拡張し、既存の手法では不可能なエレガントな方法で対象値の収束を解析できるようにする。 ゼロオーダーの場合、この手法はデ・バゼルヘスら (2022) による最先端の結果も改善する。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
  分散最適化問題は分散制約の存在下では解決できない。 目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。 合成と実世界の両方のデータセットに数値的な結果を示す。
  論文  参考訳（メタデータ） (2024-09-08T06:57:35Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [17.384717824118255]
  この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。 これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
  論文  参考訳（メタデータ） (2024-02-14T10:48:00Z)
• Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
  我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。 各種設定に対してサブ線形後悔と制約違反境界を推定する。 我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
  論文  参考訳（メタデータ） (2023-05-02T11:27:34Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)

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

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