Enhancing Learning Algorithms via Sublinear-Time Methods

Our society increasingly relies on algorithms and data analysis to make critical decisions. Yet, almost all work in the theory of supervised learning has long relied on the following two assumptions: 1. Distributional assumptions: data satisfies conditions such as Gaussianity or uniformity. 2. No distribution shift: data distribution does not change between training and deployment. While natural and often correct, these assumptions oftentimes do not hold. Yet, these assumptions are routinely made for giving theoretical guarantees for supervised learning algorithms. These guarantees can become null and void, should one of these algorithms be used in a setting where these assumptions do not hold. Overall, if critical decisions rely on theoretical reliability guarantees, incorrect assumptions can result in catastrophic failure. The first part of this thesis shows how to mitigate this dependence. We introduce and develop testers which can alert a user if some assumptions are not satisfied. Leveraging insights from the area of property testing, the first part of this thesis constructs such testers for a number of well-studied function classes, addressing distributional assumptions and distribution shift. The second part of this thesis shows how insights from sublinear-time algorithms can also be used to make learning algorithms more runtime-efficient. We show that sublinear-time local algorithms, capable of deriving partial solutions by examining only a fraction of the input, can be used as a powerful primitive to resolve problems in learning theory.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Vasilyan, Arsen

Advisors dc:contributor.advisor

• Kelner, Jonathan
• Rubinfeld, Ronitt

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156652

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156652