betaFeedback

WorksMathematics

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/ε))O((1+\sqrt{δ_ω/μ})\log(1/\varepsilon)), 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.

Paper details

vlnc:W_r3vff6ur
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Generative AI tools

View statement
Looking for related papers…