論文の概要: Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization

• arxiv url: http://arxiv.org/abs/2306.01869v1
• Date: Fri, 2 Jun 2023 18:55:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 23:30:29.977389
• Title: Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization
• Title（参考訳）: 二元行列因子化のための高速$(1+\varepsilon)$近似アルゴリズム
• Authors: Ameya Velingker, Maximilian V\"otsch, David P. Woodruff, Samson Zhou
• Abstract要約: 本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
• 参考スコア（独自算出の注目度）: 54.29685789885059
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce efficient $(1+\varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix $\mathbf{A}\in\{0,1\}^{n\times d}$, a rank parameter $k>0$, as well as an accuracy parameter $\varepsilon>0$, and the goal is to approximate $\mathbf{A}$ as a product of low-rank factors $\mathbf{U}\in\{0,1\}^{n\times k}$ and $\mathbf{V}\in\{0,1\}^{k\times d}$. Equivalently, we want to find $\mathbf{U}$ and $\mathbf{V}$ that minimize the Frobenius loss $\|\mathbf{U}\mathbf{V} - \mathbf{A}\|_F^2$. Before this work, the state-of-the-art for this problem was the approximation algorithm of Kumar et. al. [ICML 2019], which achieves a $C$-approximation for some constant $C\ge 576$. We give the first $(1+\varepsilon)$-approximation algorithm using running time singly exponential in $k$, where $k$ is typically a small integer. Our techniques generalize to other common variants of the BMF problem, admitting bicriteria $(1+\varepsilon)$-approximation algorithms for $L_p$ loss functions and the setting where matrix operations are performed in $\mathbb{F}_2$. Our approach can be implemented in standard big data models, such as the streaming or distributed models.
• Abstract（参考訳）: 入力は行列 $\mathbf{a}\in\{0,1\}^{n\times d}$、ランクパラメータ $k>0$、精度パラメータ $\varepsilon>0$ であり、低ランク因子 $\mathbf{u}\in\{0,1\}^{n\times k}$と$\mathbf{v}\in\{0,1\}^{k\times d}$である。 同様に、フロベニウスの損失を最小化する $\mathbf{U}$ と $\mathbf{V}$ は、$\|\mathbf{U}\mathbf{V}\mathbf{A}\|_F^2$ である。 この研究の前に、この問題の最先端は、kumar etの近似アルゴリズムであった。 アル 一定の$C\ge 576$に対して$C$-approximationを達成する[ICML 2019]。 最初の$(1+\varepsilon)$近似アルゴリズムは、実行時間singlely exponential in $k$であり、通常$k$は小さい整数である。 我々の手法はBMF問題の他の一般的な変種に一般化し、$L_p$損失関数に対するbicriteria $(1+\varepsilon)$-approximationアルゴリズムと$\mathbb{F}_2$で行列演算を行う設定を許容する。 当社のアプローチは,ストリーミングや分散モデルといった,標準的なビッグデータモデルにも適用可能です。

関連論文リスト

• Fast, robust approximate message passing [2.668787455520979]
  本稿では,AMPアルゴリズムを頑健に実装するための高速なスペクトル計算法を提案する。 提案アルゴリズムはスペクトル前処理のステップを実行し,$mathcal A$の摂動を緩やかに修正する。
  論文  参考訳（メタデータ） (2024-11-05T03:20:14Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Solving Regularized Exp, Cosh and Sinh Regression Problems [40.47799094316649]
  注意計算はTransformer、GPT-4、ChatGPTといった大規模言語モデルの基本的なタスクである。 素直な方法はニュートンの方法を使うことである。
  論文  参考訳（メタデータ） (2023-03-28T04:26:51Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)

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

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