論文の概要: Reweighted Solutions for Weighted Low Rank Approximation

• arxiv url: http://arxiv.org/abs/2406.02431v1
• Date: Tue, 4 Jun 2024 15:50:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-05 15:30:46.797358
• Title: Reweighted Solutions for Weighted Low Rank Approximation
• Title（参考訳）: 軽量低ランク近似に対する再加重解法
• Authors: David P. Woodruff, Taisuke Yasuda,
• Abstract要約: 重み付き低階近似(WLRA)は、統計解析から信号処理に至るまで、重要かつ困難なプリミティブである。 そこで本研究では,WLRAに対して,必ずしも低ランクではないが極めて少ないパラメータで保存可能な行列を出力する緩和解を提案する。 我々の中心となる考え方は、重み行列自体を低階解の重み付けに利用することであり、これは非常に単純なアルゴリズムであり、顕著な経験的性能を与える。
• 参考スコア（独自算出の注目度）: 47.790126028106734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal processing. To cope with the NP-hardness of this problem, prior work considers heuristics, bicriteria, or fixed parameter tractable algorithms to solve this problem. In this work, we introduce a new relaxed solution to WLRA which outputs a matrix that is not necessarily low rank, but can be stored using very few parameters and gives provable approximation guarantees when the weight matrix has low rank. Our central idea is to use the weight matrix itself to reweight a low rank solution, which gives an extremely simple algorithm with remarkable empirical performance in applications to model compression and on synthetic datasets. Our algorithm also gives nearly optimal communication complexity bounds for a natural distributed problem associated with this problem, for which we show matching communication lower bounds. Together, our communication complexity bounds show that the rank of the weight matrix provably parameterizes the communication complexity of WLRA. We also obtain the first relative error guarantees for feature selection with a weighted objective.
• Abstract（参考訳）: 重み付き低階近似(WLRA)は、統計解析、モデル圧縮、信号処理など、重要かつ計算的に難しいプリミティブである。 この問題のNPハードネスに対処するため、先行研究では、この問題を解決するためにヒューリスティックス、ビクリテリア、あるいは固定パラメータ抽出可能なアルゴリズムを検討する。 本研究では,WLRAに新たな緩和解を導入する。これは必ずしも低ランクではない行列を出力するが,非常に少ないパラメータで保存することができ,重み行列が低ランクである場合に証明可能な近似保証を与える。 我々の中心的な考え方は、重み行列自体を低階解の重み付けに利用することであり、これは、圧縮や合成データセットのモデル化への応用において、顕著な経験的性能を持つ非常に単純なアルゴリズムを提供する。 また、本アルゴリズムは、この問題に関連する自然分散問題に対して、ほぼ最適な通信複雑性境界を与える。 重み行列のランクがWLRAの通信複雑性をパラメータ化することを示す。 また、重み付けされた目的を持つ特徴選択に対する最初の相対誤差保証を得る。

関連論文リスト

• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach [6.952045528182883]
  スパースプラス低ランク分解問題(SLR)について検討する。 SLRはオペレーションリサーチと機械学習の基本的な問題である。 本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
  論文  参考訳（メタデータ） (2021-09-26T20:49:16Z)
• Smooth Bilevel Programming for Sparse Regularization [5.177947445379688]
  反復再重み付き最小二乗法(IRLS)は、機械学習における空間的回帰問題を解くための一般的な手法である。 両レベルスキームが組み合わさって、IRLSの驚くほど再パラメータ化が、いかにスパーシティの上位化を実現するかを示す。
  論文  参考訳（メタデータ） (2021-06-02T19:18:22Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)
• On the simplicity and conditioning of low rank semidefinite programs [28.71984085513293]
  完全データによるSDPの正確な解は、元の低階行列回復問題に対する解を復元することがよく知られている。 ノイズの多い問題データで定式化されたSDPの近似解が元の問題を許容的に解くことを示すことはより困難である。 本稿では,ノイズ問題データや不完全収束による誤差を制限する簡易性と呼ばれる条件の集合を同定する。
  論文  参考訳（メタデータ） (2020-02-25T05:18:36Z)

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

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