論文の概要: A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

• arxiv url: http://arxiv.org/abs/2304.03641v3
• Date: Mon, 02 Dec 2024 00:54:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-03 16:54:21.137675
• Title: A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints
• Title（参考訳）: 直交制約下での非滑らかな合成最適化のためのブロックコーディネートDescent法
• Authors: Ganzhao Yuan,
• Abstract要約: textbfOBCDは標準臨界点よりも高い最適性を示すことを示す。 また,textbfOBCDの非エルグ収束率を示す。
• 参考スコア（独自算出の注目度）: 7.9047096855236125
• License:
• Abstract: Nonsmooth composite optimization with orthogonality constraints has a wide range of applications in statistical learning and data science. However, this problem is challenging due to its nonsmooth objective and computationally expensive, non-convex constraints. In this paper, we propose a new approach called \textbf{OBCD}, which leverages Block Coordinate Descent to address these challenges. \textbf{OBCD} is a feasible method with a small computational footprint. In each iteration, it updates $k$ rows of the solution matrix, where $k \geq 2$, by globally solving a small nonsmooth optimization problem under orthogonality constraints. We prove that the limiting points of \textbf{OBCD}, referred to as (global) block-$k$ stationary points, offer stronger optimality than standard critical points. Furthermore, we show that \textbf{OBCD} converges to $\epsilon$-block-$k$ stationary points with an ergodic convergence rate of $\mathcal{O}(1/\epsilon)$. Additionally, under the Kurdyka-Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of \textbf{OBCD}. We also extend \textbf{OBCD} by incorporating breakpoint searching methods for subproblem solving and greedy strategies for working set selection. Comprehensive experiments demonstrate the superior performance of our approach across various tasks.
• Abstract（参考訳）: 直交制約を伴う非滑らかな複合最適化は、統計学習やデータ科学に幅広い応用がある。 しかし,非滑らかで計算コストが高く,非凸制約のため,この問題は困難である。 本稿では,これらの課題に対処するためにブロックコーディネート・ダイセンシャル(Block Coordinate Descent)を利用する,‘textbf{OBCD}’という新しい手法を提案する。 textbf{OBCD} は計算フットプリントが小さい実現可能な方法である。 各反復において、解行列の$k$行を更新し、ここで$k \geq 2$は、直交制約の下で小さな非滑らかな最適化問題を大域的に解決する。 我々は、(グローバル)ブロック-$k$定常点と呼ばれる \textbf{OBCD} の極限点が、標準臨界点よりも強い最適性をもたらすことを証明した。 さらに、 \textbf{OBCD} は $\epsilon$-block-$k$ に収束し、エルゴード収束率は $\mathcal{O}(1/\epsilon)$ となる。 さらに、クルディカ・ロジャシエヴィチ(KL)の不等式の下では、非エルゴード収束速度を \textbf{OBCD} とする。 また、サブプロブレム解決のためのブレークポイント探索手法と作業セット選択のための欲求戦略を組み込むことで、 \textbf{OBCD} を拡張した。 総合的な実験は、様々なタスクにまたがるアプローチの優れた性能を実証する。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [18.425648833592312]
  ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。 我々の分析はユークリッドの制約を明示的に用いている。
  論文  参考訳（メタデータ） (2023-12-16T05:40:19Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
  本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。 提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
  論文  参考訳（メタデータ） (2021-10-22T11:49:15Z)
• Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
  我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。 このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。 我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
  論文  参考訳（メタデータ） (2020-06-23T20:51:00Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
  論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)

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

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