# On Solution Functions of Optimization: Universal Approximation and Covering Number Bounds

arXiv: https://arxiv.org/abs/2212.01314 · HTML: https://mlsanity.com/paper/2212.01314/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 77 references that are in the map.
- First posted on arXiv 2 Dec 2022.

## Builds on (most cited first, 25 of 25)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Visual Foresight: Model-Based Deep Reinforcement Learning for Vision-Based Robotic Control](https://mlsanity.com/paper/1812.00568/) (2018)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Adversarial Unlearning of Backdoors via Implicit Hypergradient](https://mlsanity.com/paper/2110.03735/) (2021)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation](https://mlsanity.com/paper/1906.09255/) (2019)
- [Piecewise Linear Regression via a Difference of Convex Functions](https://mlsanity.com/paper/2007.02422/) (2020)
- [Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning](https://mlsanity.com/paper/2106.03279/) (2021)

## Built on by (most cited first, 6 of 6)

- [Skin-in-the-Game: Decision Making via Multi-Stakeholder Alignment in LLMs](https://mlsanity.com/paper/2405.12933/) (2024)
- [Winning the CityLearn Challenge: Adaptive Optimization with Evolutionary Search under Trajectory-based Guidance](https://mlsanity.com/paper/2212.01939/) (2022)
- [A Human-on-the-Loop Optimization Autoformalism Approach for Sustainability](https://mlsanity.com/paper/2308.10380/) (2023)
- [Graph Your Own Prompt](https://mlsanity.com/paper/2509.23373/) (2025)
- [An Encoder-Decoder Network for Beamforming over Sparse Large-Scale MIMO Channels](https://mlsanity.com/paper/2510.02355/) (2025)
- [Optimization Solution Functions as Deterministic Policies for Offline Reinforcement Learning](https://mlsanity.com/paper/2408.15368/) (2024)

## Abstract (arXiv)

We study the expressibility and learnability of convex optimization solution functions and their multi-layer architectural extension. The main results are: (1) the class of solution functions of linear programming (LP) and quadratic programming (QP) is a universal approximant for the Ck smooth model class or some restricted Sobolev space, and we characterize the rate-distortion, (2) the approximation power is investigated through a viewpoint of regression error, where information about the target function is provided in terms of data observations, (3) compositionality in the form of a deep architecture with optimization as a layer is shown to reconstruct some basic functions used in numerical analysis without error, which implies that (4) a substantial reduction in rate-distortion can be achieved with a universal network architecture, and (5) we discuss the statistical bounds of empirical covering numbers for LP/QP, as well as a generic optimization problem (possibly nonconvex) by exploiting tame geometry. Our results provide the first rigorous analysis of the approximation and learning-theoretic properties of solution functions with implications for algorithmic design and performance guarantees.