{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T18:10:15Z","timestamp":1788891015082,"version":"build-2803163510"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T00:00:00Z","timestamp":1756857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T00:00:00Z","timestamp":1756857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2239527"],"award-info":[{"award-number":["2239527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2022663"],"award-info":[{"award-number":["2022663"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0242"],"award-info":[{"award-number":["FA9550-23-1-0242"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["2486\/21"],"award-info":[{"award-number":["2486\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1007\/s10107-025-02268-3","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T08:32:55Z","timestamp":1756888375000},"page":"865-899","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Price of Adaptivity in Stochastic Convex Optimization"],"prefix":"10.1007","volume":"219","author":[{"given":"Yair","family":"Carmon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5077-0359","authenticated-orcid":false,"given":"Oliver","family":"Hinder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"2268_CR1","unstructured":"Kavis, A., Levy, K.Y., Bach, F., Cevher, V.: UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in Neural Information Processing Systems (NeurIPS) (2019)"},{"key":"2268_CR2","unstructured":"Orabona, F.: Simultaneous model selection and optimization through parameter-free stochastic learning. Advances in Neural Information Processing Systems (NeurIPS) (2014)"},{"key":"2268_CR3","unstructured":"Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., Lacoste-Julien, S.: Painless stochastic gradient: Interpolation, line-search, and convergence rates. In: Advances in Neural Information Processing Systems (NeurIPS) (2019)"},{"issue":"1","key":"2268_CR4","first-page":"3117","volume":"18","author":"HB McMahan","year":"2017","unstructured":"McMahan, H.B.: A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research 18(1), 3117\u20133166 (2017)","journal-title":"The Journal of Machine Learning Research"},{"key":"2268_CR5","unstructured":"Zhang, Z., Cutkosky, A., Paschalidis, I.: PDE-based optimal strategy for unconstrained online learning. In: International Conference on Machine Learning (ICML) (2022)"},{"key":"2268_CR6","doi-asserted-by":"crossref","unstructured":"Zhang, J., Cutkosky, A.: Parameter-free regret in high probability with heavy tails. In: Advances in Neural Information Processing Systems (NeurIPS) (2022)","DOI":"10.52202\/068431-0581"},{"key":"2268_CR7","doi-asserted-by":"crossref","unstructured":"Chen, K., Langford, J., Orabona, F.: Better parameter-free stochastic optimization with ODE updates for coin-betting. In: AAAI Conference on Artificial Intelligence (2022)","DOI":"10.1609\/aaai.v36i6.20573"},{"key":"2268_CR8","unstructured":"Orabona, F., P\u00e1l, D.: Parameter-free stochastic optimization of variationally coherent functions. arXiv:2102.00236 (2021)"},{"key":"2268_CR9","unstructured":"Carmon, Y., Hinder, O.: Making SGD parameter-free. In: Conference on Learning Theory (COLT) (2022)"},{"key":"2268_CR10","unstructured":"Orabona, F., P\u00e1l, D.: Coin betting and parameter-free online learning. In: Advances in Neural Information Processing Systems (NeurIPS) (2016)"},{"key":"2268_CR11","unstructured":"Orabona, F.: A modern introduction to online learning. arXiv:1912.13213 (2021)"},{"key":"2268_CR12","unstructured":"Cutkosky, A., Orabona, F.: Black-box reductions for parameter-free online learning in Banach spaces. In: Conference on Learning Theory (COLT) (2018)"},{"issue":"1","key":"2268_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/18M1216250","volume":"30","author":"C Paquette","year":"2020","unstructured":"Paquette, C., Scheinberg, K.: A stochastic line search method with expected complexity analysis. SIAM J. Optim. 30(1), 349\u2013376 (2020)","journal-title":"SIAM J. Optim."},{"key":"2268_CR14","unstructured":"Mhammedi, Z., Koolen, W.M., Van\u00a0Erven, T.: Lipschitz adaptivity with multiple learning rates in online learning. In: Conference on Learning Theory, pp. 2490\u20132511 (2019)"},{"key":"2268_CR15","unstructured":"Sharrock, L., Nemeth, C.: Coin sampling: Gradient-based Bayesian inference without learning rates. In: International Conference on Machine Learning (ICML) (2023)"},{"key":"2268_CR16","unstructured":"Jacobsen, A., Cutkosky, A.: Unconstrained online learning with unbounded losses. In: International Conference on Machine Learning (ICML) (2023)"},{"key":"2268_CR17","unstructured":"Ivgi, M., Hinder, O., Carmon, Y.: DoG is SGD\u2019s best friend: A parameter-free dynamic step size schedule. In: International Conference on Machine Learning (ICML) (2023)"},{"issue":"5","key":"2268_CR18","doi-asserted-by":"publisher","first-page":"3235","DOI":"10.1109\/TIT.2011.2182178","volume":"58","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Bartlett, P.L., Ravikumar, P., Wainwright, M.J.: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory 58(5), 3235\u20133249 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2268_CR19","unstructured":"McMahan, H.B., Orabona, F.: Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations. In: Conference on Learning Theory (COLT) (2014)"},{"key":"2268_CR20","volume-title":"Selfish Routing and the Price of Anarchy","author":"T Roughgarden","year":"2005","unstructured":"Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT press, Cambridge, MA (2005)"},{"key":"2268_CR21","unstructured":"Cutkosky, A.: Artificial constraints and hints for unbounded online learning. In: Conference on Learning Theory (COLT) (2019)"},{"key":"2268_CR22","unstructured":"Gupta, V., Koren, T., Singer, Y.: A unified approach to adaptive regularization in online and stochastic optimization. arXiv:1706.06569 (2017)"},{"issue":"7","key":"2268_CR23","doi-asserted-by":"publisher","first-page":"4709","DOI":"10.1109\/TIT.2017.2701343","volume":"63","author":"G Braun","year":"2017","unstructured":"Braun, G., Guzm\u00e1n, C., Pokutta, S.: Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Trans. Inf. Theory 63(7), 4709\u20134724 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2268_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1090\/pcms\/025\/03","volume":"25","author":"JC Duchi","year":"2018","unstructured":"Duchi, J.C.: Introductory lectures on stochastic optimization. The Mathematics of Data 25, 99\u2013186 (2018)","journal-title":"The Mathematics of Data"},{"key":"2268_CR25","unstructured":"Karp, R.M., Kleinberg, R.: Noisy binary search and its applications. In: Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"2268_CR26","doi-asserted-by":"publisher","DOI":"10.1063\/1.3057290","volume-title":"Transmission of information","author":"RM Fano","year":"1961","unstructured":"Fano, R.M., Wintringham, W.: Transmission of information. M.I.T. Press and John Wiley and Sons, New York & London (1961)"},{"key":"2268_CR27","unstructured":"Streeter, M., McMahan, H.B.: No-regret algorithms for unconstrained online convex optimization. In: Advances in Neural Information Processing Systems (NeurIPS) (2012)"},{"key":"2268_CR28","unstructured":"Orabona, F.: Dimension-free exponentiated gradient. Advances in Neural Information Processing Systems (NeurIPS) (2013)"},{"key":"2268_CR29","unstructured":"Cutkosky, A., Boahen, K.: Online learning without prior information. In: Conference on Learning Theory (COLT) (2017)"},{"key":"2268_CR30","unstructured":"Mhammedi, Z., Koolen, W.M.: Lipschitz and comparator-norm adaptivity in online learning. In: Conference on Learning Theory (COLT) (2020)"},{"issue":"1","key":"2268_CR31","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imag. Sci."},{"key":"2268_CR32","doi-asserted-by":"crossref","unstructured":"Carmon, Y., Hausler, D., Jambulapati, A., Jin, Y., Sidford, A.: Optimal and adaptive Monteiro-Svaiter acceleration. In: Advances in Neural Information Processing Systems (NeurIPS) (2022)","DOI":"10.52202\/068431-1479"},{"key":"2268_CR33","volume-title":"Introduction to Optimization","author":"BT Polyak","year":"1987","unstructured":"Polyak, B.T.: Introduction to Optimization. Optimization Software, Inc., New York (1987)"},{"key":"2268_CR34","unstructured":"Hazan, E., Kakade, S.: Revisiting the Polyak step size. arXiv:1905.00313 (2019)"},{"key":"2268_CR35","unstructured":"Mishchenko, K., Defazio, A.: Prodigy: An expeditiously adaptive parameter-free learner. arXiv:2306.06101 (2023)"},{"key":"2268_CR36","unstructured":"Attia, A., Koren, T.: How free is parameter-free stochastic optimization? In: International Conference on Machine Learning (ICML) (2024)"},{"key":"2268_CR37","unstructured":"Khaled, A., Jin, C.: Tuning-free stochastic optimization. In: International Conference on Machine Learning (ICML) (2024)"},{"key":"2268_CR38","volume-title":"Probability Theory","author":"AA Borovkov","year":"1999","unstructured":"Borovkov, A.A.: Probability Theory. CRC Press, Boca Raton, FL (1999)"},{"key":"2268_CR39","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovski","year":"1983","unstructured":"Nemirovski, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York (1983)"},{"key":"2268_CR40","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1134\/S0005117919090042","volume":"80","author":"AV Nazin","year":"2019","unstructured":"Nazin, A.V., Nemirovsky, A.S., Tsybakov, A.B., Juditsky, A.B.: Algorithms of robust stochastic optimization based on mirror descent method. Autom. Remote. Control. 80, 1607\u20131627 (2019)","journal-title":"Autom. Remote. Control."},{"key":"2268_CR41","unstructured":"Gorbunov, E., Danilova, M., Gasnikov, A.: Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In: Advances in Neural Information Processing Systems (NeurIPS) (2020)"},{"key":"2268_CR42","unstructured":"Gorbunov, E., Danilova, M., Shibaev, I., Dvurechensky, P., Gasnikov, A.: Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv:2106.05958 (2021)"},{"issue":"1","key":"2268_CR43","first-page":"2237","volume":"22","author":"D Davis","year":"2021","unstructured":"Davis, D., Drusvyatskiy, D., Xiao, L., Zhang, J.: From low probability to high confidence in stochastic convex optimization. The Journal of Machine Learning Research 22(1), 2237\u20132274 (2021)","journal-title":"The Journal of Machine Learning Research"},{"key":"2268_CR44","unstructured":"Sadiev, A., Danilova, M., Gorbunov, E., Horv\u00e1th, S., Gidel, G., Dvurechensky, P., Gasnikov, A., Richt\u00e1rik, P.: High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In: International Conference on Machine Learning (ICML) (2023)"},{"key":"2268_CR45","doi-asserted-by":"crossref","unstructured":"Nguyen, T.D., Nguyen, T.H., Ene, A., Nguyen, H.: Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In: Advances in Neural Information Processing Systems (NeurIPS) (2023)","DOI":"10.52202\/075280-1052"},{"key":"2268_CR46","doi-asserted-by":"crossref","unstructured":"Freedman, D.A.: On tail probabilities for martingales. the Annals of Probability, 100\u2013118 (1975)","DOI":"10.1214\/aop\/1176996452"},{"key":"2268_CR47","volume-title":"Elements of Information Theory","author":"TM Cover","year":"1991","unstructured":"Cover, T.M., Thomas, A.J.: Elements of Information Theory. John Wiley & Sons, New York (1991)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02268-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02268-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02268-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T17:50:12Z","timestamp":1788889812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02268-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,3]]},"references-count":47,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["2268"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02268-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,3]]},"assertion":[{"value":"12 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}