Unverified 2026

Rolling-Ball Projection-Free Optimizer

Implementation & benchmark of arXiv:2608.04321 — A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets

Usefulness6/10

Difficulty5/10

Novelty7/10

Optimization Speedup Stability Scalability Optimizer Fine tuning Training Convex analysis Optimization Geometry Numerical analysis

Source paper: A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets arXiv:2608.04321 ⓘ · analyzed Aug 31, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace Euclidean projection onto a smooth convex parameter constraint by a local tangent-halfspace linear minimization step. The method is particularly suitable for convex softmax heads or low-dimensional adapter parameters constrained to an ellipsoid, where projections require matrix solves or expensive nonlinear routines but membership and boundary-normal queries are cheap.

Formulas

$$\min_{z\in\mathcal{K}\cap\mathbb{B}(x,s)}\langle\nabla f(x),z\rangle.$$

$$\langle n,p-q\rangle=0.$$

$$\langle c,\widehat{p}\rangle\leq\min_{z\in\mathcal{K}\cap\mathbb{B}(x,s)}\langle c,z\rangle+\frac{2}{\rho}\lVert c\rVert s^{2}.$$

$$T=O\!\left(\left(\frac{\beta}{\alpha}+\frac{G}{\alpha\rho}\right)\log\frac{H_{0}}{\varepsilon}\right).$$

Mathematical statement

A compact convex body $\mathcal K\subset\mathbb R^d$ is $\rho$-smooth if every supporting pair $(q,n)$, with boundary point $q\in\partial\mathcal K$ and outward unit normal $n$, admits an interior tangent ball of radius $\rho$. For a local radius $s>0$, current point $x\in\mathcal K$, and linear objective vector $c$, the local problem is $\min_{z\in\mathcal K\cap\mathbb B(x,s)}\langle c,z\rangle$. The tangent repair replaces the unknown local feasible set by the computable halfspace $\langle n,z-q\rangle\le0$, producing $p$ from the intersection of this halfspace and $\mathbb B(x,s)$. The active constraint satisfies $\langle n,p-q\rangle=0$. Lemma 2.3 states that the repaired point $\widehat p$ is feasible and satisfies $\langle c,\widehat p\rangle\le\min_{z\in\mathcal K\cap\mathbb B(x,s)}\langle c,z\rangle+(2/\rho)\lVert c\rVert s^2$. Thus the local-oracle error is quadratic in $s$, while the global guarantee reaches error $\varepsilon$ in $O((\beta/\alpha+G/(\alpha\rho))\log(H_0/\varepsilon))$ iterations for a $\beta$-smooth, $\alpha$-strongly convex objective, gradient bound $G$, and initial gap $H_0$.

Implementation notes

Integrate this into the optimizer for a constrained parameter block, rather than into ordinary unconstrained Adam updates. Start with a convex softmax or linear classification head whose parameter vector $w\in\mathbb R^d$ is constrained to the ellipsoid $\mathcal K=\{w:w^TA^{-1}w\le1\}$, or use a small LoRA adapter with the same constraint. At iteration $t$, compute the minibatch gradient $g_t=\nabla f(w_t)$, choose a local radius $s_t$, and set $c=g_t$. Find an approximate boundary point $q_t$ by moving from $w_t$ in direction $-c/\|c\|$ until the membership test changes from feasible to infeasible; use bisection to refine the last feasible point. For an ellipsoid, compute the outward normal analytically as $n_t=A^{-1}q_t/\|A^{-1}q_t\|$; for a black-box set, estimate it with finite differences of the membership function. Compute $p_t$ by minimizing $c^Tz$ subject to $\|z-w_t\|\le s_t$ and $n_t^T(z-q_t)\le0$. The solution is obtained by checking the unconstrained ball minimizer $w_t-s_t c/\|c\|$; if it violates the halfspace, solve on the intersection circle using a two-dimensional span of $c$ and $n_t$. Set $w_{t+1}=p_t$, optionally damping with $w_{t+1}=(1-\eta)w_t+\eta p_t$ for noisy gradients. Use $s_t=\min(s_{\max},\gamma\sqrt{\Delta_t/(\beta+10^{-8})})$, where $\Delta_t$ is a moving estimate of the objective gap and $\gamma\in[0.1,0.5]$. The paper supplies the feasibility and additive-error bound; estimate $\beta$, $G$, and $\Delta_t$ empirically, and measure tangent accuracy by repeating the boundary search at several tolerances. First compare against projected SGD and AdamW on a 10k-example MNIST or CIFAR-10 linear-head task with an ellipsoidal constraint, using identical minibatches and gradient evaluations. Measure loss versus gradient evaluations, membership-query count, wall-clock time, final constraint violation, and validation accuracy. Success means a geometric loss tail comparable to projected SGD while avoiding projection solves, with at least 2x lower constraint-oracle cost at equal validation accuracy.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.