Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point y and a certificate g in G(y) with (E|F(y)+g| 2) 1/2 epsilon using O(n+ sqrt n LR/epsilon) expected component evaluations and resolvent evaluations. It removes the additive n n cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/sqrt n. Carrying an operator estimate between the remaining stages limits their total cost to O(n). A matching Ω(n+ sqrt n LR/epsilon) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0< epsilon LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.