Seungil You

Doyup Lee, Suehun Jung, Yeongjae Cheon et al.

Short-term demand forecasting models commonly combine convolutional and recurrent layers to extract complex spatiotemporal patterns in data. Long-term histories are also used to consider periodicity and seasonality patterns as time series data. In this study, we propose an efficient architecture, Temporal-Guided Network (TGNet), which utilizes graph networks and temporal-guided embedding. Graph networks extract invariant features to permutations of adjacent regions instead of convolutional layers. Temporal-guided embedding explicitly learns temporal contexts from training data and is substituted for the input of long-term histories from days/weeks ago. TGNet learns an autoregressive model, conditioned on temporal contexts of forecasting targets from temporal-guided embedding. Finally, our model achieves competitive performances with other baselines on three spatiotemporal demand dataset from real-world, but the number of trainable parameters is about 20 times smaller than a state-of-the-art baseline. We also show that temporal-guided embedding learns temporal contexts as intended and TGNet has robust forecasting performances even to atypical event situations.

Andrew Cotter, Heinrich Jiang, Serena Wang et al.

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.

Andrew Cotter, Maya Gupta, Heinrich Jiang et al.

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 performance, 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.

Serena Wang, Maya Gupta, Seungil You

Given a classifier ensemble and a set of examples to be classified, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble are evaluated. This can reduce both mean latency and CPU while maintaining the high accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing a fixed 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 for certain cases. For those cases, this is also the best achievable polynomial time approximation bound unless $P = NP$. Experiments on benchmark and real-world problems show that the proposed Quit When You Can (QWYC) algorithm can speed-up average evaluation time by $2$x--$4$x, and is around $1.5$x faster than prior work. QWYC's joint optimization of ordering and thresholds also performed better in experiments than various fixed orderings, including gradient boosted trees' ordering.

Seungil You, David Ding, Kevin Canini et al.

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.

Seungil You, Nikolai Matni

In this paper, we propose a new robust analysis tool motivated by large-scale systems. The H infinity norm of a system measures its robustness by quantifying the worst-case behavior of a system perturbed by a unit-energy disturbance. However, the disturbance that induces such worst-case behavior requires perfect coordination among all disturbance channels. Given that many systems of interest, such as the power grid, the internet and automated vehicle platoons, are large-scale and spatially distributed, such coordination may not be possible, and hence the H infinity norm, used as a measure of robustness, may be too conservative. We therefore propose a cardinality constrained variant of the H infinity norm in which an adversarial disturbance can use only a limited number of channels. As this problem is inherently combinatorial, we present a semidefinite programming (SDP) relaxation based on the l1 norm that yields an upper bound on the cardinality constrained robustness problem. We further propose a simple rounding heuristic based on the optimal solution of SDP relaxation which provides a lower bound. Motivated by privacy in large-scale systems, we also extend these relaxations to computing the minimum gain of a system subject to a limited number of inputs. Finally, we also present a SDP based optimal controller synthesis method for minimizing the SDP relaxation of our novel robustness measure. The effectiveness of our semidefinite relaxation is demonstrated through numerical examples.

Seungil You, Ather Gattami, John C. Doyle

This paper reformulates and streamlines the core tools of robust stability and performance for LTI systems using now-standard methods in convex optimization. In particular, robustness analysis can be formulated directly as a primal convex (semidefinite program or SDP) optimization problem using sets of gramians whose closure is a semidefinite cone. This allows various constraints such as structured uncertainty to be included directly, and worst-case disturbances and perturbations constructed directly from the primal variables. Well known results such as the KYP lemma and various scaled small gain tests can also be obtained directly through standard SDP duality. To readers familiar with robustness and SDPs, the framework should appear obvious, if only in retrospect. But this is also part of its appeal and should enhance pedagogy, and we hope suggest new research. There is a key lemma proving closure of a grammian that is also obvious but our current proof appears unnecessarily cumbersome, and a final aim of this paper is to enlist the help of experts in robust control and convex optimization in finding simpler alternatives.

Seungil You, Ather Gattami

This paper proposes a direct, and simple approach to the H infinity norm calculation in more general settings. In contrast to the method based on the Kalman-Yakubovich-Popov lemma, our approach does not require a controllability assumption, and returns a sinusoidal input that achieves the H infinity norm of the system including its frequency. In addition, using a semidefinite programming duality, we present a new proof of the Kalman- Yakubovich-Popov lemma, and make a connection between strong duality and controllability. Finally, we generalize our approach towards the generalized Kalman-Yakubovich-Popov lemma, which considers input signals within a finite spectrum.