Learn · Intermediate

Input-Convex Neural Networks: Learning Shapes That Have No Bad Local Minima

An input-convex neural network (ICNN) is a neural network designed so that its output is a convex function of its input: bowl-shaped, with a single valley and no false bottoms. Amos, Xu and Kolter introduced the design in 2017, and it matters because convexity gives guarantees about optimization and gradients that ordinary networks cannot offer. A recent Apple paper on retrieval uses one to learn how good the best match in a cluster of stored vectors is.

What convex means, concretely

A function is convex if the straight line between any two points on its graph never dips below the graph. Picture a bowl. If you roll a marble anywhere in a convex bowl, following the slope downhill always ends at the same lowest point. Ordinary neural networks have rugged landscapes with many dips, which is why gradient descent can get stuck. A convex function has no spurious dips, so minimizing it is reliable, and its slope at any point is a meaningful vector.

How to build one

A standard network composes layers of weights and nonlinearities. Two rules make the composition convex in the input. First, the activation functions must be convex and non-decreasing; the common ReLU (zero below zero, identity above) qualifies. Second, the weights that connect a hidden layer to the next hidden layer must be non-negative, because a non-negative weighted sum of convex functions is convex. Weights from the raw input into every layer can be any sign, because adding a linear function to a convex one keeps it convex. Training enforces non-negativity by clipping or reparametrizing those weights. The result is still a flexible function approximator over a restricted but useful family. Amos and colleagues used it so that choosing an action or a structured output could be done by running a convex optimization on the network's output.

Support functions: where convexity appears naturally

Take a finite set of vectors, such as the stored embeddings in one cluster. For any direction q, the support function h(q) is the largest dot product any vector in the set has with q. This is exactly the "best score any key in this set gives this query" in maximum inner product search, the operation behind retrieval-augmented generation. Two facts from convex analysis (Rockafellar's classic Convex Analysis is the standard reference) make it useful. First, h is convex in q, since it is a maximum of linear functions of q, and a maximum of convex functions is convex. Second, wherever h is differentiable, its gradient is the vector that achieves the maximum. So a model of h is also a model of "which stored vector wins".

Imagine each cluster as a bag of arrows. Shine a light in direction q and measure how far the farthest arrow tip reaches along the light. That reach, as q varies, is the support function. It captures outlier arrows that an average-position summary would hide.

How retrieval uses it

Standard approximate search compares a query to each cluster's centre and visits the nearest clusters, which misses an outlier far from its cluster's centre. Apple's SupportNet instead trains a small ICNN per cluster, offline on typical queries, to approximate h. At search time, evaluating the network scores each cluster by the quality of its best member rather than its average. Because the network is convex by construction, its form matches the true function's shape, which is the reason to use an ICNN here and not an arbitrary network. A companion network, KeyNet, exploits the gradient fact: it predicts the winning key directly. See the approximate nearest-neighbor search lesson for the surrounding methods. Shrivastava and Li's 2014 paper is a classic earlier treatment of why inner product search is harder than ordinary nearest-neighbor search, since inner products violate the triangle inequality.

Trade-offs

Convexity restricts what the network can represent, though it fits support functions exactly. Non-negativity constraints can slow training. And any learned router depends on the training queries resembling real ones: if users' questions drift, the learned shapes go stale, an instance of distribution shift. In Apple's reported setup the networks are 1% to 20% of the database size, so training and storage cost must be weighed against speedups.

The takeaway

Whenever the quantity you want is a maximum over a set, ask whether it is convex in the input. If so, an ICNN builds that shape in, and you get a function that is cheap to evaluate, safe to optimize and whose gradient tells you which item achieved the maximum. That is the mathematical trick behind a faster way to search.

Ground Truth. (2026, November 12). Input-Convex Neural Networks: Learning Shapes That Have No Bad Local Minima. Ground Truth. https://groundtruth.day/learn/input-convex-neural-networks-and-support-functions.html

@misc{groundtruth:input-convex-neural-networks-and-support-functions,
  title  = {Input-Convex Neural Networks: Learning Shapes That Have No Bad Local Minima},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {nov},
  url    = {https://groundtruth.day/learn/input-convex-neural-networks-and-support-functions.html}
}

Topics: convexity · neural-networks · retrieval · optimization · vector-search