Abstract
We consider the differentiation of the value function for parametric optimization problems. Such problems are ubiquitous in Machine Learning applications such as structured support vector machines, matrix factorization and min-min or minimax problems in general. Existing approaches for computing the derivative rely on strong assumptions of the parametric function. Therefore, in several scenarios there is no theoretical evidence that a given algorithmic differentiation strategy computes the true gradient information of the value function. We leverage a well known result from convex duality theory to relax the conditions and to derive convergence rates of the derivative approximation for several classes of parametric optimization problems in Machine Learning. We demonstrate the versatility of our approach in several experiments, including non-smooth parametric functions. Even in settings where other approaches are applicable, our duality based strategy shows a favorable performance.
Introduction: The Role of Value Functions in ML
In many Machine Learning tasks, we encounter problems where the output of a component is the optimal value of an internal optimization problem. This "best possible result," parameterized by some input $u$, is known as the value function $p(u)$. Such structures are central to bilevel optimization, structured support vector machines, and "optimization layers" in modern neural network architectures.
The Smoothness Trap
The standard approach to computing the gradient $\nabla p(u)$ involves differentiating through the solution path using the Implicit Function Theorem or Automatic Differentiation (AD). However, these methods rely on strong assumptions of smoothness. When the objective function is non-smooth—as is common with $L_1$ regularization or SVMs—or when the optimal solution resides on a constraint boundary, these traditional methods often fail, yielding zero or undefined gradients.
The Dual Gradient Estimator (DG)
To address these limitations, the proposed Dual Gradient Estimator (DG) shifts the focus from the primal solution path to the dual problem. By leveraging convex duality theory, we transform the problem of differentiating the primal value function into solving a dual optimization problem.
Key advantages of this approach include:
- Handling Non-Smoothness: The subdifferential of the value function is exactly the set of solutions to the dual problem, which remains well-defined even when the primal is non-smooth.
- Memory Efficiency: Unlike AD, which requires storing the entire computational graph of the solver, the DG method only requires the final result of the dual optimization.
- Algorithmic Flexibility: Any standard convex optimization tool (e.g., FISTA, PDHG) can be used to solve the dual problem and thus estimate the gradient.
Experimental Results
The DG method was evaluated against four synthetic problems ($f_1$ to $f_4$) designed to test various mathematical edge cases, including non-smoothness and non-attainment of minima.
Results demonstrate that while Automatic Differentiation is efficient for smooth problems, it becomes erratic or fails entirely on non-smooth tasks. In contrast, the Dual Gradient Estimator converged reliably in every scenario. Furthermore, the authors proved that the DG method inherits the convergence rates of the underlying dual solver, providing strong theoretical guarantees for its performance.
Conclusion and Future Work
The Dual Gradient Estimator provides a robust, mathematically sound framework for differentiating value functions in the presence of non-smoothness. While currently limited to jointly convex problems, future work will explore extensions to non-convex "proximal-friendly" settings and integration into large-scale deep learning pipelines where memory constraints are a primary concern.
Summary updated