I’m going to talk about some of our recent and ongoing work on topics that touch on machine learning and optimization. I’ll focus mainly on our work on model inversion attacks. Consider a machine learning model f that takes features x_1,…,x_t and produces from them a prediction y. In many …
Optimality condition for mixed-integer convex minimization problems will be discussed and the concept of center-points, a generalization of the median from the one dimensional space to vector spaces. Through the theory of center-points, I will show how to extend the general cutting plane scheme from the continuous setting to the …
Note: This seminar consisted of two half-hour student talks. Information Theory in Network Coding Ting-Ting Nan Network coding has been used in many applications. However, one of the basic problems, finding the coding capacity of most networks, is still unsolved. The entropy region is central to computing network coding capacities, …
We consider the problem of clustering a collection of N unlabeled data points assumed to lie near a union of k lower dimensional planes. This assumption works in certain computer vision applications such as face recognition and image segmentation. Elhamifar and Vidal have proposed “Sparse Subspace Clustering (SSC)” algorithm to …
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). …