Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Edwin A. Perkins

dblp:283/6801 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
0since 2021 · last 2020
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Approximation and online algorithms · 67% Mathematical optimization · 33%

Topics — the 3 heaviest of 3, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Mathematical optimization
multiplicative weights update
0.412020
Optimal anytime regret for two experts · FOCS 2020
Approximation and online algorithms
online learning
0.412020
Optimal anytime regret for two experts · FOCS 2020
Approximation and online algorithms › online learning
prediction with expert advice
0.412020
Optimal anytime regret for two experts · FOCS 2020

Methods — techniques the papers use, named apart from their topics

stochastic calculus · 0.4continuous-time analysis · 0.4
YearPublicationVenuePosition
2020 Optimal anytime regret for two experts
abstract
The multiplicative weights method is an algorithm for the problem of prediction with expert advice. It achieves the optimal regret asymptotically if the number of experts is large, and the time horizon is known in advance. Optimal algorithms are also known if there are exactly two, three or four experts, and the time horizon is known in advance. In the anytime setting, where the time horizon is not known in advance, algorithms can be obtained by the “doubling trick”, but they are not optimal, let alone practical. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret γ√t/2 is at all time steps t, where γ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus. This is the extended abstract of the paper. The full paper can be found in [arXiv:2002.08994].
Nicholas J. A. Harvey, Christopher Liaw, Edwin A. Perkins, Sikander Randhawa
FOCS3