Learning theory is an interdisciplinary field at the intersection of theoretical computer science, statistics, and mathematical optimization. Its central aim is to understand the principles that govern how algorithms learn from data.

Key foundational questions in this area include:

• What does it mean for an algorithm to learn?
• What kinds of functions or tasks can (or cannot) be learned?
• How much data is needed to learn reliably? (sample complexity)
• Can learning be performed efficiently in terms of computation? (computational complexity)
• What is the relationship between the statistical and computational resources required for learning?

In our group, we study all these aspects of learning theory with an integrated perspective that brings together statistical and computational considerations. Some of the central problems we focus on include: 

Probably Approximately Correct (PAC) learning: PAC learning formalizes supervised learning within a probabilistic framework. Here, it is assumed that data points are drawn independently from an unknown distribution. The main question is: How many examples are needed for a learning algorithm to confidently output a low-error predictor, regardless of the underlying distribution? Equally important is the question: Can this be done efficiently?

We investigate these questions from a weak-to-strong learning viewpoint: given an inexpensive algorithm that performs only slightly better than random guessing, is it possible to systematically improve it, or boost it, into one that makes highly accurate predictions?

Stochastic Convex Optimization (SCO): Going beyond classification problems in supervised learning, SCO is another approach that enables sample-optimal and computationally efficient algorithms. The goal is to minimize the expected value of a loss function given access to a sampling oracle, leveraging convexity to ensure tractability.

In our work, we delve into the theoretical foundations of widely used algorithms such as Stochastic Gradient Descent and Stochastic Mirror Descent, especially in realistic scenarios involving very noisy data distributions or limited computational memory—challenges that frequently arise in modern machine learning applications.

Unsupervised Learning: Unsupervised learning aims to uncover hidden structures in unlabeled data. Typical tasks include clustering and dimensionality reduction, both essential tools in modern data science.

Many of these problems are computationally hard, which motivates one of our key research directions: developing efficient approximation algorithms. We explore the use of coresets, compact, weighted summaries of large datasets that allow us to solve problems approximately while preserving key properties of the original data.

Learning Algorithms in Computational Games: Many real-world systems, ranging from markets to ecosystems, can be modeled as games involving multiple agents with competing interests. A central goal is to understand and compute equilibria where each agent’s strategy is optimal given the strategies of the others.

Traditional game-theoretic algorithms, while well-understood and convergent, often struggle with scalability. We study how online learning algorithms, which are lightweight and adaptive, can be applied in this setting. Our focus is on characterizing when such methods converge to equilibrium, their limitations, and how their behavior can be interpreted through economic or social perspectives.

Machine learning has become a transformative technology, driving breakthroughs in areas such as computer vision, natural language processing, autonomous systems, and beyond. These advances have largely been fueled by practical innovations—access to massive datasets, improvements in hardware, and increasingly scalable algorithms. 

However, as these engineering-driven gains begin to plateau, the need for a deeper understanding of the theoretical principles underpinning machine learning becomes more urgent. Foundational research in learning theory is essential not only to sustain progress but also to ensure that machine learning systems remain reliable, robust, and interpretable as they are deployed in high-stakes domains that affect society, such as healthcare, finance, education, and public policy

Our work contributes to this long-term stability by rigorously analyzing what learning systems can achieve, under what conditions, and at what cost—both statistically and computationally. By building the theoretical groundwork today, we help shape a future in which machine learning remains trustworthy, efficient, and accessible for the broader public good.