tensorflow_constrained_optimization-0.1.tar.gz

<!-- Copyright 2018 The TensorFlow Constrained Optimization Authors. All Rights Reserved. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. =============================================================================--> # TensorFlow Constrained Optimization (TFCO) TFCO is a library for optimizing inequality-constrained problems in TensorFlow. In the most general case, both the objective function and the constraints are represented as `Tensor`s, giving users the maximum amount of flexibility in specifying their optimization problems. Constructing these `Tensor`s can be cumbersome, so we also provide helper functions to make it easy to construct constrained optimization problems based on *rates*, i.e. proportions of the training data on which some event occurs (e.g. the error rate, true positive rate, recall, etc). For full details, motivation, and theoretical results on the approach taken by this library, please refer to: > Cotter, Jiang and Sridharan. "Two-Player Games for Efficient Non-Convex > Constrained Optimization". > [ALT'19](http://alt2019.algorithmiclearningtheory.org/). > [https://arxiv.org/abs/1804.06500](https://arxiv.org/abs/1804.06500) which will be referred to as [CoJiSr19] throughout the remainder of this document, and: > Cotter, Gupta, Jiang, Srebro, Sridharan, Wang, Woodworth and You. "Training > Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent > Constraints". > [https://arxiv.org/abs/1807.00028](https://arxiv.org/abs/1807.00028) which will be referred to as [CotterEtAl18]. ### Proxy constraints Imagine that we want to constrain the recall of a binary classifier to be at least 90%. Since the recall is proportional to the number of true positive classifications, which itself is a sum of indicator functions, this constraint is non-differentiable, and therefore cannot be used in a problem that will be optimized using a (stochastic) gradient-based algorithm. For this and similar problems, TFCO supports so-called *proxy constraints*, which are differentiable (or sub/super-differentiable) approximations of the original constraints. For example, one could create a proxy recall function by replacing the indicator functions with sigmoids. During optimization, each proxy constraint function will be penalized, with the magnitude of the penalty being chosen to satisfy the corresponding *original* (non-proxy) constraint. On a problem including proxy constraints&mdash;even a convex problem&mdash;the Lagrangian approach discussed above isn't guaranteed to work. However, a different algorithm, based on minimizing *swap regret* on a slightly *different* formulation&mdash;which we call the "proxy-Lagrangian" formulation&mdash;does work. ### Shrinking This library is designed to deal with a very flexible class of constrained problems, but this flexibility makes optimization considerably more difficult: on a non-convex problem, if one uses the "standard" approach of introducing a Lagrange multiplier for each constraint, and then jointly maximizing over the Lagrange multipliers and minimizing over the model parameters, then a stable stationary point might not even *exist*. Hence, in some cases, oscillation, instead of convergence, is inevitable. Thankfully, it turns out that even if, over the course of optimization, no *particular* iterate does a good job of minimizing the objective while satisfying the constraints, the *sequence* of iterates, on average, usually will. This observation suggests the following approach: at training time, we'll periodically snapshot the model state during optimization; then, at evaluation time, each time we're given a new example to evaluate, we'll sample one of the saved snapshots uniformly at random, and apply it to the example. This *stochastic model* will generally perform well, both with respect to the objective function, and the constraints. In fact, we can do better: it's possible to post-process the set of snapshots to find a distribution over at most **m+1** snapshots, where **m** is the number of constraints, that will be at least as good (and will usually be much better) than the (much larger) uniform distribution described above. If you're unable or unwilling to use a stochastic model at all, then you can instead use a heuristic to choose the single best snapshot. In many cases, these issues can be ignored. However, if you experience issues with oscillation during training, or if you want to squeeze every last drop of performance out of your model, consider using the "shrinking" procedure of [CoJiSr19], which is implemented in the "candidates.py" file. ## Public contents * [constrained_minimization_problem.py](https://github.com/google-research/tensorflow_constrained_optimization/tree/master/tensorflow_constrained_optimization/python/constrained_minimization_problem.py): contains the `ConstrainedMinimizationProblem` interface, representing an inequality-constrained problem. Your own constrained optimization problems should be represented using implementations of this interface. If using the rate-based helpers, such objects can be constructed as `RateMinimizationProblem`s. * [candidates.py](https://github.com/google-research/tensorflow_constrained_optimization/tree/master/tensorflow_constrained_optimization/python/candidates.py): contains two functions, `find_best_candidate_distribution` and `find_best_candidate_index`. Both of these functions are given a set of candidate solutions to a constrained optimization problem, from which the former finds the best distribution over at most **m+1** candidates, and the latter heuristically finds the single best candidate. As discussed above, the set of candidates will typically be model snapshots saved periodically during optimization. Both of these functions require that scipy be installed. The `find_best_candidate_distribution` function implements the approach described in Lemma 3 of [CoJiSr19], while `find_best_candidate_index` implements the heuristic used for hyperparameter search in the experiments of Section 5.2. * [Optimizing general inequality-constrained problems](https://github.com/google-research/tensorflow_constrained_optimization/tree/master/tensorflow_constrained_optimization/python/train/) * [constrained_optimizer.py](https://github.com/google-research/tensorflow_constrained_optimization/tree/master/tensorflow_constrained_optimization/python/train/constrained_optimizer.py): contains the `ConstrainedOptimizer` interface, which is similar to (but different from) `tf.train.Optimizer`, with the main difference being that `ConstrainedOptimizer`s are given `ConstrainedMinimizationProblem`s to optimize, and perform constrained optimization. * [lagrangian_optimizer.py](https://github.com/google-research/tensorflow_constrained_optimization/tree/master/tensorflow_constrained_optimization/python/train/lagrangian_optimizer.py): contains the `LagrangianOptimizer` implementation, which is a `ConstrainedOptimizer` implementing the Lagrangian approach discussed above (with additive updates to the Lagrange multipliers). You should use this optimizer for problems *without* proxy constraints. It may also work for problems with proxy constraints, but we recommend using a proxy-Lagrangian optimizer, instead. This optimizer is most similar to Algorithm 3 in Appendix C.3 of [CoJiSr1