QuSoft seminar

Everyone is welcome to attend the online QuSoft seminar with a lecture of Ronald de Wolf: Improved Quantum Boosting. Please contact Jop Briet for access.
  • What English Algorithms & Complexity Seminars
  • When 18-12-2020 from 11:00 to 12:00 (Europe/Amsterdam / UTC100)
  • Contact Name
  • Add event to calendar iCal

Everyone is welcome to attend the online QuSoft seminar with a lecture of Ronald de Wolf: Improved Quantum Boosting.

Abstract:
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong
learner (which generates hypotheses that are much better than random).
Recently, Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a
quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak
learner's hypothesis class, but worse as a function of the quality of the weak learner. In this talk we give a substantially faster and
simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.

Based on joint work with Adam Izdebski.