Machine Learning and Algorithms

Latest papers

• How fast can you find a good hypothesis?

  Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal · 12 November 2025

  In the hypothesis selection problem, we are given sample and query access to finite set of candidate distributions (hypotheses), $\mathcal{H} = \{H_1, \ldots, H_n\}$, and samples from an unknown distribution $P$, both over a domain $\mathcal{X}$. The goal is to output a distribution $Q$ whose distan…

• Coherence Mechanisms for Provable Self-Improvement

  Mehryar Mohri, Jon Schneider, Yifan Wu · 12 November 2025

  Self-improvement is a critical capability for large language models and other intelligent systems, enabling them to refine their behavior and internal consistency without external supervision. Despite its importance, prior approaches largely rely on empirical heuristics and lack formal guarantees. I…

• Grouped Discrete Representation for Object-Centric Learning

  Rongzhen Zhao, Vivienne Wang, Juho Kannala, Joni Pajarinen · 11 November 2025

  Object-Centric Learning (OCL) aims to discover objects in images or videos by reconstructing the input. Representative methods achieve this by reconstructing the input as its Variational Autoencoder (VAE) discrete representations, which suppress (super-)pixel noise and enhance object separability. H…

• Finite sample learning of moving targets

  Nikolaus Vertovec, Kostas Margellos, Maria Prandini · 11 November 2025

  We consider a moving target that we seek to learn from samples. Our results extend randomized techniques developed in control and optimization for a constant target to the case where the target is changing. We derive a novel bound on the number of samples that are required to construct a probably ap…

• Language Generation with Infinite Contamination

  Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou · 11 November 2025

  We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language $K$ and must eventually generate new, unseen strings from $K$. Kleinberg and Mullainathan [KM24] proved that generation is achievable in surprisingly general s…

• A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube

  Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan · 11 November 2025

  We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adversary may corrupt some fraction of examples and labels arbitrarily. We achieve an error guarantee of $\eta^{O(1)}+\epsilo…

• Language Generation: Complexity Barriers and Implications for Learning

  Marcelo Arenas, Pablo Barcel\'o, Luis Cofr\'e, Alexander Kozachinskiy · 11 November 2025

  Kleinberg and Mullainathan showed that, in principle, language generation is always possible: with sufficiently many positive examples, a learner can eventually produce sentences indistinguishable from those of a target language. However, the existence of such a guarantee does not speak to its pract…

• Neyman-Pearson Classification under Both Null and Alternative Distributions Shift

  Mohammadreza M. Kalan, Yuyang Deng, Eitan J. Neugut, Samory Kpotufe · 11 November 2025

  We consider the problem of transfer learning in Neyman-Pearson classification, where the objective is to minimize the error w.r.t. a distribution $\mu_1$, subject to the constraint that the error w.r.t. a distribution $\mu_0$ remains below a prescribed threshold. While transfer learning has been ext…

• Near-Exponential Savings for Mean Estimation with Active Learning

  Julian M. Morimoto, Jacob Goldin, Daniel E. Ho · 11 November 2025

  We study the problem of efficiently estimating the mean of a $k$-class random variable, $Y$, using a limited number of labels, $N$, in settings where the analyst has access to auxiliary information (i.e.: covariates) $X$ that may be informative about $Y$. We propose an active learning algorithm ("Pa…

• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

  Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang · 10 November 2025

  We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in R\'enyi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). The proof departs from kno…

• Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

  Jon Kleinberg, Fan Wei · 10 November 2025

  The success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of \emph{language generation in the limit}, where an adversary enumerates strings from an unknown language $K$ drawn from a countable class, and an algorithm must gen…

• A Characterization of List Language Identification in the Limit

  Moses Charikar, Chirag Pabbaraju, Ambuj Tewari · 7 November 2025

  We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct. Classical results of Gold showed …

• Model-Informed Flows for Bayesian Inference

  Joohwan Ko, Justin Domke · 6 November 2025

  Variational inference often struggles with the posterior geometry exhibited by complex hierarchical Bayesian models. Recent advances in flow-based variational families and Variationally Inferred Parameters (VIP) each address aspects of this challenge, but their formal relationship is unexplored. Her…

• Testing with Non-identically Distributed Samples

  Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur, Gregory Valiant · 5 November 2025

  We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we consider the following distributional property testing framework: Suppose there is a set of distributions over a discret…

• Learning CNF formulas from uniform random solutions in the local lemma regime

  Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang · 5 November 2025

  We study the problem of learning a $n$-variables $k$-CNF formula $\Phi$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with $k$-wise hard constraints. Revisiting Valiant's algorithm (Commun. ACM'84), we show that it can exactly learn (1)…

• Optimal Execution with Reinforcement Learning

  Yadh Hafsi, Edoardo Vittori · 4 November 2025

  This study investigates the development of an optimal execution strategy through reinforcement learning, aiming to determine the most effective approach for traders to buy and sell inventory within a finite time horizon. Our proposed model leverages input features derived from the current state of t…

• Cold-Start Active Preference Learning in Socio-Economic Domains

  Mojtaba Fayaz-Bakhsh, Danial Ataee, MohammadAmin Fazli · 4 November 2025

  Active preference learning offers an efficient approach to modeling preferences, but it is hindered by the cold-start problem, which leads to a marked decline in performance when no initial labeled data are available. While cold-start solutions have been proposed for domains such as vision and text,…

• Mechanism Learning: reverse causal inference in the presence of multiple unknown confounding through causally weighted Gaussian mixture models

  Jianqiao Mao, Max A. Little · 4 November 2025

  A major limitation of machine learning (ML) prediction models is that they recover associational, rather than causal, predictive relationships between variables. In high-stakes automation applications of ML this is problematic, as the model often learns spurious, non-causal associations. This paper …

• Calibrating Bayesian Learning via Regularization, Confidence Minimization, and Selective Inference

  Jiayi Huang, Sangwoo Park, Osvaldo Simeone · 4 November 2025

  The application of artificial intelligence (AI) models in fields such as engineering is limited by the known difficulty of quantifying the reliability of an AI's decision. A well-calibrated AI model must correctly report its accuracy on in-distribution (ID) inputs, while also enabling the detection …

• AnomalyMatch: Discovering Rare Objects of Interest with Semi-supervised and Active Learning

  Pablo G\'omez, Laslo E. Ruhberg, Maria Teresa Nardone, David O'Ryan · 31 October 2025

  Anomaly detection in large datasets is essential in astronomy and computer vision. However, due to a scarcity of labelled data, it is often infeasible to apply supervised methods to anomaly detection. We present AnomalyMatch, an anomaly detection framework combining the semi-supervised FixMatch algo…

• Active Learning with Task-Driven Representations for Messy Pools

  Kianoosh Ashouritaklimi, Tom Rainforth · 31 October 2025

  Active learning has the potential to be especially useful for messy, uncurated pools where datapoints vary in relevance to the target task. However, state-of-the-art approaches to this problem currently rely on using fixed, unsupervised representations of the pool, focusing on modifying the acquisit…

• Optimal Information Combining for Multi-Agent Systems Using Adaptive Bias Learning

  Siavash M. Alamouti, Fay Arjomandi · 31 October 2025

  Modern multi-agent systems ranging from sensor networks monitoring critical infrastructure to crowdsourcing platforms aggregating human intelligence can suffer significant performance degradation due to systematic biases that vary with environmental conditions. Current approaches either ignore these…

• Learning-Augmented Online Bipartite Fractional Matching

  Davin Choo, Billy Jin, Yongho Shin · 30 October 2025

  Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmen…

• Hyperparameters in Continual Learning: A Reality Check

  Sungmin Cha, Kyunghyun Cho · 30 October 2025

  Continual learning (CL) aims to train a model on a sequence of tasks (i.e., a CL scenario) while balancing the trade-off between plasticity (learning new tasks) and stability (retaining prior knowledge). The dominantly adopted conventional evaluation protocol for CL algorithms selects the best hyper…

• Feedback Alignment Meets Low-Rank Manifolds: A Structured Recipe for Local Learning

  Arani Roy, Marco P. Apolinario, Shristi Das Biswas, Kaushik Roy · 30 October 2025

  Training deep neural networks (DNNs) with backpropagation (BP) achieves state-of-the-art accuracy but requires global error propagation and full parameterization, leading to substantial memory and computational overhead. Direct Feedback Alignment (DFA) enables local, parallelizable updates with lowe…