2026-07-20T04:49:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22657 2026-04-17T05:31:56Z ddc:004 open_access

Extracting Dual Solutions via Primal Optimizers Carmon, Yair Jambulapati, Arun O'Carroll, Liam Sidford, Aaron Minimax optimization black-box optimization matrix games distributionally robust optimization We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yair Carmon and Arun Jambulapati and Liam O'Carroll and Aaron Sidford 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.29 urn:nbn:de:0030-drops-226578 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode