Rennala SGD and Malenia SGD

A pair of minimax time-optimal semi-asynchronous parallel stochastic gradient algorithms — Rennala SGD (Method 4, for homogeneous i.i.d. worker distributions) and Malenia SGD (Method 6, for heterogeneous worker distributions f(x) = (1/n) sum_{i=1}^n E[f_i(x; xi_i)]) — analyzed under the Time Multiple Oracles Protocol (Protocol 3) where worker i in [n] requires tau_i seconds (0 < tau_1 <= ... <= tau_n) to compute an unbiased sigma^2-variance-bounded stochastic gradient. At each outer step k, workers continuously compute gradients at the current iterate x^k while the server discards any stale gradient whose iteration tag k' != k: Rennala SGD accumulates S = max{ceil(sigma^2 / epsilon), 1} fresh gradients g^k = (1/S) sum_{s=1}^S hat{nabla} f(x^k; xi_s) and attains the homogeneous minimax wall-clock time complexity Theta(min_{m in [n]} ((1/m) sum_{i=1}^m 1/tau_i)^{-1} (L Delta / epsilon + sigma^2 L Delta / (m epsilon^2))) without prior knowledge of tau_1, ..., tau_n, whereas Malenia SGD accumulates per-worker counts B_i until ((1/n) sum_{i=1}^n 1/B_i)^{-1} >= S/n and updates with the unweighted worker-mean average g^k = (1/n) sum_{i=1}^n (1/B_i) sum_{j=1}^{B_i} hat{nabla} f_i(x^k; xi_{i,j}), attaining the heterogeneous minimax time complexity Theta(tau_n L Delta / epsilon + ((1/n) sum_{i=1}^n tau_i) sigma^2 L Delta / (n epsilon^2)).