Differentiating the Value Function by using Convex Duality

Sheheryar Mehmood, Peter Ochs

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

In many machine learning applications, we encounter optimization layers defined by a value function $p(u) = \inf_x f(x, u)$, where $u$ represents parameters such as regularization weights or target vectors. Training models with these layers requires the gradient $\nabla p(u)$. Traditionally, this is handled via the Implicit Function Theorem or Automatic Differentiation (AD). However, these methods often require $f$ to be twice differentiable and can be extremely memory-intensive due to the need to store intermediate solver states. Furthermore, they struggle when the optimal solution $x^*(u)$ lies on a moving boundary. This paper introduces a novel "Dual Gradient Estimator" (DG) that leverages convex duality to bypass these smoothness and memory constraints.

Methodology: The Dual Gradient Estimator

The proposed method shifts the focus from the primal problem to its dual. For a jointly convex function $f(x, u)$, a fundamental result in convex analysis states that the subdifferential of the value function $p(u)$ is the set of solutions to a specific dual problem involving the convex conjugate $f^*$: $$\nabla p(u) = \arg \max_{y} \langle u, y \rangle - f^*(0, y)$$

This formulation offers several advantages:

  • Algorithmic Versatility: Any standard convex optimizer (e.g., ISTA, FISTA, or PDHG) can be used to solve the dual problem and obtain the gradient.
  • Memory Efficiency: Unlike AD, which "unrolls" the optimizer, the dual approach only requires the final state of the dual variable, significantly reducing the memory footprint.
  • Theoretical Robustness: The authors provide explicit convergence rates for the gradient estimate, even for non-smooth objectives where traditional methods might fail.

Experimental Evaluation

The effectiveness of the Dual Gradient estimator was evaluated using synthetic setups designed to probe specific mathematical challenges. These included toy 1D examples, high-dimensional linear regression variants (Huber loss, Elastic-net), and scaling tests across different parameter-to-variable ratios.

Value functions $p(u)$ and their cross-sections for various parametric optimization problems.

As shown in Figure 1, the value function $p(u)$ can exhibit various behaviors depending on the underlying objective $f(x, u)$. The dual method proves particularly stable in non-smooth settings (e.g., $L_1$ penalties), where standard analytic and implicit estimators often show erratic or non-convergent behavior.

Key Insights and Results

  • Duality as Smoothing: The dual problem often provides a more reliable path to the gradient than direct primal differentiation, especially for non-smooth objectives.
  • Dimensional Scaling: The dual method is highly efficient when the number of parameters $P$ is smaller than the number of variables $N$.
  • Convergence Performance: The authors proved and empirically demonstrated that the dual estimator achieves competitive convergence rates. For quadratic problems, it converges at a rate of $O(\omega^K)$, where $\omega$ is related to the dual matrix's condition number.

Conclusion

By utilizing convex duality, this work provides a robust framework for differentiating value functions without the strict smoothness requirements of previous methods. While currently limited to jointly convex objectives, the Dual Gradient estimator offers a memory-efficient and stable alternative for structured machine learning tasks. Future research will explore extensions to non-convex models and more complex bilevel optimization problems.

Summary updated

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.
BibTeX
@inproceedings{mehmood2021differentiating,
  author = {Sheheryar Mehmood and Peter Ochs},
  title = {{Differentiating the Value Function by using Convex Duality}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=WG_A9aCWMQ7},
}
Figure