Two-Player Games for Efficient Non-Convex Constrained Optimization

By Andrew Cotter, Heinrich Jiang, Karthik Sridharan. 2018

137 citations recorded by the source corpus.

In recent years, constrained optimization has become increasingly relevant to the machine learning community, with applications including Neyman-Pearson classification, robust optimization, and fair machine learning. A natural approach to constrained optimization is to optimize the Lagrangian, but this is not guaranteed to work in the non-convex setting, and, if using a first-order method, cannot cope with non-differentiable constraints (e.g. constraints on rates or proportions). The Lagrangian can be interpreted as a two-player game played between a player who seeks to optimize over the model parameters, and a player who wishes to maximize over the Lagrange multipliers. We propose a non-zero-sum variant of the Lagrangian formulation that can cope with non-differentiable--even discontinuous--constraints, which we call the "proxy-Lagrangian". The first player minimizes external regret in terms of easy-to-optimize "proxy constraints", while the second player enforces the original constraints by minimizing swap regret. For this new formulation, as for the Lagrangian in the non-convex setting, the result is a stochastic classifier. For both the proxy-Lagrangian and Lagrangian formulations, however, we prove that this classifier, instead of having unbounded size, can be taken to be a distribution over no more than m+1 models (where m is the number of constraints). This is a significant improvement in practical terms.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Beyond Individual and Group Fairness (2020, background): “These publications either reduce the problem to that of cost-sensitive classification [Agarwal et al., 2018, Dwork et al., 2018] or replace the non-convex constraints by convex proxies and next optimize them via external or swap regret minimization algorithms [Cotter et al., 2018b,a].”
Wasserstein Fair Classification (2019, methodology): “Some methods transform the constrained optimization problem via the method of Lagrange multipliers (Agarwal et al., 2018; Corbett-Davies et al., 2017; Cotter et al., 2018; Goh et al., 2016; Narasimhan, 2018; Wu et al., 2018; Zafar et al., 2017).”
Characterizing Fairness Over the Set of Good Models Under Selective Labels (2021, methodology): “[45] Andrew Cotter, Heinrich Jiang, and Karthik Sridharan.”
Pairwise Fairness for Ranking and Regression (2019, methodology): “Cotter et al. [2019a] use a no-regret optimization strategy for minimization over the model parameters, and a swapregret optimization strategy for maximization over λ, with the indicators I replaced with hinge-based surrogates for the first player only.”
Equal Opportunity in Online Classification with Partial Feedback (2019, methodology): “3) Finally, we follow an approach similar to that of [10] to shrink the support size of the solution returned by the fair classiﬁcation algorithm down to at most 2, which can be done in polynomial time.”
User-oriented Fairness in Recommendation (2021, background): “[12, 31, 40, 44] and ranking tasks [8, 38, 39, 43], etc.”
FairBatch: Batch Selection for Model Fairness (2020, methodology): “, 2020; Jiang & Nachum, 2020), which debias or reweight data, (2) in-processing techniques (Kamishima et al., 2012; Zafar et al., 2017a;b; Agarwal et al., 2018; Zhang et al., 2018; Cotter et al., 2019; Roh et al., 2020), which tailor the model training for fairness, and (3) postprocessing techniques”
Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints (2018, methodology): “The optimality and feasibility goals were already tackled by Cotter et al. [2018] in the context of the proxy-Lagrangian formulation of Definition 1.”
Identifying and Correcting Label Bias in Machine Learning (2019, methodology): “In the non-convex case, there is work which frames the constrained optimization problem as a two-player game (Kearns et al., 2017; Agar-wal et al., 2018; Cotter et al., 2018b) .”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “The follow-up work [29, 120] have improved this approach using the surrogate relaxations for the primal updates.”
Fairness in Machine Learning (2020, methodology): “Some methods transform the constrained optimization problem via the method of Lagrange multipliers [3, 15, 34, 37, 38, 59, 97, 135, 183, 185] or add penalties to the objective [5, 14, 22, 44, 46, 56, 58, 62, 73, 74, 75, 79, 82, 87, 88, 89, 93, 94, 95, 98, 104, 115, 119, 123, 133, 134, 135, 138, 139,”