More Like this

1. Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems

   https://doi.org/10.1109/Allerton49937.2022.9929349  

   Karabag, Mustafa O.; Fridovich-Keil, David; Topcu, Ufuk (September 2022, 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton))

   Saddle-point problems appear in various settings including machine learning, zero-sum stochastic games, and regression problems. We consider decomposable saddle-point problems and study an extension of the alternating direction method of multipliers to such saddle-point problems. Instead of solving the original saddle-point problem directly, this algorithm solves smaller saddle-point problems by exploiting the decomposable structure. We show the convergence of this algorithm for convex-concave saddle-point problems under a mild assumption. We also provide a sufficient condition for which the assumption holds. We demonstrate the convergence properties of the saddle-point alternating direction method of multipliers with numerical examples on a power allocation problem in communication channels and a network routing problem with adversarial costs. 

   more » « less
2. First-Order Methods for Stochastic Variational Inequality Problems with Function Constraints

   https://doi.org/10.1287/moor.2024.0531  

   Boob, Digvijay; Deng, Qi; Khalafi, Mohammad (January 2026, Mathematics of Operations Research)

   We study monotone function-constrained variational inequalities (FCVIs) whose feasible region is the intersection of a projection-friendly set and several convex function constraints; both the operator and the constraint functions may be smooth, nonsmooth, and/or stochastic. Computing the projection operator is challenging for FCVIs. We introduce the adaptive operator extrapolation (AdOpEx) method, which employs an operator extrapolation on the Karush–Kuhn–Tucker operator of the FCVI in a smooth deterministic setting. Because this operator is not uniformly Lipschitz continuous in the Lagrange multipliers, we employ an adaptive two-timescale algorithm leading to bounded multipliers and achieving the optimal [Formula: see text] convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel P-OpEx method that takes a partial extrapolation. It converges at the rate of [Formula: see text] when both the operator and constraints are stochastic or nonsmooth. This method has suboptimal dependence on the noise and Lipschitz constants of function constraints. We propose a constraint extrapolation approach leading to the OpConEx method that improves this dependence by an order of magnitude. All our algorithms also extend to solving saddle point problems with jointly convex function constraints that couple the primal and dual variables. Within this structured class of problems, our methods preserve their respective complexity guarantees, establishing what we believe to be the first such comprehensive complexity results. Funding: D. Boob and M. Khalafi were partially supported by the National Science Foundation [Grants 2245705 and 2340858]. D. Boob was partially supported by the Office of Naval Research [Grant N000142412749]. Q. Deng was partially supported by the National Natural Science Foundation of China [Grants 12571325 and 72394364/72394360] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300]. 

   more » « less
3. Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent

   Farina, G.; Kroer, C.; Sandholm, T. (January 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Blackwell approachability is a framework for reasoning about repeated games with vector-valued payoffs. We introduce predictive Blackwell approachability, where an estimate of the next payoff vector is given, and the decision maker tries to achieve better performance based on the accuracy of that estimator. In order to derive algorithms that achieve predictive Blackwell approachability, we start by showing a powerful connection between four well-known algorithms. Follow-the-regularized-leader (FTRL) and online mirror descent (OMD) are the most prevalent regret minimizers in online convex optimization. In spite of this prevalence, the regret matching (RM) and regret matching+ (RM+) algorithms have been preferred in the practice of solving large-scale games (as the local regret minimizers within the counterfactual regret minimization framework). We show that RM and RM+ are the algorithms that result from running FTRL and OMD, respectively, to select the halfspace to force at all times in the underlying Blackwell approachability game. By applying the predictive variants of FTRL or OMD to this connection, we obtain predictive Blackwell approachability algorithms, as well as predictive variants of RM and RM+. In experiments across 18 common zero-sum extensive-form benchmark games, we show that predictive RM+ coupled with counterfactual regret minimization converges vastly faster than the fastest prior algorithms (CFR+, DCFR, LCFR) across all games but two of the poker games, sometimes by two or more orders of magnitude. 

   more » « less
4. Primal-Dual Extrapolation Methods for Monotone Inclusions Under Local Lipschitz Continuity

   https://doi.org/10.1287/moor.2024.0407  

   Lu, Zhaosong; Mei, Sanyou (October 2024, Mathematics of Operations Research)

   In this paper, we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone, whereas the other is locally Lipschitz continuous. We propose primal-dual (PD) extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of [Formula: see text] and [Formula: see text], measured by the number of fundamental operations consisting only of evaluations of one operator and resolvent of the other operator, for finding an ε-residual solution of strongly and nonstrongly MI problems, respectively. The latter complexity significantly improves the previously best operation complexity [Formula: see text]. As a byproduct, complexity results of the primal-dual extrapolation methods are also obtained for finding an ε-KKT or ε-residual solution of convex conic optimization, conic constrained saddle point, and variational inequality problems under local Lipschitz continuity. We provide preliminary numerical results to demonstrate the performance of the proposed methods. Funding: This work was partially supported by the National Science Foundation [Grant IIS-2211491], the Office of Naval Research [Grant N00014-24-1-2702], and the Air Force Office of Scientific Research [Grant FA9550-24-1-0343]. 

   more » « less
5. Extracting Dual Solutions via Primal Optimizers

   https://doi.org/10.4230/LIPICS.ITCS.2025.29  

   Carmon, Yair; Jambulapati, Arun; O'Carroll, Liam; Sidford, Aaron (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   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. 

   more » « less