論文の概要: Manifold Proximal Point Algorithms for Dual Principal Component Pursuit
and Orthogonal Dictionary Learning
- arxiv url: http://arxiv.org/abs/2005.02356v2
- Date: Wed, 21 Jul 2021 13:40:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 13:15:16.087938
- Title: Manifold Proximal Point Algorithms for Dual Principal Component Pursuit
and Orthogonal Dictionary Learning
- Title（参考訳）: 二重主成分探索と直交辞書学習のためのマニフォールド近点アルゴリズム
- Authors: Shixiang Chen, Zengde Deng, Shiqian Ma, Anthony Man-Cho So
- Abstract要約: 様々な機械学習アプリケーションで発生する球面上の線形写像を最大化する問題を考える。
球面をスティーフェル行列に置き換える問題に対する新しいアプローチを提案する。
- 参考スコア（独自算出の注目度）: 32.87704663543739
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of maximizing the $\ell_1$ norm of a linear map over
the sphere, which arises in various machine learning applications such as
orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The
problem is numerically challenging due to its nonsmooth objective and nonconvex
constraint, and its algorithmic aspects have not been well explored. In this
paper, we show how the manifold structure of the sphere can be exploited to
design fast algorithms for tackling this problem. Specifically, our
contribution is threefold. First, we present a manifold proximal point
algorithm (ManPPA) for the problem and show that it converges at a sublinear
rate. Furthermore, we show that ManPPA can achieve a quadratic convergence rate
when applied to the ODL and RSR problems. Second, we propose a stochastic
variant of ManPPA called StManPPA, which is well suited for large-scale
computation, and establish its sublinear convergence rate. Both ManPPA and
StManPPA have provably faster convergence rates than existing subgradient-type
methods. Third, using ManPPA as a building block, we propose a new approach to
solving a matrix analog of the problem, in which the sphere is replaced by the
Stiefel manifold. The results from our extensive numerical experiments on the
ODL and RSR problems demonstrate the efficiency and efficacy of our proposed
methods.
- Abstract（参考訳）: 直交辞書学習 (ODL) やロバスト部分空間回復 (RSR) などの機械学習アプリケーションにおいて, 球面上の線形写像の$\ell_1$ノルムを最大化する問題を考える。
この問題は非滑らかな目的と非凸制約のために数値的に困難であり、そのアルゴリズム的側面はよく研究されていない。
本稿では,球面の多様体構造を利用して,この問題に対処するための高速アルゴリズムを設計する方法について述べる。
特に、私たちの貢献は3倍です。
まず,問題に対する多様体近位点アルゴリズム(ManPPA)を提案する。
さらに,ODL問題とRSR問題に適用した場合,ManPPAは2次収束率が得られることを示す。
第2に,大規模計算に好適なManPPAの確率的変種StManPPAを提案し,そのサブ線形収束率を確立する。
ManPPA と StManPPA はどちらも、既存の下降型手法よりも明らかに高速な収束速度を持つ。
第3に,manppa をビルディングブロックとして用いることにより,球面をスティーフェル多様体に置き換えた問題に対する行列アナログの解法を提案する。
ODLおよびRSR問題に関する広範な数値実験の結果,提案手法の有効性と有効性を示した。
関連論文リスト
- A Natural Primal-Dual Hybrid Gradient Method for Adversarial Neural Network Training on Solving Partial Differential Equations [9.588717577573684]
偏微分方程式(PDE)を解くためのスケーラブルな事前条件付き原始ハイブリッド勾配アルゴリズムを提案する。
本稿では,提案手法の性能を,一般的なディープラーニングアルゴリズムと比較する。
その結果,提案手法は効率的かつ堅牢に動作し,安定に収束することが示唆された。
論文 参考訳（メタデータ） (2024-11-09T20:39:10Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - 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) - A Deep Learning algorithm to accelerate Algebraic Multigrid methods in
Finite Element solvers of 3D elliptic PDEs [0.0]
本稿では,有限要素解法として用いる場合の代数的多重グリッド法の計算コストを最小化する新しいDeep Learningアルゴリズムを提案する。
本研究では,大きなスパース行列処理の計算コストを削減し,手前の回帰処理に必要な特徴を保存できることを実験的に証明する。
論文 参考訳（メタデータ） (2023-04-21T09:18:56Z) - Decentralized Riemannian natural gradient methods with Kronecker-product
approximations [11.263837420265594]
本稿では,分散化多様体最適化問題の解法として,効率的な分散化自然勾配降下法(DRNGD)を提案する。
クロネッカー因子を介して通信を行うことにより、RFIMの高品質な近似を低コストで得ることができる。
論文 参考訳（メタデータ） (2023-03-16T19:36:31Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Converting ADMM to a Proximal Gradient for Convex Optimization Problems [4.56877715768796]
融解ラッソや凸クラスタリングなどのスパース推定では、問題を解くために、近位勾配法またはマルチプライヤー(ADMM)の交互方向法のいずれかを適用します。
本論文では,制約と目的が強く凸であると仮定し,ADMM溶液を近位勾配法に変換する一般的な方法を提案する。
数値実験により, 効率の面で有意な改善が得られることを示した。
論文 参考訳（メタデータ） (2021-04-22T07:41:12Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳（メタデータ） (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。