{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:21Z","timestamp":1778231421755,"version":"3.51.4"},"reference-count":51,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>In the problem of online portfolio selection as formulated by Cover [Cover TM (1991) Universal portfolios. Math. Finance 1(1):1\u201329], the trader repeatedly distributes the trader\u2019s capital over d assets in each of T &gt; 1 rounds with the goal of maximizing the total return. Cover proposed an algorithm, termed \u201cuniversal portfolios,\u201d that performs nearly as well as the best (in hindsight) static assignment of a portfolio with an [Formula: see text] logarithmic regret. Without imposing any restrictions on the market, this guarantee is known to be worst case optimal, and no other algorithm attaining it has been discovered so far. Unfortunately, Cover\u2019s algorithm crucially relies on computing a certain d-dimensional integral, which must be approximated in any implementation; this results in a prohibitive [Formula: see text] per-round runtime for the fastest known implementation. We propose an algorithm for online portfolio selection that satisfies essentially the same regret guarantee as universal portfolios\u2014up to a constant factor and replacement of [Formula: see text] with [Formula: see text]\u2014yet has a drastically reduced runtime of [Formula: see text] per round. The selected portfolio minimizes the observed logarithmic loss regularized with the log-determinant of its Hessian\u2014equivalently, the hybrid logarithmic-volumetric barrier of the polytope specified by the asset return vectors. As such, our work reveals surprising connections of online portfolio selection with two classic topics in optimization theory: cutting-plane and interior-point algorithms.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the Directorate for Computer and Information Science and Engineering [Grant CIF-1908905].<\/jats:p>","DOI":"10.1287\/moor.2023.0175","type":"journal-article","created":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T10:02:16Z","timestamp":1747908136000},"page":"1350-1384","source":"Crossref","is-referenced-by-count":0,"title":["Efficient and Near-Optimal Online Portfolio Selection"],"prefix":"10.1287","volume":"51","author":[{"given":"R\u00e9mi","family":"J\u00e9z\u00e9quel","sequence":"first","affiliation":[{"name":"Inria & D\u00e9partement d\u2019Informatique de l\u2019\u00c9cole Normale Sup\u00e9rieure, 75230 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0812-5249","authenticated-orcid":false,"given":"Dmitrii","family":"Ostrovskii","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, School of Mathematics & H. Milton Stewart School of Industrial and Systems Engineering, Atlanta, Georgia 30332"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6777-6127","authenticated-orcid":false,"given":"Pierre","family":"Gaillard","sequence":"additional","affiliation":[{"name":"University of Grenoble Alpes, Inria, CNRS, Grenoble INP, Laboratoire Jean Kuntzmann, 38000 Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Agarwal A, Hazan E, Kale S, Schapire RE (2006) Algorithms for portfolio management based on the Newton method.\n                      Proc. 23rd Internat. Conf. Machine Learn.\n                      (PMLR, New York), 9\u201316.","DOI":"10.1145\/1143844.1143846"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206828"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614386"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529979"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.3150\/15-BEJ742"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1540"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007530728748"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"B9","unstructured":"Brosse N, Durmus A, Moulines \u00c9, Pereyra M (2017) Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo.\n                      Proc. 30th Conf. Learn. Theory\n                      (PMLR, New York), 319\u2013342."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-9992-1"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9965.1991.tb00002.x"},{"key":"B13","volume-title":"Elements of Information Theory","author":"Cover TM","year":"1999"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/18.485708"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1038"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-008-5051-0"},{"key":"B17","unstructured":"Dwivedi R, Chen Y, Wainwright MJ, Yu B (2018) Log-concave sampling: Metropolis-Hastings algorithms are fast!\n                      Proc. 31st Conf. Learn. Theory\n                      (PMLR, New York), 793\u2013797."},{"key":"B18","doi-asserted-by":"crossref","unstructured":"Gatmiry K, Mhammedi Z (2024) Projection-free online convex optimization via efficient Newton iterations. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds.\n                      Advances in Neural Information Processing Systems\n                      , vol. 36 (Curran Associates, Inc., Red Hook, NY), 986\u20131008.","DOI":"10.52202\/075280-0047"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9965.00058"},{"key":"B23","unstructured":"Kalai A, Vempala S (2002) Efficient algorithms for universal portfolios.\n                      J. Machine Learn. Res.\n                      3(Nov):423\u2013440."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1956.tb03809.x"},{"key":"B25","first-page":"1093","volume-title":"Doklady Akademii Nauk","volume":"244","author":"Khachiyan LG","year":"1979"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2612"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.878172"},{"issue":"3","key":"B28","first-page":"1","volume":"46","author":"Li B","year":"2014","journal-title":"ACM Comput. Surveys"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1201\/b19011"},{"key":"B30","unstructured":"Luo H, Wei CY, Zheng K (2018) Efficient online portfolio with logarithmic regret.\n                      Proc. 33rd Internat. Conf. Neural Inform. Processing Systems\n                      , vol. 31 (Curran Associates Inc., Red Hook, NY), 8245\u20138255."},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1142\/7598"},{"issue":"1","key":"B32","first-page":"77","volume":"7","author":"Markowitz HM","year":"1952","journal-title":"J. Finance"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1991.tb02669.x"},{"key":"B34","unstructured":"Marteau-Ferey U, Bach F, Rudi A (2019) Globally convergent newton methods for ill-conditioned generalized self-concordant losses. Wallach H, Larochelle H, Beygelzimer A, d\u2019Alche-Buc F, Fox E, Garnett R, eds.\n                      Advances in Neural Information Processing Systems\n                      , vol. 32 (Curran Associates Inc., Red Hook, NY)."},{"key":"B35","first-page":"5561","volume-title":"Conf. Learn. Theory","author":"Mhammedi Z","year":"2022"},{"issue":"1","key":"B36","first-page":"4017","volume":"18","author":"Narayanan H","year":"2017","journal-title":"J. Machine Learn. Res."},{"key":"B37","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovskii AS","year":"1983"},{"key":"B38","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","volume":"87","author":"Nesterov Y","year":"2003"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"B40","unstructured":"Orseau L, Lattimore T, Legg S (2017) Soft-Bayes: Prod for mixtures of experts with log-loss.\n                      Internat. Conf. Algorithmic Learn. Theory\n                      (PMLR, New York), 372\u2013399."},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1780"},{"key":"B42","unstructured":"Paris Q (2021) Online learning with exponential weights in metric spaces. Preprint, submitted March 26, https:\/\/arxiv.org\/abs\/2103.14389."},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1214\/12-STS393"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1111\/1540-6261.00453"},{"issue":"3","key":"B45","first-page":"450","volume":"7","author":"Shor NZ","year":"1971","journal-title":"Cybernetics Systems Anal."},{"key":"B46","doi-asserted-by":"crossref","unstructured":"Vaidya PM (1989) A new algorithm for minimizing convex functions over convex sets.\n                      30th Annual Sympos. Foundations Comput. Sci.\n                      (IEEE Computer Society, Washington, DC), 338\u2013343.","DOI":"10.1109\/SFCS.1989.63500"},{"key":"B47","unstructured":"Van Erven T, Van der Hoeven D, Kot\u0142owski W, Koolen WM (2020) Open problem: Fast and optimal online portfolio selection.\n                      Proc. 33rd Conf. Learn. Theory\n                      (PMLR, New York), 3864\u20133869."},{"key":"B48","volume-title":"Probability in High Dimension: Lecture Notes","author":"van Handel R","year":"2016"},{"issue":"270","key":"B49","first-page":"1","volume":"23","author":"Wu K","year":"2022","journal-title":"J. Machine Learn. Res."},{"key":"B50","first-page":"182","volume-title":"Conf. Learn. Theory","author":"Zimmert J","year":"2022"},{"key":"B51","unstructured":"Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent.\n                      Proc. 20th Internat. Conf. Machine Learn.\n                      (AAAI Press, Palo Alto, CA), 928\u2013936."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:23:34Z","timestamp":1778228614000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0175"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0175","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}