Relaxation-assisted reverse annealing on nonnegative/binary matrix factorization

• URL: http://arxiv.org/abs/2501.02114v1
• Date: Fri, 03 Jan 2025 21:48:35 GMT
• Title: Relaxation-assisted reverse annealing on nonnegative/binary matrix factorization
• Abstract summary: We propose an improved strategy that integrates reverse annealing with a linear programming relaxation technique.<n>Our experiments on facial image datasets show that our method provides better convergence than known reverse annealing methods.
• Score: 0.4915744683251151
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealing has garnered significant attention as meta-heuristics inspired by quantum physics for combinatorial optimization problems. Among its many applications, nonnegative/binary matrix factorization stands out for its complexity and relevance in unsupervised machine learning. The use of reverse annealing, a derivative procedure of quantum annealing to prioritize the search in a vicinity under a given initial state, helps improve its optimization performance in matrix factorization. This study proposes an improved strategy that integrates reverse annealing with a linear programming relaxation technique. Using relaxed solutions as the initial configuration for reverse annealing, we demonstrate improvements in optimization performance comparable to the exact optimization methods. Our experiments on facial image datasets show that our method provides better convergence than known reverse annealing methods. Furthermore, we investigate the effectiveness of relaxation-based initialization methods on randomized datasets, demonstrating a relationship between the relaxed solution and the optimal solution. This research underscores the potential of combining reverse annealing and classical optimization strategies to enhance optimization performance.

Related papers

• A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization [1.7068557927955381]
  We build a connection between inverse optimization and the Fenchel-Young (FY) loss originally designed for structured prediction.<n>This new approach is amenable to efficient gradient-based optimization, hence much more efficient than existing methods.
  arXiv  Detail & Related papers  (2025-02-22T07:04:32Z)
• Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization [2.1485350418225244]
  We construct an analogous relax-then-sample strategy for low-rank optimization problems.<n>We derive a semidefinite relaxation and a randomized rounding scheme, which obtains near-optimal solutions.<n>We numerically illustrate the effectiveness and scalability of our relaxation and our sampling scheme.
  arXiv  Detail & Related papers  (2025-01-06T11:31:41Z)
• A novel algorithm for optimizing bundle adjustment in image sequence alignment [6.322876598831792]
  This paper introduces a novel algorithm for optimizing the Bundle Adjustment (BA) model in the context of image sequence alignment for cryo-electron tomography. Extensive experiments on both synthetic and real-world datasets were conducted to evaluate the algorithm's performance.
  arXiv  Detail & Related papers  (2024-11-10T03:19:33Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective. We present a series of state-of-the-art implicit bias rates for mirror descent and steepest descent algorithms. Our accelerated rates are derived by leveraging the regret bounds of online learning algorithms within this game framework.
  arXiv  Detail & Related papers  (2023-05-27T18:16:56Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Reverse Annealing for Nonnegative/Binary Matrix Factorization [0.0]
  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.
  arXiv  Detail & Related papers  (2020-07-10T18:40:02Z)
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning [95.85269649177336]
  ZO optimization iteratively performs three major steps: gradient estimation, descent direction, and solution update. We demonstrate promising applications of ZO optimization, such as evaluating and generating explanations from black-box deep learning models, and efficient online sensor management.
  arXiv  Detail & Related papers  (2020-06-11T06:50:35Z)
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning [3.511851311025242]
  We propose a primal-dual algorithm to optimize the primal and dual variables iteratively. We prove convergence of the proposed algorithm and show its non-asymptotic convergence rate. Preliminary experimental results on an optimal fund selection problem in fund of funds management showed its efficacy.
  arXiv  Detail & Related papers  (2020-05-19T03:31:01Z)

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.