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.