Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine

• URL: http://arxiv.org/abs/2303.14993v2
• Date: Tue, 8 Aug 2023 03:37:18 GMT
• Title: Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Authors: Hiroshi Yamashita, Ken-ichi Okubo, Suguru Shimomura, Yusuke Ogura, Jun Tanida, Hideyuki Suzuki
• Abstract summary: We propose a new computing model for the SPIM that can accommodate any Ising problem without changing its optical implementation. The proposed model is particularly efficient for Ising problems with low-rank interaction matrices, such as knapsack problems. We demonstrate that learning, classification, and sampling of the MNIST handwritten digit images are achieved efficiently using the model with low-rank interactions.
• Score: 0.44040106718326594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The spatial photonic Ising machine (SPIM) [D. Pierangeli et al., Phys. Rev. Lett. 122, 213902 (2019)] is a promising optical architecture utilizing spatial light modulation for solving large-scale combinatorial optimization problems efficiently. The primitive version of the SPIM, however, can accommodate Ising problems with only rank-one interaction matrices. In this Letter, we propose a new computing model for the SPIM that can accommodate any Ising problem without changing its optical implementation. The proposed model is particularly efficient for Ising problems with low-rank interaction matrices, such as knapsack problems. Moreover, it acquires the learning ability of Boltzmann machines. We demonstrate that learning, classification, and sampling of the MNIST handwritten digit images are achieved efficiently using the model with low-rank interactions. Thus, the proposed model exhibits higher practical applicability to various problems of combinatorial optimization and statistical learning, without losing the scalability inherent in the SPIM architecture.

Related papers

• Bridging Visualization and Optimization: Multimodal Large Language Models on Graph-Structured Combinatorial Optimization [56.17811386955609]
  Graph-structured challenges are inherently difficult due to their nonlinear and intricate nature. In this study, we propose transforming graphs into images to preserve their higher-order structural features accurately. By combining the innovative paradigm powered by multimodal large language models with simple search techniques, we aim to develop a novel and effective framework.
  arXiv  Detail & Related papers  (2025-01-21T08:28:10Z)
• Self-Adaptive Ising Machines for Constrained Optimization [0.4450107621124637]
  We propose a self-adaptive IM that shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. We benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
  arXiv  Detail & Related papers  (2025-01-09T05:02:50Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Encoding arbitrary Ising Hamiltonians on Spatial Photonic Ising Machines [0.0]
  We introduce and experimentally validate a SPIM instance that enables direct control over the full interaction matrix. We demonstrate the conformity of the experimentally measured Ising energy with the theoretically expected values and then proceed to solve both the unweighted and weighted graph problems. Our approach greatly expands the applicability of SPIMs for real-world applications without sacrificing any of the inherent advantages of the system.
  arXiv  Detail & Related papers  (2024-07-12T10:54:07Z)
• Efficient Computation Using Spatial-Photonic Ising Machines: Utilizing Low-Rank and Circulant Matrix Constraints [0.0]
  spatial-photonic Ising machines (SPIMs) address computationally intensive Ising problems that employ low-rank and circulant coupling matrices. Our results indicate that the performance of SPIMs is critically affected by the rank and precision of the coupling matrices.
  arXiv  Detail & Related papers  (2024-06-03T15:03:31Z)
• L0-regularized compressed sensing with Mean-field Coherent Ising Machines [0.8292466835099597]
  We propose the mean-field CIM model, which is a physics-inspired solver without quantum noise. Our results indicate that the proposed model has similar performance to physically accurate SDEs in both artificial and magnetic resonance imaging data.
  arXiv  Detail & Related papers  (2024-05-01T07:43:26Z)
• Learning Controllable Adaptive Simulation for Multi-resolution Physics [86.8993558124143]
  We introduce Learning controllable Adaptive simulation for Multi-resolution Physics (LAMP) as the first full deep learning-based surrogate model. LAMP consists of a Graph Neural Network (GNN) for learning the forward evolution, and a GNN-based actor-critic for learning the policy of spatial refinement and coarsening. We demonstrate that our LAMP outperforms state-of-the-art deep learning surrogate models, and can adaptively trade-off computation to improve long-term prediction error.
  arXiv  Detail & Related papers  (2023-05-01T23:20:27Z)
• Conservative Objective Models for Effective Offline Model-Based Optimization [78.19085445065845]
  Computational design problems arise in a number of settings, from synthetic biology to computer architectures. We propose a method that learns a model of the objective function that lower bounds the actual value of the ground-truth objective on out-of-distribution inputs. COMs are simple to implement and outperform a number of existing methods on a wide range of MBO problems.
  arXiv  Detail & Related papers  (2021-07-14T17:55:28Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Complexity continuum within Ising formulation of NP problems [0.0]
  Minimisation of the Ising Hamiltonian is known to be NP-hard problem for certain interaction matrix classes. We propose to identify computationally simple instances with an optimisation simplicity criterion' Such simplicity can be found for a wide range of models from spin glasses to k-regular maximum cut problems.
  arXiv  Detail & Related papers  (2020-08-02T11:36:38Z)
• A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encoding [57.1077544780653]
  We introduce a general framework for designing and training neural network layers whose forward passes can be interpreted as solving non-smooth convex optimization problems. We focus on convex games, solved by local agents represented by the nodes of a graph and interacting through regularization functions. This approach is appealing for solving imaging problems, as it allows the use of classical image priors within deep models that are trainable end to end.
  arXiv  Detail & Related papers  (2020-06-26T08:34:54Z)

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.