Session Detail Information Add this session to your itinerary Cluster : Sparse Optimization and Applications Session Information : Friday Jul 17, 13:10 - 14:40 Title: Algebraic Methods in Conic Optimization Chair: Amir Ali Ahmadi,Princeton University, a_a_a@princeton.edu Abstract Details Title: Generic Sensitivity Analysis for Semi-Algebraic Optimization Presenting Author: Adrian Lewis,Professor, Cornell University, School of ORIE, Ithaca NY 14853, United States of America, adrian.lewis@cornell.edu Co-Author: Dmitriy Drusvyatskiy,Professor, University of Washington, Box 354350, Seattle 98195, United States of America, ddrusv@uw.edu Alexander Ioffe,TECHNION, Israel Institute of Technology, Haifa, Israel, alexander.ioffe38@gmail.com Abstract: Concrete optimization is often semi-algebraic, definable using only polynomial inequalities. The first-order optimality conditions involve a set-valued operator on n-dimensional space whose graph is everywhere n-dimensional (or “thin”). Semi-algebraic monotone operators also have thin graphs, by Minty’s theorem. A Sard-type theorem holds for semi-algebraic operators with thin graphs, ensuring good sensitivity behavior for generic data. In particular, optimizers of semi-algebraic problems typically lie on an “active manifold” (identified by popular algorithms), and satisfy strict complementarity and the second-order sufficient conditions. Title: Fast Binary Embeddings Presenting Author: Constantine Caramanis,University of Texas-Austin, United States of America, constantine@utexas.edu Abstract: Binary embedding is a nonlinear dimension reduction methodology where high dimensional data are embedded into the Hamming cube while preserving the structure of the original space. Specifically, for an arbitrary set of N distinct points on the p-dimensional sphere, our goal is to encode each point using m-dimensional binary strings such that we can reconstruct their geodesic distance up to $\delta$-uniform distortion. Existing binary embedding algorithms either lack theoretical guarantees or suffer from running time $O(mp)$. We make three contributions: (1) we establish a lower bound that shows any binary embedding oblivious to the set of points requires $m = \Omega(\log{N}/\delta^2)$ bits and a similar lower bound for non-oblivious embeddings into Hamming distance; (2) we propose a novel fast binary embedding algorithm with provably optimal bit complexity m = O(\log{N}/\delta^2}) and near linear running time O(p \log p) whenever $\log N \ll \delta \sqrt{p}$, with a slightly worse running time for larger \log N; (3) we also provide an analytic result about embedding a general set of points on the sphere, with even infinite size. Our theoretical findings are supported through experiments on both synthetic and real data sets. Title: Relative Entropy Relaxations for Signomial Optimization Presenting Author: Venkat Chandrasekaran,Caltech, 1200 E. California Blvd, MC 305-16, Pasadena CA 91125, United States of America, venkatc@caltech.edu Co-Author: Parikshit Shah,Yahoo! Research Lab, Yahoo! Research Lab, San Jose CA, United States of America, pshah@discovery.wisc.edu Abstract: Due to its favorable analytical properties, the relative entropy function plays a prominent role in a variety of contexts in information theory and in statistics. In this talk, we discuss some of the beneficial computational properties of this function by describing a class of relative-entropy-based convex relaxations for obtaining bounds on signomials programs (SPs), which arise commonly in many problems domains. SPs are non-convex in general, and families of NP-hard problems can be reduced to SPs. The central idea underlying our approach is a connection between the relative entropy function and efficient proofs of nonnegativity via the arithmetic-geometric-mean inequality.