Approximately Optimal Core Shapes for Tensor Decompositions

• URL: http://arxiv.org/abs/2302.03886v1
• Date: Wed, 8 Feb 2023 05:24:01 GMT
• Title: Approximately Optimal Core Shapes for Tensor Decompositions
• Authors: Mehrdad Ghadiri, Matthew Fahrbach, Gang Fu, Vahab Mirrokni
• Abstract summary: We give an algorithm with provable approximation guarantees for 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 constraint-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid.
• Score: 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.

Related papers

• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  This work proposes an efficient parallel algorithm for non-monomodular size under a knapsack constraint. Our algorithm improves the existing parallel one from $8+epsilon$ to $7+epsilon$ with $O(log n)$ adaptive complexity.
  arXiv  Detail & Related papers  (2024-09-06T17:17:52Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications [26.602371644194143]
  We show that this fundamental tensor problem is NP-hard for any tensor rank higher than one. For low-enough ranks, the proposed continuous reformulation is amenable to low-complexity gradient-based optimization. We demonstrate promising results on a number of hard problems, including low density parity check codes and general decoding parity check codes.
  arXiv  Detail & Related papers  (2022-10-16T11:53:42Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition [62.41259783906452]
  We present a novel global compression framework for deep neural networks. It automatically analyzes each layer to identify the optimal per-layer compression ratio. Our results open up new avenues for future research into the global performance-size trade-offs of modern neural networks.
  arXiv  Detail & Related papers  (2021-07-23T20:01:30Z)
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions [1.8356693937139124]
  Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition. It is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor.
  arXiv  Detail & Related papers  (2021-04-02T15:55:02Z)
• Optimization Landscape of Tucker Decomposition [10.382642122818648]
  Tucker decomposition is a popular technique for many data analysis and machine applications. As learning problems increase, local search scale have become popular in practice.
  arXiv  Detail & Related papers  (2020-06-29T18:15:22Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  This paper proposes a working set algorithm for non-regular regularizers with convergence guarantees. Our results demonstrate high gain compared to the full problem solver for both block-coordinates or a gradient solver.
  arXiv  Detail & Related papers  (2020-06-24T07:40:31Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.