Results 481 - 490 of 24335

As machine learning and AI systems become increasingly pervasive in high-stakes domains, building theoretical foundations to understand and analyze their behavior has become more elusive, yet more pressing than ever before. Modern AI systems learn sophisticated structures that far exceed the analytical reach of classic learning theory.

In this talk, I will present work from my group on the learnability of complex objects within modern AI settings. First, I will discuss new frameworks for training verifiers that can flag off-track inference. These learned verifiers help mitigate catastrophic failure modes of LLMs (e.g., they can appear convincing while being wrong) and, more generally, enhance the reasoning capabilities of current LLM generators.

I will then discuss the learnability of another class of complex objects: algorithms for tasks like pricing or partitioning that are intractable within traditional frameworks. I will present general sample complexity results via dual-function classes applicable to a variety of learning-augmented algorithms.

The Occam's Razor principle is easily expressed in pac learning bounds via noting that hypothesis description length complexity easily appears in these bounds. With the transformer models underlying modern ai agents it appears that there is a different form of occam's razor principle: transformers that learn a simple state generalize and even extrapolate better. The empirical evidence here is stark: a factor of 3(!) reduction in extrapolation error. But what are the principles behind this? Standard PAC theory appears inapplicable.

Abstract: Given points in $n$-dimensional space drawn independently from an arbitrary (unknown) distribution and labeled red or blue so that the colors can be separated by an (unknown) intersection of $k$ halfspaces, can you efficiently compute (learn) a rule to separate the colors?  Avrim posed this question in my first meeting with him 33 years ago, and I've been (happily) struggling with it since. In this talk, I'll describe a simple algorithm with complexity exponential in $\sqrt{n \log(1/\rho) \log k}$, assuming a (soft) margin $\rho$. This improves known results (which are exponential in either $k$ or $1/\rho$) and matches statistical query and cryptographic lower bounds up to the logarithmic factors in $k$ and $1/rho$. 

Joint work with Shyamal Patel.   

A number of Latent Variable Models in Machine Learning (including Mixture Models, Topic Models, Stochastic block models and Mixed Membership Community Mod els) can be abstracted to the geometric problem of learn ing a latent polytope K given data points, each obtained by randomly perturbing a latent point in K. The challenge is that perturbations are typically much larger than the dimensions of K and so data points lie (far) outside K. To tackle this, we introduce the “Subset Smoothed” polytope K′ which is the convex hull of (n/k) points, each obtained by averaging a k− subset of the n data points. [k is a parameter.] We will observe that K′ ≈ K under reasonable assumptions on data. We will also observe that K′ has a polynomial time optimization oracle. These simple observations are the starting point of our provable algorithm for learning K which the talk will describe.

Joint Work with Chiranjib Bhattacharyya, Amit Kumar

In current Large Language Models, we can trust the production of smoothly flowing prose on the basis of the principles of machine learning. However, there is no comparably principled basis to justify trust in the content of the text produced. It appears to be conventional wisdom that addressing this issue by adding more principled reasoning is not computationally affordable.

Here we propose a principled approach to this problem that is efficient enough to be practical for large language models. Further, the method allows the retention of much of the currently used software and hardware base. Our method for improving the functioning of large language models consists of a first stage of preprocessing that recodes the data to a Unary Relational Integracode that is more explicit about the relationships among the objects described in the text, followed as a second stage by a standard but possibly streamlined machine learning process that then also learns to predict these relationships.

The method may be viewed as realizing a world model that applies beyond natural language, to vision and actions, for example, where the multiple properties of an object referred to in an input are brought together explicitly, rather than remaining distributed in the various references to it in the input. We articulate its advantages in terms of Robust Logic, a system for performing principled chaining on learned, and hence uncertain, information. We show that this recoding has the surprising and fortuitous property that, while succinct, it makes a core problem in learning relational rules that hold in the world described in the training data polynomial time learnable, the polynomial depending on the complexity of the rule. This gives heuristic support for sound reasoning within each call of the learned classifier as well as between multiple calls.

We explain how hallucinations in language models are rise in the first place. Prior work has shown how to modify models to reduce hallucinations. We also argue that the reason hallucinations persist is that benchmarks inadvertently reward guessing when unsure, and we discuss incentive compatible ways to modify the benchmarks.

Joint work with Santosh Vempala, Ofir Nachum and Edwin Zhang.

Not long ago, two reasonable assumptions about machine learning were: (1) the primary mechanism to achieve learning is to tune parameters, and (2) because we have little prior knowledge to provide a strong inductive bias, learning must rely on big data and sophisticated statistics. Today, both assumptions seem out of date when one considers architecting learning agents that employ LLMs as subroutines. We will explore this new style of LLM-based learning agents, as well as theoretical questions they raise.