Training Machine Learning Models with Ising Machines

Authors: sayantan  pramanik
kaumudibikash  goswami
sourav  chatterjee
m girish chandra
tata consultancy services
Venue: NeurIPS_cc_2024_Workshop_MLNCP
Published: 2024-09-12 03:59:54

Abstract: In this study, we use Ising machines to help train machine learning models by employing a suitably tailored version of opto-electronic oscillator-based coherent Ising machines with clipped transfer functions to perform trust region-based optimisation with box constraints. To achieve this, we modify such Ising machines by including non-symmetric coupling and linear terms, modulating the noise, and introducing compatibility with convex-projections. The convergence of this method, dubbed $i$Trust has also been established analytically. We validate our theoretical result by using $i$Trust to optimise the parameters in a quantum machine learning model in a binary classification task. The proposed approach achieves similar performance to other second-order trust-region based methods while having a lower computational complexity. Our work serves as a novel application of Ising machines and allows for a unconstrained optimisation problems to be performed on energy-efficient computers with non von Neumann architectures.

Main paper: 
 introduction: 
 Traditionally, the utility of Ising machines has been limited to solving combinatorial optimisation problems [1, 2, 3] with polynomial resources by mapping them onto ground-state search problems of the Ising model [4, 5] , using them as machine learning models [6, 7, 8, 9] , or modelling optical neural networks [10] . While a variety of approaches for realizing this model of artificial spins network has been demonstrated in literature [11, 12, 13] , the approach of employing opto-electronic-oscillators (OEOs) for building a coherent Ising machine (CIM) [14] has been lately gaining a lot of attention because of its cost-effective implementation, ambient operation, and scope for miniaturization [15] .In this work, we present a novel application of OEO-CIMs to unconstrained optimisation, and provide analytical proof of convergence of Ising machines to perform trust region-based optimization [16, 17, 18] . We refer to this technique as iTrust (Ising machines for trust-region optimisation). Along with the other aforementioned benefits of OEO-CIMs, the main advantage of iTrust stems from avoiding matrix-inversion and Cholesky decomposition of the Hessian. This opens up a new avenue of applications where the Ising machines may be used to optimise any parameterised, unconstrained objective function f : R n → R. We denote the parameters of the objective function f (•) with the vector θ ∈ R n . Particularly, using iTrust, we aim to find the optimal point θ * that minimises the objective function: Problem 1.f (θ * ) := minEQUATIONwhere θ * satisfies second-order optimality conditions [16] , under the following assumption [16] :Assumption 1. If θ (0)is the starting point of an iterative algorithm, then the functionf (•) is bounded below on the level set S = {θ | f (θ) ≤ f (θ (0) )} by some value f * , such that f * ≤ f (θ) ∀ θ ∈ S. Further, f is twice continuously differentiable on S.This allows us to use iTrust as an optimisation procedure for training models in traditional machine learning (ML) [19, 20, 21] , quantum ML (QML) [22, 23, 24] , quantum-inspired ML (QiML) [25] , and variational quantum algorithmic (VQA) [26] models. Such optimisation problems are conventionally tackled by digital computers based on von Neumann architecture, leading to substantial memory and energy consumption, also known as 'von Neumann bottleneck' [27] . In contrast, since iTrust is based on Ising machines, it may potentially lead to more energy-efficient protocols [28, 29, 1] with an increased clock-speed [30] . This paper (along with a contemporary studies in [31] and [32] -which use analog thermodynamic computers to perform natural gradient descent, and quantum linear solvers [33, 34, 35] to calculate the Newton-update, respectively) hopes to open up new avenues of research where benefits of new-compute paradigms are reaped not only by using them as ML models, but also by employing them to aid in the training of models.The remainder of this extended abstract is organised as follows: we propose essential modifications to a specific type of CIMs to make them compatible for trust-region optimisation in Section 2, and analytically examine its performance on convex objective functions with bounded gradients, and on smooth, locally-Polyak-Łojasiewicz (PŁ) [36] functions in Section 2.1. We describe the proposed algorithm iTrust in Section 3, before showing its convergence to second-order optimal solutions of Problem 1 in Theorem 3. We then proceed to demonstrate its efficacy through numerical experiments in Section 4 Conclusions and future outlook are in Section 5. 
economical coherent ising machine: 
 For iTrust, we consider the poor man's CIM introduced in [14] with clipped nonlinearity [37] , and refer to it as the Economical CIM (ECIM). It is then modified to find ε-suboptimal solutions of the following problem with J as the coupling-matrix, and h as the external field:EQUATIONInspired by an earlier work [38] , our modifications include setting α = 1 and viewing β as the stepsize in equation 8 of [37] . The variance of the injected noise is modulated, and varying step-sizes β k are considered to facilitate better convergence. Provisions for accommodating non-symmetric coupling and linear terms are also made without relying on ancillary spins [39, 15] . The clipping voltage is set to ±∆, and finally, the ECIM is made compatible with the definition of projection to the convex box C = [-∆, ∆] n . As a result, the iterative update equation of the modified ECIM is given by:EQUATIONwhere ζ (k) ∼ N (0, σ 2 I), and Π C (•) is the projection operator to C.In this section, we present the convergence-results of the modified ECIM for convex or locally-Polyak-Łojasiewicz (PŁ) E(•). While PŁ may not be as popular a condition as convexity, it is definitely more general. For instance, PŁ (or PŁ * ) functions have been shown to include neural networks with ReLU activations and quadratic losses where convexity cannot be assumed [40, 41, 42] . Further, [36] argues and proves that among Lipschitz-smooth functions such as strongly convex, essentially strongly convex, weakly strongly convex, and functions obeying the restricted secant inequality, PŁ functions entail the weakest assumptions. A more detailed exposition on the relations and implications between function-classes may be found in Theorem 2 of [36] . Furthermore, it is known that PŁ functions obey the Polyak-Łojasiewicz inequality. We, however, require the objective function to be PŁ locally on the constraint set C, i.e., for some µ > 0 and for all s ∈ C,EQUATIONWe now state the convergence results through the following informal Theorems. Their formal statements and proofs have not been included in adherence to the page-limits. Theorem 1 (Informal). For convex E(•) with bounded gradients, the ECIM in equation (3) finds an ε-suboptimal solution to Problem 2 in C with fixed step-sizes in O( 1 /ε 2 ) iterations. With diminishing step-sizes such that∞ k=0 β k = ∞ and ∞ k=0 β 2 k < ∞, lim k→∞ (E(s (k) ) -E * ) = 0, where E * = min s∈C E(s). Theorem 2 (Informal). For smooth E(•) that obeys the PŁ inequality locally, the ECIM in equation (3) finds an ε-suboptimal solution to Problem 2 in C with fixed step-sizes in O (ln ( 1 /ε)) iterations.If s is the output of the ECIM, then the above results may be unified into the following equation for some constant c ∈ (0, 1], as suggested in [18] :-E(s) ≥ c|E(s * )|.(5) 
itrust: 
 Very briefly, the update p * (t) to θ (t) at the iteration t of a Newton-like trust-region method is found from the minimiser of: Problem 3.EQUATIONwhere ∇f (θ (t) ) and H(θ (t) ) are the gradient and Hessian of f at θ (t) , respectively. If the radius of the trust-region at iteration t is δ t , then the feasible set, which is a ball 1 , is represented withB t = {z ∈ R n | ||z -θ (t) || 2 ≤ δ t }.A major disadvantage of using the method proposed in Algorithm 3.2 stated in [18] to find p * (t) is the repeated requirement for Cholesky decomposition and inversion of the Hessian, both of which are in O(n 3 ). This becomes prohibitively expensive for problems where n is large, for instance machine learning models with millions of parameters. We aim to alleviate this problem by using the enhanced ECIM to find p * (t) . We achieve this by exploiting the structural similarity Problems 2 and 3. Specifically, at each iteration t, J is set to H(θ (t) ), h to ∇f (θ (t) ), and ∆ to δ t . Here, the importance of the inclusion of linear terms in the Ising machine becomes clear, without which the gradient ∇E(s (k) ) could not have been provided to the ECIM without additional overheads in the form of ancillary spins [38, 39] .Remark 1. It is interesting to note that if the coupling matrix J (t) is positive semidefinite at the iteration t, then as per the definition of convexity, the objective function of the trust-region subproblem is convex. Additionally, since the coupling matrix is equal to the Hessian H(θ (t) ), this also implies that the objective function f is convex in the region around θ (t) . Thus, in a convex region of the original problem, the result in Theorem 1 becomes applicable for the ECIM.Further, we distinguish between the minimisers of E t (s) and m t (p) on the sets C t and B t by denoting them with s * (t) and p * (t) , respectively. Remark 2. We would like to emphasize that the box C t and the ball B t share a common centre θ (t) , and by design, the side-length of the box is set equal to the diameter of the ball at each iteration. Thus, the ball is contained completely within the box: B t ⊂ C t 2 . Now, since the objective function 1 To avoid situations where the optimisation Problem 1 has a poor scaling with respect to the decision variables θ, elliptical trust regions may be employed by replacing the constraint of Problem 3 with:EQUATIONwhere D = diag(d1, . . . , dn) with di ≥ 0. The elements di are adjusted according to the sensitivity of f (•) to θi: if f (•) varies highly with a small change in θi, then a large value of di is used; and vice versa [16] . 2 Differential scaling with respect to different components of the decision variables may be handled by setting individual ∆i for each coordinate θi such that the elliptical trust-region from equation (7) lies within the box defined by the ∆is.of the Problems 3 and 2 are identical, and the constraint set of the former is contained in that of the latter, we have:EQUATIONThis means that if the ECIM and the Algorithm 3.14 in [18] can both reach near-optimal solutions of their respective optimisation problems, then the objective value obtained by the ECIM is guaranteed to be better. This results in a higher reduction in the value of f (θ) at each iteration.We name this technique of using the ECIM for trust-region optimisation as iTrust. The workflow for iTrust has been portrayed in Algorithm 1, which draws inspiration from, and is an amalgamation of, Algorithms 4.1 and 4.2 of [16] and [18] , respectively.Algorithm 1: i Trust input: initial point θ (0) ∈ R n ; maximum trust-region radius δ max > 0; initial radius δ 0 ∈ (0, δ max ]; thresholds on ρ t : 0 < µ < η < 1; radius-updation parameters γ 1 < 1 and γ 2 > 1; noise variance σ 2 ; sequence of step-sizes (β k ); and number of iterations T andK 1 begin 2 for t ∈ [T ] do 3 evaluate ∇f (θ (t) ) and H(θ (t) ); 4 J (t) ← H(θ (t) ); 5 h (t) ← ∇f (θ (t) ); 6 ∆ t ← δ t ; 7 initialise s (0) randomly in C t = [-∆ t , ∆ t ] n ; 8 for k ∈ [K] do 9 sample ζ (k) ∼ N (0, σ 2 I); s (k+1) = Π Ct s (k) -β k ∇E t (s (k) ) -ζ (k) ; end calculate ρ t = f (θ (t) +s (K) )-f (θ (t) ) Et(s (K) ) ; if ρ t < µ then δ t+1 = γ 1 δ t ; continue; else if ρ t > (1 -µ) and ||s (K) || ∞ = δ t then δ t+1 = min(γ 2 δ t , δ max ); else δ t+1 = δ t ; end end if ρ t > η then θ (t+1) = θ (t) + s (K) ; else θ (t+1) = θ (t) ; end end return θ (T ) 30 endWe claim that this technique of employing ECIMs to solve the subproblem of trust-region methods converges (or tends to converge to) second-order optimal solutions of Problem 1 in S. This claim is formalised in the form of the following theorem [16, 18] , the proof of which has been omitted for brevity:Theorem 3 (Convergence of iTrust). Let assumption 1 be true, and let (θ (t) ) be the sequence of iterates generated by Algorithm 1 such that equation ( 5) is satisfied at each iteration. Then we have that:lim t→∞ ||∇f (θ (t) )|| 2 = 0. (9)Moreover, if S is compact, the either Algorithm 1 terminates at a point θ (T ) ∈ S where ∇f (θ (T ) ) = 0 and H(θ (T ) ) ≽ 0; or (θ (t) ) has a limit point θ * ∈ S such that ∇f (θ * ) = 0 and H(θ * ) ≽ 0. 
empirical evaluation: 
 In this section, we will demonstrate the efficacy fo the proposed method through numerical experiments. Specifically, iTrust will be applied to optimise the parameters in a quantum machine learning (QML) model that performs binary classification. QML is another instance where an alternatecompute paradigm is used to enhance machine learning through the introduction of quantum models as hypothesis functions that are non-trivial to simulate classically. QML models have been found to provide advantages in laboratory setting in terms of the number of parameters [43] , the volume of training data required [44] , and the number of iterations/epochs the models are trained for [45] . Nevertheless, in recent times, the use of variational models [26] for QML has garnered some criticism that questions their advantage [46] , especially due to the presence of barren plateaus [47, 48] and classical simulablity [49, 50] . However, proving a quantum-advantage in ML is far from the scope of this study, and neither does the iTrust algorithm alleviate the issues of barren plateaus or classical simulability in QML.Here, we aim to enhance the training of a small QML model to perform classification of the Iris dataset [51] . Since our focus is only on facilitating the training of models and not on their generalisability, only the training error at each iteration will be observed and reported as a measure of the performance of iTrust. The Iris dataset consists of four floral-features that may be used to categorise the flowers into three distinct classes, only the first two of which have been used here.The details of the quantum classification model are as follows: the four features were encoded into the states of four qubits using AngleEmbedding with a combination of Hadamard and R Z gates on each of the qubits. The features were first scaled to lie in the range of [0, π] before being passed as parameters into the R Z gates. Subsequently, three layers of the BasicEntanglingLayers ansatz from Pennylane [52] were appended to the circuit. The gates in the ansatz contain learnable parameters that were optimised. Finally, the expectation value of the Pauli-Z operator of the first qubit was measured. To calculate the empirical risk, the label for each datapoint was expressed as {±1} and the mean squared error was evaluated over the entire training set.The performance of iTrust was benchmarked against those of two other algorithms: gradient-descent (GD) which only uses the first-order derivatives; and Algorithm 3.2 from [18] -henceforth refereed to as More & Sorensen (MnS) -which like iTrust additionally requires the Hessian. Hence, GD requires only n evaluations of the quantum circuit at each iteration to estimate the gradient using the Parameter-Shift Rule [53] , while the second-order methods need 2n 2 + n circuit executions (2 for the gradients of each coordinate, 4 for each of the off-diagonal terms of the Hessian, and an additional 1 for the diagonal terms [54] ). Each of the algorithms was run for 100 iterations with the same initial point; and the experiment was repeated 10 times with different starting points sampled from a uniform distribution. A learning rate of 0.1 was used for GD. The hyperparameters for the second-order methods were: δ max = δ 0 = 0.5, η = 0.1, µ = η -0.001, γ 1 = 0.75, and γ 2 = 1.25.In addition, for iTrust, β was set to 0.5, with K = 10.The results of the aforementioned experiments have been reported in Figure 1 , where 1a shows the training loss at each iteration of training. The bold lines denote the mean, while the shaded regions indicate the standard deviation around the mean across the 10 experiments. It may be noted that the second-order methods outperformed the first-order one, as expected. Between Mns and iTrust, the former obtained a quicker reduction in loss at the initial iterations, with the latter catching up soon.As the training progressed, iTrust converged to a marginally lower value of loss compared to MnS and was found to be more stable, owing to its lower standard deviation.However, as detailed earlier, the second-order methods come at an increased overhead of calculation the Hessian for QML models. To check if this overhead eclipses the benefit of a reduced number of iterations, Figure 1b demonstrates the training loss against the total number of circuit-executions on a logarithmic scale. It is apparent from the plot that the second-order methods perform better towards the initial epochs and that the performance of MnS is slightly better than that of iTrust. But, one may recall that MnS requires Cholesky decomposition of the Hessian, whose complexity scales cubically with n. In comparison, iTrust forgoes this extra complexity while still retaining comparable performance.With the above results in mind, we propose a training schedule where iTrust is used in the initial phase to get a quick reduction in the training loss, followed by the utilisation of GD until convergence. This method is markedly distinct from the existing convention of starting with GD to reach a Newton's region, followed by the use of second-order Newton's method. It must be noted at this point that evaluating the performance against the number of circuit/function executions would be unnecessary for models where the gradients and Hessians may be calculated (or estimated) with similar complexity as the function execution. In such cases, the advantages of iTrust (and MnS) become more pronounced. 
conclusions and outlook: 
 In this paper, we introduced iTrust, an algorithm that leverages Ising machines for trust-region based optimisation. In doing so, we proposed necessary modifications to the Ising machine, and proved the feasibility and convergence of iTrust. The use of Ising machines provides the potential for higher clock-speeds and reduced energy-consumption compared to conventional approaches. We validated our theoretical results by introducing the iTrust as an optimiser in a simple quantum machine learning model to perform binary classification, and compared its performance against other first and second-order methods. We find that iTrust delivers similar performance to the other trust-region based method, but has the advantage of avoiding Hessian inversion and Cholesky decomposition. In this way, we extend the previously allowed class of optimisation problems using the Ising machines and open up the possibility of training machine learning models with new compute paradigms.Possible future directions may include generalising the ECIM for non-convex and non-PŁ objective functions. Variants of iTrust can also be constructed that are compatible with natural gradient descent [55, 56] , by replacing the Hessian with the Fisher Information Matrix. iTrust may be further augmented by zeroth order methods like SPSA [57] in scenarios where evaluation of the gradients, Hessian, and Fisher information matrix is computationally expensive [58] . Lastly, the advantages of the ECIM over noisy projected gradient descent for the subproblem minimisation in terms of the clock-speed and energy-consumption can also be examined. We hope that this paper opens up new avenues of research in the analytical and empirical exploration of new applications of Ising machines. 
 
 Appendix:  



Reviews: review: title: title: Recommendation for acceptance
main_review: main_review: The authors present an exciting set of results relating to applying a Coherent Ising Machine (CIM) to unconstrained optimization of convex and locally invex functions, particularly their algorithm can offload subprocedure of trust region optimization onto CIM without additional resource overhead. More specifically, they formulated economical CIM (ECIM), which suits the problem structure of convex and locally invex trust region optimization. ECIM can replace heavy operations of Cholesky decomposition and inversion of the Hessian in Newton-like trust region methods. In addition, they theoretically analyzed $\epsilon$ suboptimal convergence of the algorithm and evaluated numerically against existing trust region optimization algorithm and gradient descent using a quantum machine learning (QML) setup. CIM and Ising machines, in general, are active areas of research on their application, especially applications not related to existing approaches to combinatorial optimization, which will be of great interest. As such, the presented work is timely and will interest the community. The work was also thorough and well-written. As such, I recommend acceptance of this work to MLNCP. That being said, I have a small question and comment that, if addressed, would improve the work's readability.

1) In lines 84-85, the authors mentioned that the convergence results can be unified into Eq. (5) and referred to a citation [18]. The related result is Eq. (4.3) of [18], an assumption for the convergence of the trust region method. Other similar forms exist in Lem. 3.4 and 3.13 of [18] were confusing, although they require some conditions related to the trust region's boundary. Eq. (5) is mentioned for the assumption above, which comes from the minimization error being linear to the minimal energy. If this is correct, it would be great if the manuscript mentioned how it relates to the result and how it is introduced.
title: title: Review
main_review: main_review: This paper proposes to use a modified Ising machine for natively solving sub-optimization problems in trust-region-based optimization. The authors give theoretical guarantees on the convergence rate of the Ising machine, and propose the iTrust (Ising trust region optimization) scheme for training machine learning models. They also conduct numerical experiments to compare iTrust with traditional first-order and second-order methods on the task of training quantum machine learning models. Preliminary analysis of the resource consumption is also given. I agree with the authors that this work opens up a new direction in exploring the applications of Ising machines as optimizers in machine learning.

Strengths:

1. This paper gives careful theoretical analysis of the convergence rate of the proposed scheme, and accompanies it with numerical experiments.

2. The topic and proposed ideas fit the scope of this workshop very well.

3. Although the detailed proofs are omitted due to length limit, the results seem sound.

Weaknesses and comments: 

1. The author should polish the writing a bit, as there are many typos: line 24 Ising; line 74 Polyak-Lojasiewicz; line 161 was repeated; line 196 trust-region.

2. It would be great if the authors can discuss how the gradient and Hessian can be implemented on real Ising machines.

3. From the perspective of computational complexity, the authors mentioned that traditional second-order methods require matrix manipulation using $O(n^3)$ time. Can you explicitly state how does the complexity of using Ising machines scales with $n$? My understanding is that it's constant from Theorems 1 and 2. If so, it would be better to say it explicitly.

4. The execution overhead in gradient and Hessian estimation is unique to quantum machine learning. In classical machine learning, they can be achieved with constant overhead using back-propagation. So in comparison (e.g., Fig 1(b)), the authors may want to also compare on training classical neural networks, where the advantage of iTrust may be more prominent.