PaperlayerView exact revision on arXiv

Source-linked AI summary

Two-Player Games for Efficient Non-Convex Constrained Optimization

Andrew Cotter, Heinrich Jiang, Karthik Sridharan

arXiv:1804.06500v2cs.LGcs.GTmath.OCstat.ML

TL;DR

Non-convex constrained optimization can lack a pure Lagrangian equilibrium, and first-order methods cannot handle non-differentiable constraints. The paper introduces the proxy-Lagrangian, using proxy constraints for one player and original constraints for the other, and proves that the resulting stochastic classifiers can be supported on at most m + 1 models.

  • Problem

    In non-convex settings, Lagrangian optimization may not converge to a pure equilibrium, and first-order methods lack gradients for non-differentiable constraints.

    Source: §1.1 · p. 2

  • Method

    The proxy-Lagrangian uses proxy constraints for the parameter player and original constraints for the multiplier player, with external regret for the former and swap regret for the latter.

    Source: §1.2 · p. 3, §1.3 · p. 4

  • Results

    Both Lagrangian and proxy-Lagrangian stochastic classifiers can be supported on at most m + 1 models, and the proxy formulation's suitable Φ-correlated equilibrium guarantees nearly optimal and nearly feasible solutions in expectation.

    Source: §1.1 · p. 3, §4.1 · p. 10

  • Takeaways & Limitations

    The shrinking procedure makes the stochastic classifier more practical by reducing its support to at most m + 1 models.

    Source: §1.1 · p. 3, §4.1 · p. 10

    Whether the original constraints generalize from training data to evaluation time is outside the paper's scope.

    Source: §2.1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper examines non-convex constrained optimization, where fairness constraints may be data-dependent and non-differentiable. It develops Lagrangian and proxy-Lagrangian game formulations whose stochastic classifiers can be reduced to at most m + 1 models.

1 Introduction

  • Fairness constraints such as the 80% rule can be data-dependent, non-convex, and non-subdifferentiable, complicating first-order optimization.The example requires at least 80% of positive predictions to fall on a minority population.Source: §1 · p. 2

1.1 Dealing with non-Convexity

  • Without strong duality, the Lagrangian game may lack a pure Nash equilibrium, while mixed equilibria yield stochastic classifiers supported on at most m + 1 models.Here m is the number of constraints; the multiplier can be non-random.Source: §1.1 · pp. 2–3

1.2 Introducing Proxy Constraints

  • The proxy-Lagrangian lets the parameter player use smooth upper-bound proxy constraints while the multiplier player uses original constraints to enforce feasibility.A Φ-correlated equilibrium can yield a nearly optimal and nearly feasible solution in expectation; finding a mixed Nash equilibrium in these non-zero-sum games is PPAD-complete even in finite settings.Source: §1.2 · pp. 3–4

1.3 Contributions

  • The paper provides regret-based algorithms and a shrinking procedure that reduces proxy-Lagrangian and standard Lagrangian stochastic classifiers to at most m + 1 models.The end-to-end recipe can use SGD in practice instead of an optimization oracle.Source: §1.3 · p. 4

2 Related Work

Prior work casts constrained optimization as a two-player game, while this paper situates its approach among related fair-classification and robust-optimization methods. Alternative approaches face difficulties with complex, non-differentiable, or data-dependent constraints, and training-time feasibility does not ensure evaluation-time feasibility.

2 Related Work

  • Agarwal et al. [2018] use a similar Lagrangian game for fair classification, while Chen et al. [2017] address non-convex robust optimization.The paper identifies shrinking and a more general problem setting as differences from Agarwal et al. [2018].Source: §2 · p. 4
  • The paper's shrinking procedure and proxy objectives can extend to robust optimization, including non-differentiable losses, with an extra bisection search when transforming robust problems to constrained ones.The shrinking procedure yields a distribution over at most m + 1 solutions.Source: §2 · p. 4

2.1 Alternative Approaches

  • Projection and constrained-subproblem methods can be ruled out by complex constraints, while penalizing violations can require non-differentiable optimization or full-dataset evaluation.These requirements make penalized formulations incompatible with computationally cheap stochastic optimization.Source: §2.1 · p. 5
  • Satisfying un-relaxed constraints on training data does not necessarily ensure that they hold at evaluation time, a generalization issue the paper leaves outside its scope.The passage points to post-training correction approaches for certain applications and says further work remains.Source: §2.1 · p. 5

3 Starting Point: Lagrangian Optimization

The Lagrangian game connects approximate equilibria to nearly optimal, feasible solutions in expectation, using an approximate optimization oracle. A linear program can then shrink the resulting mixture to at most m + 1 models.

3 Starting Point: Lagrangian Optimization

  • If a point satisfies every constraint with margin γ, sufficiently large multiplier-radius choices can guarantee feasibility to within O(ε).The feasibility guarantee depends on the average multiplier norm staying below the maximum radius R.Source: §3 · p. 6
  • The proposed Lagrangian algorithm uses an approximate Bayesian optimization oracle for the θ-player and projected gradient ascent for the λ-player.The oracle provides an additive approximation for nonnegative linear combinations of the objective and constraints.Source: §3 · p. 6
  • With sufficiently large R, Algorithm 1 yields a distribution that is O(ρ)-far from optimality and feasibility at an O(1/T) rate.Here ρ is the error of the approximate Bayesian optimization oracle.Source: §3 · p. 7

3.1 Shrinking

  • An optimal feasible mixture of candidate iterates can be found by linear programming, with every optimal vertex supported on at most m + 1 iterates.The bound follows from the number of active constraint inequalities in the LP.Source: §3.1 · p. 7
  • The LP-selected distribution is no worse than the uniform mixture over the iterates and shrinks its support to at most m + 1 models.A mixed Nash equilibrium with θ supported on at most m + 1 elements also exists under the stated compactness and continuity conditions.Source: §3.1 · p. 7

4 Proxy-Lagrangian Optimization

The proxy-Lagrangian uses smooth proxy constraints for the θ-player while the λ-player enforces the original constraints. Regret-based methods yield a stochastic classifier, and the equilibrium can be shrunk to at most m + 1 models.

4 Proxy-Lagrangian Optimization

  • The proxy-Lagrangian uses a weaker Φ-correlated equilibrium, with external regret for the θ-player and swap regret for the λ-player, to obtain a nearly optimal and feasible solution in expectation.The θ-player compares against its best constant strategy, while the λ-player compares against its best action-swapping strategy.Source: §4 · pp. 8–9
  • The proxy-Lagrangian guarantee compares against feasibility under the proxy constraints, but its larger original-constraint feasible region may leave more room for a better practical solution.The passage says this potential practical advantage is demonstrated experimentally in Section 6.2.Source: §4 · p. 9
  • Algorithm 2 uses SGD for θ-updates in the convex setting, except that the original constraint functions need not be convex; an oracle-based alternative can avoid the convexity requirement.The paper gives the convex-setting algorithm because proxy constraints are intended to replace constraints that are difficult to optimize.Source: §4 · pp. 9–10

4.1 Shrinking

  • Under the stated compactness and continuity conditions, a proxy-Lagrangian mixed Nash equilibrium exists with θ supported on at most m + 1 models.The same linear-programming procedure, defined using original constraints, yields a support size of m + 1.Source: §4.1 · p. 10

5 Overall Procedure

The procedure first generates an approximately feasible and optimal distribution over candidate models, then uses a linear program to shrink it without losing its guarantees. In practice, non-convex SGD provides candidates without guarantees, and the final distribution defines a stochastic classifier.

5 Overall Procedure

  • The second phase evaluates each candidate’s objective and constraints, then uses an LP to select a distribution supported on at most m+1 models.Choosing the LP tolerance from the applicable theorem’s bound preserves the original guarantees.Source: §5 · p. 10
  • In the first phase, an appropriate algorithm produces a distribution over candidates that is approximately feasible and optimal under the applicable theorem.The approach covers convex and non-convex problems, with or without proxy constraints.Source: §5 · p. 10
  • For non-convex problems, practical SGD has no guarantees; its candidate set must contain enough good solutions for the LP to select from.The procedure proposes bisection to choose the smallest feasible LP tolerance and allows subsampling an overly large candidate set.Source: §5 · p. 10
  • For classification, the resulting distribution is a stochastic classifier; its small support makes heuristic conversion to a deterministic classifier easier.At evaluation, the classifier samples a model and returns its prediction; weighted averaging or voting are suggested alternatives.Source: §5 · p. 10

6 Experiments

The experiments test the practical procedure on robust MNIST optimization and proxy-Lagrangian fairness constraints on UCI Adult. The reported results compare model performance, constraint satisfaction, and the effect of shrinking.

6 Experiments

  • Across both experiments, the algorithms produced stochastic classifiers, and results included both theorem-based classifiers and LP-optimized distributions.For the LP distributions, optimization was performed on the training dataset.Source: §6 · p. 11

6.1 Robust Optimization

  • The robust experiment used four corrupted MNIST datasets, cross-entropy objectives, and a neural network; baselines trained on the union of the datasets.The compared baselines were a uniform distribution over iterates and the last iterate; models ran for 50,000 iterations with 100-example minibatches.Source: §6.1 · pp. 11–12
  • The LP-shrunk robust model and the other proposed algorithm both outperformed their natural baseline equivalents, while shrinking simplified the model and improved performance.The Lagrangian LP selected one model in these experiments, making it non-stochastic; the authors report not quite matching Chen et al.’s raw performance.Source: §6.1 · p. 12

6.2 Equal Opportunity

  • The fairness experiment used UCI Adult census data and linear models, minimizing average hinge loss subject to one 95% equal-opportunity constraint per protected class.Proxy constraints replaced rate indicators with hinge upper bounds; the non-proxy version used those upper bounds throughout instead of the indicator-based constraints.Source: §6.2 · p. 12
  • Fairness LP models uniformly outperformed their corresponding average-classifier versions, while proxy-Lagrangian LP slightly violated test constraints but matched the unconstrained baseline’s classification performance.The non-proxy algorithms satisfied train and test constraints, but their conservative relaxed constraints significantly damaged classification performance.Source: §6.2 · pp. 12–13

A Proofs of Sub{optimality,feasibility} Guarantees

The proofs establish suboptimality and feasibility guarantees for the Lagrangian and proxy-Lagrangian formulations. The proxy-Lagrangian optimality comparison is with respect to proxy constraints, rather than the original constraints.

Lagrangian guarantees

  • Theorem 3’s feasibility proof derives its claim by rearranging a bound after applying dual-norm reasoning and Hölder’s inequality.Its optimality proof chooses an optimal feasible comparator and sets the comparator multiplier to zero.Source: A Proofs of… · p. 16

Proxy-Lagrangian guarantees

  • The proxy-Lagrangian proof identifies the resulting pair as an approximate Nash equilibrium, then derives suboptimality and feasibility claims.The optimality comparator is optimal for the proxy constraints, so the guarantee is not a comparison to the optimum under the original constraints.Source: A Proofs of… · pp. 16–18

Lagrangian guarantees

  • The Lagrangian margin lemma assumes a feasible solution with q-norm constraint margin and a bounded objective range.The supplied proof excerpt concludes that this assumption yields the lemma’s claim.Source: A Proofs of… · pp. 16–17

Proxy-Lagrangian guarantees

  • The proxy-Lagrangian margin lemma assumes a solution satisfying every proxy constraint with margin γ and a bounded objective range.The proof uses that proxy-feasible margin to bound the multiplier quantity.Source: A Proofs of… · p. 18

B Proofs of Existence of Sparse Equilibria

The existence results show that sparse equilibria can represent both Lagrangian formulations, and that the candidate-selection LP has an optimal sparse solution. The support bound is at most m+1 models.

Lagrangian equilibrium

Proxy-Lagrangian equilibrium

  • Under continuity of the objective, constraint, and proxy-constraint functions, the proxy-Lagrangian game likewise has an equilibrium with θ supported on at most m+1 models and non-random λ.The proof applies the game result in the m-dimensional space of the last m multiplier coordinates.Source: B Proofs of Existence of Sparse… · pp. 19–20

Candidate-selection LP

  • Every optimal vertex of the candidate-selection LP has at most m*+1 nonzero weights, hence at most m+1, where m* counts active functional constraints.The sparsity follows from the LP’s active constraints together with its simplex constraints.Source: B Proofs of Existence of Sparse… · p. 20

C.1 Non-Stochastic One-Player Convergence Rates

This section presents one-player convergence results for convex optimization, including Euclidean gradient descent and mirror descent. It also adapts mirror descent to stochastic-matrix optimization and stationary-distribution-based simplex optimization.

C.1 Non-Stochastic One-Player Convergence Rates

  • Mirror descent treats convex losses on a compact convex set using a strongly convex distance-generating function and compares iterates with an arbitrary reference vector.The update uses subgradients and the associated Bregman divergence.Source: §C.1 · pp. 20–21
  • Gradient descent specializes the convex optimization setup to Euclidean projections and subgradients, with an arbitrary reference vector for comparison.Source: §C.1 · p. 21
  • For left-stochastic matrices, the mirror-descent update is element-wise multiplicative, using negative Shannon entropy as its regularizer.Projection onto the matrix set amounts to normalizing columns under KL divergence; the regularizer is strongly convex in the L1,2 norm.Source: §C.1 · pp. 21–22
  • A left-stochastic matrix supplies a stationary distribution that connects optimization over the simplex to matrix optimization.The stated argument uses Mλ = λ to recover the simplex guarantee from the matrix formulation.Source: §C.1 · pp. 22–23

C.2 Stochastic One-Player Convergence Rates

The section extends one-player convergence results to stochastic subgradients and supergradients. Its guarantees use high-probability bounds, with the matrix and simplex cases handled through stochastic mirror-descent variants.

C.2 Stochastic One-Player Convergence Rates

  • Stochastic mirror descent gives high-probability guarantees for convex losses using stochastic subgradients and the mirror-descent setup.The proof uses Hoeffding-Azuma to control the stochastic terms.Source: §C.2 · pp. 23–24
  • The stochastic and non-stochastic procedures can produce the same iterates when the stochastic update is applied to the underlying losses.The proof treats the difference terms as a martingale and bounds them using Hoeffding-Azuma.Source: §C.2 · pp. 23–24
  • Stochastic gradient descent specializes the result to Euclidean projections and stochastic subgradients, with probability at least 1 − δ.Source: §C.2 · p. 24
  • For concave functions on left-stochastic matrices, the stochastic mirror-descent guarantee uses stochastic supergradients and a stationary distribution.The update starts from a uniform matrix, and the simplex result follows using Mλ = λ.Source: §C.2 · p. 25

C.3 Two-Player Convergence Rates

This section gives convergence guarantees for two-player Lagrangian and proxy-Lagrangian algorithms. The guarantees distinguish convex Lagrangian optimization from proxy-Lagrangian optimization, which assumes convexity of the objective and proxy constraints rather than the original constraints.

C.3 Two-Player Convergence Rates

  • Algorithm 3 optimizes the Lagrangian in the convex setting, with a stochastic convergence guarantee under convex objective and constraint functions.The algorithm uses projected updates for the model parameters and multipliers.Source: §C.3 · p. 26
  • Algorithm 4 uses an approximate Bayesian optimization oracle for the θ-player and has the λ-player minimize swap regret.The λ update uses a stationary distribution of the current left-stochastic matrix.Source: §C.3 · p. 27
  • The proxy-Lagrangian guarantee includes the oracle error ρ, and its stochastic version holds with probability 1 − δ.Source: §C.3 · p. 27
  • Algorithm 2's proxy-Lagrangian guarantee requires convex objective and proxy constraints, but not convex original constraints.The result is stated for a compact convex parameter set and bounded quantities.Source: §C.3 · p. 27
Loading 1804.06500v2…