Universal Representation of Generalized Convex Functions and their Gradients

Moeen NehzatiICML 2026 · OpenReview

Introduction: The Challenge of Bilevel Optimization

Many complex problems in machine learning and economics—such as designing optimal auctions or computing optimal transport—are inherently "bilevel" or "min-max" in nature. For instance, a seller attempting to set optimal prices must anticipate how a strategic buyer will react. Finding the optimal price requires solving an optimization problem inside another optimization problem. This nested structure is notoriously computationally expensive and often lacks theoretical guarantees when solved with standard deep learning methods.

While standard neural networks are excellent universal approximators, they typically ignore the underlying mathematical structure of specific domains. In fields like Mechanism Design and Optimal Transport, optimal solutions naturally exhibit a property known as generalized convexity. Until recently, the field lacked a practical, differentiable method to parameterize these functions while guaranteeing the ability to approximate any possible Generalized Convex Function (GCF) and its gradient.

The Solution: A Differentiable GCF Layer

To bridge this gap, researchers have introduced a novel differentiable neural network layer explicitly designed to represent GCFs and their gradients. This approach relies on a parameterization called finitely $Y$-convex functions.

Instead of a standard linear layer, the architecture utilizes a "kernel" function $\Phi(x, y)$ that defines the relationship between inputs ($x$) and parameters ($y$). The layer computes:

$$f(x) = \max_{i=1, \dots, n} \{ \Phi(x, y_i) - p_i \}$$

where $y_i$ represents trainable support points and $p_i$ represents trainable intercepts.

Conceptually, this GCF layer can be viewed as a generalization of a Maxout unit. While a traditional Maxout unit takes the maximum of affine (linear) functions, the GCF layer takes the maximum of "kernel sections," providing a powerful bridge between classical convex analysis and modern deep learning architectures.

Theoretical Foundations

Universal Approximation and Gradient Stability

The authors provide rigorous proofs (Theorems 5.1 and 5.2) demonstrating that as the number of support points ($n$) increases, this layer can universally approximate any GCF and—crucially—its gradient.

A major hurdle in machine learning theory is that even if a sequence of functions converges to a target function, their gradients might not converge to the target's gradient. To solve this, the authors leverage the concept of equi-semiconvexity (a lower bound on curvature). If the kernel $\Phi$ is sufficiently smooth, the resulting GCFs avoid "downward kinks." This stability ensures that first-order optimization methods, like Adam, do not get stuck or behave erratically.

Practical Smoothing

For practical training, the "hard" maximum in the GCF equation can be replaced with a Log-Sum-Exp (softmax) relaxation. This smoothing technique maintains the theoretical approximation guarantees while making the layer highly amenable to standard backpropagation.

Applications and Key Results

By parameterizing functions as GCFs, complex strategic problems can be collapsed into single-level maximization problems. The authors validated this approach on synthetic benchmarks where ground truth is known:

  • Scaling Optimal Auctions: In mechanism design, the authors applied the Revelation Principle from economics. By parameterizing the buyer's "indirect utility" as a GCF, the seller’s nested bilevel problem becomes a single-level task. This allowed the method to scale to multi-item auctions with up to 250 goods—a massive leap over previous state-of-the-art "learned auction" benchmarks, which typically maxed out at 10–15 goods. In smaller settings, the learned GCF model successfully matched the theoretical maximum revenue of the optimal "Straight-Jacket Auction" (SJa).
  • Optimal Transport with General Costs: The model successfully learned optimal transport maps for non-convex costs (such as negative quadratic costs). This is a notoriously difficult task for standard solvers. The GCF layer correctly identified that under negative quadratic costs, mass should be moved as far as possible rather than as little as possible.

Limitations and Future Directions

While the GCF layer represents a significant step forward for structured optimization, the authors note a few limitations:

  1. Non-convex Training Landscape: Although the parameter space is convex, the training objective (the loss function) remains non-convex. Understanding the conditions under which local optimization reliably finds the global optimum is a critical area for future study.
  2. Single Buyer Constraint: The current auction experiments focus on a single buyer. Extending this framework to multi-buyer auctions will require handling significantly more complex constraints.
  3. Architectural Depth: The current work focuses on "shallow" architectures utilizing a single GCF layer. Exploring "deep" compositions of these layers could capture even more complex structures and remains a highly promising next step.

By embedding mathematical structure directly into the network architecture, the GCF layer offers a robust, scalable new tool for tackling some of the most challenging bilevel optimization problems in machine learning and economics.

Summary updated

Abstract

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.
BibTeX
@inproceedings{nehzati2026universal,
  author = {Moeen Nehzati},
  title = {{Universal Representation of Generalized Convex Functions and their Gradients}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=63o9EmYHXt},
}
Figure