TIGER: Tunable-Geometry Accelerated Gradient Sliding with Adaptive Safeguards under Similarity
Abstract
We study distributed composite optimization under function similarity when synchronized gradient queries dominate local computation. We propose TIGER, an accelerated gradient-sliding method in problem-adapted Bregman geometry. The method applies to constrained non-Euclidean domains, allows the communicated correction term to be nonconvex, and terminates each local subproblem using a computable stationarity residual. Each iteration reuses one synchronized correction gradient during the local solve and makes a second query to construct the composite subgradient for the mirror step. Under relative strong convexity and cocoercivity of the stabilized model error, the communication complexity is O((1+√(δω/μ))log(1/ε)), where μ is the relative strong-convexity parameter and δω is a geometry-adjusted similarity parameter. The analysis recovers the Hessian-similarity rate in Hilbert geometry and provides an explicit finite bound on δω in entropy geometry on a truncated simplex. We also introduce Adaptive TIGER, which selects the stabilization coefficient and the similarity estimate during the run. Under uniform backtracking bounds, the adaptive method has the same asymptotic communication order as fixed-parameter TIGER, including the queries spent on backtracking. Numerical experiments compare Adaptive TIGER with several applicable first-order methods on entropic Wasserstein barycenter problems using the Fashion-MNIST dataset.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in p-norm geometry
- AdamX: Cosine similarity meets gradient descent
- On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
- Accelerated Safe Gradient Flow
BibTeX
@misc{dvinskikh2026tiger,
title = {{TIGER: Tunable-Geometry Accelerated Gradient Sliding with Adaptive Safeguards under Similarity}},
author = {Darina M. Dvinskikh and Anton G. Novitskii and Ewsey R. Obzherin and Alexander V. Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25504},
eprint = {2610.25504},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25504},
}
RIS
TY - UNPB
TI - TIGER: Tunable-Geometry Accelerated Gradient Sliding with Adaptive Safeguards under Similarity
AU - Darina M. Dvinskikh
AU - Anton G. Novitskii
AU - Ewsey R. Obzherin
AU - Alexander V. Gasnikov
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25504
UR - https://arxiv.org/abs/2610.25504
AB - We study distributed composite optimization under function similarity when synchronized gradient queries dominate local computation. We propose TIGER, an accelerated gradient-sliding method in problem-adapted Bregman geometry. The method applies to constrained non-Euclidean domains, allows the communicated correction term to be nonconvex, and terminates each local subproblem using a computable stationarity residual. Each iteration reuses one synchronized correction gradient during the local solve and makes a second query to construct the composite subgradient for the mirror step. Under relative strong convexity and cocoercivity of the stabilized model error, the communication complexity is O((1+√(δ_ω/μ))log(1/ε)), where μ is the relative strong-convexity parameter and δ_ω is a geometry-adjusted similarity parameter. The analysis recovers the Hessian-similarity rate in Hilbert geometry and provides an explicit finite bound on δ_ω in entropy geometry on a truncated simplex. We also introduce Adaptive TIGER, which selects the stabilization coefficient and the similarity estimate during the run. Under uniform backtracking bounds, the adaptive method has the same asymptotic communication order as fixed-parameter TIGER, including the queries spent on backtracking. Numerical experiments compare Adaptive TIGER with several applicable first-order methods on entropic Wasserstein barycenter problems using the Fashion-MNIST dataset.
ER -