Hypothesis Class

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 25

Sep 27, 2026cs.LG

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

We consider contextual binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm with Gaussian perturbation for each observed context achieves the optimal

\widetilde O(\sqrt{T\log N})

expected regret for a class of

N

experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class

\mathcal H

, the algorithm attains

\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})

regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning.

Gon Buzaglo, Elad Hazan

Department of Computer Science, Princeton University · Google DeepMind

Learning-Augmented Algorithms Hypothesis Class \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Adversarial Robustness Optimistic Follow-The-Regularized-Leader Stochastic

Sep 23, 2026stat.ML

On the Sample Complexity of Active Learning with Membership Queries

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, we find that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular, some hypothesis classes that are inherently slow to learn in the pool-based setting, achieving only polynomial error decay in the number of samples, become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its complexity. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

Ganghua Wang, Shaddin Dughmi

Department of Mathematics University of Arizona · Department of Computer Science University of Southern California

Pool-Based Active Learning Active Learning Hypothesis Class Membership Inference Sample Complexity

Sep 17, 2026cs.PL

The Output-Space Hypothesis: Enumerative Equivalence Checking for Tensor Programs

Tensor programs, as used in deep learning models, are a prime target for optimization, as small performance improvements can have a large impact across training or inference workloads. However, such optimizations are complicated and can produce subtle bugs. Traditionally, correctness is assumed when differential testing against a reference on random inputs fails to reveal bugs. However, the inputs to these programs are massive tensors, and finding bugs can require generating extremely low likelihood inputs with precise relationships among their values. We propose a novel way to find bugs more consistently by flipping the quantifiers. Rather than generating a single input and checking all output tensor locations for equivalence, what if you could check a single output tensor location's equivalence for all inputs? We implement this idea in a system, \dirigo, by using a novel symbolic execution strategy. We demonstrate that \dirigo can find bugs effectively in a public dataset of 6,988 AI-written CUDA kernels that are all marked correct by differential testing. Of these, \dirigo finds 600 kernels that are actually buggy, and finds 97.3% of those bugs within two minutes.

Paul Biberstein, Joseph Devietti, Mayur Naik

University of Pennsylvania Philadelphia, PA, USA

Cuda Bug Tensor Networks Inference Workloads Equivalence Hypothesis Class

Aug 31, 2026stat.ML

Learning the Geometry of Admissible Hypotheses through Inductive Bias in Training Distributions

Scientific discovery often requires reasoning over competing hypotheses that are consistent with experimental observations. For mixed-variable and combinatorial hypothesis spaces, however, constructing probabilistic representations remains challenging because both the active model components and their associated parameters are unknown. In this work, we present a framework for learning continuous latent representations of admissible partial differential equations (PDEs) by embedding a scientific inductive bias directly into the training distribution. Progressively richer structural principles (e.g., sparsity, logical dependencies, common PDE families, and physical admissibility) are used to generate a structured distribution of hypotheses from which a gated variational autoencoder learns a continuous latent manifold. Experimental results show that the resulting 11-dimensional representation accurately reconstructs a broad collection of representative PDEs, while exhibiting smooth geometric transitions both within and across equation families. Through an ablation study we further demonstrate that introducing scientific principles reduces both structural misclassifications of equation forms and parameter estimation errors when reconstructing a representative benchmark set of admissible partial differential equations. These results show that embedding a scientific inductive bias in the training distribution enables the learning of compact and geometrically meaningful hypothesis manifolds, providing a principled foundation for future inference over competing governing equations.

James Crowley, Faez Ahmed, Anton van Beek

School of Mechanical and Material Engineering University College Dublin · Department of Mechanical Engineering Massachusets Institute of Technology

Partial Differential Equations Hypothesis Class Inductive Bias Probabilistic Model Autoencoder Architectures

Aug 13, 2026cs.LG

Defensive Boosting for Online Probabilistic Forecasting

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class

H

, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of

H

on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of

H

at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

Georgy Noarov, Aaron Roth

Probabilistic Forecasting Learning-Augmented Algorithms Data-Driven Forecasting Hypothesis Class LLM Defense Mechanisms

Aug 9, 2026cs.LG

Constrained Learning with Universally Learnable Concept Classes

We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS

\mathcal{H}_K

, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity

\mathfrak{T}^{\varepsilon}_{n}

, the least RKHS norm reaching an

\varepsilon

-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in

1/\varepsilon

under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap

\varepsilon^\star_\infty

, an index of how well

\mathcal{H}_K

retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when

\varepsilon^\star_\infty=0

, in particular under dual differentiability, and near-PACC with residual exactly

\varepsilon^\star_\infty

otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.

Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

1Yale University · 2King’s College London

Learnability Uncoupled Learning Primal-Dual Methods Hypothesis Class Nonconvex Lyapunov Function

Aug 3, 2026cs.AI

Hypercubes, Hyperplanes, and Constraint-Induced Complexity Collapse in Atomic Concept Learning

We revisit higher-arity atomic concept learning through the geometry of hypercubes and hyperplanes of ground instances. Our starting point is the observation that the ambient r-dimensional hypercube of ground atoms is not structurally uniform. Its logical complexity is organized by hyperplanes: every hyperplane other than the full diagonal collapses into finitely many elementary-equivalence classes, with a bound independent of the term depth, while the full diagonal is exceptional and its class count grows without bound. This asymmetry is not merely geometric. It reflects the reduction-theoretic structure of the concepts themselves. Building on a higher-dimensional framework developed in the author's earlier work, we reinterpret these results through canonical simple concepts, minimal orderings, and representative reductions. This yields a taxonomy of hyperplane behavior in higher dimensions and shows that complexity is localized rather than spread uniformly through the instance space. The paper includes a fully worked binary case, an explicit treatment of the ternary hypercube, and an unpacked account of the reduction machinery that drives the collapse. The three-dimensional case already exhibits the essential phenomenon of orthogonal families, partial diagonals, and the exceptional full diagonal. This geometric-logical perspective clarifies where complexity is concentrated in atomic concept learning and suggests a modern interpretation in terms of constrained hypothesis spaces and structured classification.

Irene Tsapara

National University, San Diego, United States

Hypothesis Class Atoms Equivalence

Jul 30, 2026cs.LG

Fast Rates for Swap-Agnostic Learning of Proper Losses

Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem for every possible prediction value. We show that, for proper losses, these prediction-level comparisons can instead be controlled jointly. Our main result is an offline swap-agnostic learner for any fixed proper loss. For a finite hypothesis class

H

and any fixed smooth proper loss, the excess risk from

m

i.i.d. samples is

\widetilde{O}((\log |H|/m)^{2/3})

, with a corresponding online swap-regret bound of

\widetilde{O}(T^{1/3}(\log |H|)^{2/3})

. We also give algorithms whose predictions are simultaneously swap-agnostic for entire families of losses. For all proper losses bounded in

[-1,1]

, we obtain online and offline rates of

\widetilde{O}(\sqrt{T\log |H|})

and

\widetilde{O}(\sqrt{\log |H|/m})

, respectively. For convex,

1

-Lipschitz proper losses, these rates improve to

\widetilde{O}(T^{1/3}(\log |H|)^{2/3})

online and

\widetilde{O}((\log |H|/m)^{2/3})

offline. These bounds are tight up to logarithmic factors and improve upon the

\widetilde{O}(T^{2/3}(\log |H|)^{1/3})

rate implied by the swap-omniprediction guarantee of Luo et al. (2025). Our main technical contribution is a reduction from swap-agnostic learning to a second-order form of multicalibration, obtained via Blackwell approachability with a Bernstein-style variance correction.

Princewill Okoroafor

Harvard University

Learning-Augmented Algorithms Optimal Sample Complexity Hypothesis Class

Jul 17, 2026cs.LG

Hierarchical Domain Generalization

We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i.i.d. sampling with arbitrary domain hierarchies. We show that the central obstruction is not only the complexity of the hypothesis class, but the train/test domain partition through which evidence is revealed. In particular, no matter how small the class or how large the training size, some partition makes generalization fail for some target. These results suggest that modern generalization theory must treat domain structure as a first-class object.

Chenxiao Yang, Zhiyuan Li, Shai Ben-David +1

Toyota Technological Institute at Chicago · University of Waterloo

Multimodal Domain Generalization Hypothesis Class

Jun 28, 2026cs.LG

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g.,

\{+,\times,\sin,\exp\}

and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth

d

and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size

K=|\mathcal{H}_{\mathrm{base}}|

together with Maurer-type vector contraction yields

\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})

with arity bound

b

; corresponding high-probability risk bounds scale as

\mathcal{O}(L^{d}/\sqrt{n})

when

K,b=O(1)

and

\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2})

. We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term

(\widehat{L}^{d})/\sqrt{n}

.

Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

Independent Researcher · TÜBİTAK Science High School

Symbolic Regression Sample Complexity Hypothesis Class Learnability Model Discovery Scientific Discovery

Jun 13, 2026stat.ML

Finite Resources False Discovery Rate Control in Structured Hypothesis Spaces

Scientific discovery relies on large-scale hypothesis testing. However, the capacity to identify true discoveries while controlling false discovery faces major challenges: obtaining relevant reference data (the null distribution) is resource-intensive, leaving finite-data uncertainty, and the procedure should account for the inherent structure in the hypothesis space, when such structure exists. Here, we present a framework for controlling the false discovery rate both when each hypothesis is evidenced only by a finite count of null draws, leaving its p-value uncertain, and when the hypothesis space carries arbitrary structure, requiring only that the structure be represented through a suitable reproducing kernel. We present two decision rules that are both robust to structural mis-specification, yet offer a distinct trade-off between exact FDR control and statistical power. The first rule guarantees exact FDR control; the second maximizes power by adapting mirror-statistic control into count space, utilizing an analytical framework to assess FDR control when exact mirror symmetry is relaxed. Furthermore, the tractability gained by the RKHS framework allows us to directly investigate finite-data uncertainties, which we leverage to suggest a policy for the efficient allocation of null distribution samples.

Binyamin Perets, Shie Mannor

Technion – Israel Institute of Technology · NVIDIA

False Discovery Rate Two-Sample Testing Hypothesis Class Scientific Discovery

Jun 12, 2026cs.LG

A Complexity Measure for Active Learning in Multi-group Mean Estimation

We study a \emph{max-risk} objective for active learning in a multi-group mean estimation

d

-armed bandits: a learner adaptively allocates a budget of

T

samples across

d

groups to minimize the worst-case uncertainty index

\max_{k\in[d]}σ_k^2/n_k

, where

σ_k

is the standard deviation of the distribution of arm

d

, and

n_k

is the number of times arm

d

is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} (

\mathrm{VLC}

), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the

\mathrm{VLC}

is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced

\ell_1

geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub

Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University

Active Learning Optimal Sample Complexity Hypothesis Class Minimax Cohort

Jun 12, 2026cs.LG

Discovery under Hypothesis Redundancy: A Geometric Theory of Discovery Bottlenecks

Scientific discovery saturates when new hypotheses cease to provide independent information, even if the nominal hypothesis space remains large. We study hybrid discovery systems that combine structured local search with LLM-generated non-local proposals and pose the Search Compression Hypothesis: non-local exploration helps only when three geometric conditions co-occur: spectral compression, orthogonal escape from the explored span, and residual signal alignment with the target. We formalize these conditions, derive necessary conditions for hybrid advantage, and test the mechanism in controlled synthetic environments, large-scale A-share factor discovery, and symbolic-regression benchmarks; a public tabular operational sanity check tests the associated budget-allocation implication. Signal-planting and directed-versus-random experiments show that novelty alone is insufficient: random orthogonal jumps expand coverage but do not improve yield without predictive alignment. Across compression sweeps, real factor archives, and LLM-SRBench tasks, hybrid gains concentrate in weakly represented but target-bearing directions and vanish as the hypothesis space approaches full rank. The framework turns LLM-guided discovery from generic novelty search into a diagnostic procedure for deciding when directed non-local exploration is warranted.

Li Xia, Baoxun Wang

School of Economics and Management, Tsinghua University · Platform & Content Group, Tencent

Model Discovery Discovery Hypothesis Class Stochastic Exploration Redundancy Theory+2

Jun 6, 2026cs.CY

Contemporary AI lacks the imagination to diverge or negate in science

Bold projections that artificial intelligence will accelerate scientific discovery have raced ahead of evidence from working scientists, and the field still lacks large-scale, scientist-in-the-loop tests of these claims. Here we mount the largest such evaluation to date and map what AI cannot yet do for science. We invited authors of 121,640 recent preprints across biology, medicine, chemistry, and the social sciences to judge ideas that large language models (LLMs) generated from the context and puzzles of their own papers. 6,749 scientists returned 25,139 sets of ratings on novelty, empirical feasibility, probability of being true, and favorability of adoption. Three patterns emerge. First, non-reasoning LLMs collapse into a narrow "hivemind" of similar ideas; reasoning models roam a wider hypothesis space, yet no model class spontaneously proposes null hypotheses -- a move humans make more freely. Second, scientists reward ideas that resemble their own and prize probability over novelty, though social scientists tolerate risk more readily than life scientists. Senior social scientists are the harshest critics, and their skepticism is well-earned: LLMs falter most in pluralistic fields like the social sciences that demand context-aware interpretation and evolving theories. Third, automated evaluators on which the community currently relies -- LLM-as-a-judge, artificial metrics, and even state-of-the-art (SOTA) models -- agree only weakly with expert judgment, and retrieval augmentation and scientist persona prompting yield only marginal gains. A Qwen3-14B reward model we post-trained on human ratings captures field taste nuances, beats SOTA models by up to 27%, and closes the gap to the inter-rater consistency of independent peer reviewers. For all the hype, today's scientific AI still represents a collaborator whose imagination, outputs and judgment benefit from human grounding.

Honglin Bao, Siyang Wu, Xiao Liu +3

Data Science Institute, University of Chicago · Knowledge Lab, University of Chicago

Scientific Discovery Artificial Intelligence Evaluation Peer Review Artificial Intelligence Systems Computational Social Science Inter-Annotator Agreement+2

Jun 5, 2026cs.AI

Quantum-Inspired Trace-Augmented Evidence Selection for Reasoning over Structured Hypothesis Spaces

Large language models (LLMs) now solve a wide range of expert-level exams at or above human level, yet remain brittle on specialised, evidence-intensive domains such as law. On these tasks, errors arise not only from gaps in world knowledge but also from subtle distinctions between pieces of evidence and inconsistent use of supporting evidence. The most common aggregator over sampled chain-of-thought (CoT) traces, majority vote, returns the most popular answer regardless of whether its evidence is actually strongest. We propose to treat the selection of CoT reasoning fragments into a set of evidence as an explicit combinatorial optimisation problem, allowing well-supported but minority hypotheses to override noisy majorities, and to evaluate the approach on legal-reasoning benchmarks that are particularly sensitive to evidence quality. We introduce EP-HUBO (Evidence Pool Higher-Order Binary Optimisation), which generates multiple CoT traces with a small local model, parses fragments into per-hypothesis evidence pools, solves a higher-order unconstrained binary optimisation per pool with quality-derived weights (relevance, specificity, distinctiveness), and delegates a single adjudication call per question to a frontier model. We evaluate EP-HUBO on two evidence-intensive legal benchmarks using both simulated annealing on classical hardware and the Dirac-3 photonic entropy-quantum machine from Quantum Computing Inc. HUBO-style optimisation gives a principled way to aggregate reasoning fragments while preserving minority-but-correct hypotheses, and is most valuable in low-contamination domains where frontier models have not already absorbed the benchmark material.

Laura Wynter, Nirvik Sahoo, Paul Griffin

School of Computing and Information Systems Singapore Management University Singapore

Legal Reasoning Tasks Legal Domain Chain-of-Thought Reasoning Hypothesis Class Minority

May 31, 2026cs.LO

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?

We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.

Michael Benedikt, Alessio Mansutti

University of Oxford, UK · IMDEA Software Institute, Spain

Hypothesis Class Tractability Finite-Sample Infinities

May 28, 2026cs.LG

The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity

This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the

γ

-graph dimension characterizes learnability for a broad class of natural aggregation procedures. Furthermore, we prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures, and is strictly more powerful than proper learning. Finally, we show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses or by using non-interpolating aggregation rules (which may predict outside the range of their inputs), and any finite interpolating aggregation fails to achieve even trivial performance.

Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou

Department of Computer Science, Aarhus University, Aarhus, Denmark · Department of Statistics, University of Oxford, Oxford, United Kingdom

Stochastic Interpolants Learnability Optimal Sample Complexity Hypothesis Class Interpolation

May 17, 2026stat.ME

Controlling False Discovery in Arbitrarily Structured Hypothesis Spaces via Reproducing Kernels

Large-scale hypothesis testing is central to modern science, where controlling the False Discovery Rate (FDR) has become the standard approach to managing false positives across many simultaneous tests. Hypotheses rarely exist in isolation; they often exhibit structure through proximity, connectivity, or hierarchy. This structure represents both a challenge and an opportunity: while classical methods treat these dependencies as obstacles requiring conservative correction, leveraging them can substantially increase discovery power. Here, we reframe structured FDR control as a regularized learning problem. By optimizing within a suitable Reproducing Kernel Hilbert Space (RKHS), we introduce a framework that unifies continuous domains, graphs, and hierarchies under a single algorithm through kernel choice alone. This formulation enables smooth solutions in place of the piecewise-constant fits of prior methods, principled likelihood-based hyperparameter selection rather than heuristic tuning, and inference at unobserved locations which in turn supports sample-efficient experimental design. Building on this estimator, we provide two decision rules which we prove to control the FDR. We validate our method on two sources: spatial locations derived from high-dimensional real-world datasets, and a differential gene expression task utilizing protein-protein interaction graphs.

Binyamin Perets, Shie Mannor

Technion – Israel Institute of Technology · NVIDIA

False Discovery Rate Reproducing Kernel Hilbert Spaces Hypothesis Class Two-Sample Testing Exponential Family Regularization+1

May 13, 2026cs.LG

Strategic PAC Learnability via Geometric Definability

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension

1

on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over

\mathbb{R}_{\mathtt{exp}}

. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including

\ell_p

distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.

Yuval Filmus, Shay Moran, Elizaveta Nesterova +2

Faculty of Mathematics, Technion – Israel Institute of Technology. · Faculty of Computer Science, Technion – Israel Institute of Technology. · Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology. +1

Hypothesis Class Learnability Structural Complexity Voice Conversion

May 13, 2026stat.ML

A Survey on Data-Dependent Worst-Case Generalization Bounds

Deep neural networks generalize well despite being heavily overparameterized, in apparent contradiction with classical learning theory based on uniform convergence over fixed hypothesis spaces. Uniform bounds over the entire parameter space are vacuous in this regime, and recent work has shown that non-vacuous guarantees can be recovered by restricting attention to the part of parameter space that the algorithm actually visits. This survey paper organizes this line of work around three steps: extending PAC-Bayesian theory to random, data-dependent hypothesis sets (arXiv:2404.17442); refining the complexity term with geometric and topological descriptors of the optimization trajectory, including fractal dimensions, alpha-weighted lifetime sums, and positive magnitude (arXiv:2006.09313, arXiv:2302.02766, arXiv:2407.08723); and replacing the resulting information-theoretic terms by stability assumptions (arXiv:2507.06775). We unify these contributions around a single template inequality and a head-to-head comparison of the resulting bounds.

Hubert Leroux, Jean Marcus, Julien Roger

´Ecole polytechnique Palaiseau, France

Generalization Bounds Overparameterization Upper Bounds Pac-Bayesian Theory Hypothesis Class Survey

May 8, 2026cs.LG

CellScientist: From Execution Feedback to Auditable Model-Revision Trajectories for Cellular Perturbation Prediction

Cellular perturbation-response modeling requires coordinated choices of representations, fusion mechanisms, objectives, and training procedures. Large language models (LLMs) can propose executable candidates, but unconstrained revision can produce invalid implementations, change task semantics, or discard useful components. We present CellScientist, a protocol-constrained workflow that converts execution and validation feedback into auditable model-revision trajectories. It records design states and outcomes, routes discrepancies to specific components, and applies local revisions under a fixed task contract. A matched-budget study fixes the candidate language, predictor, fitting, and evaluator: structured revision finds better held-out predictors at small budgets under two LLM backbones. Operational audits link history to fewer repeated proposals, contract checks to contained violations, and discrepancy routing to targeted repairs. Refits of two frozen designs on an independently acquired cohort evaluate external predictive utility. Open-workflow trajectories retain improvements, regressions, and failures, while transcriptomic and single-cell searches extend application to additional response spaces. CellScientist produces both a selected predictor and an inspectable record of its development. Project page: https://limengran98.github.io/CellScientist/.

Mengran Li, Bo Li, Jiaying Wang +7

Center for Artificial Intelligence and Robotics (CAIR), Hong Kong Institute of Science and Innovation (HKISI)

Virtual Cell Single-Cell Perturbation Prediction Heterogeneous Modeling Tools Scientific Agents Hypothesis Class Vehicle Routing Problem

May 7, 2026stat.ML

Ratio-based Loss Functions

Algorithms in machine learning and AI do critically depend on at least three key components: (i) the risk function, which is the expectation of the loss function, (ii) the function space, which is often called the hypothesis space, and (iii) the set of probability measures, which are allowed for the specified algorithm. This paper gives a survey of a certain class of loss functions, which we call ratio-based. In supervised learning, margin-based loss functions for classification tasks depending on the product of the output values

y_i

and the predictions

f(x_i)

as well as distance-based loss functions depending on the difference of

y_i

and

f(x_i)

for regression are common. Distance-based loss functions are in particular useful, if an additive model assumption seems plausible, i.e. the common signal plus noise assumption. However, in the literature, several loss functions proposed for regression purposes have a multiplicative error structure in mind and pay attention to relative errors, i.e. to the ratio of

y_i

and

f(x_i)

. In this survey article, we systematically investigate such ratio-based loss functions and propose a few new losses, which may be interesting for future research. We concentrate on investigating general properties of ratio-based loss functions like continuity, Lipschitz-continuity, convexity, and differentiability, because these properties play a central role in most machine learning algorithms. Therefore, we do not focus on some specific machine learning algorithm to derive universal consistency, learning rates, or stability results. Instead, we want to enable future research in this direction.

Lena Helgerth, Andreas Christmann

Department of Mathematics, University of Bayreuth, Chair of Stochastics and Machine Learning, 95440 Bayreuth, Germany

Loss Function Lipschitz Continuity Hypothesis Class

May 5, 2026cs.LG

Realizable Bayes-Consistency for General Metric Losses

We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond

0

-

1

classification (Bousquet et al., 2020; Hanneke et al., 2021) and real-valued regression (Attias et al., 2024). Given an instance space

(X,ρ)

, a label space

(Y,\ell)

with possibly unbounded loss, and a hypothesis class

H \subseteq Y^{X}

, we resolve the realizable case of an open problem presented in Tsir Cohen and Kontorovich (2022). Specifically, we find the necessary and sufficient conditions on the hypothesis class

H

under which there exists a distribution-free learning rule whose risk converges almost surely to the best-in-class risk (which is zero) for every realizable data-generating distribution. Our main contribution is this sharp characterization in terms of a combinatorial obstruction: Similarly to Attias et al. (2024), we introduce the notion of an infinite non-decreasing

(γ_k)

-Littlestone tree, where

γ_k \to \infty

. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.

Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich

1Ben-Gurion University of the Negev · 2Purdue University, USA.

Hypothesis Class Pac-Bayesian Theory Metric Spaces Loss Function

Apr 27, 2026cs.LG

The Optimal Sample Complexity of Multiclass and List Learning

While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of

\sqrt{\text{DS}}

has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.

Chirag Pabbaraju

Stanford University

Multiclass Classification Optimal Sample Complexity Sample Complexity Hypothesis Class Hypergraphs Algebraic Structures

Apr 21, 2026cs.AI

Separable Pathways for Causal Reasoning: How Architectural Scaffolding Enables Hypothesis-Space Restructuring in LLM Agents

Causal discovery through experimentation and intervention is fundamental to robust problem solving. It requires not just updating beliefs within a fixed framework but revising the hypothesis space itself, a capacity current AI agents lack when evidence demands representations they have not previously constructed. We extend the blicket detector paradigm from developmental science to test this capacity in AI agents equipped with architectural scaffolding that targets hypothesis-space restructuring. Our compositional architecture has two discrete components: context graphs, which structure exploration as typed state machines, and dynamic behaviors, which monitor for evidence that the current hypothesis space is inadequate and expand it at runtime. Across 1,085 experimental trials, these components make orthogonal contributions: context graphs drive reasoning quality within the post-switch hypothesis space, accounting for 94% of the accuracy gain, while dynamic behaviors drive reasoning eligibility by detecting regime changes and preventing premature commitment to outdated hypotheses.

John Alderete, Sebastian Benthal, Connie Xu +1

Amigo AI · Simon Fraser University · International Computer Science Institute

Agentic Reasoning Hypothesis-Driven Model Expansion Artificial Intelligence Agents Large Language Model Agents Causal Reasoning Hypothesis Class