Machine Learning for Algorithms A Workshop at STOC 2026 · Salt Lake City, Utah · June 22–24, 2026

Abstract

An important question for Retrieval-Augmented Generation (RAG) is how much data (pre-training knowledge) is required to answer reasoning queries with a small number of augmentation steps. To address this question, we formulate multi-step reasoning as an $s$-$t$ connectivity problem on a knowledge graph. We represent a model's data (pre-training parametric knowledge) as a random subset of edges (a random subgraph) of this overall knowledge graph. We view augmentation as querying an oracle for true edges that augment the model's knowledge. Then, we characterize the necessary and sufficient number of augmentation steps for the model to generate an accurate answer given partial prior knowledge. One key result shows a phase transition: if the prior knowledge graph over $n$ vertices is disconnected into small components, then finding a path via augmentation is inefficient and requires $\Omega(\sqrt{n})$ queries. On the other hand, once the density of correct knowledge surpasses a threshold, forming a giant component, we can find paths with an expected constant number of queries.

arXiv:2510.16609 →

Abstract

We introduce Deep Flow Networks (DFNs), a new class of discrete function approximators. DFNs are inspired by and generalize minimum-cost flow value functions that map node imbalances on a subset of nodes to the optimal flow cost. Such functions are known to be M-convex (Murota 2003) and admit efficient optimization.

On the theoretical side, we prove that DFNs are universal approximators for discrete functions on $\mathbb{Z}^d$ that admit convex extensions to $\mathbb{R}^d$, and characterize their optimization complexity in terms of their deviation from the M-convex regime. Guided by these results, we develop a practical DFN implementation for learning from data. Finally, we evaluate our implementation empirically on data from different ground-truth functions, showing that DFNs achieve strong approximation accuracy while being substantially faster to optimize than benchmark approaches.

Manuscript (PDF) →

Abstract

Distribution-free property testing asks whether a Boolean function $f: \{0,1\} \rightarrow \{0,1\}$ satisfies a property $P$ or is $\epsilon$-far from every such function, when test points are drawn from an arbitrary unknown distribution $D$ rather than the uniform measure. This model is the natural formalization of how learned algorithmic components must behave under distributional shift — and is substantially harder than uniform-distribution testing, with most classical speedup techniques failing entirely.

We initiate a systematic study of quantum distribution-free property testing, where the tester receives quantum random examples: coherent superpositions $\sum_f | \sqrt{D(x)} \mid x, f(x) \rangle$ over the unknown D. We show that quantum Fourier sampling under $D$ yields spectral certificates of property violation that are provably inaccessible to any classical tester — including statistical query (SQ) algorithms — at the same sample budget. For halfspaces and polynomial threshold functions, central objects in learning-augmented algorithm design, we establish superpolynomial quantum-classical separations in sample complexity in the distribution-free setting. This contrasts sharply with the near-absence of quantum advantages in the uniform model, and separates the quantum random example model from the quantum SQ model.

Lower bounds are derived via a quantum analogue of the SQ dimension that accounts for distributional uncertainty, and match our upper bounds up to logarithmic factors. Our results identify distribution-free testing as a regime where quantum examples are provably powerful, with implications for quantum PAC learning, data-driven algorithm design, and the structural theory of Boolean functions under non-product distributions.

Abstract

We provide the first analysis of clock auctions in the learning-augmented framework. These auctions satisfy several appealing practical properties, making them well-suited for real-world applications. Unfortunately, early work demonstrated that no deterministic clock auction with $n$ bidders can achieve an $O(\log^{1-\epsilon}{n})$-approximation of the optimal social welfare for constant $\epsilon>0$ in the worst case. This pessimistic impossibility result heavily depends on the assumption that the designer has no information regarding bidders' values. We instead consider a designer equipped with unreliable advice regarding the optimal solution. Our main results are learning-augmented clock auctions that achieve strong performance whenever the advice is accurate (i.e., consistency), while maintaining worst-case guarantees even if this advice is arbitrarily inaccurate (i.e., robustness). Our first clock auction achieves best-of-both-worlds guarantees: $(1+\epsilon)$-consistency for any constant $\epsilon>0$ and $O(\log{n})$-robustness. We then consider a stronger notion of consistency, called consistency$^\infty$, and provide an auction achieving near-optimal trade-offs between consistency$^\infty$ and robustness.

Published version (SIAM) →

Abstract

The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies, performing clinical trials, and hyperparameter selection from learning curves. Each pull of an arm provides reward that increases monotonically with diminishing returns. A growing line of work has designed algorithms for improving bandits, albeit with somewhat pessimistic worst-case guarantees. Indeed, strong lower bounds of $\Omega(k)$ and $\Omega(\sqrt{k})$ multiplicative approximation factors are known for both deterministic and randomized algorithms (respectively) relative to the optimal arm, where $k$ is the number of bandit arms. In this work, we propose two new parameterized families of bandit algorithms and bound the sample complexity of learning the near-optimal algorithm from each family using offline data. The first family we define includes the optimal randomized algorithm from prior work. We show that an appropriately chosen algorithm from this family can achieve stronger guarantees, with optimal dependence on $k$, when the arm reward curves satisfy additional properties related to the strength of concavity. Our second family contains algorithms that both guarantee best-arm identification on well-behaved instances and revert to worst-case guarantees on poorly-behaved instances. Taking a statistical learning perspective on the bandit rewards optimization problem, we achieve stronger data-dependent guarantees without the need for actually verifying whether the assumptions are satisfied.

arXiv:2511.10619 →

Abstract

Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden (STOC 2014), adopts a distribution-free perspective (which parallels the PAC learning framework in learning theory). This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, thus leading to error bounds that do not capture the shape of the learning curves.

In this work we initiate the study of learning curves for revenue maximization and we provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning its learning curve converges to zero for any arbitrary valuation distribution as the number of samples $n \to \infty$. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price then the optimal rate of decay is roughly $1/\sqrt{n}$. Finally, for distributions supported on discrete sets of values, we show that learning curves decay (almost) exponentially fast, a rate unattainable under the PAC framework.

From a technical perspective, establishing lower bounds on learning curves is significantly more challenging than in the PAC framework, as it requires fixing a single hard distribution and proving a bound that holds for infinitely many values of $n$. Conversely, deriving upper bounds involves non-trivial algorithmic principles, including techniques such as regularization and structural risk minimization, which are crucial for achieving optimal learning rates.

arXiv:2604.26922 →

Abstract

Gradient-based iterative optimization methods are the workhorse of modern machine learning. They crucially rely on careful tuning of parameters like learning rate and momentum. However, one typically sets them using heuristic approaches without formal near-optimality guarantees. Recent work by Gupta and Roughgarden studies how to learn a good step-size in gradient descent. However, like most of the literature with theoretical guarantees for gradient-based optimization, their results rely on strong assumptions on the function class including convexity and smoothness which do not hold in typical applications. In this work, we develop novel analytical tools for provably tuning hyperparameters in gradient-based algorithms that apply to non-convex and non-smooth functions. We obtain matching sample complexity bounds for learning the step-size in gradient descent shown for smooth, convex functions in prior work (up to logarithmic factors) but for a much broader class of functions. Our analysis applies to gradient descent on neural networks with commonly used activation functions (including ReLU, sigmoid and tanh). We extend our framework to tuning multiple hyperparameters, including tuning the learning rate schedule, simultaneously tuning momentum and step-size, and pre-training the initialization vector. Our approach can be used to bound the sample complexity for minimizing both the validation loss as well as the number of gradient descent iterations.

arXiv:2512.05084 →

Abstract

Machine learning has emerged as a powerful tool for automatically selecting optimization solvers based on problem characteristics and solver behavior. This work focuses on Pseudo-Boolean Optimization (PBO), an NP-hard problem that generalizes Integer Programming, SAT and MaxSAT. Since solver performance varies substantially across instances and computational budgets, selecting the right solver is critical for obtaining high-quality solutions.

We present two complementary advances in machine learning-based algorithm selection for PBO. First, we develop anytime meta-solvers that incorporate user-specified time limits and predict the solver, or set of solvers, most likely to achieve the best solution quality within the user-prescribed computational time limit. Second, we introduce MetaPB, a new algorithm selection framework that combines traditional static instance features with dynamic probing features obtained from short solver executions, demonstrating the value of integrating solver behavior information into the prediction process.

Extensive experiments on benchmarks from the Pseudo-Boolean Optimization Competition show that the proposed methods consistently outperform the best individual solver and substantially reduce the gap to the theoretical perfect oracle. Furthermore, MetaPB achieves performance competitive with leading commercial solvers while relying exclusively on open-source components. These results establish new state-of-the-art performance for automatic algorithm selection in PBO and highlight the effectiveness of combining instance characteristics, solver dynamics, and time-aware decision making.

Paper (anytime meta-solvers) →  ·  Paper (MetaPB) →

Abstract

Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages.

Abstract

Verifying network reachability under combinatorial link failures is critical for the robustness of complex policy networks. However, this problem poses a double computational intractability. Not only is the combinatorial search for $k$-link failures strongly NP-hard, but evaluating reachability for even a single given failure scenario requires computing non-monotonic control-plane convergence (e.g., BGP), which is itself NP-hard in the worst case. Consequently, traditional exact solvers suffer from intractable state-space explosion.

To overcome this, we propose a learning-augmented sequential search architecture that pairs a Deep Reinforcement Learning (DRL) oracle with a deterministic verifier. Instead of blindly exploring the combinatorial space, our neural agent incrementally predicts the single most critical link to remove based on the strictly accurate, post-convergence routing state. This autoregressive design effectively prunes the massive search tree into a highly directed path, bypassing the double intractability to achieve orders-of-magnitude empirical speedup while maintaining the rigorous correctness guarantees of formal verification.

While our system demonstrates striking empirical success, establishing formal approximation bounds and worst-case guarantees for such learning oracles in non-monotonic policy graphs remains an open theoretical challenge. We present these empirical findings to motivate cross-disciplinary exploration into the theoretical limits of learning-augmented network verification.

Learned oracle implementation (APNOMS 2023) →

Formal approximation bounds remain an open area of ongoing research.

Abstract

Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathcal S \subseteq 2^{[n]}$, and each query to $S \in \mathcal S$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$.

Learnability is governed by the co-occurrence graph associated with $\mathcal S$: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete.

The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity $\widetilde O(n^2/\epsilon^2)$, and this bound is tight in the worst case. On the other hand, if every subset is queryable, the optimal worst-case complexity improves to $\Theta(n/\epsilon^2)$. More generally, we identify hierarchical comparability as a sufficient structural condition on $\mathcal S$ under which the optimal complexity is nearly linear, $\widetilde \Theta(n/\epsilon^2)$, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every $\alpha \in (1,2)$, there exists a query family with optimal PAC rate $\widetilde \Theta(n^\alpha/\epsilon^2)$.

Abstract

There has been growing interest in applying reinforcement learning (RL) to inventory management, either by optimizing over temporal transitions or by learning directly from full historical demand trajectories. This contrasts sharply with classical data-driven approaches, which first estimate demand distributions from past data and then compute well-structured optimal policies via dynamic programming. This paper considers a hybrid approach that combines trajectory-based RL with policy regularization imposing base-stock and (s, S) structures. We provide generalization guarantees for this combined approach for several well-known classes in a T-period dynamic inventory model, using tools from the celebrated Vapnik-Chervonenkis (VC) theory, such as the Pseudo-dimension and Fat-shattering dimension. Our results have implications for regret against the best-in-class policies, and allow for an arbitrary distribution over demand sequences, which makes no assumptions such as independence across time.

Surprisingly, we prove that the class of policies defined by T non-stationary base-stock levels exhibits a generalization error that does not grow with T, whereas the two-parameter (s, S) policy class has a generalization error growing logarithmically with T. Overall, our analysis leverages specific inventory structures within the learning theory framework, and improves sample complexity guarantees even compared to existing results assuming independent demands.

arXiv:2404.11509 →

Abstract

The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud computing motivate bin packing models that capture costs associated with highly utilized servers. In this work, we introduce the green bin packing problem, an online variant with a linear cost $\beta$ for filling above a fixed level $G$. For a given instance, the goal is to minimize the sum of the number of opened bins and the linear cost. We show that when $\beta \le 1/G$, classical online bin packing algorithms such as FirstFit or Harmonic perform well, and can achieve competitive ratios lower than in the classic setting. However, when $\beta > 1/G$, new algorithmic solutions can improve both worst-case and typical performance. We introduce variants of classic online bin packing algorithms and establish theoretical bounds, as well as test their empirical performance.

paper →

Abstract

We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following.

1. For Max-Cut and Max 2-Lin, we design an algorithm that yields near-optimal solutions when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees.

2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still $1/2 + \eta$ hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is $1/2 + \eta$ hard to approximate even when the average degree of the instance is linear in the number of variables.

arXiv:2403.02212 →