A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition

• URL: http://arxiv.org/abs/2110.12564v1
• Date: Mon, 25 Oct 2021 00:46:02 GMT
• Title: A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition
• Authors: Chuanfu Xiao, Chao Yang
• Abstract summary: We show that the rank-adaptive HOOI algorithm is advantageous in terms of both accuracy and efficiency. Some further analysis on the HOOI algorithm and the classical alternating least squares method are presented to further understand why rank adaptivity can be introduced into the HOOI algorithm and how it works.
• Score: 3.4666021409328653
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a novel rank-adaptive higher-order orthogonal iteration (HOOI) algorithm to compute the truncated Tucker decomposition of higher-order tensors with a given error tolerance, and prove that the method is locally optimal and monotonically convergent. A series of numerical experiments related to both synthetic and real-world tensors are carried out to show that the proposed rank-adaptive HOOI algorithm is advantageous in terms of both accuracy and efficiency. Some further analysis on the HOOI algorithm and the classical alternating least squares method are presented to further understand why rank adaptivity can be introduced into the HOOI algorithm and how it works.

Related papers

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  We seek to find an ordering that can improve the convergence rates for the non-replacement form of the algorithm. We develop optimal orderings for constant and decreasing step sizes for strongly convex and convex functions. In addition, we are able to combine the ordering with mini-batch and further apply it to more complex neural networks.
  arXiv  Detail & Related papers  (2023-06-28T00:46:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  These algorithms exploit a non-Euclidean metric on the product space of the factor matrices of the low-rank tensor in the polyadic decomposition form. We prove that the proposed gradient descent algorithm globally converges to a stationary point of the tensor completion problem. Numerical results on synthetic and real-world data suggest that the proposed algorithms are more efficient in memory and time compared to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2021-01-26T22:11:06Z)
• Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors [1.827510863075184]
  Sparse tensor best rank-1 approximation (BR1Approx) is a sparsity generalization of the dense tensor BR1Approx. Four approximation algorithms are proposed, which are easily implemented, of low computational complexity. We provide numerical experiments on synthetic and real data to illustrate the effectiveness of the proposed algorithms.
  arXiv  Detail & Related papers  (2020-12-05T18:13:14Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  This work presents a new algorithm for empirical risk. The algorithm bridges the gap between first- and second-order search methods by computing a second-order search-type update in one subspace, coupled with a scaled steepest descent step in the Theoretical complement.
  arXiv  Detail & Related papers  (2020-06-06T19:28:14Z)
• Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
  We propose randomized Dykstra-style algorithms based on randomized dual coordinate ascent. For accelerated coordinate descent, we obtain a new algorithm that has better convergence properties than existing gradient methods in the interpolating regime.
  arXiv  Detail & Related papers  (2020-03-30T20:44:56Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10: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.