We consider the fundamental problem of parallel stochastic convex optimization (SCO), whose aim is to approximately minimize a convex objective when given the ability to query a moment-bounded stochastic gradient oracle multiple times in parallel per round. Whereas most previous results have focused on the variance-bounded Euclidean (
ℓ2-norm) setting, meaning the objective is Lipschitz with respect to the
ℓ2-norm over an
ℓ2-bounded feasible set in
Rd, in this work we study parallel SCO in
ℓp settings for
2≤p<∞ under a heavy-tailed noise model. We begin by introducing a new class of
ℓp-optimal-distance-convergence (ODC
p) algorithms, drawing on prior stochastic bias-reduced techniques [ACJ+21], which combine with multilevel Monte Carlo methods to efficiently estimate the optimum of uniformly convex objectives. As a consequence of our ODC
p algorithms, we first establish rates for projection-efficient
ℓp-Lipschitz optimization, composite convex minimization, and efficient
ℓp-proximal point estimation. Combining our ODC
p algorithms with a new
ℓp-generalized Gaussian-based stochastic gradient estimator (
p-GREG), we provide two efficient
ℓp parallel algorithms, EpochDA and
ℓp-AC-SA, which achieve optimization error
ε>0 with at most
O~(d2p+2pε−p+1p) query depth, improving upon the sequential heavy-tailed stochastic query depth of
O(ε−p) for
ε≤O~(d−1/(2p)). We also establish dimension-dependent lower bounds of
Ω(min{ε−p,dp/(3p−2)}) adaptive rounds for nonsmooth convex optimization over a subset of the unit
ℓp ball. Our results improve upon the
Ω(min{ε−p,ε2/3d1/3}) bounds of [DG19], when adapted to the same feasible set.