Principled nonparametric tests for regression curvature in $\mathbb{R}^{d}$ are often statistically and computationally challenging. This paper introduces the stratified incomplete local simplex (SILS) tests for joint concavity of nonparametric multiple regression. The SILS tests with suitable bootstrap calibration are shown to achieve simultaneous guarantees on dimension-free computational complexity, polynomial decay of the uniform error-in-size, and power consistency for general (global and local) alternatives. To establish these results, a general theory for incomplete $U$-processes with stratified random sparse weights is developed. Novel technical ingredients include maximal inequalities for the supremum of multiple incomplete $U$-processes.