Frank-Wolfe over Data Hulls with Graph-Search Oracles

Many data-driven optimization problems ask for the best point inside the convex hull of a large set of high-dimensional vectors. Examples include finding the closest "plausible" point to a query, fitting a robust regression whose answer must stay inside the region covered by observed data, or checking whether a candidate lies in the data's support. Two obvious routes are both closed. Writing the hull down as linear inequalities is hopeless, because the number of faces grows like $n^{\lfloor d/2 \rfloor}$. Optimizing over mixture weights on all $n$ points costs a full pass over the data at every step. Frank-Wolfe methods, which move toward one vertex of the feasible set per iteration, avoid both problems. Their cost is a vertex-selection subproblem at every step. Frank-Wolfe with a Nearest Extreme Point Oracle showed that choosing the vertex nearest to a gradient-shifted point gives rates that depend on the size of the optimal face rather than the whole feasible set, and can be linear. That subproblem is a nearest-neighbor query. Over $n$ unstructured vectors it is exactly the query that proximity graphs answer approximately in sublinear time.

We propose to run nearest-extreme-point Frank-Wolfe over data hulls with the oracle answered by an approximate, warm-started search on a flat proximity graph: a graph whose nodes are data points and whose edges link near neighbors, searched greedily. The claim has two parts. First, the oracle's error can be scheduled and monitored so that the linear rate survives. Second, because the query point moves only slightly between iterations, warm-starting each search from the previous answer makes the per-iteration cost nearly independent of $n$. If both parts hold, a subproblem cursed by dimension becomes an inexact oracle whose cost is set by optimization progress rather than dataset size.

Core Claim

Let $\mathcal{V}=\{v_1,\dots,v_n\}\subset\mathbb{R}^d$ be the data, $K=\mathrm{conv}(\mathcal{V})$ the hull, and $f$ the objective. At iterate $x_k$, the nearest-extreme-point oracle of Garber and Wolf returns the data point closest to the query $y_k = x_k - \tfrac{1}{2\lambda}\nabla f(x_k)$, where $\lambda>0$ is a step-scale parameter. Our oracle instead returns some $\tilde v_k$ that is close to optimal in squared distance:

$$\|\tilde v_k - y_k\|^2 \le \min_{v\in\mathcal{V}}\|v-y_k\|^2 + \delta_k,$$

where $\delta_k\ge 0$ is the excess squared distance of the graph search's answer. We conjecture, and will try to prove, that under the conditions Garber and Wolf use (smooth, strongly convex $f$ and strict complementarity), the suboptimality $h_k = f(x_k)-f^*$ satisfies a perturbed contraction $h_{k+1}\le(1-\gamma)h_k + c\,\delta_k$. Here $\gamma$ is their contraction factor and $c$ depends on smoothness and step size. This recursion has a direct consequence. Any $\delta_k$ decaying geometrically at a rate slower than $1-\gamma$ preserves linear convergence. A constant $\delta$ yields a floor of order $c\delta/\gamma$. The floor form follows directly from the recursion, the same way that Characterizations of inexact proximal operators obtains an error ball for forward-backward splitting under errors that do not vanish.

What is new is not "inexact Frank-Wolfe" in the abstract. It is three concrete things. The inexact quantity is a graph-search excess distance. The search effort that controls $\delta_k$ (the beam width and the warm start) is chosen online. The resulting cost per iteration is measured against $n$.

Non-smooth objectives enter as the application regime rather than the core mechanism. We target robust losses such as $\|Ax-b\|_1$ or a maximum of affine terms over $K$. We handle them with Moreau smoothing, which replaces a kinked function by a smooth surrogate whose gradient comes from a proximal step, and we shrink the smoothing parameter in epochs as in Variable Smoothing for Weakly Convex Composite Functions. For these losses the proximal step is closed-form. The only hard subproblem is therefore the geometric one, so the study isolates it cleanly.

Research Program

The method has three pieces.

The first is the oracle. A flat navigable graph in the style of FlatNav is built once over $\mathcal{V}$. Down with the Hierarchy shows that for $d\ge 32$, hub nodes make the hierarchical layers of HNSW redundant, and we rely on that result. Each oracle call is a beam search started from $\tilde v_{k-1}$, the previous answer, rather than from a global entry point. As an option, routing uses the probabilistic pruning of Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search to skip most exact distance evaluations.

The second piece handles the fact that $\delta_k$ cannot be observed. This is the "unknown error bound" problem flagged for inexact methods. We borrow the monitor step from Inexact Proximal Gradient Methods for Non-convex and Non-smooth Optimization, which falls back to a safe step when a descent test fails. Here, if the step toward $\tilde v_k$ fails a sufficient-decrease test, the beam width is doubled and the search restarted. As a rare last resort, an exact scan is run. The count of fallbacks becomes a measured quantity.

The third piece is analysis on two fronts. We will attempt the perturbed-contraction proof above. We will also bound warm-start search cost in terms of the query displacement $\|y_k-y_{k-1}\|$, which shrinks as the iterates converge. This second result is the step that would make cost nearly independent of $n$. We expect it to hold only empirically, or under assumptions of low intrinsic dimension, and we will report it that way.

One tension needs direct study. The theory for persistent oracle error, in Inexact subgradient methods for semialgebraic functions and in Lauga and Vaiter, treats errors as unstructured. Graph-search misses are not unstructured. They are biased toward hubs. Optimization queries also differ from data-like queries: early on they sit near the hull's center, which is exactly where hubs live. We will measure whether missed nearest neighbors cluster around hubs and whether this bias stalls progress on particular faces of the hull.

Baselines

The naive reference is nearest-extreme-point Frank-Wolfe with an exact brute-force scan, which costs $O(nd)$ per iteration. This is Garber and Wolf's algorithm applied unchanged to data hulls. It fixes the iteration trajectory and the final accuracy we must match. We beat it if we reach the same suboptimality, for example $10^{-6}$ relative, with a large reduction in exact distance evaluations and wall-clock time. That reduction should grow with $n$.

The strongest existing optimization competitor is accelerated projected gradient on the simplex of mixture weights $w\in\Delta_n$, with $x=Vw$. This is a mature, tuning-light method. Its per-iteration cost is also $O(nd)$, but it can need far fewer iterations.

The strongest existing search-side competitor is classic Frank-Wolfe whose linear oracle (pick the vertex maximizing an inner product with the negative gradient) is answered by approximate maximum-inner-product search on the same graph. It isolates whether the choice of nearest-point oracle matters once both oracles are approximate.

Garber and Wolf report that their method reached error $10^{-12}$ "approximately 1.2x faster than the standard fully corrective method" on a 660-dimensional video co-localization problem. That problem is over a structured flow polytope, so the number is not comparable to data hulls. We found no reported result on Lacuna for any optimizer over the convex hull of SIFT1M, GloVe, DEEP or GIST. On the search side, PEOs reports "1.6x to 2.5x higher throughput" for retrieval and FlatNav reports "38% to 39%" lower peak memory than hnswlib. These numbers bound the oracle speedups we can plausibly inherit.

Two ablations isolate the key ingredients. The first is cold-start search, which begins each oracle call at the graph's default entry point. The second is a fixed beam width with no monitor step. A geometric baseline in the style of PCH also enters: learn a compact polytope $Ax\ge b$ approximating $K$ with Projection Convex Hull, then optimize over it. It is measured by the feasibility error it introduces as well as by speed.

All methods share the same data, the same graph index (its build time is reported separately and amortized over many solves), the same single-machine budget, and the same random-search tuning budget over step sizes and beam widths.

Why not just…?

Why not just optimize the mixture weights with accelerated projected gradient? This is the real threat. Simplex projection is cheap, acceleration is strong, and on hulls of moderate size it may win outright. Its weakness is that every iteration touches all $n$ points. Our method touches a roughly constant number of points per iteration if the warm-start hypothesis holds. The scaling experiment from 1M to 100M points on DEEP settles the question. If the crossover point never appears, we will report that the graph oracle is not worth building.

Why not just use standard Frank-Wolfe with approximate inner-product search? That is the cheapest way to make Frank-Wolfe sublinear in $n$. Garber and Wolf show its exact version pays for the diameter of the whole feasible set and zigzags between distant vertices. Approximate search may not change that, and inner-product search is also harder for graphs than Euclidean search. Running both oracles on the same graph, at matched oracle cost, shows whether the nearest-point choice still pays once both are inexact.

Why not just learn the hull's facets and project? PCH fits 100-dimensional polytopes with "15" hyperplanes where QuickHull produces "over 23 million facets," which makes it an attractive shortcut. However, the learned polytope is a surrogate. Optimizing over it can return points outside the true hull or miss parts of it. Our method never leaves $\mathrm{conv}(\mathcal{V})$, because every iterate is a convex combination of data points. The comparison reports the hull-membership violation alongside speed.

Proposed Experiments

The benchmarks are SIFT1M, GIST1M, GloVe, DEEP1M and DEEP100M, plus the UNIFORM synthetic set as a worst case with weak clustering. The tasks are of two kinds. The smooth task is projection of held-out vectors onto the hull of the training vectors. The non-smooth tasks are least-absolute-deviation regression constrained to the hull and minimax-affine objectives, both handled with variable smoothing. The metrics are suboptimality against wall-clock time and against the number of exact distance evaluations, the per-iteration oracle recall and excess distance $\delta_k$, the fallback rate, and the final gap to the brute-force solution.

The decisive checks are four. First, on DEEP from 1M to 100M points, per-iteration distance evaluations should stay roughly flat for the warm-started method and grow linearly for brute force and for simplex-weight gradient methods. Second, the convergence curve should stay linear down to the predicted floor, and the floor should shrink as the beam width grows, matching the $c\delta/\gamma$ form. Third, cold-start ablations should lose most of the speedup; if they do not, warm-starting is not the mechanism. Fourth, on UNIFORM and on queries far from hubs, measuring whether misses concentrate around hubs will show whether hub bias produces stalls that the monitor step must absorb. A failure on UNIFORM alone would delimit the method's reach rather than refute it.