Universal Representation of Generalized Convex Functions and their Gradients

A wide range of optimization problems can often be written in terms of generalized convex functions (GCFs). When this structure is present, it can convert certain nested bilevel objectives into single-level problems amenable to standard first-order optimization methods. We provide a new differentiable layer with a convex parameter space and show (Theorems 5.1 and 5.2) that it and its gradient are universal approximators for GCFs and their gradients. We demonstrate how this parameterization can be leveraged in practice by (i) learning optimal transport maps with general cost functions and (ii) learning optimal auctions of multiple goods. In both these cases, we show how our layer can be used to convert the existing bilevel or min-max formulations into single-level problems that can be solved efficiently with first-order methods.

In some optimization problems, the optimizer is known to lie in a structured function class; restricting the search to that class does not exclude the optimum and can substantially reduce the space of candidates we need to explore. One such class is generalized convex functions (GCFs), a weakening of ordinary convexity. For example, in optimal transport and in auction design, the key unknowns (dual potentials and buyers’ indirect utilities) can be chosen to be GCFs. We introduce a differentiable parameterization of GCFs with a convex parameter space, and we show it can approximate any GCF and its gradient arbitrarily well (under mild regularity conditions). This enables direct, gradient-based search over the GCF hypothesis class. Beyond pruning the search space, the parameterization can also convert certain nested (bilevel or min–max) learning formulations into single-level objectives that are much easier to optimize. We demonstrate the approach by learning optimal transport maps with general costs and by learning revenue-optimal multi-item auctions.