ProxSkip and Scaffnew Probabilistic Proximal Skipping for Accelerated Local Gradient Descent

A randomized composite first-order optimization algorithm (ProxSkip) and its federated consensus instantiation (Scaffnew) for minimizing f(x) + psi(x) where f is L-smooth and mu-strongly convex and psi is a proper closed convex function with an expensive proximity operator prox_{(gamma/p) psi}. At each step t, the algorithm forms a shifted gradient iterate x_hat_{t+1} = x_t - gamma * (nabla f(x_t) - h_t), draws theta_t ~ Bernoulli(p), evaluates x_{t+1} = prox_{(gamma/p) psi}(x_hat_{t+1} - (gamma/p) h_t) with probability p (and skips the prox via x_{t+1} = x_hat_{t+1} with probability 1 - p), and updates the control variate h_{t+1} = h_t + (p / gamma) * (x_{t+1} - x_hat_{t+1}) so h_t -> nabla f(x_*). Setting gamma = 1/L and p = 1/sqrt(kappa) (kappa = L/mu) achieves O(kappa log(1/eps)) gradient steps and O(sqrt(kappa) log(1/eps)) expected prox/communication evaluations without any data-similarity assumption.