Acceleration of Generalized Conditional Gradient Methods
Abstract
We develop an adaptive acceleration of generalized conditional gradient methods for convex objectives with a strongly convex regularizer. A computable primal--dual residual certifies Lyapunov decrease without evaluating the regularizer or any Hessian. Each iteration accepts a balanced accelerated trial when the residual is nonpositive; otherwise it takes a mirror-descent step with doubling backtracking and sets the auxiliary parameter explicitly from the dual decrease and the stopping gap. Under uniform strong-convexity and smoothness bounds on the relevant sublevel set, the method converges globally at a linear rate. Near a nondegenerate minimizer, balanced trials pass above a fixed curvature threshold. The adaptive curvature updates then guarantee a positive fraction of accelerated steps and a local accelerated rate. The method applies directly to entropically regularized Jordan--Kinderlehrer--Otto (JKO) steps whose energies contain nonlocal interaction terms with nondiagonal Hessians. Experiments on JKO steps for granular media and for Poisson--Nernst--Planck systems, in one and three dimensions, show that the method reduces both oracle calls and computing time by a large fraction compared with generalized conditional gradient methods with fixed or adaptive step sizes.
Related
- Restart and Adaptive Acceleration in Stochastic Gradient Methods
- Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
- Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
- Acceleration Survives Heavy Tails and Generalized Smoothness
- A Tight Surrogate-Based Adaptive Step Size for the Multiobjective Conditional Gradient Method
BibTeX
@misc{chen2026acceleration,
title = {{Acceleration of Generalized Conditional Gradient Methods}},
author = {Long Chen and Zeyi Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25473},
eprint = {2610.25473},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25473},
}
RIS
TY - UNPB
TI - Acceleration of Generalized Conditional Gradient Methods
AU - Long Chen
AU - Zeyi Xu
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25473
UR - https://arxiv.org/abs/2610.25473
AB - We develop an adaptive acceleration of generalized conditional gradient methods for convex objectives with a strongly convex regularizer. A computable primal--dual residual certifies Lyapunov decrease without evaluating the regularizer or any Hessian. Each iteration accepts a balanced accelerated trial when the residual is nonpositive; otherwise it takes a mirror-descent step with doubling backtracking and sets the auxiliary parameter explicitly from the dual decrease and the stopping gap. Under uniform strong-convexity and smoothness bounds on the relevant sublevel set, the method converges globally at a linear rate. Near a nondegenerate minimizer, balanced trials pass above a fixed curvature threshold. The adaptive curvature updates then guarantee a positive fraction of accelerated steps and a local accelerated rate. The method applies directly to entropically regularized Jordan--Kinderlehrer--Otto (JKO) steps whose energies contain nonlocal interaction terms with nondiagonal Hessians. Experiments on JKO steps for granular media and for Poisson--Nernst--Planck systems, in one and three dimensions, show that the method reduces both oracle calls and computing time by a large fraction compared with generalized conditional gradient methods with fixed or adaptive step sizes.
ER -