論文の概要: A Block Coordinate Descent Method for Nonsmooth Composite Optimization
under Orthogonality Constraints
- arxiv url: http://arxiv.org/abs/2304.03641v1
- Date: Fri, 7 Apr 2023 13:44:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-10 11:57:16.454786
- Title: A Block Coordinate Descent Method for Nonsmooth Composite Optimization
under Orthogonality Constraints
- Title（参考訳）: 直交制約下における非滑らか複合最適化のためのブロック座標降下法
- Authors: Ganzhao Yuan
- Abstract要約: 一般性制約を伴う非滑らかな複合最適化は、統計学習とデータ科学に幅広い応用がある。
textittextbfOBCDは非滑らかな複合問題を解くための新しいブロック座標法である。
- 参考スコア（独自算出の注目度）: 7.716156977428555
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nonsmooth composite optimization with orthogonality constraints has a broad
spectrum of applications in statistical learning and data science. However,
this problem is generally challenging to solve due to its non-convex and
non-smooth nature. Existing solutions are limited by one or more of the
following restrictions: (i) they are full gradient methods that require high
computational costs in each iteration; (ii) they are not capable of solving
general nonsmooth composite problems; (iii) they are infeasible methods and can
only achieve the feasibility of the solution at the limit point; (iv) they lack
rigorous convergence guarantees; (v) they only obtain weak optimality of
critical points. In this paper, we propose \textit{\textbf{OBCD}}, a new Block
Coordinate Descent method for solving general nonsmooth composite problems
under Orthogonality constraints. \textit{\textbf{OBCD}} is a feasible method
with low computation complexity footprints. In each iteration, our algorithm
updates $k$ rows of the solution matrix ($k\geq2$ is a parameter) to preserve
the constraints. Then, it solves a small-sized nonsmooth composite optimization
problem under orthogonality constraints either exactly or approximately. We
demonstrate that any exact block-$k$ stationary point is always an approximate
block-$k$ stationary point, which is equivalent to the critical stationary
point. We are particularly interested in the case where $k=2$ as the resulting
subproblem reduces to a one-dimensional nonconvex problem. We propose a
breakpoint searching method and a fifth-order iterative method to solve this
problem efficiently and effectively. We also propose two novel greedy
strategies to find a good working set to further accelerate the convergence of
\textit{\textbf{OBCD}}. Finally, we have conducted extensive experiments on
several tasks to demonstrate the superiority of our approach.
- Abstract（参考訳）: 直交制約を伴う非滑らかな複合最適化は、統計的学習とデータサイエンスに幅広い応用範囲を持つ。
しかし、この問題は一般に非凸かつ非滑らかな性質のため解決が難しい。
既存のソリューションは、以下の制限のいずれかに制限されている。
(i)各イテレーションで高い計算コストを必要とする全勾配法である。
二 一般の非平滑複合問題を解くことができないこと。
(iii)それらは実現不可能な方法であり、限界点での解の実現性しか達成できない。
(iv) 厳密な収束保証が欠けていること。
(v)臨界点の弱最適性のみを得る。
本稿では,直交制約下での一般非平滑な複合問題を解くブロックコーディネート Descent 法である \textit{\textbf{OBCD}} を提案する。
\textit{\textbf{OBCD}} は計算複雑性の少ない実現可能な方法である。
各イテレーションで、アルゴリズムは制約を保存するために解行列の$k$行を更新する($k\geq2$ is a parameter)。
そして、直交性制約の下で小さな非滑らかな合成最適化問題を正確にあるいはほぼ解決する。
我々は、任意のブロック-$k$定常点が常に近似ブロック-$k$定常点であることを示し、これは臨界定常点と同値である。
特に、結果のサブプロブレムとして$k=2$が1次元の非凸問題に還元される場合に興味がある。
本稿では,この問題を解決するために,ブレークポイント探索法と5階反復法を提案する。
また, 2 つの新しい欲望戦略を提案し, 優れた作業集合を探索し, \textit{\textbf{obcd}} の収束をさらに促進する。
最後に,提案手法の優越性を示すため,いくつかの課題について広範な実験を行った。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - 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) - 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) - First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。
本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
論文 参考訳（メタデータ） (2023-07-14T19:59:18Z) - Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
本稿では,候補アルゴリズムの集合に有効な手法を提案する。
内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。
提案手法は,他のアルゴリズムのスコアを大幅に改善する。
論文 参考訳（メタデータ） (2023-05-26T21:49:37Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - 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) - Coordinate Descent Methods for DC Minimization [12.284934135116515]
差分凸(英: difference-of-Convex、DC)とは、2つの凸関数の差を最小化する問題である。
本稿では,非次元の1次元サブプロブレムを世界規模で提案し,座標の定常点に収束することが保証される。
論文 参考訳（メタデータ） (2021-09-09T12:44:06Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。