{"id":"arxiv/2606.22669","url":"https://arxiv.org/abs/2606.22669","tags":["cs.LG","math.OC"],"score":0,"title":"Clipping the Price of Adaptivity at the Tail","domain":"cs.LG","source":"arxiv","authors":["Itai Kreisler","Yair Carmon","Oliver Hinder"],"reviews":0,"subject":"cs.LG","summary":"Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by requiring a small amount of additional structure common to many learning problems. Specifically, we assume that the objective decomposes into a model and a loss function, enabling us to intervene by modifying the model's output before it passes to the loss function. Under this assumption, we design a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-21","reactions":{}}