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

Quinlan Dawkins, Minbiao Han, Haifeng XuAAAI 2022 · DOI

TL;DR

This paper introduces First-Order Convex Fitting (FCF), a framework for constructing a convex function that matches a given set of gradients. The authors identify a simple "permutation stability" condition as the necessary and sufficient requirement for such a fit and demonstrate how this theory can both predict consumer behavior in economics and drastically accelerate large-scale convex optimization.

What Problem Does This Paper Address?

In traditional machine learning, we usually try to fit a function to a set of values (e.g., given $x$, predict $y$). However, in many fields—like economics or physics—we might only observe the slopes or gradients of a function.

The authors tackle a fundamental question in convex analysis: Given a sequence of points $\{x_i\}$ and a sequence of vectors $\{p_i\}$, when does there exist a convex function $f$ such that $\nabla f(x_i) = p_i$ for all $i$?

While this sounds like a textbook problem, it has been surprisingly overlooked. Previous mathematical work (notably by Rockafellar) provided abstract conditions like "cyclical monotonicity," but these were non-constructive and computationally inefficient. This paper seeks an efficient, algorithmic way to determine if a fit is possible and how to build that function.

Methods

The researchers introduce two main contributions: a theoretical condition and a constructive algorithm.

  1. Permutation Stability: They prove that FCF is possible if and only if the data is "permutation stable." Formally, this means that for any permutation $\sigma$, the sum of the dot products $\sum x_i \cdot p_i$ must be greater than or equal to $\sum x_{\sigma(i)} \cdot p_i$. This is a much more intuitive and checkable condition than previous theories.
  2. Algorithm 1 (The FCF Constructor): If the data is stable, the authors show you can construct the function $f(x)$ as the maximum of $T$ linear functions: $f(x) = \max_i [p_i \cdot (x - x_i) + c_i]$. They use a linear inequality system and techniques from network flow decomposition to solve for the constants $c_i$ efficiently.
  3. SMCF (Surrogate Minimization using Convex Fitting): They apply FCF to optimization. Instead of just following a gradient (like Gradient Descent), they use the gradients collected so far to build an FCF "surrogate" function. They then minimize this surrogate to find the next point, effectively "learning" the shape of the objective function as they go.

Datasets

The authors evaluated their optimization algorithm (SMCF) on two large-scale classical datasets for logistic regression:

  • covtype (UCI): 581,012 data points with 54 features.
  • ijcnn1: 49,990 data points with 22 features.

They compared their method against standard benchmarks like Gradient Descent (GD), Stochastic Gradient Descent (SGD), and more complex surrogate-based solvers like MISO.

Key Insights and Ideas

  • The Network Flow Connection: One of the most elegant parts of the paper is the proof of sufficiency. The authors map the problem of finding function constants ($c_i$) to a dual problem that looks like directed flow in a network. This allows them to use the Flow Decomposition Theorem to prove that permutation stability is the "missing link" for convex fitting.
  • Gradients are Enough: In optimization, we often think we need function values (zeroth-order info) to do well. This paper shows that gradients alone are incredibly powerful for building a surrogate that captures the global structure of a convex objective.
  • Economic Rationality: In economics, "revealed preference" theory tries to figure out if a buyer is acting rationally. This paper shows that a buyer is "rational" (maximizing a concave utility function) if and only if their purchase history is permutation stable.

Key Results

  • Optimization Speedup: On the massive covtype dataset, the FCF-based algorithm (SMCF) reached near-optimal solutions in roughly 4,600 to 5,200 seconds. In contrast, standard Gradient Descent and SGD failed to finish within 24 hours.
  • Efficiency: Even compared to other surrogate methods (like Quadratic Surrogates), SMCF was at least 10 times faster while achieving similar or better accuracy.
  • PAC Learnability: The authors provide the first polynomial sample complexity bounds for learning the gradients of separable and piecewise-linear convex functions, proving that these functions can be learned "efficiently" in a formal computational sense.

Limitations and Future Work

  • I.I.D. Assumptions: The theoretical "PAC learning" results assume that data points are drawn independently from a fixed distribution. However, in the optimization application (SMCF), the points are chosen iteratively, violating this assumption. Bridging this theoretical gap is a noted area for future work.
  • Computational Overhead: While SMCF is fast, it requires solving a Linear Program (LP) at each step to find the constants $c_i$. For extremely high-dimensional problems or a very large number of iterations, this LP could become a bottleneck. The authors suggest a "trick" of only using the last 100 points to mitigate this.
  • Generalization: The current empirical success is demonstrated on logistic regression. Testing FCF surrogates on a wider variety of non-smooth or constrained convex problems remains to be explored.

Summary updated

BibTeX
@inproceedings{dawkins2022first,
  author = {Quinlan Dawkins and Minbiao Han and Haifeng Xu},
  title = {{First-Order Convex Fitting and Its Application to Economics and Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20600},
}
Figure