Shrinking the Feasible Set to Recover Curvature Acceleration at Degenerate Boundary Optima

Frank-Wolfe methods solve constrained problems without ever projecting onto the constraint set. Each step calls a "linear minimization oracle", which returns the point of the set that is furthest in the direction of the negative gradient, and then moves toward that point. On sets with curved boundaries, such as Euclidean or $\ell_p$ balls, this simple method can converge very fast, but only under one condition: the solution must sit on the boundary and the objective's gradient must still be nonzero there. When the unconstrained minimizer of the objective happens to land exactly on the boundary, the gradient vanishes at the solution and the speedup disappears. This "degenerate boundary" case is not exotic. It is exactly what happens in noiseless low-rank matrix completion when the nuclear-norm radius equals the norm of the true matrix, and more generally whenever a constraint is tuned to be just barely active. In this case a recent constructive lower bound pins vanilla Frank-Wolfe at $\Omega(1/\sqrt{\varepsilon})$ iterations even for strongly convex objectives on strongly convex sets (Lower Bounds for Frank-Wolfe on Strongly Convex Sets).

We propose a cheap fix and the theory to go with it. We shrink the set slightly toward an interior point, which costs nothing extra with the oracle. The shrunken set now cuts off the unconstrained minimizer, so the gradient on it is bounded away from zero, and curvature acceleration switches back on. We then grow the set back toward full size on a schedule. How fast the gradient vanishes as the shrunken solution approaches the true one is governed by how sharply the objective grows around its minimizer. Objective sharpness therefore sets the cost of each stage, and boundary curvature sets the speed within a stage. The result should be a projection-free method with an explicit complexity in terms of the objective's growth exponent. Its predicted advantage over vanilla Frank-Wolfe appears exactly in the regime where existing analyses are silent: flat objectives, meaning growth exponent above two, whose minimizer touches a curved boundary.

Core Claim

Write the problem as $\min_{x\in\mathcal C} f(x)$, with optimal set $X^*$ and value $f^*$. Assume the objective satisfies a two-sided growth condition $c\,\mathrm{dist}(x,X^*)^\alpha \le f(x)-f^* \le C\,\mathrm{dist}(x,X^*)^\alpha$ near $X^*$, with exponent $\alpha \ge 1$ and constants $c\le C$. Let $c_0$ be a point whose surrounding ball of radius $r$ lies inside $\mathcal C$. The shrunken set is

$$ \mathcal C_\rho = c_0 + \rho(\mathcal C - c_0), \qquad \mathrm{LMO}_{\mathcal C_\rho}(g) = c_0 + \rho\,(\mathrm{LMO}_{\mathcal C}(g) - c_0), $$

so shrinking costs nothing beyond the original oracle. Three facts drive the method.

First, a point of $\mathcal C_\rho$ is at distance at least $(1-\rho)r$ from a boundary solution. Combining this with convexity, $f(x)-f^*\le \|\nabla f(x)\|\,\mathrm{dist}(x,X^*)$, gives a gradient floor on $\mathcal C_\rho$ of order $c\,((1-\rho)r)^{\alpha-1}$.

Second, on a strongly convex set with curvature parameter $\beta$ and smoothness $L$, vanilla Frank-Wolfe converges linearly. The number of iterations per digit of accuracy scales like $L/(\beta\, g)$, where $g$ is the gradient floor. This is the nonvanishing-gradient regime analyzed in Projection-Free Optimization on Uniformly Convex Sets and Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition.

Third, shrinking introduces a bias. The best point of $\mathcal C_\rho$ is worse than $f^*$ by at most $C\,((1-\rho)D)^\alpha$, where $D$ bounds the distance from $c_0$ to $X^*$.

Balancing the bias against the per-stage cost, with $1-\rho \sim \varepsilon^{1/\alpha}$, gives a predicted total complexity of

$$ N(\varepsilon) \;=\; O\!\left(\frac{L}{\beta c\, r^{\alpha-1}}\;\varepsilon^{-(\alpha-1)/\alpha}\,\log\frac{1}{\varepsilon}\right). $$

At $\alpha=2$ this matches the $\Omega(1/\sqrt{\varepsilon})$ barrier up to a logarithm. That is a consistency check, not a win. For $\alpha>2$ it gives $\varepsilon^{-3/4}$ at $\alpha=4$, for example. We conjecture this strictly beats vanilla Frank-Wolfe there, because the argument that yields $1/\sqrt{\varepsilon}$ for vanilla Frank-Wolfe relies on quadratic growth.

A side observation sharpens which regimes even exist. A smooth function with zero gradient at its minimizer cannot grow faster than quadratically, so $\alpha<2$ is impossible at a degenerate boundary optimum unless $f$ is nonsmooth or only Hölder-smooth. The interesting smooth degenerate regime is therefore the flat one, $\alpha \ge 2$. The sharp regime, $\alpha<2$, is a separate nonsmooth question that we treat as an extension.

Relation to Prior Work

Two lines of work motivate the proposal by exposing the gap. The first studies curvature acceleration. Projection-Free Optimization on Uniformly Convex Sets proves vanilla Frank-Wolfe rates on curved sets but requires a boundary solution with nonzero gradient, and it lists functional sharpness as future work. Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition shows vanilla Frank-Wolfe adapts to error bounds on strongly convex sets, but its accelerated case assumes the objective decreases outside the set, so the gradient never vanishes on it. On Frank-Wolfe and Equilibrium Computation obtains fast rates for nonsmooth objectives on strongly convex sets via a game-theoretic variant, again needing gradients bounded away from zero. Our method works exactly where all three assumptions fail.

The second line constrains the proposal. Lower Bounds for Frank-Wolfe on Strongly Convex Sets tells us not to expect to beat $1/\sqrt{\varepsilon}$ at quadratic growth with vanilla steps, so we do not claim to. Our homotopy is a different algorithm, and whether it can beat that barrier at $\alpha=2$ is something we will measure, not assume.

The methodological ingredients come from two sources. The idea of using an observable gap to trigger stage changes, and a logarithmic grid over unknown sharpness constants, comes from Sharpness, Restart and Acceleration and Restarting Frank-Wolfe. The latter is the closest existing work. It converts sharpness into acceleration for Frank-Wolfe, but only on polytopes via fractional away steps, and those steps have no analogue on curved sets with infinitely many extreme points. Restarting vanilla Frank-Wolfe on a fixed set is nearly pointless because the method carries almost no memory. What we restart is the set, not the iterate.

The homotopy idea parallels Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/\epsilon). That method anneals a smoothing parameter and needs proximal operators, whereas we anneal a constraint scale and need only the linear oracle.

Research Program

The theory has three parts. The first is a proof of the stated complexity on strongly convex sets under two-sided Hölder growth. It uses warm starts between stages and a geometric schedule for $1-\rho_k$. Each stage stops when the Frank-Wolfe gap on $\mathcal C_{\rho_k}$, which is observable, falls below a constant times the predicted bias of that stage. Because the bias constant is unknown, we use the logarithmic grid of Sharpness, Restart and Acceleration and pay a log factor.

The second part extends the result to $q$-uniformly convex sets. There the inner rate with a gradient floor is sublinear, and the stage accounting must be redone with the inner rates of Projection-Free Optimization on Uniformly Convex Sets.

The third part attempts a matching or separating lower bound. We will adapt the high-precision worst-case trajectory construction of Halbey et al. to flat objectives with $\alpha>2$, and use it to pin down vanilla Frank-Wolfe's rate in the degenerate regime. That rate is currently unknown, and it is the comparison the whole proposal rests on.

We will also check robustness. When the solution is interior or the gradient is nonzero at the solution, the schedule should not hurt. Once $\rho$ is large enough the shrunken set either contains the solution or keeps a gradient floor, and we will verify this in theory and in code.

The implementation is a thin wrapper around the oracles in FrankWolfe.jl: a rescaled oracle plus a stage controller. This keeps every baseline in the same codebase.

Baselines

The naive reference point is vanilla Frank-Wolfe with exact line search or short steps, run on the full set. Theory says it is the right thing to compare against at $\alpha=2$, since it already attains the Garber–Hazan $1/\sqrt{\varepsilon}$ rate cited in the lower-bound paper. Beating it means a measurably steeper log-log slope of suboptimality against iterations for $\alpha\ge3$, not merely a better constant.

The second baseline is Frank-Wolfe with open-loop step sizes, as analyzed in Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes. These schedules are known to pick up accelerated rates in some boundary settings without line search, so they are a natural "no new idea" competitor.

The strongest LMO-only competitor is away-step and blended pairwise Frank-Wolfe from FrankWolfe.jl. These run over the atoms the oracle has returned, and on a strictly convex set the boundary solution is itself an extreme point that such methods can concentrate weight on. We will run them with their default active-set settings, and we treat beating them in wall-clock time and oracle calls as the real bar.

Where projection is cheap, which on our benchmarks means only the Euclidean ball, restarted accelerated projected gradient following Sharpness, Restart and Acceleration serves as an honest upper reference that we expect to lose to.

All methods get the same starting point, the same oracle and gradient implementations, and a log-scale grid of five values for each method's free constant. Comparisons are made at equal counts of gradient and oracle calls, and also at equal wall-clock time.

There are two ablations. The first is a fixed shrink factor with no growing schedule. It isolates whether the schedule, rather than shrinking itself, gives the rate. The second applies the same homotopy on a polytope of matching scale, where there is no boundary curvature. If the gain persists there, curvature is not the mechanism and our explanation is wrong.

The file reports no numerical optimality-gap results for any of these baselines. In particular, no reported result was found on Lacuna for Frank-Wolfe or away-step Frank-Wolfe gaps on $\ell_p$-ball instances or on MovieLens; Projection-Free Optimization on Uniformly Convex Sets describes its $\ell_p$ experiments only qualitatively. The one reported figure relevant to cost is from FrankWolfe.jl: Frank-Wolfe variants completed 1,000 iterations in roughly the time projected gradient took for 100 on MovieLens. That figure motivates staying projection-free on nuclear-norm problems.

Why not just…?

Why not just run vanilla Frank-Wolfe with line search? At quadratic growth this is a genuine threat. It already achieves $1/\sqrt{\varepsilon}$, and that bound is tight for it, so our method can at best match it up to a logarithm. The proposal stands or falls on flat objectives. If vanilla Frank-Wolfe's measured slope at $\alpha=3,4$ equals ours, the homotopy adds nothing, and we will say so. The lower-bound construction in the research program is designed to settle this in theory as well.

Why not just use away-step or pairwise Frank-Wolfe over stored atoms? These methods fix zig-zagging on polytopes (Restarting Frank-Wolfe, Active Set Complexity of the Away-Step Frank-Wolfe Algorithm). Their linear-rate analyses, however, depend on polytope geometry with finitely many vertices, which has no counterpart on a ball. Away mechanisms are also not affine invariant (An Extended Frank-Wolfe Method with "In-Face" Directions). They might still work well empirically, so they are our main baseline and may win. If they match our slopes, the contribution narrows to a rate guarantee for something practitioners already have.

Why not just project and use restarted accelerated gradient? On the Euclidean ball, projection is a rescaling and this should win; we include it as a control. On $\ell_p$ balls with $p\ne 1,2,\infty$, projection has no closed form. On nuclear-norm balls it needs a full singular value decomposition, which is the cost gap the FrankWolfe.jl comparison above illustrates. Our claims are restricted to these oracle-only sets.

Why not just add a log-barrier and solve without constraints? Barriers force tiny steps near the boundary (Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations), and the degenerate regime is by definition a near-boundary problem. Barriers also destroy the low-rank structure that makes Frank-Wolfe attractive for matrix completion. We do not run this baseline beyond a single sanity check.

Proposed Experiments

The core testbed is synthetic. We minimize $f(x)=\|x-p\|_2^\alpha$ over $\ell_p$ balls with $p\in\{1.5,2,3,4\}$, matching the instances of Projection-Free Optimization on Uniformly Convex Sets. Here $\alpha\in\{2,3,4\}$ and the dimension ranges from $10^2$ to $10^4$. The anchor $p$ is placed in one of three positions: exactly on the boundary (degenerate), slightly outside (nondegenerate), or inside. We also run the adversarial $\alpha=2$ instance of Lower Bounds for Frank-Wolfe on Strongly Convex Sets in 1,000-bit arithmetic, since that paper reports 64-bit floats lose the worst-case trajectory.

The metric is the fitted log-log slope of $f(x_N)-f^*$ against oracle calls $N$. The prediction is a slope of $-\alpha/(\alpha-1)$ for the homotopy on degenerate instances with $p=2$, which inverts the complexity formula. For vanilla Frank-Wolfe we expect a shallower slope at $\alpha\ge3$, and we expect no loss on nondegenerate or interior instances.

The transfer test is noiseless low-rank matrix completion with synthetic matrices $wUV^\top$, following An Extended Frank-Wolfe Method with "In-Face" Directions with the noise weight set to zero. The nuclear-norm radius is set to the norm of the true matrix, so the optimum is degenerate and on the boundary. The nuclear-norm ball has flat faces and is not strongly convex, so this experiment probes whether the mechanism survives without uniform curvature. We compare against standard Frank-Wolfe, away-step Frank-Wolfe, and the in-face method from the InFaceExtendedFW-MatrixCompletion code, measuring both error and iterate rank. MovieLens 10M is used only as a scale and wall-clock check, because its optimum is not known to be degenerate.

The decisive checks are three. The first is whether the homotopy's slope at $\alpha=4$ on the Euclidean and $\ell_{1.5}$ balls is measurably steeper than vanilla Frank-Wolfe's, near the predicted $-4/3$, and steeper than the slope of pairwise Frank-Wolfe. The second is whether the polytope ablation shows no gain, confirming that boundary curvature is the operative ingredient. The third is whether, at $\alpha=2$ on the Halbey construction, the homotopy matches the $1/\sqrt{\varepsilon}$ barrier rather than beating it. If it beats it, our understanding of that bound's scope is wrong in an interesting way. If it falls short, the stage-stopping rule is leaking a polynomial factor.