# Rolling-Ball Projection-Free Optimizer

- ID: 1785
- Canonical URL: https://synthcore.org/idea/1785/rolling-ball-projection-free-optimizer
- API JSON: https://synthcore.org/api/idea/1785.json
- API Markdown: https://synthcore.org/api/idea/1785.md
- Verification status: unverified
- Source: [arXiv:2608.04321](https://arxiv.org/abs/2608.04321)
- Category: optimization
- Solves: speedup, stability, scalability
- ML areas: optimizer, fine-tuning, training
- Math tags: convex-analysis, optimization, geometry, numerical-analysis
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## 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.

## 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\).

## Key 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).$$

## 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.

## Disclaimer

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