BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CREST - ECPv5.1.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CREST
X-ORIGINAL-URL:https://crest.science
X-WR-CALDESC:Events for CREST
BEGIN:VTIMEZONE
TZID:Europe/Helsinki
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Helsinki:20230330T170000
DTEND;TZID=Europe/Helsinki:20230330T180000
DTSTAMP:20260711T141248
CREATED:20230328T045846Z
LAST-MODIFIED:20230330T080943Z
UID:14794-1680195600-1680199200@crest.science
SUMMARY:Dmitrii OVSTROSKI - "Fast and optimal algorithm for online portfolio\, and beyond "
DESCRIPTION:Statistical Seminar : \nTime: 5:00 pm – 6:00 pm\nDate: 30th of March 2023\nPlace: Room 3001 + ZOOM \n  \nDmitrii OVSTROSKI – “Fast and optimal algorithm for online portfolio\, and beyond ” \n  \nhttps://ecolepolytechnique.zoom.us/j/84450260075​  \n  \nAbstract: \nIn his seminal 1991 paper\, Thomas M. Cover introduced a simple and elegant mathematical model for stock trading\, which later on came to be known as online portfolio selection (OPS). This model is specified with only two integer parameters: the number of assets d and time horizon T. In each round\, the trader selects a portfolio—distribution of the current capital over the set of d assets; then\, the adversary generates a vector of returns (i.e.\, relative prices of the assets)\, and the trader’s capital is multiplied by the “aggregated return”. Despite its simplicity\, this model captures the two key properties of the stock market: (i) market “plays against” the trader; (ii) money accumulates multiplicatively. In the 30 years that followed\, the OPS model has received a great deal of attention from the learning theory\, information theory\, and quantitative finance communities. \n  \nIn the same paper\, Cover also proposed an algorithm\, termed Universal Portfolios\, that admitted a strong performance guarantee: the regret of O(d log(T)) against the best portfolio in hindsight\, and without any restrictions of returns or portfolios. This guarantee was later on shown to be worst-case optimal\, and no other algorithm attaining it has been found to date. Unfortunately\, exact computation of a universal portfolio amounts to averaging over a log-concave distribution\, which is a challenging task. Addressing this\, Kalai and Vempala (2002) achieved the running time of O(d^4 T^14 ) per round via sampling techniques. However\, with such a running time essentially prohibiting problems of nontrivial size\, yet remaining state-of-the-art\, the problem of finding an optimal and practical OPS algorithm was left open. \n  \nIn this talk\, after discussing some of the arising technical challenges\, I shall present a fast \nand optimal OPS algorithm that combines regret optimality with the runtime of O(d^2 T )\, thus dramatically improving state of the art. As we shall see\, its motivation and analysis are closely related to establishing a sharp bound on the accuracy of the Laplace approximation for a log-concave distribution with a polyhedral support\, which is a result of independent interest. Finally\, I will briefly discuss possible extensions of these ideas beyond the OPS context—in particular\, in quantum state tomography.​ \n  \n  \n  \nOrganizers:\nCristina BUTUCEA (CREST)\, Alexandre TSYBAKOV (CREST)\, Karim LOUNICI (CMAP) \, Jaouad MOURTADA (CREST)\nSponsors:\nCREST-CMAP \n
URL:https://crest.science/event/dmitrii-ovstroski-fast-and-optimal-algorithm-for-online-portfolio-and-beyond/
CATEGORIES:Statistics
ATTACH;FMTTYPE=:
END:VEVENT
END:VCALENDAR