mlsanityData to 7 Oct 2026

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

arXiv 2212.01314 ↗First posted 2 Dec 2022cs.LG math.OCcited by 6

Not on the map. Why?

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.

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

Builds on

25 of 77 references.

References · 25

  1. 2021Convex optimizationcited by 2,479
  2. 2020Meta-Learning in Neural Networks: A Surveycited by 944
  3. 2017OptNet: Differentiable Optimization as a Layer in Neural Networkscited by 588
  4. 2016Error bounds for approximations with deep ReLU networkscited by 567
  5. 2019Differentiable Convex Optimization Layerscited by 458
  6. 2017Smart "Predict, then Optimize"cited by 332
  7. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  8. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  9. 2018Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimizationcited by 220
  10. 2018Visual Foresight: Model-Based Deep Reinforcement Learning for Vision-Based Robotic Controlcited by 220
  11. 2017A Rewriting System for Convex Optimization Problemscited by 178
  12. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
13 more
  1. 2020Deep Network Approximation for Smooth Functionscited by 163
  2. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  3. 2021Adversarial Unlearning of Backdoors via Implicit Hypergradientcited by 160
  4. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  5. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  6. 2018Stochastic subgradient method converges on tame functionscited by 120
  7. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  8. 2019MIPaaL: Mixed Integer Program as a Layercited by 93
  9. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 59
  10. 2013Data-Driven Estimation in Equilibrium Using Inverse Optimizationcited by 32
  11. 2019Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimationcited by 15
  12. 2020Piecewise Linear Regression via a Difference of Convex Functionscited by 14
  13. 2021Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learningcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 2; 2025: 2.

6 papers.

  1. 2024Skin-in-the-Game: Decision Making via Multi-Stakeholder Alignment in LLMscited by 8
  2. 2022Winning the CityLearn Challenge: Adaptive Optimization with Evolutionary Search under Trajectory-based Guidancecited by 6
  3. 2023A Human-on-the-Loop Optimization Autoformalism Approach for Sustainabilitycited by 2
  4. 2025Graph Your Own Promptcited by 2
  5. 2025An Encoder-Decoder Network for Beamforming over Sparse Large-Scale MIMO Channelscited by 2
  6. 2024Optimization Solution Functions as Deterministic Policies for Offline Reinforcement Learningcited by 0