Track manipulation, locomotion and embodied systems.
Search papers, labs, and topics across Lattice.
The authors design a damped Newton Frank–Wolfe framework that solves constrained second-order subproblems using inner linear minimization oracles coupled with a root-Newton residual backtracking line search. This resolves a key theoretical bottleneck in projection-free optimization, extending fast second-order convergence guarantees from restricted polyhedral domains to arbitrary compact convex sets. Under Hölder smoothness assumptions on higher-order derivatives, the method proves global linear convergence alongside local superlinear-to-quadratic rates, outperforming standard first- and second-order conditional gradient baselines on matrix sensing and regularized regression tasks.
Second-order Frank–Wolfe optimization is no longer handcuffed to polytopes: damped Newton subproblems coupled with residual backtracking unlock global linear and local quadratic convergence across general compact convex sets.
We study convex optimization over compact convex sets for twice differentiable objective functions with positive definite Hessians, assuming access to the feasible set through a linear minimization oracle. Existing second-order Frank--Wolfe methods either provide only a local linear rate over general convex sets or achieve global linear and local quadratic convergence only over polytopes. We propose damped Newton Frank--Wolfe methods that approximately solve constrained damped Newton subproblems using Frank--Wolfe or away-step Frank--Wolfe inner iterations. We develop residual backtracking, using a root Newton stepsize as a safe reference, together with a switching rule that eventually takes full steps. Under Hölder smoothness assumptions for $p$th derivatives, we establish global linear convergence and local convergence with Q-order at least $1+ν$ ($p=2$) and local quadratic convergence ($p=3$). Experiments on matrix sensing and ridge-regularized logistic regression show that the residual-backtracking variant is consistently robust and often achieves the best performance among the tested first- and second-order baselines.
RIKEN