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 SemiAlgebraic Optimization 
 Presenting Author:  Adrian Lewis,Professor, Cornell University, School of ORIE, Ithaca NY 14853, United States of America, adrian.lewis@cornell.edu

 CoAuthor:  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 semialgebraic, definable using only polynomial inequalities. The firstorder optimality conditions involve a setvalued operator on ndimensional space whose graph is everywhere ndimensional (or “thin”). Semialgebraic monotone operators also have thin graphs, by Minty’s theorem. A Sardtype theorem holds for semialgebraic operators with thin graphs, ensuring good sensitivity behavior for generic data. In particular, optimizers of semialgebraic problems typically lie on an “active manifold” (identified by popular algorithms), and satisfy strict complementarity and the secondorder sufficient conditions. 
 
Title:  Fast Binary Embeddings 
 Presenting Author:  Constantine Caramanis,University of TexasAustin, 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 pdimensional sphere, our goal
is to encode each point using mdimensional 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
nonoblivious 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 30516, Pasadena CA 91125, United States of America, venkatc@caltech.edu

 CoAuthor:  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 relativeentropybased convex relaxations for
obtaining bounds on signomials programs (SPs), which arise commonly in
many problems domains. SPs are nonconvex in general, and families of
NPhard 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 arithmeticgeometricmean
inequality. 
 
