The optimal power flow (OPF) problem is a nonconvex quadratically constrained continuous optimization problem that is a key problem in the area of electrical power systems operations. The theme of our work is to design algorithmic techniques for finding globally optimal solutions of OPF. We begin by presenting a new …
For all problems we provide some sort of guarantee that is much better than worst-case. For the first part of this talk, I will present our work on streaming, memory-limited Principal Component Analysis. Therein, we give the first finite-sample, global-convergence guarantees for an algorithm that solves PCA in the single-pass …
We will present recent progress on the connections functions and covering/tiling properties of subsets of euclidean sets. Important structural information about strong cut-generating functions can be translated to geometric questions like: Does a particular compact subset X of R^n cover all of R^n when we consider all of its translates …
Respondent driven sampling (RDS) is sampling technique for studying marginalized or hard to reach populations where the study participants refer their friends into the study. To account for the fact that RDS participants are incentivized to refer up to five future participants, this talk models RDS as a Markov chain …
Cutting planes have become a key component of integer programming solvers. Most cutting planes in use currently are valid for Gomory’s corner relaxation, which is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this talk, we do not relax these nonnegativity constraints. We generalize …
We show that there exists a family of Knapsack polytopes such that for each P in the family and each epsilon>0, any epsilon-approximated formulation of P in the original space R^n requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). …
Identifying contamination in datasets is important in a wide variety of settings, including view and click fraud in online advertising. After a brief overview of digital ad fraud, I’ll describe a technique for estimating contamination in large, categorical datasets. The technique involves solving a series of convex programs, resulting in …
In Sparse Principal Component Analysis (PCA) we wish to reconstruct a low-rank matrix from noisy observations, under sparsity assumptions on the factors recovered. Johnstone and Lu (2004) formalized these assumptions in the ‘spiked covariance model’, wherein we observe $n$ i.i.d. samples from a $p$ dimensional Gaussian distribution $N(0, I + …
Digital adverting is arguably the largest and most ubiquitous application of machine learning. Learning algorithms pick the ads we see by inferring information about who we are and what we might buy. Graph datasets, due to their simplicity, play a central role in facilitating this inference. Internet Device Graphs are …
Today, machine learning is responsible for most of what we perceive as the personalization of the web: automatic recommendations for movies (Netflix) or music (Spotify,Last.fm), personalized search results based on your recent searches or email (Google), automatic credit card fraud detection (Chase), social network friend identification (Facebook,Linked-in), and, of course, …