AISTATS 2025 Papers

Stochastic compositional minimax problems are prevalent in machine learning, yet there exist only limited established findings on the convergence of this class of problems. In this paper, we propose a formal definition of the stochastic compositional minimax problem, which involves optimizing a minimax loss with a compositional structure either in primal, dual, or both primal and dual variables. We introduce a simple yet effective algorithm, stochastically Corrected stOchastic gradient Descent Ascent (CODA), which is a primal-dual type algorithm with compositional correction steps, and establish its convergence rate in the aforementioned three settings. We also propose a variance reduced variant, CODA+, which achieves the best-known rate on nonconvex-strongly-concave and nonconvex-concave compositional minimax problems. This work initiates the theoretical study of the stochastic compositional minimax problem in various settings and may inform modern machine learning scenarios such as domain adaptation or robust model-agnostic meta-learning.

Acyclic directed mixed graphs (ADMG) – graphs that contain both directed and bidi- rected edges but no directed cycles – are used to model causal and conditional independence relationships between a set of random vari- ables in the presence of latent or unmeasured variables. Bow-free ADMGs, Arid ADMGs, and Ancestral ADMGs (AADMG) are three widely studied classes of ADMGs where each class is contained in the previously mentioned class. There are a number of published meth- ods – primarily heuristic ones – to find score- maximizing AADMGs from data. Bow-free and Arid ADMGs can model certain equal- ity restrictions – such as Verma constraints – between observed variables that maximal AADMGs cannot. In this work, we develop the first exact methods – based on integer programming – to find score-maximizing Bow- free and Arid ADMGs. Our methods work for data that follows a continuous Gaussian distri- bution and for scores that linearly decompose into the sum of scores of c-components of an ADMG. To improve scaling, we develop an effective linear-programming based heuris- tic that yields solutions with high parent set sizes and/or large districts. We show that our proposed algorithms obtain better scores than other state-of-the-art methods and re- turn graphs that have excellent fits to data.