CMU-CS-19-115Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-19-115
Vijay Bhattiprolu Ph.D. Thesis June 2019
Keywords:
Injective Tensor Norm, Operator Norm, Hypercontractive Norms, Sum of Squares
Hierarchy, Convex Programming, Continuous Optimization, Optimization over the Sphere,
Approximation Algorithms, Hardness of Approximation
The theory of approximation algorithms has had great success with combinatorial optimization, where it is known that for a variety of problems, algorithms based on semidefinite programming are optimal under the unique games conjecture. In contrast, the approximability of most continuous optimization problems remains unresolved.
In this thesis we aim to extend the theory of approximation algorithms to a wide class
of continuous optimization problems captured by the injective tensor norm framework.
Given an order- T,x,^{1} ⊗ … ⊗ x^{d}⟩x
^{i}∈C_{i}
Injective tensor norm has manifestations across several branches of computer science, optimization and analysis. To list some examples, it has connections to maximum singular value, max-cut, Grothendieck's inequality, non-commutative Grothendieck inequality, quantum information theory, We study various important special cases of the problem (through the lens of convex optimization and the sum of squares (SoS) hierarchy) and obtain the following results:
- We obtain the first NP-hardness of approximation results for hypercontractive norms. Specifically, we prove inapproximability results for computing the q,q ′ < ∞.
- We obtain improved approximation algorithms for computing the - We introduce the technique of weak decoupling inequalities and use it to analyze the integrality gap of the SoS hierarchy for the maxima of various classes of polynomials over the sphere, namely arbitrary polynomials, polynomials with non-negative coefficients and sparse polynomials. We believe this technique is broadly applicable and could find use beyond optimization over the sphere. We also study how well higher levels of SoS approximate the maximum of a random polynomial over the sphere ([RRS16] concurrently obtained a similar result). 190 pages
Srinivasan Seshan, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |