論文の概要: Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion

• arxiv url: http://arxiv.org/abs/2208.11246v1
• Date: Wed, 24 Aug 2022 00:56:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-25 12:30:40.879551
• Title: Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
• Title（参考訳）: 大規模オンラインマトリックスコンプリートのためのSGDの高速化
• Authors: Gavin Zhang, Hong-Ming Chiu, Richard Y. Zhang
• Abstract要約: 実世界の行列補完は、しばしば大規模な最適化問題である。 SGDは大規模で行列補完を解くことができる数少ないアルゴリズムの1つである。 本稿では,大規模なオンライン最適化のために,SGDの実用的特性をすべて保存した事前条件付きSGDを提案する。
• 参考スコア（独自算出の注目度）: 10.65673380743972
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The matrix completion problem seeks to recover a $d\times d$ ground truth matrix of low rank $r\ll d$ from observations of its individual elements. Real-world matrix completion is often a huge-scale optimization problem, with $d$ so large that even the simplest full-dimension vector operations with $O(d)$ time complexity become prohibitively expensive. Stochastic gradient descent (SGD) is one of the few algorithms capable of solving matrix completion on a huge scale, and can also naturally handle streaming data over an evolving ground truth. Unfortunately, SGD experiences a dramatic slow-down when the underlying ground truth is ill-conditioned; it requires at least $O(\kappa\log(1/\epsilon))$ iterations to get $\epsilon$-close to ground truth matrix with condition number $\kappa$. In this paper, we propose a preconditioned version of SGD that preserves all the favorable practical qualities of SGD for huge-scale online optimization while also making it agnostic to $\kappa$. For a symmetric ground truth and the Root Mean Square Error (RMSE) loss, we prove that the preconditioned SGD converges to $\epsilon$-accuracy in $O(\log(1/\epsilon))$ iterations, with a rapid linear convergence rate as if the ground truth were perfectly conditioned with $\kappa=1$. In our numerical experiments, we observe a similar acceleration for ill-conditioned matrix completion under the 1-bit cross-entropy loss, as well as pairwise losses such as the Bayesian Personalized Ranking (BPR) loss.
• Abstract（参考訳）: 行列完備問題は、個々の要素の観察から低ランクの$r\ll d$の$d\times d$ ground truth matrixを回復することを求める。 実世界の行列完備化は、しばしば大規模な最適化問題であり、$d$非常に大きいので、$O(d)$時間複雑性を持つ最も単純な完全次元ベクトル演算でさえ、非常に高価になる。 確率勾配降下(SGD)は、大規模で行列補完を解くことができる数少ないアルゴリズムの1つであり、また、進化する地上の真実をストリーミングデータを扱うことができる。 少なくとも$o(\kappa\log(1/\epsilon))$の反復が必要で、条件番号$\kappa$で$\epsilon$-close to ground truth行列を得る。 本稿では,大規模なオンライン最適化のために,SGDの実用的特性をすべて保存し,かつ,$\kappa$を無視できる事前条件付きSGDを提案する。 対称基底真理と根平均二乗誤差(rmse)の損失に対して、事前条件付きsgdは$o(\log(1/\epsilon)$の反復で$\epsilon$-accuracyに収束し、基底真理が$\kappa=1$で完全に条件付けされたかのように高速に線形収束する。 数値実験では、1ビットのクロスエントロピー損失とベイズ個人ランキング (bpr) 損失のようなペアリー損失の下での非条件行列完了に対する同様の加速を観測した。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• 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)
• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。 最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。 一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
  論文  参考訳（メタデータ） (2024-05-29T18:36:59Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Online Robust Regression via SGD on the l1 loss [19.087335681007477]
  ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。 この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
  論文  参考訳（メタデータ） (2020-07-01T11:38:21Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient Descent [1.0953917735844645]
  マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。 さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
  論文  参考訳（メタデータ） (2020-03-18T04:44:05Z)

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

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