論文の概要: An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function

• arxiv url: http://arxiv.org/abs/2503.23832v1
• Date: Mon, 31 Mar 2025 08:27:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-01 14:37:33.260256
• Title: An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function
• Title（参考訳）: ReLU関数を用いた非線形行列分解のための外挿および証明可能な収束アルゴリズム
• Authors: Nicolas Gillis, Margherita Porcelli, Giovanni Seraghiti,
• Abstract要約: 2つの定式化は、特に低ランクの $Theta を生じる可能性がある。 また、$Theta$をパラメータ化する3B-ReLUNMDと呼ばれる別のモデルも検討する。
• 参考スコア（独自算出の注目度）: 12.059960289576154
• License:
• Abstract: Nonlinear matrix decomposition (NMD) with the ReLU function, denoted ReLU-NMD, is the following problem: given a sparse, nonnegative matrix $X$ and a factorization rank $r$, identify a rank-$r$ matrix $\Theta$ such that $X\approx \max(0,\Theta)$. This decomposition finds application in data compression, matrix completion with entries missing not at random, and manifold learning. The standard ReLU-NMD model minimizes the least squares error, that is, $\|X - \max(0,\Theta)\|_F^2$. The corresponding optimization problem is nondifferentiable and highly nonconvex. This motivated Saul to propose an alternative model, Latent-ReLU-NMD, where a latent variable $Z$ is introduced and satisfies $\max(0,Z)=X$ while minimizing $\|Z - \Theta\|_F^2$ (``A nonlinear matrix decomposition for mining the zeros of sparse data'', SIAM J. Math. Data Sci., 2022). Our first contribution is to show that the two formulations may yield different low-rank solutions $\Theta$; in particular, we show that Latent-ReLU-NMD can be ill-posed when ReLU-NMD is not, meaning that there are instances in which the infimum of Latent-ReLU-NMD is not attained while that of ReLU-NMD is. We also consider another alternative model, called 3B-ReLU-NMD, which parameterizes $\Theta=WH$, where $W$ has $r$ columns and $H$ has $r$ rows, allowing one to get rid of the rank constraint in Latent-ReLU-NMD. Our second contribution is to prove the convergence of a block coordinate descent (BCD) applied to 3B-ReLU-NMD and referred to as BCD-NMD. Our third contribution is a novel extrapolated variant of BCD-NMD, dubbed eBCD-NMD, which we prove is also convergent under mild assumptions. We illustrate the significant acceleration effect of eBCD-NMD compared to BCD-NMD, and also show that eBCD-NMD performs well against the state of the art on synthetic and real-world data sets.
• Abstract（参考訳）: ReLU-NMD 函数を持つ非線形行列分解(NMD)は以下の問題である: スパースで非負の行列 $X$ と分解ランク $r$ が与えられると、ランク-r$行列 $\Theta$ が$X\approx \max(0,\Theta)$ となる。 この分解は、データ圧縮、ランダムではないエントリを持つ行列補完、および多様体学習における応用を見出す。 標準ReLU-NMDモデルは最小二乗誤差、すなわち$\|X - \max(0,\Theta)\|_F^2$を最小化する。 対応する最適化問題は非微分可能であり、非常に非凸である。 これにより、Sul は代替モデルである Latent-ReLU-NMD を提案し、そこで潜伏変数 $Z$ を導入して $\max(0,Z)= X$ を満たすが、$\|Z - \Theta\|_F^2$ (``A linear matrix decomposition for mining the zeros of sparse data', SIAM J. Math. Data Sci., 2022) を最小化する。 我々の最初の貢献は、2つの定式化が異なる低ランク解を$\Theta$で得ることを示すことであり、特に、ReLU-NMDがなければ、Latent-ReLU-NMDが悪用される可能性がある。 また、3B-ReLU-NMDという別のモデルも検討しています。これは$\Theta=WH$をパラメータ化し、$W$は$r$カラムを持ち、$H$は$r$行を持ち、Latent-ReLU-NMDのランク制約を取り除くことができます。 第2の貢献は、3B-ReLU-NMDに適用されたブロック座標降下(BCD)の収束を証明し、BCD-NMDと呼ぶことである。 第3の貢献は、eBCD-NMDと呼ばれる新しいBCD-NMD外挿版であり、軽度の仮定の下でも収束することが証明されている。 我々は,BCD-NMDと比較して,eBCD-NMDが有意な加速効果を示した。

関連論文リスト

• A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
  Lipschitz-of-$nabla f$ $mathcalS_k|p$。 $mathcalS_k|p$。 $nabla f$. $mathcalS_k|p$。
  論文  参考訳（メタデータ） (2024-09-28T18:16:32Z)
• A Momentum Accelerated Algorithm for ReLU-based Nonlinear Matrix Decomposition [0.0]
  本稿では,Tikhonov正規化ReLU-NMDモデル(ReLU-NMD-T)を提案する。 本稿では,ReLU-NMD-Tモデルを扱うための運動量加速アルゴリズムを提案する。 実世界のデータセットに関する数値実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2024-02-04T10:43:35Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Accelerated Algorithms for Nonlinear Matrix Decomposition with the ReLU function [17.17890385027466]
  我々は、$f(cdot) = max(0, cdot)$, rectified unit (ReLU) non-linear activation の場合に焦点を当てる。 本稿では,(1)適応型ネステロフ外挿法を用いて既存のアルゴリズムを高速化するアグレッシブアクセラレーションNMD (A-NMD) と,(2)$Theta = WH$をパラメータ化して計算コストを大幅に削減する3ブロックNMD (3B-NMD) の2つの新しいアルゴリズムを紹介する。
  論文  参考訳（メタデータ） (2023-05-15T14:43:27Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。 シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
  論文  参考訳（メタデータ） (2021-10-15T09:27:50Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
  本稿では,線形整列ユニット(ReLU)を活性化した2層残基を学習するアルゴリズムについて述べる。 解析最小化器はそのパラメータと非線形性の観点から、正確な地上構造ネットワークを表現できる機能として層ワイドな目的を設計する。 我々は,アルゴリズムの統計的強い一貫性を証明し,実験によるアルゴリズムの堅牢性とサンプル効率を実証する。
  論文  参考訳（メタデータ） (2020-08-17T22:11:26Z)

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

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