Optimization Landscape of Tucker Decomposition

• URL: http://arxiv.org/abs/2006.16297v1
• Date: Mon, 29 Jun 2020 18:15:22 GMT
• Title: Optimization Landscape of Tucker Decomposition
• Authors: Abraham Frandsen, Rong Ge
• Abstract summary: 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.
• Score: 10.382642122818648
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconvex objective of Tucker decomposition, all local minima are also globally optimal. We also give a local search algorithm that can find an approximate local (and global) optimal solution in polynomial time.

Related papers

• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Approximately Optimal Core Shapes for Tensor Decompositions [7.1439425093981574]
  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.
  arXiv  Detail & Related papers  (2023-02-08T05:24:01Z)
• 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)
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling [5.740578698172382]
  We study Tucker decompositions and use tools from randomized numerical linear algebra called ridge leverage scores. We show how to use approximate ridge leverage scores to construct a sketched instance for any ridge regression problem. We demonstrate the effectiveness of our approximate ridge regressioni algorithm for large, low-rank Tucker decompositions on both synthetic and real-world data.
  arXiv  Detail & Related papers  (2021-07-22T13:32:47Z)
• 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)
• Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
  Non-used optimization is ubiquitous in modern machine learning. We rigorously formalize it for instances of machine learning problems. We hypothesize a unified explanation for this phenomenon.
  arXiv  Detail & Related papers  (2021-03-24T19:34:11Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries [1.3212010735248336]
  Change point detection is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. We propose optimistic search strategies with $O(log T)$ exploiting specific structure of the gain function.
  arXiv  Detail & Related papers  (2020-10-20T11:09:52Z)
• a-Tucker: Input-Adaptive and Matricization-Free Tucker Decomposition for Dense Tensors on CPUs and GPUs [6.308492837096872]
  A-Tucker is a new framework for input-adaptive and matricization-free Tucker decomposition of dense tensors. A machine-learning adaptive solver selector is applied to automatically cope with the variations of both the input data and the hardware.
  arXiv  Detail & Related papers  (2020-10-20T08:52:14Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)

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.