We develop a new parallel algorithm for minimizing Lipschitz, convex
functions with a stochastic subgradient oracle. The total number of queries
made and the query depth, i.e., the number of parallel rounds of queries, match
the prior state-of-the-art, [CJJLLST23], while improving upon the computational
depth by a polynomial factor for sufficiently small accuracy. When combined
with previous state-of-the-art methods our result closes a gap between the
best-known query depth and the best-known computational depth of parallel
algorithms.
Our method starts with a ball acceleration framework of previous parallel
methods, i.e., [CJJJLST20, ACJJS21], which reduce the problem to minimizing a
regularized Gaussian convolution of the function constrained to Euclidean
balls. By developing and leveraging new stability properties of the Hessian of
this induced function, we depart from prior parallel algorithms and reduce
these ball-constrained optimization problems to stochastic unconstrained
quadratic minimization problems. Although we are unable to prove concentration
of the asymmetric matrices that we use to approximate this Hessian, we
nevertheless develop an efficient parallel method for solving these quadratics.
Interestingly, our algorithms can be improved using fast matrix multiplication
and use nearly-linear work if the matrix multiplication exponent is 2.

我们开发了一种新的并行算法，用于最小化具有随机次梯度子序列的 Lipschitz 函数。与现有的先进交互式查询次数和查询深度相匹配的同时，在精度足够小时通过多项式因子改进了计算深度。结合之前现有的最先进方法，我们的结果填补了并行算法的已知最佳查询深度和计算深度之间的差距。