2nd-order Updates with 1st-order Complexity
This addresses the challenge of high computational cost in second-order methods for optimization and numerical problems, offering a more efficient alternative, though it appears incremental as it builds on existing physics-based approximations.
The paper tackles the problem of efficiently computing second-order information for numerical approximations by developing an algorithm (VA-Flow) that achieves this with O(N) complexity, applied to inverse kinematics and gradient descent, showing fast and robust performance with smooth behavior near singularities in IK and good results in GD for polynomial-like cost functions.
It has long been a goal to efficiently compute and use second order information on a function ($f$) to assist in numerical approximations. Here it is shown how, using only basic physics and a numerical approximation, such information can be accurately obtained at a cost of ${\cal O}(N)$ complexity, where $N$ is the dimensionality of the parameter space of $f$. In this paper, an algorithm ({\em VA-Flow}) is developed to exploit this second order information, and pseudocode is presented. It is applied to two classes of problems, that of inverse kinematics (IK) and gradient descent (GD). In the IK application, the algorithm is fast and robust, and is shown to lead to smooth behavior even near singularities. For GD the algorithm also works very well, provided the cost function is locally well-described by a polynomial.