A Conservation Law Method in Optimization
Bin Shi








A Conservation Law Method in Optimization
    Bin Shi
    December 30, 2023
=========================================


We propose some algorithms to find local minima in nonconvex optimization and to obtain global minima in some degree from the Newton Second Law without friction. With the key observation of the velocity observable and controllable in the motion, the algorithms simulate the Newton Second Law without friction based on symplectic Euler scheme. From the intuitive analysis of analytical solution, we give a theoretical analysis for the high-speed convergence in the algorithm proposed. Finally, we propose the experiments for strongly convex function, non-strongly convex function and nonconvex function in high-dimension.








§ INTRODUCTION




Non-convex optimization is the dominating algorithmic technique behind many state-of-art results in machine learning, computer vision, natural language processing and reinforcement learning. Finding a global minimizer of a non-convex optimization problem is NP-hard. Instead, the local search method become increasingly important, which is based on the method from convex optimization problem. Formally, the problem of unconstrained  optimization is stated in general terms as that of finding the minimum value that a function attains over Euclidean space, i.e.

    min_x ∈ℝ^nf(x).

Numerous methods and algorithms have been proposed to solve the minimization problem, notably gradient methods, Newton's methods, trust-region method, ellipsoid method  and interior-point method <cit.>.

First-order optimization algorithms are the most popular algorithms to perform optimization and by far the most common way to optimize neural networks, since the second-order information obtained is supremely expensive.  The simplest and earliest method for minimizing a convex function f is the gradient method, i.e.,

    {    x_k+1 = x_k - h ∇ f(x_k)
       Any Initial Point:   x_0.
    .

There are two significant improvements of the gradient method to speed up the convergence. One is the momentum method, named as Polyak heavy ball method, first proposed in <cit.>, i.e.,

    {    x_k+1 = x_k - h ∇ f(x_k) + γ_k (x_k - x_k-1)
       Any Initial Point:   x_0.
    .

Let κ be the condition number, which is the ratio of the smallest eigenvalue and the largest eigenvalue of Hessian at local minima. The momentum method speed up the local convergence rate from 1 - 2κ to 1 - 2√(κ). The other is the notorious Nesterov's accelerated gradient method, first proposed in <cit.> and an improved version <cit.>, i.e.

    {    y_k+1 = x_k - 1/L∇ f(x_k) 
        x_k+1 = x_k + γ_k(x_k+1 - x_k)
       Any Initial Point:   x_0 = y_0.

where the parameter is set as 

    γ_k = α_k (1 - α_k)/α_k^2 + α_k+1  and  α_k+1^2 = (1 - α_k+1)α_k^2 + α_k+1κ.

The scheme devised by Nesterov does not only own the property of the local convergence for strongly convex function, but also is the global convergence scheme, from 1 - 2κ to 1 - √(κ) for strongly convex function and from 𝒪(1/n) to 𝒪(1/n^2) for non-strongly convex function.

Although there is the complex algebraic trick in Nesterov's accelerated gradient method, the three methods above can be considered from continuous-time limits <cit.> to obtain physical intuition. In other words, the three methods can be regarded as the discrete scheme for solving the ODE. The gradient method (<ref>) is correspondent to 

    {   ẋ = - ∇ f(x_k)
        x(0)= x_0,
    .

and the momentum method and Nesterov accelerated gradient method are correspondent to 

    {   ẍ + γ_tẋ + ∇ f(x) = 0
        x(0)= x_0,  ẋ(0) =0,
    .

the difference of which are the setting of the friction parameter γ_t. There are two significant intuitive physical meaning in the two ODEs (<ref>) and (<ref>). The ODE (<ref>) is the governing equation for potential flow, a correspondent phenomena of waterfall from the height along the gradient direction. The infinitesimal generalization is correspondent to heat conduction in nature. Hence, the gradient method (<ref>) is viewed as the implement in computer or optimization simulating the phenomena in the real nature. The ODE (<ref>) is the governing equation for the heavy ball motion with friction.  The infinitesimal generalization is correspondent to chord vibration in nature.  Hence, the momentum method (<ref>) and the Nesterov's accelerated gradient method (<ref>) are viewed as the update version implement in computer or optimization by use of setting the friction force parameter γ_t.
     
Furthermore, we can view the three methods above as the thought for dissipating energy implemented in the computer. The unknown objective function in black box model can be viewed as the potential energy.  Hence, the initial energy is from the potential function f(x_0) at any position x_0 to the minimization value f(x^⋆) at the position x^⋆. The total energy is combined with the kinetic energy and the potential energy. The key observation in this paper is that we find the kinetic energy, or the velocity, is observable and controllable variable in the optimization process. In other words, we can compare the velocities in every step to look for local minimum in the computational process or re-set them to zero to arrive to artificially dissipate energy. 

Let us introduce firstly the governing motion equation in a conservation force field, that we use in this paper, for comparison as below, 

    {   ẍ = - ∇ f(x) 
         x(0)= x_0,  ẋ(0) =0. 
    .

The concept of phase space, developed in the late 19th century, usually consists of all possible values of position and momentum variables. The governing motion equation in a conservation force field (<ref>) can be rewritten as

    {   ẋ = v 
       v̇ = -∇ f(x) 
         x(0)= x_0,  v(0) =0 .
    .


In this paper, we implement our discrete strategy with the utility of the observability and controllability of the velocity, or the kinetic energy, as well as artificially dissipating energy for two directions as below,   


  * To look for local minima in non-convex function or global minima in convex function, the kinetic energy, or the norm of the velocity, is compared with that in the previous step,  it will be re-set to zero until it becomes larger no longer. 


  * To look for global minima in non-convex function, an initial larger velocity v(0) = v_0 is implemented at the any initial position x(0) = x_0. A ball is implemented with (<ref>), the local maximum of the kinetic energy  is recorded to discern how many local minima exists along the trajectory. Then implementing the strategy above to find the minimum of all the local minima.

For implementing our thought in practice, we utilize the scheme in the numerical method for Hamiltonian system, the symplectic Euler method. We remark that a more accuracy version is the Störmer-Verlet method for practice. 




 §.§ An Analytical Demonstration For Intuition

For a simple 1-D function with ill-conditioned Hessian, f(x) = 1/200 x^2 with the initial position at x_0 = 1000.  The solution and the function value along the solution for (<ref>) are given by

 x(t) = x_0e^-1/100t      

 f(x(t)) = 1/200x_0^2 e^-1/50t. 

The solution and the function value along the solution for (<ref>) with the optimal friction parameter γ_t = 1/5 are

 x(t) = x_0(1 + 1/10t )e^-1/10t      

 f(x(t)) = 1/200x_0^2 (1 + 1/10t )^2 e^-1/5t.

The solution and the function value along the solution for (<ref>) are

 x(t) = x_0cos(1/10t)  and  v(t) = x_0sin(1/10t)     

 f(x(t)) = 1/200x_0^2 cos^2(1/10t)

stop at the point that |v| arrive maximum. Combined with (<ref>), (<ref>) and (<ref>) with stop at the point that |v| arrive maximum, the function value approximating f(x^⋆) are shown as below,

From the analytical solution for local convex quadratic function with maximum eigenvalue L and minimum eigenvalue μ, in general, the step size by 1/√(L) for momentum method and Nesterov accelerated gradient method, hence the simple estimate for iterative times is approximately 

    n ∼π/2√(L/μ).
 
hence, the iterative times n is proportional to the reciprocal of the square root of minimal eigenvalue √(μ), which is essentially different from the convergence rate of the gradient method and momentum method.

The rest of the paper is organized as follows. Section <ref> summarize relevant existing works. In Section <ref>, we propose the artificially dissipating energy algorithm, energy conservation algorithm and the combined algorithm based on the symplectic Euler scheme, and remark a second-order scheme — the Störmer-Verlet scheme . In Section <ref>, we propose the locally theoretical analysis for High-Speed converegnce. In section <ref>, we propose the experimental result for the proposed algorithms on strongly convex function, non-strongly convex function and nonconvex function in high-dimension. Section <ref> proposes some perspective view for the proposed algorithms and two adventurous ideas based on the evolution of Newton Second Law — fluid and quantum.


































§ RELATED WORK




The history of gradient method for convex optimization can be back to the time of Euler and Lagrange. However, since it is relatively cheaper to only calculate for first-order information, this simplest and earliest method is still active in machine learning and nonconvex optimization, such as the recent work <cit.>. The natural speedup algorithms are the momentum method first proposed in <cit.> and Nesterov accelerated gradient method first proposed in <cit.> and an improved version <cit.>. A acceleration algorithm similar as Nesterov accelerated gradient method, named as FISTA, is designed to solve composition problems <cit.>.  A related comprehensive work is proposed in <cit.>.  

The original momentum method, named as Polyak heavy ball method, is from the view of ODE in <cit.>, which contains extremely rich physical intuitive ideas and mathematical theory. An extremely important work in application on machine learning is the backpropagation learning with momentum <cit.>. Based on the thought of ODE, a lot of understanding and application on the momentum method and Nesterov accelerated gradient methods have been proposed. In <cit.>, a well-designed random initialization with momentum parameter algorithm is proposed to train both DNNs and RNNs. A seminal deep insight from ODE to understand the intuition behind Nesterov scheme is proposed in <cit.>. The understanding for momentum method based on the variation perspective is proposed on <cit.>, and the understanding from Lyaponuv analysis is proposed in <cit.>.  From the stability theorem of ODE, the gradient method always converges to local minima in the sense of almost everywhere is proposed in <cit.>.  Analyzing and designing iterative optimization algorithms built on integral quadratic constraints from robust control theory is proposed in <cit.>. 

Actually the “high momentum” phenomenon has been firstly observed in <cit.> for a restarting adaptive accelerating algorithm, and also the restarting scheme is proposed by <cit.>. However, both works above utilize restarting scheme for an auxiliary tool to accelerate the algorithm based on friction. With the concept of phase space in mechanics, we observe that the kinetic energy, or velocity, is controllable and utilizable parameter to find the local minima. Without friction term, we can still find the local minima only by the velocity parameter.  Based on this view, the algorithm is proposed very easy to practice and propose the theoretical analysis. Meanwhile, the thought can be generalized to nonconvex optimization to detect local minima along the trajectory of the particle. 


 

For heavy ball method, or momentum method, the seminal theoretical paper is from <cit.>, which contains extremely rich ideas. In application in machine learning, there is also a extremely important work on backpropagation learning <cit.>. Some recent work on moment method for optimization algorithm based Bregman divergence and variational method have appeared <cit.>. For Non-strongly convex optimization,  a surprising and extremely mysterious scheme, named as Nesterov accelerated gradient method, is first proposed in <cit.> andSome recent works <cit.> introduce the geometrical perspective. 

The most popular technique for the accelerated method comes from the ODE as well as the mechanic background. The differential equation is a traditional subfield of mathematics. However, with the development of machine learning, this study can be seen as an extension of classical mathematical fields such as dynamical systems and differential equations among others, but with the important addition of the notion of computational efficiency.  Some recent work <cit.>