A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type
ACM / IMS Journal of Data Science · 2025
DOI: 10.1145/3728480 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM / IMS Journal of Data Science, 2025. Verfasst von Jelena Diakonikolas. Die Arbeit nennt 74 Literaturangaben. Gefördert von: Air Force Office of Scientific Research, U.S. Office of Naval Research.
Abstract (Originalsprache)
Block coordinate methods have been extensively studied for minimization problems, where they come with significant complexity improvements whenever the considered problems are compatible with block decomposition and, moreover, block Lipschitz parameters are highly nonuniform. For the more general class of variational inequalities with monotone operators, essentially none of the existing methods transparently shows potential complexity benefits of using block coordinate updates in such settings. Motivated by this gap, we develop a new randomized block coordinate method and study its oracle complexity and runtime. We prove that in the setting where block Lipschitz parameters are highly nonuniform—the main setting in which block coordinate methods lead to high complexity improvements in any of the previously studied settings—our method can lead to complexity improvements by a factor order- m , where m is the number of coordinate blocks. The same method further applies to the more general problem with a finite-sum operator with m components, where it can be interpreted as performing variance reduction. Compared to the state-of-the-art, the method leads to complexity improvements up to a factor \(\sqrt {m},\) obtained when the component Lipschitz parameters are highly nonuniform.
Förderung
- Air Force Office of Scientific Research
- U.S. Office of Naval Research
Zitieren
APA
Diakonikolas, J. (2025). A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type. ACM / IMS Journal of Data Science. https://doi.org/10.1145/3728480
Vancouver
Diakonikolas J. A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type. ACM / IMS Journal of Data Science. 2025. doi:10.1145/3728480
BibTeX
@article{Diakonikolas2025,
author = {Diakonikolas, Jelena},
title = {A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type},
journal = {ACM / IMS Journal of Data Science},
year = {2025},
doi = {10.1145/3728480}
}
EUVIMED