Accelerating Optimization via Differentiable Stopping Time
Zhonglin Xie, Yiman Fong, Haoran Yuan, Zaiwen Wen
Optimization is an important module of modern machine learning applications. Tremendous efforts have been made to accelerate optimization algorithms. A common formulation is achieving a lower loss at a given time. This enables a differentiable framework with respect to the algorithm hyperparameters. In contrast, its dual, minimizing the time to reach a target loss, is believed to be non-differentiable, as the time is not differentiable. As a result, it usually serves as a conceptual framework or is optimized using zero-th order methods. To address this limitation, we propose a differentiable stopping time (DST) and theoretically justify it based on differential equations. An efficient algorithm is designed to backpropagate through DST. As a result, the proposed DST enables a new differentiable formulation for accelerating algorithms. We further discuss its applications, such as online hyperparameter tuning and learning to optimize. Our proposed methods show superior performance in comprehensive experiments across various problems, which confirms their effectiveness.