Learning-driven Algorithms and Machine-aided Proofs (LAMP)

As machine learning and AI systems become increasingly pervasive and are deployed in high-stakes domains, developing theoretical foundations to understand and analyze their behavior has become more challenging, yet more pressing than ever before. Modern AI systems learn sophisticated structures that far exceed the analytical reach of classical learning theory and increasingly operate in environments where learning occurs in the presence of other learners.
In this talk, I will present new directions in learning theory that provide principled guarantees for increasingly complex AI systems. I will discuss general learnability guarantees for rich structured objects based on dual function classes and show how they apply to a broad range of settings, including using machine learning for algorithm design and automating hyperparameter tuning for machine learning itself. Finally, I will highlight emerging challenges for learning in the presence of other learners, spanning both cooperative settings and competitive strategic interactions.

Consider the following learning problem. Alice picks a linear order over n elements, and Bob is trying to reveal it. They interact in rounds: in each round Bob proposes a linear order, and if his guess is incorrect, Alice returns a counterexample - a pair whose relative order is wrong. How many rounds can Bob guarantee in the worst case? Does the answer change if the counterexamples are chosen uniformly at random or by other, less adversarial, counterexample generators? What can be said for more restricted families of linear orders? For example, suppose the elements are embedded as points x₁,…,xₙ in ℝᵈ, and the order is determined by their distances to an unknown point x*.
We will discuss these questions, present solutions to some of them, and describe several open problems and partial results.

A central challenge in modern machine learning is learning generalizable procedures that remain effective on unseen, potentially out-of-distribution (OOD) data. Such generalization depends on a complex interplay among model architectures, task structures, data assumptions, and training methodologies. In this talk, I will focus on the interaction between model architecture and task structure in the context of graphs tasks or geometric problems. We are particularly interested in three questions: Do different neural networks learn fundamentally different algorithmic procedures? Can OOD generalization be achieved with only finite samples? How do we probe what's learned internally? How can we use obtained insights help design more effective neural models that can tackle (geometric) problems more efficiently? I will present some of our initial studies exploring these questions. This talk is based on joint work with several collaborators, whom I will acknowledge during the talk.

We consider the problem of sequentially solving linear systems Ax=b, a fundamental problem in scientific computing, and show how to efficiently learn to do (in some cases instance-optimal) linear solver configuration while using only the number of iterations as feedback. Our theoretical results rely on a domain-informed semi-stochastic assumption on the linear systems being solved, which enables the use of anti-concentration to control solver sensitivity. We demonstrate that the approach is practically effective by using it to tune preconditioners in the widely used software OpenFOAM, obtaining a 2x speedup in linear solver wallclock on a magnetohydrodynamics problem. Lastly, we extend its applicability to much larger solver configuration spaces by introducing the first adversarial bandit algorithm that provably takes advantage of losses that are smooth with respect to a similarity graph over the arms.

The prevailing recipe of ever-larger models trained on passively collected data is showing diminishing returns and facing growing constraints on data. To sustain progress, the next phase of AI will hinge on experience: agents and systems that actively curate their own data through interaction. This talk asks: which principles behind today's foundation model pipeline will carry us there, and where do we need new ones?

I present our approach that we use agentic AI to faithfully formalize research papers in Lean, verifying their main results and core reasoning while clearly separating what each paper proves from what it imports from prior work.

Recent months have seen unprecedented breakthroughs in artificial intelligence for mathematical reasoning and scientific verification. From Gemini achieving gold-medal performance at the International Mathematical Olympiad (IMO), to OpenAI’s resolution of long-standing open math problems, to the deployment of the Paper Assistant Tool (PAT) which successfully identified critical theoretical flaws in thousands of submissions to STOC, ICML, and NeurIPS. As task complexity scales to "Level 4" autonomous research, single-pass LLM generations (pass@1) hit a fundamental ceiling due to compounding logical errors and context window limits. In this talk, we unpack the mechanics and theory of Inference-Time Scaling (ITS)—the paradigm of structuring test-time compute to solve intractable problems. We explore how empirical frameworks like the Verification & Refinement (V&R) pipeline and Recursive Self-Aggregation (RSA) successfully decompose complex proofs by separating generation, verification, and combination.
To explain why these frameworks succeed, we introduce Algorithmic Thinking Theory. By modeling inference-scaling pipelines as algorithms interacting with a probabilistic reasoning oracle, we formalize the "Decaying Model" of context noise. Through this mathematical framework, we prove the monotonicity principle of context combination and establish that branching and genetic (aggregation) algorithms theoretically attain the optimal limits of success. Finally, we look toward the future of orchestration, demonstrating how agentic structures like the persistent "Ralph Loop" will transition AI from solving bounded math problems to conducting perpetual, open-ended scientific discovery.
Based on: Algorithmic Thinking Theory. COLT 2026

Algorithms with predictions have emerged as one of the most influential developments in algorithms research over the past decade. By augmenting classical algorithmic decision-making with machine-learned forecasts, this paradigm has led to significant advances across a wide range of optimization and online decision problems. As the field matures, however, it is natural to ask: what are the next fundamental questions and challenges that will shape its future? In this talk, I will discuss two research directions that I find particularly interesting. The first part will explore the search for "universal problems": broad algorithmic principles and design frameworks that transcend individual problems, moving beyond techniques tailored to specific applications toward a more unified theory of algorithms with predictions. The second part will focus on "universal predictions": prediction models that are meaningful across problem domains, enabling a principled study of algorithmic robustness.

We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023). The decision-maker has access to machine-learned predictions of candidate values in advance, and the key challenge is to balance consistency and robustness: when predictions are accurate, the algorithm should hire a near-best secretary; when they are inaccurate, it should still achieve a bounded competitive ratio. We consider both the standard Random Order Secretary Problem (ROSP), where candidates arrive in a uniform random order, and the Chosen Order Secretary Problem (COSP), where the decision-maker chooses the arrival order based on predicted candidate values — capturing scenarios such as an interview schedule set by the decision-maker.
We propose a randomized algorithm that applies to both ROSP and COSP, building on the threshold-based approach of Fujii and Yoshida. For ROSP, our algorithm achieves competitive ratio max{0.221, (1−ε)/(1+ε)}, improving on their bound of max{0.215, (1−ε)/(1+ε)}. For COSP, our algorithm achieves max{0.262, (1−ε)/(1+ε)}, surpassing the 0.25 upper bound on the worst-case competitive ratio of their approach, and getting closer to the classical secretary benchmark of 1/e ≈ 0.368. Our result highlights the benefit of integrating predictions with arrival-order control in online decision-making.
Based on joint work with Helia Karisani, Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, and Cameron Musco; appeared in ITCS 2026.