論文の概要: Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM
- arxiv url: http://arxiv.org/abs/2407.13731v1
- Date: Thu, 18 Jul 2024 17:33:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-19 14:21:47.891445
- Title: Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM
- Title（参考訳）: 部分観測による予測的低ランク行列学習:混合投影ADMM
- Authors: Dimitris Bertsimas, Nicholas A. G. Johnson,
- Abstract要約: 低階仮定の下で部分的に観察された行列を学習する問題について検討する。
この問題は、レコメンデーションシステム、信号処理、システム識別、画像デノイングといった応用で発生する。
我々のアルゴリズムは、$n = 10000$行と$m = 10000$列を1分以内で解くことができる。
- 参考スコア（独自算出の注目度）: 5.877778007271621
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning a partially observed matrix under the low rank assumption in the presence of fully observed side information that depends linearly on the true underlying matrix. This problem consists of an important generalization of the Matrix Completion problem, a central problem in Statistics, Operations Research and Machine Learning, that arises in applications such as recommendation systems, signal processing, system identification and image denoising. We formalize this problem as an optimization problem with an objective that balances the strength of the fit of the reconstruction to the observed entries with the ability of the reconstruction to be predictive of the side information. We derive a mixed-projection reformulation of the resulting optimization problem and present a strong semidefinite cone relaxation. We design an efficient, scalable alternating direction method of multipliers algorithm that produces high quality feasible solutions to the problem of interest. Our numerical results demonstrate that in the small rank regime ($k \leq 15$), our algorithm outputs solutions that achieve on average $79\%$ lower objective value and $90.1\%$ lower $\ell_2$ reconstruction error than the solutions returned by the experiment-wise best performing benchmark method. The runtime of our algorithm is competitive with and often superior to that of the benchmark methods. Our algorithm is able to solve problems with $n = 10000$ rows and $m = 10000$ columns in less than a minute.
- Abstract（参考訳）: 本研究では, 真基底行列に線形に依存する完全観測側情報の存在下で, 低階の仮定の下で部分的に観測された行列を学習する問題について検討する。
この問題は、統計学、オペレーションリサーチ、機械学習における中心的な問題であるマトリックスコンプリート問題の重要な一般化から成り、レコメンデーションシステム、信号処理、システム識別、画像デノーミングなどのアプリケーションで発生する。
この問題を最適化問題として定式化し, 得られた項目に対する再構成の適合性の強さと, サイド情報の予測能力とをバランスさせる目的を定式化する。
我々は、結果の最適化問題の混合射影再構成を導出し、強い半定値円錐緩和を示す。
興味のある問題に対する高品質な実現可能な解を生成する乗算器アルゴリズムの効率的でスケーラブルな交互方向法を設計する。
数値計算の結果, 提案手法では, 平均目標値が79.%, 目標値が9.0.1.%, 目標値が9.0.1.%, 最小値が9.5%, 最小値が9.5%, 最小値が9.5%, 最小値が9.5%, 最小値が9.5%, 最小値が9.5%, 最小値が9.5%であった。
我々のアルゴリズムのランタイムは、ベンチマークメソッドのランタイムと競合し、しばしば優れている。
我々のアルゴリズムは、$n = 10000$行と$m = 10000$列を1分以内で解くことができる。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Matrix Completion with Convex Optimization and Column Subset Selection [0.0]
本稿では,カラム選択行列補完法(CSMC)を実装した2つのアルゴリズムを提案する。
本研究では, 行列サイズ, ランク計算, 欠落要素の割合が解の質と時間に与える影響について検討するため, 合成データについて実験を行った。
我々の徹底的な分析により,CSMCは凸最適化に基づく行列補完アルゴリズムに匹敵する品質のソリューションを提供することが示された。
論文 参考訳（メタデータ） (2024-03-04T10:36:06Z) - Orthogonally weighted $\ell_{2,1}$ regularization for rank-aware joint
sparse recovery: algorithm and analysis [7.7001263654719985]
我々は,新たな正規化法である $ell_2,1$$(mathitowell_2,1$) を用いて,結合スパース回復問題の効率的な解法を提案し,解析する。
この手法は特徴抽出、行列列選択、辞書学習に応用され、一般的な$ell_2,1$正規化とは異なる。
提案手法のランク認識の証明を行い,提案手法の最適化問題に対する解が存在することを証明し,収束を解析した効率的な解法を開発した。
論文 参考訳（メタデータ） (2023-11-21T01:52:15Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization
Approach [6.952045528182883]
スパースプラス低ランク分解問題(SLR)について検討する。
SLRはオペレーションリサーチと機械学習の基本的な問題である。
本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
論文 参考訳（メタデータ） (2021-09-26T20:49:16Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳（メタデータ） (2020-07-14T09:50:33Z) - The Backbone Method for Ultra-High Dimensional Sparse Machine Learning [3.7565501074323224]
超高次元問題にスケールできるスパースかつ解釈可能な機械学習手法を実現する汎用フレームワークであるBackbone法を提案する。
私たちは、分で107ドル、時間で108ドル、分で105ドルという決定ツリーの問題でスパースレグレッションの問題を解決する。
論文 参考訳（メタデータ） (2020-06-11T16:43:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。