BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UM//UM*Events//EN
CALSCALE:GREGORIAN
BEGIN:VTIMEZONE
TZID:America/Detroit
TZURL:http://tzurl.org/zoneinfo/America/Detroit
X-LIC-LOCATION:America/Detroit
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20070311T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20071104T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260522T102454
DTSTART;TZID=America/Detroit:20260605T130000
DTEND;TZID=America/Detroit:20260605T150000
SUMMARY:Presentation:Learning with Quantum Examples: Multiclass\, Online\, and Smoothed Settings
DESCRIPTION:Abstract:\n\nAs quantum computing progresses toward fault-tolerant architectures\, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory\, and in particular learning from quantum examples\, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e.\, worst-case) PAC learning\, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast\, under the uniform distribution\, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together\, these results reveal a striking dichotomy. However\, this understanding has largely been developed in the context of learning Boolean functions in the batch setting\, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning\, online learning\, and smoothed learning.\n\nIn the multiclass PAC setting\, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes\, finding that quantum examples continue to yield no distribution-independent separation from classical examples\, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning\, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples\, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon\, we develop a smoothed learning framework that constrains distributions to be smooth\, interpolating between the concentrated-distribution regime\, in which no quantum advantage exists\, and the uniform-distribution regime\, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions\, we show that such separations persist throughout a nontrivial near-uniform regime in both the batch and online settings.\n\nTogether\, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting\, showing that quantum-classical separations depend on the interplay between hypothesis class structure\, distributional assumptions\, and the degree of adversarial control permitted in the learning process.
UID:148398-21904185@events.umich.edu
URL:https://events.umich.edu/event/148398
CLASS:PUBLIC
STATUS:CONFIRMED
CATEGORIES:Dissertation,Graduate,Graduate Students,Mathematics
LOCATION:East Hall - 3088
CONTACT:
END:VEVENT
END:VCALENDAR