Interpolation Is All You Need

AI people need to get more creative with their paper titles

This is the live blog of Lecture 12 of my graduate class “Convex Optimization.” A Table of Contents is here.

My favorite linear map is function evaluation. If I have a real-valued function f and a point x, the map from f to f(x) is linear in f. If I have two scalars a and b and two functions f and g then (a f + b g) (x) = af(x) + bg(x). This little observation lets us solve a variety of optimization problems where the optimization variable is a function.

The foundational problems we can pose are interpolation problems. Interpolation asks us to find a function that goes through a specified set of outputs on a specified set of inputs. Particular xs must map to particular ys. We often call these “function fitting” problems as we constrain the function to fit a specified data set. For any fixed x and y, “f(x)=y” is a linear constraint. This means that problems that constrain the values of f on a list of points are convex feasibility problems. Interpolation is a convex problem. And if you want approximate interpolation, you can add the constraint f(x)=y+w and minimize some penalty on the w’s, just like we did in last week’s lecture on inverse problems. 

We can use interpolation constraints as building blocks of general function fitting problems. I can take linear combinations of interpolation constraints and get more linear constraints. For example, if I want the average of x over some set to equal some value, this will also be a linear constraint. Similarly, the moments of f, given by integrals of the form

are linear constraints on f.  

I can write restrictions on the variability of f as constraints as well. The derivative operator, mapping f to the derivative of f, is a linear operator. Thus, interpolation constraints of the gradient of a function are linear constraints. Moreover, constraints on the magnitude of the gradient at particular points are convex constraints. Similarly, you can constrain the smoothness of the function at points by penalizing the Hessian (applying the gradient twice). Bounds on the Hessian at points are convex constraints.

Now, can we solve the convex optimization problems associated with fitting functions? Function spaces are usually infinite dimensional, so we need to make some extra assumptions to get problems we can tractably solve with computers. The easiest and most common way to get tractability is to force f to be in the span of basis functions. 

where f_i(x) are fixed functions and the variables are now the coefficients c_i. Now the problem becomes a search for coefficients and is d-dimensional. All of the above constraints I listed become convex constraints on the coefficients of a basis expansion. This basis expansion could just be linear (where f_i(x) is the ith component of x). You could choose low-degree polynomials, and the problem would be linear in the coefficients of the polynomial. If you were doing signal processing, you could choose trigonometric functions. Now you’d be interpolating with sinusoids. You could make a mesh and fit piecewise linear functions or splines to it. As long as the representation is linear in the parameters, you can probably pose your interpolation problem as a convex problem.

What if you don’t want to specify a basis? With a little bit of hand waving, we can take apparently infinite-dimensional problems and make them finite-dimensional. No matter the dimension of the primal variable, the dual problem of a convex optimization problem has a number of variables equal to the number of constraints in the primal problem. This means the dual problem of an interpolation problem will necessarily be finite-dimensional. Provided that you can compute the dual function, which requires solving an unconstrained minimization over a function space, you can often back out the function you care about using the KKT conditions. 

The sketchy argument in this last paragraph plays a little fast and loose with the KKT conditions on function spaces, and strong duality only holds with appropriate convex optimization rigor in place. I managed to write a high-level blog here without a ton of equations, and it felt like a shame to spoil it with too many derivations. If there’s interest, I could write out the gory details of how this works with a bunch of equations tomorrow. Let me know in the comments. 

Regardless, duality gives you a computational means to solve these problems. This idea reduces classic problems in robust control theory to interpolation problems. It is what enables the fitting of cubic splines. In machine learning, this weird dual fact was called the “Representer Theorem.” It’s why reproducing kernels are unavoidable in the theory of machine learning. It’s also why we used to spend so much time on the dual problem of support vector machines in machine learning classes. Convex optimization lets you solve a ton of interpolation problems, and maybe interpolation is all you need.