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-d tensor C₁, . . . C_d, the injective tensor norm of T is defined as

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, k-XOR, refuting random constraint satisfaction problems, tensor PCA, densest-k-subgraph, and small set expansion. So a general theory of its approximability promises to be of broad scope and applicability.

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 p → q operator norm (which is a special case of injective norm involving two convex sets) when p ≤ q and 2 ∉ [p, q]. Towards the goal of obtaining strong inapproximability results for 2 → q norm when q > 2, we give random label cover (for which polynomial level SoS gaps are available) based hardness results for mixed norms, i.e., 2 → ℓ_q(ℓ_q') for some 2 < q,q ′ < ∞.

- We obtain improved approximation algorithms for computing the p → q operator norm when p ≥ 2 ≥ q.

- 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

Thesis Committee:
Venkatesan Guruswami (Chair)
Anupam Gupta
David Woodruff
Madhur Tulsiani (Toyota Technological Institute at Chicago)

Srinivasan Seshan, Head, Computer Science Department
Tom M. Mitchell, Interim Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]