論文の概要: A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints
- arxiv url: http://arxiv.org/abs/2511.03443v1
- Date: Wed, 05 Nov 2025 13:03:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-06 18:19:32.431592
- Title: A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints
- Title（参考訳）: 非負および直交制約を持つ最適化問題に対するサポートセットアルゴリズム
- Authors: Lei Wang, Xin Liu, Xiaojun Chen,
- Abstract要約: サポートセットを固定することにより、最小化サブプロブレムの大域的な解は、少なくとも$n$非ゼロなエントリを持つ閉形式で計算できることが示される。
中心となる要素は、ゼロでないエントリの配置を調整するサポートセットのための戦略的に考案された更新スキームである。
非負のPCA,クラスタリング,コミュニティ検出など,実世界のアプリケーションでは,数値的な結果が強く支持されている。
- 参考スコア（独自算出の注目度）: 9.143066261696683
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate optimization problems with nonnegative and orthogonal constraints, where any feasible matrix of size $n \times p$ exhibits a sparsity pattern such that each row accommodates at most one nonzero entry. Our analysis demonstrates that, by fixing the support set, the global solution of the minimization subproblem for the proximal linearization of the objective function can be computed in closed form with at most $n$ nonzero entries. Exploiting this structural property offers a powerful avenue for dramatically enhancing computational efficiency. Guided by this insight, we propose a support-set algorithm preserving strictly the feasibility of iterates. A central ingredient is a strategically devised update scheme for support sets that adjusts the placement of nonzero entries. We establish the global convergence of the support-set algorithm to a first-order stationary point, and show that its iteration complexity required to reach an $\epsilon$-approximate first-order stationary point is $O (\epsilon^{-2})$. Numerical results are strongly in favor of our algorithm in real-world applications, including nonnegative PCA, clustering, and community detection.
- Abstract（参考訳）: 本稿では,非負および直交制約を用いた最適化問題について検討し,各行が少なくとも1つの非零エントリに収まるようなスペーサ性パターンを示すサイズが$n \times p$の任意の実現可能な行列について述べる。
解析により、支持集合を固定することにより、目的関数の近位線型化に対する最小化サブプロブレムの大域解が、少なくとも$n$非ゼロエントリを持つ閉形式で計算できることが示される。
この構造特性の爆発は、計算効率を劇的に向上させる強力な道を提供する。
この知見に導かれて,本研究では,反復処理の有効性を厳密に保ったサポートセットアルゴリズムを提案する。
中心となる要素は、ゼロでないエントリの配置を調整するサポートセットのための戦略的に考案された更新スキームである。
我々は、サポートセットアルゴリズムの1次定常点への大域収束を確立し、その反復複雑性が$\epsilon$-approximate 1次定常点に到達するのに必要となることを示し、$O (\epsilon^{-2})$とする。
非負のPCA,クラスタリング,コミュニティ検出など,実世界のアプリケーションでは,数値的な結果が強く支持されている。
関連論文リスト
- Scalable Second-order Riemannian Optimization for $K$-means Clustering [22.839486642997187]
K$-meansクラスタリング問題をサブ多様体として新たに定式化する。
K$-平均多様体を積多様体に分解することにより、ニュートン部分確率がどのように解けるかを示す。
実験の結果,提案手法は最先端の1次負の非負の非負の分解法よりもはるかに高速に収束することがわかった。
論文 参考訳（メタデータ） (2025-09-25T22:49:00Z) - Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。
第一のアルゴリズムは真の解に線形に収束する。
第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
論文 参考訳（メタデータ） (2024-10-08T21:19:22Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - 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) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳（メタデータ） (2021-03-15T11:20:31Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。