Accelerating Optimization via Differentiable Stopping Time

A common approach for accelerating optimization algorithms is to minimize the loss achieved in a fixed time, which enables a differentiable framework with respect to the algorithm's hyperparameters. In contrast, the complementary objective of minimizing the time to reach a target loss is traditionally considered non-differentiable. To address this limitation, we propose a differentiable discrete stopping time and theoretically justify it based on its connection to continuous differential equations. We design an efficient algorithm to compute its sensitivities, thereby enabling a new differentiable formulation for directly accelerating algorithms. We demonstrate its effectiveness in 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.

or non-smooth function of parameters, addressed only conceptually or via zeroth-order optimization methods [6].

To overcome this fundamental challenge and enable the direct, gradient-based optimization of convergence speed towards a target accuracy for iterative algorithms, this paper introduces the concept of differentiable stopping time. We propose a comprehensive framework that allows for the computation of sensitivities of the number of iterations required to reach a stopping criterion with respect to algorithm parameters. Our main contributions are summarized as follows:

• We formulate a new class of differentiable objectives for algorithm acceleration, aiming to directly minimize the number of iterations or computational time required to achieve a target performance. This is supported by a theoretical framework that establishes the differentiability of discrete stopping time via a connection between discrete-time iterative algorithms and continuous-time dynamics, leveraging tools from the theory of continuous stopping times.

• We develop a memory-efficient and scalable algorithm for computing sensitivities of discrete stopping time, enabling effective backpropagation through iterative procedures. Our experimental results validate the accuracy and efficiency of the proposed method, particularly in high-dimensional settings, and show clear advantages over approaches relying on exact ordinary differential equation solvers.

• We demonstrate the applicability of differentiable stopping time in practical applications, including L2O and the online adaptation of optimizer hyperparameters. These case studies show that differentiable stopping time can be seamlessly integrated into existing frameworks, and our empirical evaluations suggest that it provides a principled and effective lens for understanding and improving algorithmic acceleration. 1.1 Related Work ODE Perspective of Accelerated Methods. Offering a continuous-time view of optimization algorithms, this perspective provides both theoretical insights and practical improvements. The foundational work [7] established a connection between Nesterov's accelerated gradient method and a second-order ordinary differential equation, introducing a dynamical systems viewpoint for understanding acceleration. Building on this, acceleration phenomena have been analyzed through high-resolution differential equations [8], revealing deeper insights into optimization dynamics. The symplectic discretization of these high-resolution ODEs [9] has also been explored, leading to practical acceleration techniques with theoretical guarantees. A Lyapunov analysis of accelerated gradient methods was developed in [10], extending the framework to stochastic settings. For optimization on parametric manifolds, accelerated natural gradient descent methods have been formulated in [11], based on the ODE perspective. Implicit Differentiation in Deep Learning. This technique enables efficient gradient computation through complex optimization procedures. A modular framework for implicit differentiation was presented in [12], unifying existing approaches and introducing new methods for optimization problems. In non-smooth settings, [13] developed a robust theory of nonsmooth implicit differentiation with applications to machine learning and optimization. Implicit differentiation has also been applied to train iterative refinement algorithms [14], treating object representations as fixed points. For non-smooth convex learning problems, fast hyperparameter selection methods have been developed using implicit differentiation [15]. Training techniques for implicit models that match or surpass traditional approaches have been explored in [16], leveraging implicit differentiation. Implicit bias in overparameterized bilevel optimization has been investigated in [17], providing insights into the behavior of implicit differentiation in high-dimensional settings. In optimal control, implicit differentiation for learning problems has been revisited in [18], where new methods for differentiating optimization-b