First-Order Convex Fitting and Its Application to Economics and Optimization

Authors

  • Quinlan Dawkins University of Virginia
  • Minbiao Han University of Virginia
  • Haifeng Xu University of Virginia

DOI:

https://doi.org/10.1609/aaai.v36i6.20600

Keywords:

Machine Learning (ML), Game Theory And Economic Paradigms (GTEP)

Abstract

This paper studies a function fitting problem which we coin first-order convex fitting (FCF): given any two vector sequences x1, ..., xT and p1, ..., pT, when is it possible to efficiently construct a convex function f(x) that ``fits'' the two sequences in the first-order sense, i.e, the (sub)gradient of f(xi) equals precisely pi, for all i = 1, ..., T? Despite a basic question of convex analysis, FCF has surprisingly been overlooked in the past literature. With an efficient constructive proof, we provide a clean answer to this question: FCF is possible if and only if the two sequences are permutation stable: p1 * x1 + ... + pT * xT is greater than or equal to p1 * x’1 + ... + pT * x’T where x’1, ..., x’T is any permutation of x1, ..., xT. We demonstrate the usefulness of FCF in two applications. First, we study how it can be used as an empirical risk minimization procedure to learn the original convex function. We provide efficient PAC-learnability bounds for special classes of convex functions learned via FCF, and demonstrate its application to multiple economic problems where only function gradients (as opposed to function values) can be observed. Second, we empirically show how it can be used as a surrogate to significantly accelerate the minimization of the original convex function.

Downloads

Published

2022-06-28

How to Cite

Dawkins, Q., Han, M., & Xu, H. (2022). First-Order Convex Fitting and Its Application to Economics and Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6), 6480-6487. https://doi.org/10.1609/aaai.v36i6.20600

Issue

Section

AAAI Technical Track on Machine Learning I