Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals

Andrew Cotter; Heinrich Jiang; Serena Wang; Taman Narayan; Maya Gupta; Seungil You; Karthik Sridharan

Source-linked AI summary

Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals

Andrew Cotter, Heinrich Jiang, Serena Wang, Taman Narayan, Maya Gupta, Seungil You, Karthik Sridharan

arXiv:1809.04198v1Sep 11, 2018cs.LGcs.AIcs.GTmath.OCstat.ML

TL;DR

Training nonlinear models with rate constraints is challenging because the constraints can be non-convex, non-differentiable, and data-dependent. The paper develops proxy-Lagrangian game-based methods and reports generally better empirical optimization and test metrics for its 0-1 formulation, while sparsifying stochastic solutions effectively.

Problem
Rate-constraint training can involve non-convex objectives and constraints, non-differentiable indicator functions, and expensive data-dependent evaluations.
Method
The paper uses Lagrangian and proxy-Lagrangian formulations, two-player games, equilibrium procedures, and shrinking to optimize constrained problems and produce sparse stochastic solutions.
Results
The 0-1 non-zero-sum formulation generally improves train and test metrics, while T-stochastic solutions can be sparsified to m-stochastic solutions with generally improved metrics.
Takeaways & Limitations
The study provides theoretical, algorithmic, and experimental guidance for applying broad rate constraints to real-world classifier objectives.
Takeaways & Limitations
The theoretical guarantees depend on regret-minimization rates, including O(√m log m) dependence on the number of constraints.

Abstract

from arXiv · show

We show that many machine learning goals, such as improved fairness metrics, can be expressed as constraints on the model's predictions, which we call rate constraints. We study the problem of training non-convex models subject to these rate constraints (or any non-convex and non-differentiable constraints). In the non-convex setting, the standard approach of Lagrange multipliers may fail. Furthermore, if the constraints are non-differentiable, then one cannot optimize the Lagrangian with gradient-based methods. To solve these issues, we introduce the proxy-Lagrangian formulation. This new formulation leads to an algorithm that produces a stochastic classifier by playing a two-player non-zero-sum game solving for what we call a semi-coarse correlated equilibrium, which in turn corresponds to an approximately optimal and feasible solution to the constrained optimization problem. We then give a procedure which shrinks the randomized solution down to one that is a mixture of at most $m+1$ deterministic solutions, given $m$ constraints. This culminates in algorithms that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints with theoretical guarantees. We provide extensive experimental results enforcing a wide range of policy goals including different fairness metrics, and other goals on accuracy, coverage, recall, and churn.

1. Introduction

The paper formulates many practical goals as rate constraints and develops methods for optimizing non-convex objectives with non-differentiable, data-dependent constraints. Its proxy-Lagrangian approach provides theoretically guaranteed sparse stochastic classifiers for these problems.

Broad applicability of rate constraints: Many real-world goals, including fairness, accuracy, recall, precision, coverage, churn, and multi-dataset training objectives, can be expressed as rate constraints.Examples include statistical parity, equal opportunity, equal odds, slice-specific accuracy or recall, and constrained churn.
Why constraints: Penalty methods require selecting weights whose interactions can be unexpected, whereas hard constraints give each goal an absolute meaning independent of other constraints.The paper gives 80% recall in India as an example of a constraint whose meaning does not depend on how many other constraints are present.
Training with constraints: Rate-constrained training is challenging because objectives and constraints may be non-convex, non-differentiable, and expensive to evaluate on data.Rate constraints use indicator functions and depend on potentially large constraint datasets.
Optimization framework: The paper develops stochastic-equilibrium methods that correspond to nearly feasible and nearly optimal solutions for the original constrained optimization problem.The randomized model samples a model parameter from a distribution over candidate parameters.
Proxy-Lagrangian: The proxy-Lagrangian relaxes non-differentiable constraints only when necessary and yields algorithms with optimality and feasibility guarantees on the original constraints.The end-to-end procedure returns a mixture of at most m + 1 deterministic solutions, with m denoting the number of constraints.

2. Related Work

Prior work studied specific rate constraints and two-player formulations, while this paper develops a broader proxy-Lagrangian approach for non-differentiable, non-convex constraints and sparse stochastic solutions.

Prior rate-constraint work: Earlier work expressed fairness, low-churn retraining, and recall lower bounds as constraints on classifier decisions, but its algorithm was limited to linear classifiers.The earlier cutting-plane method upper-bounded ramp loss with a convex loss and used SVM solvers, making it slow and difficult to scale beyond a handful of constraints.
Rate constraints and fairness: Fairness-constraint research used two-player games and stochastic classifiers, but assumed zero-sum games or oracle solvers and did not provide the sparse m+1 solution developed here.Grid-searching over λ for deterministic solutions becomes less suitable as the number of constraints grows.
Scope of rate constraints: Rate constraints are prediction-rate restrictions that can encode goals including statistical parity, accuracy or recall bounds, precision, and AUC approximations.They differ from shape or parameter constraints because they generally depend on every model parameter and can be expensive to compute.
Two-player constrained optimization: This paper extends two-player constrained optimization with a shrinking procedure, a proxy-Lagrangian non-zero-sum formulation, and support for any problem represented by its constraint form.The approach targets non-differentiable constraints without relying on the zero-sum assumption used in prior work.
Robust optimization: The paper also connects constrained and robust optimization, showing that its shrinking procedure and non-differentiable optimization ideas can transfer through a slack-variable reformulation.This transfer can require an additional bisection search.
Alternative optimization strategies: Existing alternatives include projected methods and violation penalties, but data-dependent, non-differentiable rate constraints make projection and first-order penalty optimization poorly matched to the problem.Penalty methods may require enumerating an entire constraint dataset even to determine whether a constraint is violated.

3. How To Use Rate Constraints

Rate constraints express prediction-rate requirements over selected datasets, allowing practitioners to encode coverage, performance, fairness, churn, and decision-rule goals during training.

Rate-constraint formulation: Rate constraints combine positive and negative classification rates across datasets to impose upper or lower bounds on model behavior.They can be added to structural risk minimization as m constraints, with coefficients, datasets, and bounds specifying each constraint.
Performance and fairness goals: Rate constraints can represent accuracy, recall, precision, win-loss ratio, AUC approximations, churn, and group-specific fairness goals.The paper notes generalization caveats for precision and win-loss ratio, because constraints on ratios do not straightforwardly transfer to i.i.d. test samples.
Coverage constraints: Coverage constraints control the proportion of positive or negative predictions and can encode prior knowledge on full datasets or specific slices.Examples include predicting 10% of customers positively, enforcing 51% female predictions overall, or imposing different state-specific rates.
Coverage constraints: Because coverage constraints require no labels, they can combine labeled training data from one distribution with unlabeled data representing the desired deployment distribution.This creates a simple semi-supervised use of constraints while targeting a specified positive-class proportion.
Performance and fairness goals: Group-specific constraints support fairness objectives such as equal positive rates, while also expressing practical goals including no lost benefits and steering examples.Steering examples are more accurately labeled auxiliary examples used to constrain behavior when the main training set is noisy or less reliable.

4. Optimizing with Constraints

Non-convex constrained training can be handled through a game-based Lagrangian approach that produces approximately feasible and optimal stochastic classifiers, then compresses their support.

Problem setting: For nonlinear function classes, rate-constrained training is non-convex over a non-convex constraint set.The paper develops algorithms and theory for this setting rather than relying on convex constrained optimization.
Minimal stochastic solution: A shrinking procedure converts a stochastic classifier supported on T iterates into one supported on at most m+1 models without worsening its objective or feasibility.The reduction follows from solving a linear program over candidate objective and constraint values.
Lagrangian optimization: A regret-based procedure alternates approximate best responses from the model-parameter player with regret minimization by the Lagrange-multiplier player.The parameter player uses an approximate Bayesian optimization oracle, while the multiplier player uses projected gradient ascent.
Lagrangian optimization: The resulting stochastic classifier is provably approximately feasible and optimal in expectation under the stated oracle and domain assumptions.The convergence guarantee is O(ρ)-far from optimal and feasible at an O(1/√T) rate when R is sufficiently large.
Assumptions and guarantees: The feasibility guarantee depends on bounded multiplier radius and is ensured to within O(ϵ) when a strictly feasible point exists with margin γ and R is sufficiently large.The theorem also assumes compact domains and an approximate optimization oracle for the parameter player.

4.2 Proxy Constraints and a Non-Zero Sum Game

Proxy constraints make non-differentiable rate-constrained optimization compatible with gradient-based model updates while retaining feasibility guarantees for the original constraints.

Motivation: Rate constraints are piecewise-constant because they contain indicators, so their gradients are zero almost everywhere and ordinary gradient methods cannot reliably optimize them.Non-differentiable constraints arise naturally when constraining counts or proportions.
Proxy constraints: Using a surrogate for both players would enforce the relaxed constraints rather than the original ones, so the paper uses a proxy only for the model-parameter player.The multiplier player continues evaluating the original constraint functions.
Proxy-Lagrangian game: The proxy-Lagrangian forms a non-zero-sum game with separate payoffs: the parameter player minimizes a smooth proxy objective, while the multiplier player maximizes a payoff based on original constraints.The multiplier player weights proxy constraints but chooses those weights to satisfy the original constraints.
Equilibrium and algorithm: The algorithm targets a semi-coarse correlated equilibrium, where the parameter player competes with constant strategies and the multiplier player with action-swapping strategies.This weaker equilibrium concept is presented as achievable for the non-zero-sum formulation and yields stochastic solutions with guarantees.
Guarantees: The proxy-Lagrangian guarantees feasibility for original constraints while optimizing approximately against the best solution feasible for the proxy constraints.Compared with relaxing both players’ constraints, it can have more room to find better solutions because the original feasible region is larger.

4.4 Proxy-Lagrangian Optimization Algorithm

The proxy-Lagrangian algorithm uses distinct regret-minimization strategies for model and multiplier players, yielding convergence guarantees and sparse stochastic solutions.

The θ-player minimizes external regret using an oracle, while the λ-player minimizes swap regret.
The convergence analysis states conditions under which the regret-based sequences satisfy Theorem 2’s guarantees.The supplied passages introduce Lemma 4 and Lemma 5 as the relevant convergence results.
Algorithm 3 replaces the θ-player’s oracle with SGD when the objective and proxy-constraints are convex, while original constraints may remain non-convex.This provides a more practical procedure while retaining optimality and feasibility guarantees.
Algorithms 2 and 3 return stochastic solutions supported on T iterates, which can be reduced to at most m + 1 deterministic solutions.The same linear-programming shrinking procedure applies using the original constraints.

5. Experiments

The experiments evaluate rate-constrained optimization across datasets, model classes, constraint types, and algorithmic variants. Results examine feasibility, predictive performance, stochastic solutions, and practical hyperparameter selection.

Research questions: The experiments investigate whether rate constraints improve practice, interact with other constraints, and are better solved by the proxy-Lagrangian.They also test hinge over-constraint, swap versus external regret, stochastic classifiers, and last-iterate behavior.
Experimental setup: The study compares twelve optimization algorithms across seven datasets using linear models, two-layer ReLU neural networks, and calibrated random tiny lattices.Datasets are randomly split into training, validation, and test sets.
Hyperparameter optimization: Hyperparameter selection must balance validation accuracy against constraint violation rather than optimize a single metric.The chosen strategy selects a setting with low loss and small violations while avoiding a jointly better validation alternative.
Algorithms: The four algorithm groups are unconstrained, hinge-relaxed, 0-1 swap-regret, and 0-1 external-regret optimization.The 0-1 swap method uses the proxy-Lagrangian with swap regret for λ and external regret for θ.
Algorithms: The evaluated solution types include the uniform T-iterate stochastic classifier, an m + 1-support stochastic classifier, and the last iterate.The m-stochastic solution is obtained by shrinking the T-stochastic solution on the training set.
Results: Across the thresholding experiment, noisy-data training has 35% noisy-test error and 36% steering-example error, while steering-only training has 39% noisy-test error.Training with a 67% steering-example accuracy constraint produced essentially feasible solutions, often matching or improving unconstrained test performance.
Results: The unconstrained entity-resolution model reaches 27.61% test error but has 32.27% maximum test constraint violation across ten regions.The production classifier’s test error rate was 39.72%, while the constrained goal concerned preserving wins across regions.

6. Discussion of Experimental Results

Across experiments, m-stochastic and best-iterate procedures generally reduced constraint violations while retaining reasonable error, though generalization and method comparisons varied.

The 0-1 swap-regret m-stochastic method consistently lowered training violations while maintaining reasonable training error across experiments.For Adult, violation fell from .0803 to .0176 with training error only .001 worse; Bank Marketing fell from .0202 to 0.0.
The m-stochastic and best-iterate solutions produced lower test violations and reasonable test errors in six of seven experiments.Adult was the exception: substantially better training and validation violations did not generalize to the test set.
Small constraint datasets can cause poor generalization, with especially large training–test violation gaps reported for Business Entity Resolution.Business Entity Resolution used 16 regional constraints, some based on very small datasets.
The 0-1 external-regret m-stochastic method achieved both lower training error and lower training violation than hinge m-stochastic in 7 of 7 experiments.
Hinge-based methods sometimes over-constrained or underperformed, while proxy-Lagrangian superiority over hinge remained inconclusive across datasets.On Map Intent, hinge solutions were worse in both accuracy and fairness constraints; on Business Entity Resolution, hinge methods had higher errors but better test constraint satisfaction.
m-stochastic solutions generally outperformed T-stochastic solutions on training error and constraint violation, while test comparisons often involved an accuracy–fairness trade-off.

7. Conclusions, Advice to Practitioners, and Open Questions

The paper presents rate constraints and proxy-Lagrangian optimization as broadly applicable tools, recommends two practical training procedures, and identifies generalization and nonlinear constraints as open boundaries.

The paper provides a comprehensive theoretical, algorithmic, and experimental study of training classifiers with broad arrays of rate constraints.
7.1 Advice to Practitioners: How To Train Classifiers with Rate Constraints: Practitioners are advised to use 0-1 swap-regret m-stochastic proxy-Lagrangian optimization or 0-1 external-regret best-iterate optimization.
7.1 Advice to Practitioners: How To Train Classifiers with Rate Constraints: The external-regret best-iterate procedure is simpler but requires storing candidate iterates on the Pareto frontier for later ranking.
7.1 Advice to Practitioners: How To Train Classifiers with Rate Constraints: Relaxing indicators for both players is discouraged because it is generally, though not always, associated with worse test results.
7.2 More Experimental Conclusions: The T-stochastic solution has stronger theoretical guarantees, but deterministic best-iterate solutions generally performed better in practice.
7.3 Generalization: Rate-constraint satisfaction may fail to generalize, especially with small constraint datasets or distribution shifts, so slack should be added.
7.6 Open Questions on Nonlinear Rate Constraints: The techniques are limited to linear non-negative combinations of positive and negative classification rates; nonlinear rate constraints remain open.
7.7 Some Open Theoretical Questions: Theoretical guarantees retain dependencies on iteration count, number of constraints, and model complexity, motivating tighter-bound research.

Appendix A. Proofs of Sub{optimality,feasibility} Guarantees

The appendix establishes optimality and feasibility guarantees for randomized proxy-Lagrangian solutions under stated assumptions, using regret inequalities and feasibility margins.

The appendix also uses feasible comparators, zero multipliers, dual norms, and Hölder’s inequality to establish optimality and feasibility claims.
Theorem 4 analyzes jointly distributed model parameters and multipliers for proxy-Lagrangians under left-stochastic transformations.
The appendix defines a resampled model variable weighted by the multiplier’s first coordinate and states that it is nearly optimal.
The optimality proof compares against a solution satisfying proxy constraints and uses the proxy-Lagrangian’s linearity in the multiplier.
The feasibility proof rewrites the Lagrangian using a zero objective component and the original constraint evaluations, then derives the feasibility claim.
The feasibility-margin lemma assumes a solution satisfying every proxy constraint with margin γ and bounds the resulting multiplier quantity.

Appendix B. Proofs of Existence of Sparse Equilibria

The appendix establishes existence of sparse equilibria and shows that feasible randomized solutions can be supported on at most m + 1 candidate solutions.

Existence of equilibria: Theorem 5 guarantees a Nash equilibrium for the two-player game under compactness, continuity in θ, and linearity in λ.The equilibrium is characterized by mutually optimal actions for the minimizing θ-player and maximizing λ-player.
Related results: The appendix notes that related, sometimes more general sparse-equilibrium results exist in game theory, while providing a direct proof for this setting.The cited comparison includes work by Bohnenblust et al. and Parthasarathy.
Sparse mixed equilibria: The support bound follows by expressing a point in the closed convex hull of G as a convex combination of at most m + 1 elements of G.This converts the equilibrium strategy into a discrete random variable over candidate solutions.
Sparse mixed equilibria: A mixed Nash equilibrium exists with θ supported on at most m + 1 elements of Θ and deterministic λ.The proof reduces the multiplier space to its final m coordinates before applying the equilibrium theorem.
Linear-program reduction: Every optimal vertex of the reduction linear program has at most m* + 1 ≤ m + 1 nonzero probabilities.Here m* counts active linearized functional constraints.

C.1 Non-Stochastic One-Player Convergence Rates

This section states non-stochastic convergence tools for one-player convex optimization, including mirror descent, gradient descent, and multiplicative updates for matrix strategies.

Mirror descent: Mirror descent minimizes sequences of convex functions over compact convex sets using a nonnegative 1-strongly convex distance-generating function.Its guarantee is expressed through the associated Bregman divergence and dual norm.
Gradient descent: Gradient descent is obtained as a Euclidean specialization using projected updates and a uniform bound on subgradient norms.The iterates start from a minimum-norm point and are projected back onto Θ.
Matrix updates: For left-stochastic matrix strategies, the entropy-based mirror map produces element-wise multiplicative updates and column-wise KL projections.The projection normalizes each column, and the construction establishes strong convexity under the L1,2 norm.
Related results: The section connects its mirror-descent statement to prior formulations, citing Nemirovski and Yudin, Beck and Teboulle, Srebro et al., and Gordon et al.The Gordon et al. result is identified as the source of the matrix-update algorithmic instance.

C.2 Stochastic One-Player Convergence Rates

This section extends one-player convergence guarantees to stochastic subgradients and supergradients, using high-probability regret bounds for vector and matrix domains.

Stochastic mirror descent: Stochastic mirror descent minimizes convex function sequences with probability 1 − δ when updates use stochastic subgradients.The result is stated for compact convex domains and a strongly convex distance-generating function.
High-probability analysis: The stochastic guarantee follows by treating gradient-noise terms as martingale differences and applying the Hoeffding-Azuma inequality.The proof also uses convexity and norm bounds to control the accumulated deviations.
Stochastic gradient descent: Stochastic gradient descent provides the Euclidean projected-update counterpart for convex minimization with uniformly bounded stochastic subgradients.Its guarantee is likewise stated with probability 1 − δ over the stochastic draws.
Matrix strategies: For left-stochastic matrix strategies, stochastic mirror updates use element-wise multiplication and exponentiation with high-probability guarantees.The matrix formulation uses stochastic supergradients and a left-stochastic reference matrix.
Matrix strategies: The matrix-game analysis uses stationary distributions of left-stochastic matrices, which always exist for the matrices considered.The stationary distribution supplies the multiplier-side strategy used in the update analysis.

C.3 Two-Player Convergence Rates

This section combines convergence guarantees for the two-player optimization with projected and stochastic updates for convex settings and proxy-Lagrangian games.

Two-player convergence: Algorithm 1’s multiplier update is analyzed through a stochastic-gradient bound and the definition of the optimization error quantity Oρ.The proof uses linearity in λ and the multiplier-radius relation BΛ = R.
Convex Lagrangian optimization: Algorithm 5 optimizes the Lagrangian formulation in the convex setting using projected updates onto the primal and multiplier domains.The multiplier domain Λ is defined by a radius parameter R, and both projections use the Euclidean norm.
Convex Lagrangian optimization: For convex objectives and constraints, Algorithm 5 satisfies Theorem 1 under step sizes selected from bounds on primal and stochastic-gradient norms.The guarantee is obtained by combining the two players’ stochastic optimization bounds.
Proxy-Lagrangian optimization: Algorithm 3 applies when the objective and proxy constraints are convex even though the original constraints may not be convex.The resulting guarantee is derived by combining primal stochastic gradient descent with multiplier-side stochastic mirror descent.
Proof structure: The proofs obtain the stated two-player bounds by adding the players’ inequalities and using the definitions of the averaged iterates.The failure probability is combined as δ = 2δ′ in the stochastic analyses.