Sequential Testing in High Dimensions | Relaxations for Production Planning Problems with Increasing By-products

Sequential methods make use of information as it becomes available, creating an interactive connection between a sampling procedure and information gathered by that procedure. In this talk we explore sequential methods applied to sparse recovery problems, motivated by applications in both communications and biology. Surprisingly, sequential methods can result in a large reduction in the sample size needed to recover a sparse signal.
More specifically, we consider an n-dimensional vector x whose elements are drawn from one of two distributions, p0 and p1. Most of the elements are drawn from p0, but a small number, s, are drawn from p1. The goal is to identify the unknown locations of this sparse subset. Non-sequential testing schemes require at least log(n)/D(p1||p0) samples per dimension, where D(p0||p1) is the KL-divergence from p1 to p0. In the high-dimensional and sparse regimes (n large, s<<n) sequential methods can greatly reduce sample requirements. We begin by discussing a lower bound for any high dimensional sequential test. If the number of samples per dimension is less than log(s)/D(p0||p1) then no method can reliably determine the locations. Coordinate-wise sequential probability ratio tests (SPRT) can reliably identify the locations using log(s)/D(p0||p1) samples in expectation, achieving the lower bound. Implementing an SPRT is often impractical, as it requires complete knowledge of p0, p1, and the level of sparsity. We consider and discuss a simple, robust alternative termed Sequential Thresholding (ST) that automatically adapts to unknown distribution parameters and sparsity levels. With some constraints on the sparsity, ST achieves the lower bound discussed above.

Krishna’s talk:
Title: Relaxations for Production Planning Problems with Increasing By-products

We consider a production planning problem where the production creates a mixture of desirable products and undesirable by-products. A distinguishing feature of this process is that the fraction of each undesirable by-product increases as the process advances.
In this talk, we discuss a novel discrete time formulation of this non convex problem. Further, we derive three scalable mixed integer programming approximation and relaxations. We demonstrate the usefulness of our formulations, approximations and relaxations on realistic applications. This is joint work with Prof Jeff Linderoth and Prof. Jim Luedtke
Keywords: Mixed Integer Programming, Global optimization.