論文の概要: An inexact LPA for DC composite optimization and application to matrix
completions with outliers
- arxiv url: http://arxiv.org/abs/2303.16822v3
- Date: Tue, 21 Nov 2023 05:03:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 05:42:43.381832
- Title: An inexact LPA for DC composite optimization and application to matrix
completions with outliers
- Title(参考訳): 直流合成最適化のための不正確なLPAと外部整列行列への応用
- Authors: Ting Tao, Ruyu Liu, Shaohua Pan
- Abstract要約: 本稿では,複合最適化問題のクラスについて述べる。
合成構造を利用することで、ポテンシャル関数がイテレートで1/2$のKL特性を持つような条件を与えるので、列は局所的なRレートを持つ。
- 参考スコア(独自算出の注目度): 6.458101706833276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper concerns a class of DC composite optimization problems which, as
an extension of convex composite optimization problems and DC programs with
nonsmooth components, often arises in robust factorization models of low-rank
matrix recovery. For this class of nonconvex and nonsmooth problems, we propose
an inexact linearized proximal algorithm (iLPA) by computing in each step an
inexact minimizer of a strongly convex majorization constructed with a partial
linearization of their objective functions at the current iterate, and
establish the convergence of the generated iterate sequence under the
Kurdyka-\L\"ojasiewicz (KL) property of a potential function. In particular, by
leveraging the composite structure, we provide a verifiable condition for the
potential function to have the KL property of exponent $1/2$ at the limit
point, so for the iterate sequence to have a local R-linear convergence rate.
Finally, we apply the proposed iLPA to a robust factorization model for matrix
completions with outliers and non-uniform sampling, and numerical comparison
with the Polyak subgradient method confirms its superiority in terms of
computing time and quality of solutions.
- Abstract(参考訳): 本稿では, 対流合成最適化問題と非滑らか成分を含むdcプログラムの拡張として, 低ランク行列回復のロバスト因子分解モデルにおいてしばしば発生する直流合成最適化問題について述べる。
この非凸および非滑らかな問題に対して,各ステップにおいて,対象関数の部分的線形化により構築される強凸大化の非近似最小化法を計算し,クルディカ-\l\"ojasiewicz (kl) 特性の下で生成した反復列の収束を定め,線形化近位アルゴリズム (ilpa) を提案する。
特に, 複合構造を利用することにより, ポテンシャル関数が極限点で指数 1/2$ の kl 特性を持つような検証可能な条件を与え, 反復列が局所 r-線型収束率を持つようにした。
最後に,提案したiLPAを,外乱および非一様サンプリングを含む行列完備化のためのロバストな分解モデルに適用し,計算時間と解の質の観点からPolyak subgradient法との比較を行った。
関連論文リスト
- Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。
これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
論文 参考訳(メタデータ) (2024-02-14T10:48:00Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled
Compositional Stochastic Optimization [62.784166781064684]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳(メタデータ) (2023-12-04T19:00:07Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。
適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。
決定集合の低次元構造を高次元問題に活用する。
論文 参考訳(メタデータ) (2022-11-21T18:31:43Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳(メタデータ) (2022-10-21T13:19:45Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳(メタデータ) (2022-09-27T09:06:37Z) - On Asymptotic Linear Convergence of Projected Gradient Descent for
Constrained Least Squares [22.851500417035947]
この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。
本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
論文 参考訳(メタデータ) (2021-12-22T09:49:51Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳(メタデータ) (2021-09-13T16:13:13Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Piecewise linear regression and classification [0.20305676256390928]
本稿では,線形予測器を用いた多変量回帰と分類問題の解法を提案する。
本論文で記述されたアルゴリズムのpython実装は、http://cse.lab.imtlucca.it/bemporad/parcで利用可能である。
論文 参考訳(メタデータ) (2021-03-10T17:07:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。