Learning with classical and quantum information constraints

In modern data analysis, data may not always be fully accessible to analysts, potentially due to social concerns or physical restrictions. Since data may be costly to acquire, it is important to design data-efficient algorithms under information restrictions. This thesis establishes a general framework for proving the fundamental limit of information-constrained learning and designs sample-optimal algorithms under settings of practical interest. We consider various information constraints, including privacy and communication constraints on classical computers, and inherent randomness governed by the laws of physics in quantum computers. First, we study distribution learning and testing with local information constraints such as local differential privacy (LDP) and communication constraints. We derive a general lower-bound framework for interactive communication protocols. The techniques and ideas in this part lay the foundation for the quantum part. We then investigate user-level information constraints, a practical setup where each user or device may hold multiple samples. We design the first optimal algorithms for distribution estimation under central differential privacy. Finally, we demonstrate how prior ideas for classical problems surprisingly translate to the quantum world. Extending techniques for classical distribution testing, we propose a unified lower-bound framework for quantum state testing with restricted unentangled measurements. As a result, we derive the first known tight sample/copy complexity bounds for finite-outcome unentangled measurements and demonstrate the power of randomness in quantum state testing.

Name thesis:degree_name

Ph. D., Electrical and Computer Engineering

Level thesis:degree_level

Doctor of Philosophy

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Grantor

Cornell University

Year dc:date.issued

2024

Author dc:creator

• Liu, Yuhan

Committee members dc:contributor.committeemember

• Goldfeld, Ziv
• Sridharan, Karthik

• Differential privacy
• Federated learning
• Information theory
• Quantum state testing
• Restricted measurements
• Statistical inference

Statement dc:rights

• Attribution-ShareAlike 4.0 International

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-sa/4.0/

Language dc:language.iso

en

DOI

http://doi.org/10.7298/dfqg-s036

Dc Identifier Other

ProQuest Submission ID: 14665
ProQuest Publication ID: 31562052

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/117252