Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent
This work offers a theoretical foundation for a novel optimization algorithm that could dramatically accelerate training in machine learning, though it is currently limited to one-dimensional settings.
The paper provides the first analytical study of Energy Conserving Descent (ECD) for non-convex optimization, proving that both stochastic ECD and its quantum analog achieve exponential speedup over gradient descent baselines for positive double-well objectives. For tall barriers, the quantum version further outperforms the classical stochastic ECD.
The Energy Conserving Descent (ECD) algorithm was recently proposed (De Luca & Silverstein, 2022) as a global non-convex optimization method. Unlike gradient descent, appropriately configured ECD dynamics escape strict local minima and converge to a global minimum, making it appealing for machine learning optimization. We present the first analytical study of ECD, focusing on the one-dimensional setting for this first installment. We formalize a stochastic ECD dynamics (sECD) with energy-preserving noise, as well as a quantum analog of the ECD Hamiltonian (qECD), providing the foundation for a quantum algorithm through Hamiltonian simulation. For positive double-well objectives, we compute the expected hitting time from a local to the global minimum. We prove that both sECD and qECD yield exponential speedup over respective gradient descent baselines--stochastic gradient descent and its quantization. For objectives with tall barriers, qECD achieves a further speedup over sECD.