論文の概要: Efficient Algorithms for High-Dimensional Convex Subspace Optimization
via Strict Complementarity
- arxiv url: http://arxiv.org/abs/2202.04020v1
- Date: Tue, 8 Feb 2022 17:36:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 15:03:46.542274
- Title: Efficient Algorithms for High-Dimensional Convex Subspace Optimization
via Strict Complementarity
- Title（参考訳）: Strict Complementarityによる高次元凸部分空間最適化のための効率的なアルゴリズム
- Authors: Dan Garber, Ron Fisher
- Abstract要約: 目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。
この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。
本稿では自然について述べる。
収束する最適な次元緩和を 決定するのです
グローバルは単純です
- 参考スコア（独自算出の注目度）: 19.24470467199451
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider optimization problems in which the goal is find a $k$-dimensional
subspace of $\reals^n$, $k<<n$, which minimizes a convex and smooth loss. Such
problemsgeneralize the fundamental task of principal component analysis (PCA)
to include robust and sparse counterparts, and logistic PCA for binary data,
among others. While this problem is not convex it admits natural algorithms
with very efficient iterations and memory requirements, which is highly desired
in high-dimensional regimes however, arguing about their fast convergence to a
global optimal solution is difficult. On the other hand, there exists a simple
convex relaxation for which convergence to the global optimum is
straightforward, however corresponding algorithms are not efficient when the
dimension is very large. In this work we present a natural deterministic
sufficient condition so that the optimal solution to the convex relaxation is
unique and is also the optimal solution to the original nonconvex problem.
Mainly, we prove that under this condition, a natural highly-efficient
nonconvex gradient method, which we refer to as \textit{gradient orthogonal
iteration}, when initialized with a "warm-start", converges linearly for the
nonconvex problem. We also establish similar results for the nonconvex
projected gradient method, and the Frank-Wolfe method when applied to the
convex relaxation. We conclude with empirical evidence on synthetic data which
demonstrate the appeal of our approach.
- Abstract（参考訳）: 我々は、凸と滑らかな損失を最小化する$\reals^n$, $k<<n$ の$k$次元部分空間を目標とする最適化問題を考える。
このような問題は、主成分分析(PCA)の基本課題を、頑健でスパースな要素や、バイナリデータのためのロジスティックPCAなどを含むように一般化する。
この問題は凸ではないものの、非常に効率的な反復とメモリ要件を持つ自然アルゴリズムを認め、高次元のレジームにおいて非常に望ましいが、グローバルな最適解への高速な収束について議論することは困難である。
一方、大域的最適度への収束が単純であるような単純な凸緩和が存在するが、対応するアルゴリズムは次元が非常に大きい場合には効率的ではない。
本研究では、凸緩和に対する最適解が一意であり、また元の非凸問題に対する最適解であるような自然な決定論的十分条件を示す。
主に、この条件下では、「ウォームスタート」で初期化されると「textit{gradient orthogonal iteration}」と呼ばれる自然な高効率な非凸勾配法が非凸問題に対して線形収束することを証明している。
また,非凸射影勾配法と,凸緩和に適用した場合のフランク・ウルフ法についても同様の結果が得られた。
我々は、我々のアプローチの魅力を示す合成データに関する実証的な証拠で締めくくった。
関連論文リスト
- Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。
これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
論文 参考訳（メタデータ） (2024-02-14T10:48:00Z) - A simple uniformly optimal method without line search for convex
optimization [10.963511172615158]
パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。
滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-16T05:26:03Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints [3.667453772837954]
強い凸関数制約を受ける凸関数を最小化する方法を示す。
有限個の結果に独立な意味を持つような空間パターンを同定する。
論文 参考訳（メタデータ） (2022-12-21T16:04:53Z) - A conditional gradient homotopy method with applications to Semidefinite
Programming [1.6369790794838281]
ホモトピーに基づく条件勾配法による凸最適化問題の解法。
我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
論文 参考訳（メタデータ） (2022-07-07T05:48:27Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。