Universal Representation of Generalized Convex Functions and their Gradients

Generalized convex functions (GCFs) appear in many optimization problems, from optimal transport to economics. The authors develop a universal parameterization of GCFs and their gradients, enabling conversion of bilevel problems into single-level ones for efficient numerical optimization.

Parameterization involves mapping a parameter space to a function class, aiming for the Universal Approximation Property (UAP). Neural networks exemplify UAP for continuous functions. The authors extend this to GCFs, providing a convex, potentially one-to-one parameterization that approximates any GCF arbitrarily well.

Convex functions are well-studied with parameterizations like max-affine and smooth log-sum-exp approximations. Gradients of convex functions can be approximated reliably, unlike arbitrary vector fields. The authors build on this to handle GCFs, which generalize convexity and are crucial in applications like optimal transport and mechanism design.

Optimal transport problems seek cost-minimizing mappings between distributions. The Kantorovich dual problem involves potentials that are generalized convex functions. When the surplus function satisfies certain conditions, the optimal transport map is the gradient of a GCF, linking theory to practical parameterization needs.

In mathematical economics, mechanism design problems reduce to finding indirect utility functions that are generalized convex. Incentive compatibility and individual rationality impose constraints, making the problem a bilevel optimization. The authors show these can be reformulated as single-level problems by parameterizing GCFs and their gradients.

The authors propose finitely Y-convex functions, defined via finite subsets, as a dense subset of all Y-convex functions, establishing UAP. They prove these functions and their gradients can approximate any GCF and gradient under mild regularity, such as semiconvexity of the surplus function, enabling practical numerical methods.

To ensure injectivity and convexity of the parameter space, the authors introduce the concept of lean parameterizations, which exclude dominated functions. They prove the lean subset is convex and corresponds exactly to X-convex functions, providing a well-structured parameter space for optimization algorithms.

The parameterization parallels shallow neural networks with one hidden layer: the input is transformed by the surplus function plus parameters, aggregated by a max operation without additional nonlinear activation. This structural similarity suggests potential for deeper architectures to improve practical performance.

Numerical experiments focus on multi-item auction design, a challenging bilevel problem. Using their parameterization, the authors find revenue-maximizing mechanisms that match or closely approximate known optimal auctions like the Straight-Jacket auction, validating the approach's effectiveness in economic applications.

Visualizations of mechanisms for one and two items show that the method recovers known optimal pricing structures, such as posted price auctions for single items and complex bundling for two items. This demonstrates the parameterization's ability to capture intricate economic behaviors through GCF gradients.

In conclusion, the authors provide a foundational framework for parameterizing GCFs and their gradients with universal approximation, convexity, and injectivity properties. Their approach bridges theory and practice, enabling computational solutions to complex optimization problems in economics and optimal transport.

Future work includes exploring deep architectures for finitely convex functions and investigating optimization landscapes to understand whether local methods reliably find global optima, paralleling advances in neural network theory and practice. The gconvex Python package implements these ideas for broader use.