Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities

Abstract

Second-order methods for smooth monotone variational inequalities reach the optimal rate O(T^−3/2), but a distributed exact Jacobian costs d times more communication than an operator value. We show that similarity does part of the work for free: if the server's Jacobian differs from the global one by at most β, using it gives O(L₁D³T^−3/2+βD²T⁻¹) at first-order communication cost. A quasi-Newton approximation of the residual Jacobian ∇ F−∇ F₁, built from secants already communicated, improves the model but cannot remove the T⁻¹ term, because any uniform bound on the Jacobian error leaves it in the rate. We therefore certify the surrogate only along the candidate step: one Jacobian-vector product tests it, and a failed test is reused as an exact correction. This attains the exact rate O(L₁D³T^−3/2) while transmitting only vectors. Experiments on LIBSVM and synthetic instances measure accuracy against communication.

Residual Feedback for Transformed-State Equilibrium Seeking via General Variational Inequalities
Griffin Smith, Afrooz Jalilzadeh
arXiv28 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Optimal High-Order Methods for Solving Monotone Variational Inequalities
Xinliang Zhang, Lesi Chen, Linxuan Pan +3
arXiv20 Sep 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Extragradient and Past Extragradient Methods for (L₀,L₁)-Lipschitz Variational Inequalities
Ezra Greenberg, Nicolas Loizou
arXiv12 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Parameter-Free Adaptive Extragradient Methods for Generalized-Smooth Variational Inequalities
Zhaoyang Chu, Hongwei Liu, Yakui Huang
arXiv10 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds
Yonghong Yao, Lateef O. Jolaoso, Yekini Shehu +1
arXiv26 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{obzherin2026certified,
  title = {{Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities}},
  author = {Ewsey R. Obzherin and Roman M. Mozhaev and Alexander V. Gasnikov and Martin Takáč and Artem A. Agafonov and Dmitry I. Kamzolov},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.22481},
  eprint = {2609.22481},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.22481},
}

RIS

TY  - UNPB
TI  - Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities
AU  - Ewsey R. Obzherin
AU  - Roman M. Mozhaev
AU  - Alexander V. Gasnikov
AU  - Martin Takáč
AU  - Artem A. Agafonov
AU  - Dmitry I. Kamzolov
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.22481
UR  - https://arxiv.org/abs/2609.22481
AB  - Second-order methods for smooth monotone variational inequalities reach the optimal rate O(T^−3/2), but a distributed exact Jacobian costs d times more communication than an operator value. We show that similarity does part of the work for free: if the server's Jacobian differs from the global one by at most β, using it gives O(L_1D^3T^−3/2+βD^2T^−1) at first-order communication cost. A quasi-Newton approximation of the residual Jacobian ∇ F−∇ F_1, built from secants already communicated, improves the model but cannot remove the T^−1 term, because any uniform bound on the Jacobian error leaves it in the rate. We therefore certify the surrogate only along the candidate step: one Jacobian-vector product tests it, and a failed test is reused as an exact correction. This attains the exact rate O(L_1D^3T^−3/2) while transmitting only vectors. Experiments on LIBSVM and synthetic instances measure accuracy against communication.
ER  -

Abstract

Related

Cite