On the Parallel Optimality of Exponentiated Gradient Descent

A classic result in learning and optimization theory is that exponentiated gradient descent (EG) or the multiplicative weight update method computes an $\\epsilon$-approximate minimizer of an $\\ell_1$-Lipschitz function over the $d$-dimensional probability simplex $\\Delta_d :=\\{x \in \\mathbb{R}^d_{\\geq0}:\\sum_{i\in[d]}x_i=1\\}$ with $\\tilde{O}(\epsilon^{-2})$ queries to a first-order oracle. We investigate whether there are improved parallel algorithms for this fundamental problem. We show that, up to logarithmic factors, the answer is negative for $\\epsilon=\\tilde \\Omega(d^{-1/6})$ - any randomized algorithm that makes $O(\\mathrm{poly}(d))$ subgradient queries per round requires $\\tilde{\\Omega}(1/\\epsilon^2)$ rounds to output an $\epsilon$-optimal point with constant success probability. Moreover, to obtain this result we provide an analogous characterization of the parallel complexity of minimizing a $\ell_1$-Lipschitz convex function over the unit $\\ell_1$ ball. Previous lower bounds for non-constant $\\epsilon$ for this $\\ell_1$-Lipschitz convex optimization problem either made additional assumptions on the domain, or instead attained a bound of $\\Omega(\\epsilon^{-2/3})$ [DG19].