論文の概要: Memory-Efficient Convex Optimization for Self-Dictionary Separable
Nonnegative Matrix Factorization: A Frank-Wolfe Approach
- arxiv url: http://arxiv.org/abs/2109.11135v1
- Date: Thu, 23 Sep 2021 04:25:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-25 00:02:38.371932
- Title: Memory-Efficient Convex Optimization for Self-Dictionary Separable
Nonnegative Matrix Factorization: A Frank-Wolfe Approach
- Title（参考訳）: 自己二項分離非負行列分解のためのメモリ効率の良い凸最適化:フランク・ウルフアプローチ
- Authors: Tri Nguyen, Xiao Fu and Ruiyuan Wu
- Abstract要約: 本研究では,コンベックスSD-MMVのためのメモリ効率のアルゴリズムを提案する。
これは1950年代の古典的アルゴリズム、すなわちフランク・ウルフ(FW)アルゴリズムの特別な更新規則に乗じている。
妥当な条件下では、FWアルゴリズムは、データ量とともに線形に増大するメモリコストでノイズの多いSD-MMV問題を解く。
- 参考スコア（独自算出の注目度）: 13.369975476087934
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nonnegative matrix factorization (NMF) often relies on the separability
condition for tractable algorithm design. Separability-based NMF is mainly
handled by two types of approaches, namely, greedy pursuit and convex
programming. A notable convex NMF formulation is the so-called self-dictionary
multiple measurement vectors (SD-MMV), which can work without knowing the
matrix rank a priori, and is arguably more resilient to error propagation
relative to greedy pursuit. However, convex SD-MMV renders a large memory cost
that scales quadratically with the problem size. This memory challenge has been
around for a decade, and a major obstacle for applying convex SD-MMV to big
data analytics. This work proposes a memory-efficient algorithm for convex
SD-MMV. Our algorithm capitalizes on the special update rules of a classic
algorithm from the 1950s, namely, the Frank-Wolfe (FW) algorithm. It is shown
that, under reasonable conditions, the FW algorithm solves the noisy SD-MMV
problem with a memory cost that grows linearly with the amount of data. To
handle noisier scenarios, a smoothed group sparsity regularizer is proposed to
improve robustness while maintaining the low memory footprint with guarantees.
The proposed approach presents the first linear memory complexity algorithmic
framework for convex SD-MMV based NMF. The method is tested over a couple of
unsupervised learning tasks, i.e., text mining and community detection, to
showcase its effectiveness and memory efficiency.
- Abstract（参考訳）: 非負行列分解(NMF)は、しばしばトラクタブルアルゴリズムの設計における分離性条件に依存する。
分離性に基づくNMFは主に2種類のアプローチ、すなわち欲求追従と凸プログラミングによって処理される。
注目すべき凸 NMF の定式化は、いわゆる自己二項多重測定ベクトル (SD-MMV) であり、行列のランクを事前に知らなくても機能し、強欲な追従に対する誤差の伝播に対してより弾力性が高い。
しかし、凸SD-MMVは、問題サイズと2乗スケールする大きなメモリコストを発生させる。
このメモリ課題は10年ほど前からあり、ビッグデータ分析に凸SD-MMVを適用する上で大きな障害となっている。
本研究では,convex sd-mmvのメモリ効率向上アルゴリズムを提案する。
われわれのアルゴリズムは、1950年代の古典的アルゴリズム、すなわちフランク・ウルフ(FW)アルゴリズムの特別な更新規則を生かしている。
妥当な条件下では、FWアルゴリズムは、データ量とともに線形に増大するメモリコストでノイズの多いSD-MMV問題を解決する。
noisierのシナリオに対処するために、低メモリフットプリントを保証しながらロバスト性を改善するために、平滑化群スパーシティ調整器が提案されている。
提案手法は,コンベックスSD-MMVベースのNMFのための最初の線形メモリ複雑性アルゴリズムフレームワークを提案する。
本手法は,テキストマイニングとコミュニティ検出という,教師なしの学習課題に対して,その有効性と記憶効率を示すために試験される。
関連論文リスト
- A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。
これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。
我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
論文 参考訳（メタデータ） (2024-10-14T12:10:06Z) - The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。
イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。
実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
論文 参考訳（メタデータ） (2024-07-30T17:03:19Z) - Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark [166.40879020706151]
本稿では、微調整時のメモリコスト低減のためのソリューションとして、BPフリーゼロオーダー最適化(ZO)への移行を提案する。
従来のZO-SGD法とは異なり、我々の研究はより広い範囲のZO最適化手法に探索を広げる。
本研究は,タスクアライメントの重要性,前方勾配法の役割,アルゴリズムの複雑さと微調整性能のバランスについて,これまで見過ごされてきた最適化原理を明らかにした。
論文 参考訳（メタデータ） (2024-02-18T14:08:48Z) - Exponentially Convergent Algorithms for Supervised Matrix Factorization [2.1485350418225244]
Supervised Factorization (SMF) は、抽出タスクと分類タスクを集約する機械学習手法である。
本稿では,組合わせ係数空間推定における低ランク推定問題としてSMFを'リフト'する新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2023-11-18T23:24:02Z) - Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement
Learning in Discounted Linear MDPs [16.006893624836554]
本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。
VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。
後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
論文 参考訳（メタデータ） (2023-10-17T18:27:27Z) - Large-scale gradient-based training of Mixtures of Factor Analyzers [67.21722742907981]
本稿では,勾配降下による高次元学習を効果的に行うための理論解析と新しい手法の両立に寄与する。
MFAトレーニングと推論/サンプリングは,学習終了後の行列逆変換を必要としない精度行列に基づいて行うことができることを示す。
理論解析と行列の他に,SVHNやMNISTなどの画像データセットにMFAを適用し,サンプル生成と外乱検出を行う能力を示す。
論文 参考訳（メタデータ） (2023-08-26T06:12:33Z) - Provable Multi-instance Deep AUC Maximization with Stochastic Pooling [39.46116380220933]
本稿では,マルチインスタンス学習(MIL)における深層AUC(DAM)の新たな応用について考察する。
単一のクラスラベルは、インスタンスのバッグに割り当てられる(例えば、患者のためのスキャンの複数の2Dスライスなど)。
論文 参考訳（メタデータ） (2023-05-14T01:29:56Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。