論文の概要: Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors

• arxiv url: http://arxiv.org/abs/2012.03092v1
• Date: Sat, 5 Dec 2020 18:13:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-22 14:48:26.829522
• Title: Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors
• Title（参考訳）: 高階テンソルに対するsparse best rank-1 approximationの近似アルゴリズム
• Authors: Xianpeng Mao and Yuning Yang
• Abstract要約: スパーステンソル最高ランク1近似(英: Sparse tensor best rank-1 approximation, BR1Approx)は、密度テンソルBR1Approxの空間一般化である。 低計算量で容易に実装できる4つの近似アルゴリズムが提案されている。 提案手法の有効性を示すために,合成および実データに関する数値実験を行った。
• 参考スコア（独自算出の注目度）: 1.827510863075184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed worst-case approximation lower bounds are proved for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the effectiveness of the proposed algorithms.
• Abstract（参考訳）: スパーステンソルの最良ランク1近似(sparse tensor best rank-1 approximation, br1approx)は、密度テンソルbr1近似のスパース性一般化であり、スパース行列br1近似の高次拡張であり、スパーステンソル分解や統計や機械学習から生じる関連する問題において最も重要な問題の1つである。 多重線形性と問題のスパーシティ構造を利用することにより、計算複雑性が低く、反復アルゴリズムの初期手順として機能する4つの近似アルゴリズムが提案されている。 さらに、理論上保証された最悪のケース近似の下限を全てのアルゴリズムで証明する。 提案手法の有効性を示すために,合成および実データに関する数値実験を行った。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition [3.4666021409328653]
  ランク適応型HOOIアルゴリズムは精度と効率の両面で有利であることを示す。 HOOIアルゴリズムと古典的交代最小二乗法についてさらなる解析を行い、なぜHOOIアルゴリズムにランク適応性を導入することができるのか、どのように機能するかをさらに理解する。
  論文  参考訳（メタデータ） (2021-10-25T00:46:02Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• A Parameter-free Algorithm for Convex-concave Min-max Problems [33.39558541452866]
  洞窟なし最適化アルゴリズムは、学習速度を調整せずに初期点に対して収束率が最適であるアルゴリズムを指す。 副産物として,パラメータフリーなアルゴリズムを用いて,成長条件付きmin-max問題の高速速度を求める新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-02-27T18:10:06Z)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。 提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。 合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
  論文  参考訳（メタデータ） (2021-01-26T22:11:06Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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