Reverse Annealing for Nonnegative/Binary Matrix Factorization

• URL: http://arxiv.org/abs/2007.05565v2
• Date: Tue, 12 Jan 2021 16:42:15 GMT
• Title: Reverse Annealing for Nonnegative/Binary Matrix Factorization
• Abstract summary: It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. In this paper, we utilize reverse annealing instead of forward annealing in the quantum annealing subroutine for nonnegative/binary matrix factorization problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. The quantum annealing algorithm performed best for quick, approximate answers, but performance rapidly plateaued. In this paper, we utilize reverse annealing instead of forward annealing in the quantum annealing subroutine for nonnegative/binary matrix factorization problems. After an initial global search with forward annealing, reverse annealing performs a series of local searches that refine existing solutions. The combination of forward and reverse annealing significantly improves performance compared to forward annealing alone for all but the shortest run times.

Related papers

• Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
  Federated matrices bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning.<n>Most existing federated bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices.<n>We propose a novel federated convergence variance-reduced bilevel descent algorithm that relies solely on first-order oracles.
  arXiv  Detail & Related papers  (2026-09-14T21:12:59Z)
• Extending the computational reach of Quantum Annealing using Reverse Annealing [0.0]
  We find that combining forward and reverse annealing consistently improves solution quality and efficiency across multiple problem classes.<n>We establish these results through a systematic experimental study on a D-Wave Advantage system.
  arXiv  Detail & Related papers  (2026-07-02T13:21:57Z)
• Understanding the Curse of Unrolling [2.2452525313322966]
  We provide a non-asymptotic analysis that explains the origin of the curse of unrolling.<n>We show that truncating early iterations of the derivative computation mitigates the curse while simultaneously reducing memory requirements.<n>Our theoretical findings are supported by numerical experiments on representative examples.
  arXiv  Detail & Related papers  (2026-02-23T11:32:39Z)
• Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
  We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles.<n>We demonstrate the first dimension-independent query complexities for zeroth-order convex optimization in both smooth and nonsmooth settings.<n>By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games.
  arXiv  Detail & Related papers  (2025-03-21T17:58:12Z)
• Relaxation-assisted reverse annealing on nonnegative/binary matrix factorization [0.4915744683251151]
  We propose an improved strategy that integrates reverse annealing with a linear programming relaxation technique. Our experiments on facial image datasets show that our method provides better convergence than known reverse annealing methods.
  arXiv  Detail & Related papers  (2025-01-03T21:48:35Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment. We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Reverse quantum annealing assisted by forward annealing [0.0]
  We use a general method that improves the overall solution quality and quantity. A scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach.
  arXiv  Detail & Related papers  (2024-08-24T15:13:24Z)
• Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems [2.249916681499244]
  Given an image and an overcomplete, non-orthonormal basis, we aim to find a sparse binary vector indicating the minimal set of vectors that when added together best reconstruct the given input. This yields a quadratic binary optimization problem (QUBO), whose optimal solution(s) in general is NP-hard to find. Next, we solve the sparse representation QUBO by implementing it both on a D-Wave annealer with Pegasus chip connectivity via minor embedding, as well as on the Intel Loihi 2 spiking neuromorphic processor.
  arXiv  Detail & Related papers  (2024-05-30T22:56:15Z)
• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  We show that our algorithm converges exponentially fast to the optimal solution in the number of iterations. We discuss several applications of our algorithm in quantum resource theories and quantum Shannon theory.
  arXiv  Detail & Related papers  (2023-12-22T11:16:11Z)
• 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)
• A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization [2.646309221150203]
  We propose to improve the Multiplicative Updates algorithm by crafting a tighter upper bound of the Hessian matrix for each alternate subproblem. Convergence is still ensured and we observe in practice on both synthetic and real world dataset that the proposed fastMU algorithm is often several orders of magnitude faster than the regular Multiplicative Updates algorithm.
  arXiv  Detail & Related papers  (2023-03-31T12:09:36Z)
• Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy [1.14219428942199]
  We propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy. We analytically show that a first-order phase transition is successfully avoided for a fully connected ferro Potts model if the overlap between a ground state and a candidate solution exceeds a threshold.
  arXiv  Detail & Related papers  (2022-11-08T02:12:49Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  We develop a novel surrogate that can be optimized by closed-form solutions. We exploit upperwise correlation for completion, and thus an adaptive correlation learning model.
  arXiv  Detail & Related papers  (2022-03-04T08:50:50Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  Conditional gradient algorithm (also known as the Frank-Wolfe algorithm) has recently regained popularity in the machine learning community. ARCS is the first zeroth-order conditional gradient sliding type algorithms solving convex problems in zeroth-order optimization. In first-order optimization, the convergence results of ARCS substantially outperform previous algorithms in terms of the number of gradient query oracle.
  arXiv  Detail & Related papers  (2021-09-18T07:08:11Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)

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.