論文の概要: Approximately Optimal Core Shapes for Tensor Decompositions

• arxiv url: http://arxiv.org/abs/2302.03886v1
• Date: Wed, 8 Feb 2023 05:24:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-09 17:14:35.373749
• Title: Approximately Optimal Core Shapes for Tensor Decompositions
• Title（参考訳）: テンソル分解におけるほぼ最適コア形状
• Authors: Mehrdad Ghadiri, Matthew Fahrbach, Gang Fu, Vahab Mirrokni
• Abstract要約: 我々は,高次特異値への接続による再構成誤差の証明可能な近似保証付きアルゴリズムを提案する。 具体的には、NPハードであることが証明された新しいタッカーパッキング問題を導入し、マトロイドを用いた2次元クナップサック問題への還元に基づく制約時間近似スキームを提案する。
• 参考スコア（独自算出の注目度）: 7.1439425093981574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster.
• Abstract（参考訳）: この研究は、サイズ制約タッカー分解に対する最適コアテンソル形状(マルチ線形階数とも呼ばれる)の組合せ最適化問題を研究する。 我々は,高次特異値への接続による再構成誤差の証明可能な近似保証付きアルゴリズムを提案する。 具体的には,npハードであることが証明された新しいタッカーパッキング問題を導入し,マトロイド制約付き2次元ナップサック問題への還元に基づく多項式時間近似スキームを与える。 また、この手法をテンソルネットワーク分解木に一般化する。 我々は整数計画解法を用いてアルゴリズムを実装し、その解法品質が各ステップで真のタッカー分解損失を使い、最大1000倍高速に動作するグリージーアルゴリズムと競合する(時としてより優れている)ことを示す。

関連論文リスト

• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
  論文  参考訳（メタデータ） (2024-09-06T17:17:52Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications [26.602371644194143]
  この基本テンソル問題は 1 以上のテンソル階数に対して NP-hard であることを示す。 低次ランクの場合、提案された連続的な再構成は低複素度勾配に基づく最適化に有効である。 低密度パリティチェックコードや一般復号パリティチェックコードなど,多くの難題に対する有望な結果を示す。
  論文  参考訳（メタデータ） (2022-10-16T11:53:42Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition [62.41259783906452]
  本稿では,ディープニューラルネットワークのための新しいグローバル圧縮フレームワークを提案する。 各層を自動的に解析し、最適な層間圧縮比を特定する。 我々の結果は、現代のニューラルネットワークのグローバルなパフォーマンス-サイズトレードオフに関する将来の研究のための新たな道を開く。
  論文  参考訳（メタデータ） (2021-07-23T20:01:30Z)
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions [1.8356693937139124]
  低ランクタッカーとcpテンソル分解は、データ分析の強力なツールである。 タッカー分解のための高速かつ正確なスケッチALSアルゴリズムを提案する。 さらに、ランダム化されたタッカー圧縮と、タッカーコアテンソルのCP分解を用いて、CP分解を加速するためにも用いられる。
  論文  参考訳（メタデータ） (2021-04-02T15:55:02Z)
• Optimization Landscape of Tucker Decomposition [10.382642122818648]
  タッカー分解は多くのデータ分析やマシンアプリケーションで一般的なテクニックである。 学習問題の増加に伴い,地域検索の規模は増加傾向にある。
  論文  参考訳（メタデータ） (2020-06-29T18:15:22Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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