Abstract: This paper studies a basic function fitting problem, which we coin \textit{first-order convex fitting} (FCF): given any two vector sequences $\{\bvec{x}_i\}_{i\in[T]}$ and $\{\bvec{p}_i\}_{i\in[T]}$ in $\mathbb{R}^d$, when is it possible to \emph{efficiently} construct a convex function $f(\bvec{x})$ that ``fits'' the two sequences in the first-order sense, i.e, its gradient $\nabla f(\bvec{x}_i)$ equals $\bvec{p}_i$ for all $i \in [T] = \{ 1,\cdots, T \}$? Despite the close connection between function fitting and machine learning, FCF has surprisingly been overlooked in the past literature. With an efficient constructive proof, we discover a clean answer to this question: \name{} is possible \textit{if and only if} the two sequences are \textit{permutation stable}: $\sum_{i=1}^{T} \bvec{x}_i \cdot \bvec{p}_i \geq \sum_{i=1}^T \bvec{x}_i \cdot \bvec{p}_{\sigma(i)}$ for any permutation $\sigma$ of $[T]$.



We demonstrate the usefulness of FCF in two applications. First, we empirically show how it can be used as a surrogate to significantly accelerate the minimization of the original convex function. Second, 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.