Beyond Polytopes: Damped Newton Frank--Wolfe Methods over Compact Convex Sets
Abstract
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 pth 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.
Related
- Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
- Cohomology of Linearly Constrained Kloosterman Families: Newton Polytopes, Weights, and Boundary Monodromy
- Compact Hyperbolic Coxeter Six-dimensional Polytopes With Ten Facets
- Grad-div stabilized finite element Picard-Newton iterative methods for the Navier-Stokes equations
- Critical semilinear damped wave equations beyond moduli of continuity
BibTeX
@misc{takahashi2026beyond,
title = {{Beyond Polytopes: Damped Newton Frank--Wolfe Methods over Compact Convex Sets}},
author = {Shota Takahashi and Akiko Takeda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34290},
eprint = {2609.34290},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34290},
}
RIS
TY - UNPB
TI - Beyond Polytopes: Damped Newton Frank--Wolfe Methods over Compact Convex Sets
AU - Shota Takahashi
AU - Akiko Takeda
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34290
UR - https://arxiv.org/abs/2609.34290
AB - 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 pth 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.
ER -