Ankit Garg 0001

FOCS Conference 2020 Conference Paper

Learning sums of powers of low-degree polynomials in the non-degenerate case

• Ankit Garg 0001
• Neeraj Kayal
• Chandan Saha 0001

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials in the non-degenerate case. This problem generalizes symmetric tensor decomposition which is widely studied, having many applications in machine learning. Our algorithm for this more general problem allows us to solve the moment problem for mixtures of zero-mean Gaussians in the nondegenerate case. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from lower bound for the same model, provided certain non-degeneracy conditions hold. The scheme reduces the learning problem to the problem of decomposing two vector spaces under the action of a set of linear operators, where the spaces and the operators are derived from the input circuit and the complexity measure used in a typical lower bound proof. The non-degeneracy conditions are certain restrictions on how the spaces decompose. Such a scheme is present in a rudimentary form in an earlier work of Kayal and Saha. Here, we make it more general and detailed, and potentially applicable to learning other circuit models. An exponential lower bound on the representation above is known using the shifted partials measure. However, the number of linear operators in shifted partials is exponential and also the non-degeneracy condition emerging out of this measure is unlikely to be satisfied by a random such circuit when the number of variables is large with respect to the degree. We bypass this hurdle by proving a lower bound (which is nearly as strong as the previous bound) using a novel variant of the partial derivatives measure, namely affine projections of partials (APP). The non-degeneracy conditions appearing from this new measure are satisfied by a random circuit of the above kind. The APP measure could be of independent interest for proving other lower bounds.

FOCS Conference 2019 Conference Paper

More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer

• Ankit Garg 0001
• Visu Makam
• Rafael Oliveira 0002
• Avi Wigderson

We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on k-tensors cannot yield non-trivial lower bounds on the rank of d-tensors, for any constant d larger than k. This significantly extends recent barrier results on the limits of (matrix) rank methods by [EGOW17], which handles the (very important) case k=2. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic k-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for k=2. To prove an analogous statement for k larger than 2 we develop a "numeric to symbolic'' transfer of algebraic %analytic relations to algebraic %analytic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP ≠ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds.

FOCS Conference 2019 Conference Paper

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes

• Peter Bürgisser
• Cole Franks
• Ankit Garg 0001
• Rafael Oliveira 0002
• Michael Walter 0005
• Avi Wigderson

This paper initiates a systematic development of a theory of non-commutative optimization, a setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesic convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. More specifically, these are algorithms to minimize the moment map (a non-commutative notion of the usual gradient), and to test membership in moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which quite magically arise from this a-priori non-convex, non-linear setting). The importance of understanding this very general setting of geodesic optimization, as these works unveiled and powerfully demonstrate, is that it captures a diverse set of problems, many non-convex, in different areas of CS, math, and physics. Several of them were solved efficiently for the first time using non-commutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the "derivatives" of the function to be optimized. These in particular subsume all past results. The main technical work, again unifying and extending much of the previous work, goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of "smoothness" in the commutative case are far more complex, and require significant algebraic and analytic machinery (much existing and some newly developed here). Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We also bound these parameters in several general cases. Our work points to intriguing open problems and suggests further research directions. We believe that extending this theory, namely understanding geodesic optimization better, is both mathematically and computationally fascinating; it provides a great meeting place for ideas and techniques from several very different research areas, and promises better algorithms for existing and yet unforeseen applications.

STOC Conference 2018 Conference Paper

A matrix expander Chernoff bound

• Ankit Garg 0001
• Yin Tat Lee
• Zhao Song 0002
• Nikhil Srivastava

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves upon the inequality in [Sutter, Berta and Tomamichel 17], as well as an adaptation of an argument for the scalar case due to [Healy 08]. Our new multi-matrix Golden-Thompson inequality could be of independent interest. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.

FOCS Conference 2018 Conference Paper

Classical Lower Bounds from Quantum Upper Bounds

• Shalev Ben-David
• Adam Bouland
• Ankit Garg 0001
• Robin Kothari

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0, 1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

FOCS Conference 2018 Conference Paper

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes

• Peter Bürgisser
• Cole Franks
• Ankit Garg 0001
• Rafael Oliveira 0002
• Michael Walter 0005
• Avi Wigderson

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

STOC Conference 2018 Conference Paper

Monotone circuit lower bounds from resolution

• Ankit Garg 0001
• Mika Göös
• Pritish Kamath
• Dmitry Sokolov 0001

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

STOC Conference 2018 Conference Paper

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing

• Zeyuan Allen-Zhu
• Ankit Garg 0001
• Yuanzhi Li
• Rafael Oliveira 0002
• Avi Wigderson

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings. As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. This yields a deterministic polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.

STOC Conference 2017 Conference Paper

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute: (1) Feasibility of BL-datum, (2) Optimal BL- constant, (3) Weak separation oracle for BL-polytopes. What is particularly exciting about this progress, beyond the better understanding of BL- inequalities, is that the objects above naturally encode rich families of optimization problems which had no prior efficient algorithms. In particular, the BL-constants (which we efficiently compute) are solutions to non-convex optimization problems, and the BL-polytopes (for which we provide efficient membership and separation oracles) are linear programs with exponentially many facets. Thus we hope that new combinatorial optimization problems can be solved via reductions to the ones above, and make modest initial steps in exploring this possibility. Our algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by [Gur04]. To obtain the results above, we utilize the two (very recent and different) algorithms for the operator scaling problem [GGOW16, IQS15a]. Our reduction implies algorithmic versions of many of the known structural results on BL-inequalities, and in some cases provide proofs that are different or simpler than existing ones. Further, the analytic properties of the [GGOW16] algorithm provide new, effective bounds on the magnitude and continuity of BL-constants, with applications to non-linear versions of BL-inequalities; prior work relied on compactness, and thus provided no bounds. On a higher level, our application of operator scaling algorithm to BL-inequalities further connects analysis and optimization with the diverse mathematical areas used so far to mo- tivate and solve the operator scaling problem, which include commutative invariant theory, non-commutative algebra, computational complexity and quantum information theory.

FOCS Conference 2016 Conference Paper

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutativealgebra.

STOC Conference 2016 Conference Paper

Communication lower bounds for statistical estimation problems via a distributed data processing inequality

• Mark Braverman
• Ankit Garg 0001
• Tengyu Ma 0001
• Huy L. Nguyen 0001
• David P. Woodruff

We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m machines receives n data points from a d-dimensional Gaussian distribution with unknown mean θ which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean θ. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least Ω(min{n,d}m), where n is the number of observations that each machine receives and d is the ambient dimension. These lower results improve upon Shamir (NIPS'14) and Steinhardt-Duchi (COLT'15) by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

FOCS Conference 2015 Conference Paper

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

• Mark Braverman
• Ankit Garg 0001
• Young Kun-Ko
• Jieming Mao
• Dave Touchette

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r̂ 2 ) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2 ̂O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

STOC Conference 2015 Conference Paper

Small Value Parallel Repetition for General Games

• Mark Braverman
• Ankit Garg 0001

STOC Conference 2013 Conference Paper

From information to exact communication

• Mark Braverman
• Ankit Garg 0001
• Denis Pankratov
• Omri Weinstein

We develop a new local characterization of the zero-error information complexity function for two-party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: IC(AND,0) = C ∧ ≅ 1.4923 bits, and IC ext (AND,0) = log 2 3 ≅ 1.5839 bits. This leads to a tight (upper and lower bound) characterization of the communication complexity of the set intersection problem on subsets of {1,...,n} (the player are required to compute the intersection of their sets), whose randomized communication complexity tends to C ∧ ⋅ n pm o(n) as the error tends to zero.