Deep Legendre Transform

AI summary

Overview

Research area: Machine learning methods for convex analysis, specifically the numerical computation of convex conjugates (Legendre–Fenchel transforms), with applications to optimal control, optimal transport, physics, and economics.

Technical level: Advanced. The paper assumes familiarity with convex analysis (Fenchel–Young inequality, conjugate functions), neural network architectures (MLPs, ResNets, ICNNs, KANs), and Hamilton–Jacobi PDEs.

Scope in one sentence: The paper introduces Deep Legendre Transform (DLT), a deep learning algorithm that computes convex conjugates of differentiable convex functions in high dimensions by fitting an implicit Fenchel identity rather than inverting the gradient map.

What This Paper Is About

The convex conjugate $f^{}(y)=\sup_{x}{\langle x,y\rangle-f(x)}$ is a fundamental operation in convex analysis, but classical numerical approaches evaluate it on grids and become intractable in high dimensions because their cost grows exponentially in the dimension $d$. The paper's goal is to approximate $f^{}$ accurately in high dimensions using neural networks, without solving the constrained max-min problems that earlier neural approaches to convex conjugation typically require.

Key Contributions

1. The DLT algorithm. An implicit Fenchel formulation, $f^{*}(\nabla f(x))=\langle x,\nabla f(x)\rangle-f(x)$ for $x\in C$, which turns convex conjugation into a straightforward squared-error regression problem in which the target values $\langle x,\nabla f(x)\rangle-f(x)$ are exactly equal to the true conjugate values at the training points, without requiring the inverse gradient map $(\nabla f)^{-1}$ to exist or be available in closed form.

2. A posteriori $L^{2}$ error estimates. Because the implicit identity holds pointwise, the same test-set Monte Carlo average used for training also equals $\frac{1}{|\mathcal{X}{\text{test}}|}\sum{x}(g(\nabla f(x))-f^{}(\nabla f(x)))^{2}$, which by the law of large numbers converges to $|g-f^{}|^{2}_{L^{2}(D,\nu)}$ with respect to the push-forward $\nu=\mu\circ(\nabla f)^{-1}$. This lets the method report approximation errors even when the true conjugate is unknown, and it can be used to evaluate any numerical method for convex conjugation. Confidence intervals are given in Lemma 1 in Appendix A.

3. Inverse sampling for distorting gradient maps. The paper trains a neural network $h_{\vartheta}:D\to\mathbb{R}^{d}$ (a feed-forward network with two hidden layers and GELU activation) to approximate a generalized inverse of $\nabla f$, so training and test inputs can be placed where the target distribution $\nu$ on $D$ actually lives. The network is pretrained by minimizing one objective and then trained on a convex combination of both, omitting points whose image falls outside $C$.

4. Symbolic regression with KANs. Specifying $g_{\theta}$ as a Kolmogorov–Arnold Network makes it possible to obtain exact convex conjugates for certain convex functions via symbolic regression, rather than only numerical approximations.

Main Findings

• DLT matches direct learning of known conjugates. For functions with closed-form conjugates, DLT was compared against direct learning of $f^{}$ using pairs $(y_i,f^{}(y_i))$ as targets, across MLP, ResNet, ICNN, and MLP-ICNN architectures at $d=10$ and $d=50$, with errors computed by Monte Carlo on a test set of 4096 i.i.d. points sampled from $\text{Unif}\circ(\nabla f)^{-1}$. Example: for the quadratic at $d=10$, MLP gave RMSE $2.96\times10^{-5}$ (DLT) versus $2.86\times10^{-5}$ (direct), with training times of 86s versus 84s.

• ResNet gave the best approximations overall. Despite not guaranteeing convexity, ResNet produced the smallest errors in these tests (e.g. for the quadratic at $d=50$, $2.92\times10^{-3}$ versus $3.25\times10^{-3}$ for direct learning). MLP-ICNN showed limitations attributed to the lack of skip connections compared with ICNN.

• Constant memory and smooth scaling versus grid methods. Compared with Lucet's LLT algorithm at $N=10$ points per dimension, DLT (ResNet 128,128) kept active memory at 1.1 MB for all tested dimensions. For the negative logarithm at $d=8$, Lucet required $1.96\times10^{3}$ s to solve, 3.96 s to evaluate, $1.53\times10^{3}$ MB, and achieved RMSE $2.93\times10^{1}$, while DLT required 26.22 s to solve, 0.02 s to evaluate, 1.1 MB, and achieved RMSE $1.33\times10^{-1}$. For the negative entropy at $d=8$, Lucet's RMSE was $1.08\times10^{2}$ versus $1.40\times10^{-1}$ for DLT. Lucet was not run at $d=10$ in these comparisons.

• Inverse sampling helps substantially when the gradient map is distorting. For the negative logarithm on $C=(10^{-3},10^{-1})^{d}$, whose gradient map sends $C$ to $D=(-1000,-10)^{d}$, inverse sampling improved $L^{2}$ error by one to two orders of magnitude for $d\geq 10$ (e.g. $d=100$: $3.06$ inverse versus $5.44\times10^{1}$ direct) at the cost of longer training time (97:10 total versus 26:10).

• A posteriori estimates work without a closed-form conjugate. For

Authors’ abstract

We introduce a novel deep learning algorithm for computing convex conjugates of differentiable convex functions, a fundamental operation in convex analysis with various applications in different fields such as optimization, control theory, physics and economics. While traditional numerical methods suffer from the curse of dimensionality and become computationally intractable in high dimensions, more recent neural network--based approaches scale better, but have mostly been studied with the aim of solving optimal transport problems and require the solution of complicated optimization or max--min problems. Using an implicit Fenchel formulation of convex conjugation, our approach facilitates an efficient gradient--based framework for the minimization of approximation errors and, as a byproduct, also provides a posteriori estimates of the approximation accuracy. Numerical experiments demonstrate our method's ability to deliver accurate results across different high-dimensional examples. Moreover, by employing symbolic regression with Kolmogorov--Arnold networks, it is able to obtain the exact convex conjugates of specific convex functions.