16 citations · 20 across the 6 of their papers we have counts for
4 papers · 1 filter
No quantum speedup over gradient descent for non-smooth convex optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli +1
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function and its (sub)gradient. O…
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on input…
Scalar Poincaré Implies Matrix Poincaré
Ankit Garg, Tarun Kathuria, Nikhil Srivastava
We prove that every reversible Markov semigroup which satisfies a Poincaré inequality satisfies a matrix-valued Poincaré inequality for Hermitian matrix valued function…
Learning sums of powers of low-degree polynomials in the non-degenerate case
Ankit Garg, Neeraj Kayal, Chandan Saha
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an -variate degree- polynomial which can be written as $$f = c_1Q_1^{…