EUVIMEDEUVIMED entdecken
Crossref

A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type

Jelena Diakonikolas

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →