Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds. Our proposed objective is a combinatorial optimization problem, but we provide a greedy algorithm that achieves a 4-approximation of the optimal solution under certain assumptions, which is also the best achievable polynomial-time approximation bound. Experiments on benchmark and real-world problems show that the proposed Quit When You Can (QWYC) algorithm can speed up average evaluation time by 1.8–2.7 times on even jointly trained ensembles, which are more difficult to speed up than independently or sequentially trained ensembles. QWYC’s joint optimization of ordering and thresholds also performed better in experiments than previous fixed orderings, including gradient boosted trees’ ordering.

Classifiers can be trained with data-dependent constraints to satisfy fairness goals, reduce churn, achieve a targeted false positive rate, or other policy goals. We study the generalization performance for such constrained optimization problems, in terms of how well the constraints are satisfied at evaluation time, given that they are satisfied at training time. To improve generalization, we frame the problem as a two-player game where one player optimizes the model parameters on a training dataset, and the other player enforces the constraints on an independent validation dataset. We build on recent work in two-player constrained optimization to show that if one uses this two-dataset approach, then constraint generalization can be significantly improved. As we illustrate experimentally, this approach works not only in theory, but also in practice.

We show that many machine learning goals can be expressed as “rate constraints” on a model's predictions. We study the problem of training non-convex models subject to these rate constraints (or other non-convex or 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 a new “proxy-Lagrangian” formulation. This leads to an algorithm that, assuming access to an optimization oracle, 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 that shrinks the randomized solution down to a mixture of at most $m+1$ deterministic solutions, given $m$ constraints. This culminates in a procedure that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints, and enjoys theoretical guarantees. We provide extensive experimental results covering a broad range of policy goals, including various fairness metrics, accuracy, coverage, recall, and churn.

We introduce the problem of grouping a finite ground set into blocks where each block is a subset of the ground set and where: (i) the blocks are individually highly valued by a submodular function (both robustly and in the average case) while satisfying block-specific matroid constraints; and (ii) block scores interact where blocks are jointly scored highly, thus making the blocks mutually non-redundant. Submodular functions are good models of information and diversity; thus, the above can be seen as grouping the ground set into matroid constrained blocks that are both intra- and inter-diverse. Potential applications include forming ensembles of classification/regression models, partitioning data for parallel processing, and summarization. In the non-robust case, we reduce the problem to non-monotone submodular maximization subject to multiple matroid constraints. In the mixed robust/average case, we offer a bi-criterion guarantee for a polynomial time deterministic algorithm and a probabilistic guarantee for randomized algorithm, as long as the involved submodular functions (including the inter-block interaction terms) are monotone. We close with a case study in which we use these algorithms to find high quality diverse ensembles of classifiers, showing good results.

We propose learning deep models that are monotonic with respect to a user-specified set of inputs by alternating layers of linear embeddings, ensembles of lattices, and calibrators (piecewise linear functions), with appropriate constraints for monotonicity, and jointly training the resulting network. We implement the layers and projections with new computational graph nodes in TensorFlow and use the Adam optimizer and batched stochastic gradients. Experiments on benchmark and real-world datasets show that six-layer monotonic deep lattice networks achieve state-of-the art performance for classification and regression with monotonicity guarantees.

In this paper, we propose a coordinated localization algorithm for mobile sensor networks with camera sensors to operate under Global Positioning System (GPS) denied areas or indoor environments. Mobile robots are partitioned into two groups. One group moves within the field of views of remaining stationary robots. The moving robots are tracked by stationary robots and their trajectories are used as spatiotemporal features. From these spatiotemporal features, relative poses of robots are computed using multiview geometry and a group of robots is localized with respect to the reference coordinate based on the proposed multirobot localization. Once poses of all robots are recovered, a group of robots moves from one location to another while maintaining the formation of robots for coordinated localization under the proposed multirobot navigation strategy. By taking the advantage of a multiagent system, we can reliably localize robots over time as they perform a group task. In experiment, we demonstrate that the proposed method consistently achieves a localization error rate of 0.37% or less for trajectories of length between 715 cm and 890 cm using an inexpensive off-the-shelf robotic platform.

MIMO interference network optimization is important for increasingly crowded wireless communication networks. This paper presents a new algorithm, named Dual Link Algorithm, for weighted sum-rate maximization where the interference is efficiently managed. We consider general MIMO interference channels with Gaussian input and a total power constraint. Two of the previous state-of-the-art algorithms are the WMMSE algorithm and the polite water-filling (PWF) algorithm. The WMMSE algorithm is provably convergent, while the PWF algorithm takes the advantage of the optimal transmit signal structure and converges the fastest in most situations but is not guaranteed to converge in all situations. Therefore, it is highly desirable to design an algorithm that has the advantages of both algorithms. The proposed dual link algorithm is such an algorithm. Its fast and guaranteed convergence is important to distributed implementation and time varying channels. In addition, the technique and a scaling invariance property used in the convergence proof may find applications in other non-convex problems in communication networks.

The weighted sum-rate maximization in a general multiple-input multiple-output (MIMO) interference network has known to be a challenging non-convex problem, mainly due to the interference between different links. In this paper, by exploring the special structure of the sum-rate function being a difference of concave functions, we apply the convex-concave procedure to the weighted sum-rate maximization to handle non-convexity. With the introduction of a certain damping term, we establish the monotonie convergence of the proposed algorithm. Numerical examples show that the introduced damping term slows down the convergence of our algorithm but helps with finding a better solution in the network with high interference. Even though our algorithm has a slower convergence than some existing ones, it has the guaranteed convergence and can handle more general constraints and thus provides a general solver that can find broader applications.