ARC Colloquium: Nick Harvey (Univ. of British Columbia, Vancouver)

Event Details
  • Date/Time:
    • Monday October 26, 2020
      11:00 am - 12:00 pm
  • Location: Virtual via Bluejeans
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Optimal anytime regret with two experts: Virtual via Bluejeans at 11:00am

Full Summary: No summary paragraph submitted.

Algorithms & Randomness Center (ARC)

Nick Harvey (Univ. of British Columbia, Vancouver)

Monday, October 26, 2020

Virtual via Bluejeans - 11:00 am


Title: Optimal anytime regret with two experts

Abstract:  A central problem in online learning is regret minimization in the expert setting. The famous multiplicative weights method 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 is \gamma \sqrt{t}/2 at all time steps t, where \gamma 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.


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Additional Information

In Campus Calendar


Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Aug 3, 2020 - 12:52pm
  • Last Updated: Oct 20, 2020 - 9:13am