The Price of Adaptivity in Stochastic Convex Optimization

arXiv:2402.10898v1 Announce Type: cross
Abstract: We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a "price of adaptivity" (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for …

abstract adapt arxiv cs.lg math.oc optimization parameters price prove set speaking stat.ml stochastic type uncertainty