Workshop: Theory towards Brains, Machines and MindsWorkshop: Theory towards Brains, Machines and Minds

Title: Non-attracting dynamics for solving combinatorial optimization problems using neuromorphic systems implemented on specialized hardware

Leleu Timothee, Institute of Industrial Science, The University of Tokyo


Neural networks applied to combinatorial optimization problems have long been thought to be outperformed by other problem-specific heuristics despite the early excitement produced by the Hopfield-Tank neural networks. With the recent success of neural network approaches to machine learning and the development of novel unconventional hardware that simulate scalable neuromorphic computing, it is time to reconsider the use of neural networks for solving the hard combinatorial optimization problems. In recent years, numerous novel specialized hardware have been proposed for solving the Ising problem[1]. Many of these Ising machines share in fact various common features with neural networks, with equivalences that can be drawn based on mean-field approximations. Although these Ising machines exhibit promising performance in terms of computational speed and energy efficiency, they suffer from the same kind of limitations that have hindered the Hopfield neural networks and mean-field annealing algorithms. In this talk, we will introduce a few techniques[2,3] that allow overcoming some of these limitations, related to the escape from local minima and the taking into account of constraints. We will show that the implementation of these techniques on “neuromorphic” hardware can enable them to significantly outperform classical state-of-the-art solvers for some specific benchmark. Lastly, we will discuss future trends, such as automatic parameter tuning, that allow to further broaden the range of applicability of the neural network approach to combinatorial optimization.


References:
[1] Yamamoto Y, Aihara K, Leleu T, Kawarabayashi K, Kako S, Fejer M, Inoue K, and Takesue H, Coherent Ising machines : optical neural networks operating at the quantum limit, Nature Partner Journal: Quantum Information, 3(1), 49, 2017.
[2] Leleu T, Yamamoto Y, Utsunomiya S, and Aihara K, Combinatorial optimization using dynamical phase transitions in driven-dissipative systems, Physical Review E, 95(2), 022118, 2017.
[3] Leleu T, Yamamoto Y, McMahon PL, and Aihara K, Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity. Physical Review Letters, 122, 040607, 2019.