Minimax-Optimal Update Rules for Stochastic Optimization

We study the following question in stochastic optimization: given a single unbiased stochastic gradient observation with bounded variance, how should one design an update rule to achieve the strongest possible descent guarantee? We formulate a minimax problem in which the decision variable is a rule that maps a single observation to an update. Under a prescribed bound on the update norm, the goal is to maximize the worst-case expected one-step decrease guaranteed by smoothness. The worst case is taken over all gradient directions and observation distributions consistent with the available information. When the gradient norm is known, we derive the exact optimal descent guarantee and characterize all rules that attain it. When the gradient norm is unknown, we fix a positive calibration threshold and derive the best uniform guarantee for all gradient norms at or above that threshold, along with a fixed rule that attains this guarantee. The same rule yields a finite-time stationarity guarantee without requiring estimation of the current gradient norm at each iteration. These results establish a unified theory of optimal bounded updates under different levels of information about the gradient norm. Numerical experiments support the theoretical results.