Essays on Algorithmic Learning and Uncertainty Quantification

The thesis consists of three essays. The first, titled “Localization, Convexity, and Star Aggregation,” develops new analytical tools based upon the offset Rademacher complexity for studying stochastic optimization in non-convex domains, including statistical prediction and model aggregation problems. Using these tools, I show that a simple procedure called the star algorithm can recover near-optimal convergence rates for non-parametric logistic regression in non-convex models. The second essay, titled “Kernel Ridge Regression Inference,” introduces a new technique for deriving sharp, non-asymptotic, uniform Gaussian approximation for partial sums in a reproducing kernel Hilbert space, which is then applied to construct uniform confidence bands for the widely-used kernel ridge regression algorithm. The third and final essay, titled “Frank-Wolfe Meets Metric Entropy,” uses ideas from asymptotic geometry to derive new dimension-dependent and domain-specific lower bounds for conditional gradient algorithms, a class of optimization procedures including the popular Frank-Wolfe algorithm and many of its variants. Such algorithms have found extensive use in machine learning and high-dimensional statistics, motivating a more thorough analysis of their limitations in high-dimensional problems.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Economics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Vijaykumar, Suhas

Advisors dc:contributor.advisor

• Chernozhukov, Victor
• Mikusheva, Anna

Statement dc:rights

• Attribution 4.0 International (CC BY 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

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

Handle dc:identifier.uri

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/151512