Learnability

Follow this topic Ask about this topic

Momentum

15 papers in the last four weeks, up 67% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 126

All topics

No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems
Jun 16, 2026Khoat ThanAlgorithmic Fairness Learnability
Hanoi University of Science and Technology
ALCL: An Adaptive Log-Correntropy Loss for Robust Learning under Non-Gaussian Noise
Jun 14, 2026Mainak Kundu, Ria Kanjilal, Ismail UysalNoise-Aware Learnability
Department of Electrical Engineering, University of South Florida, Tampa, FL 33620 USA · Department of Computer Engineering, California Polytechnic State University, San Luis Obispo, CA 93407 USA
Learning High Coverage Discriminative Parsimonious Rulesets
Jun 12, 2026Mariamma Antony, Raman Sankaran, Chiranjib Bhattacharyya +1Interpretability Discriminative
Indian Institute of Science, CV Raman Rd, Bengaluru, Karnataka 560012 · Compass, Bengaluru, Karnataka 560012
Learning with Simulators: No Regret in a Computationally Bounded World
Jun 11, 2026Sasha Voitovych, Abhishek Shetty, Noah Golowich +1Learnability Regret
MIT · Microsoft Research
Information Lattice Learning as Probabilistic Graphical Model Structure Learning
Jun 11, 2026Haizi Yu, Lav R. VarshneyProbabilistic Inference Factor Graphs
Kocree, Inc. · AI Innovation Institute, Stony Brook University
Learning from almost nothing: How neural networks survive heavy input corruption
Jun 9, 2026Justin Tahmassebpur, Asadullah Bhuiyan, Hyejin Kim +1Learnability Neural Network
Department of Applied and Engineering Physics, Cornell University, Ithaca, NY 14853, USA · Department of Physics, Cornell University, Ithaca, NY 14853, USA
Robust Regression of General ReLUs with Queries
Jun 9, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen MaLearnability Rectified Linear Unit
University of Wisconsin-Madison · University of California, San Diego
Causally Evaluating the Learnability of Formal Language Tasks
Jun 8, 2026Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda +3Legal Natural Language Processing Benchmarks Learnability
1ETH Zürich · University of Copenhagen · *Now at Google
Tight Sample Complexity of Transformers
Jun 8, 2026Chenxiao Yang, Nathan Srebro, Zhiyuan LiTransformer Architectures Sample Complexity
Toyota Technological Institute at Chicago (TTIC)
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
Jun 7, 2026Blanka Köver, Alexandra Butoi, Anej Svete +2Transformer Architectures Activation Functions
Department of Mathematics, ETH Zürich, Zürich, Switzerland · Department of Computer Science, ETH Zürich, Zürich, Switzerland · Department of Language Science and Technology, Saarland University, Saarbrücken, Germany.
Trust Functions: Near-Lossless Weak-to-Strong Generalization by Learning When to Trust the Weak Teacher
May 31, 2026Arda Uzunoglu, Alvin Zhang, Daniel KhashabiLearnability Teacher
Department of Computer Science, Johns Hopkins University, Maryland, United States.
Hedging on the Frontier: Learning New Tasks with Few Samples
May 29, 2026Tobias Wegel, Federico Di Gennaro, Geelon So +1Learnability Monotonicity
Department of Computer Science, ETH Zurich · Department of Computer Science and Engineering, UC San Diego
LARK: Learnability-Grounded Trajectory Selection for Efficient Reasoning Distillation
May 28, 2026Tianrun Yu, Kaixiang Zhao, Chih-Chun Chen +5Reasoning Trajectory Learnability
Brigham Young University · The Pennsylvania State University · University of North Carolina at Chapel Hill
Universal Multiclass Transductive Online Learning
May 28, 2026Steve Hanneke, Hongao WangTransductive Learning Learnability
Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA
On Language Generation in the Limit with Bounded Memory
May 28, 2026Jon Kleinberg, Anay Mehrotra, Amin Saberi +1Bounded-Memory Learnability
Cornell University · Stanford University · Google Research
The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
May 28, 2026Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu ZouStochastic Interpolants Learnability
Department of Computer Science, Aarhus University, Aarhus, Denmark · Department of Statistics, University of Oxford, Oxford, United Kingdom
The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
May 28, 2026Wei LuoTractability Context-Free Grammars
School of Information Technology, Deakin University
Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Data
May 28, 2026Collin Cranston, Zhichao Wang, Todd Kemp +1Kernel Method Spectral Decomposition
Department of Mathematics University of California, San Diego, USA · ICSI and Department of Statistics University of California, Berkeley, USA · ICSI, LBNL and Department of Statistics University of California, Berkeley, USA
Unification and Optimization of Robust Supervised Learning
May 27, 2026Jonas Hanselle, Valentin Margraf, Clemens Damke +1Empirical Risk Minimization Learnability
LMU Munich, MCML · LMU Munich, MCML, DFKI
On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective
May 27, 2026Zhi Zhou, Ming Yang, Shi-Yu Tian +3Stable Test-Time Adaptation Test-Time Adaptation
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · School of Intelligence Science and Technology, Nanjing University, China
Restoring the Sweet Spot: Pass-Rate Weighted Self-Distillation for LLM Reasoning
May 26, 2026Zehao Liu, Yuanpu Cao, Jinghui Chen +1Unsupervised On-Policy Self-Distillation Self-Distillation Framework
College of Information Sciences and Technology Pennsylvania State University
A computational phase transition for learning-to-sample from Ising models
May 23, 2026Andrej Risteski, Thuy-Duong VuongSpatial Photonic Ising Machines Phase Transitions
Machine Learning Department, Carnegie Mellon University. · Department of Computer Science and Engineering, UC San Diego.
Toward Understanding Adversarial Distillation: Why Robust Teachers Fail
May 21, 2026Hongsin Lee, Hye Won ChungTeacher-Student Distillation Dataset Distillation
School of Electrical Engineering, KAIST, Daejeon, Korea.
Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
May 20, 2026Ilias Diakonikolas, Giannis Iakovidis, Mingchen MaMulticlass Classification Learnability
University of Wisconsin-Madison
A Sharper Picture of Generalization in Transformers
May 20, 2026Paul Lintilhac, Sair ShaikhGeneralization Bounds Sharpness-Aware Minimization
Thayer School of Engineering Dartmouth College · Dartmouth College
Sample Complexity of Transfer Learning: An Optimal Transport Approach
May 19, 2026Haoyang Cao, Xin Guo, Wenpin Tang +1Transfer Learning Learnability
Department of Applied Mathematics and Statistics, John Hopkins University, Baltimore, MD, USA · Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, USA · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA +1
Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
May 18, 2026Rita Adhikari, Shiwei ZengMulticlass Classification Learnability
Augusta University
The Learnability Gap in Medical Latent Diffusion
May 16, 2026Mischa Dombrowski, Felix Nützel, Bernhard KainzIdentity-Conditioned Latent Diffusion Models Latent Diffusion Model
FAU Erlangen-Nürnberg, Erlangen, DE · Department of Computing, Imperial College London, London, UK
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1Learnability O(\Bar{K}\Log N)$
Purdue University · Stanford University · Google Research +1
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
May 13, 2026Shashaank Aiyer, Yishay Mansour, Shay Moran +2Learnability Optimal Sample Complexity
University of Maryland · Tel Aviv University and Google Research · Technion and Google Research +1
Strategic PAC Learnability via Geometric Definability
May 13, 2026Yuval Filmus, Shay Moran, Elizaveta Nesterova +2Hypothesis Class Learnability
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
High-arity Sample Compression
May 12, 2026Leonardo N. Coregliano, William OpichLearnability Data Compression Methods
A Complete Characterization of Learnability for Adversarial Noisy Bandits
May 9, 2026Steve Hanneke, Kun WangLearnability Combinations
Department of Computer Science, Purdue University
Learnability and Competition in High-Dimensional Multi-Component ICA
May 8, 2026Eser Ilke Genc, Samet Demir, Zafer DoganIndependent Component Analysis High-Dimensional
MLIP Research Group, KUIS AI Center, Koç University · Department of EEE, Koç University
Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity
May 8, 2026Anastasis Kratsios, Gregory Cousins, Haitz Sáez de Ocáriz Borde +2Feed-Forward Learnability
Department of Mathematics & Statistics, McMaster University, Hamilton, ON, Canada · University of Cambridge, United Kingdom · Graduate School of Engineering, The University of Tokyo, Tokyo, Japan +1
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
May 7, 2026Adam R. Klivans, Shyamal Patel, Konstantinos Stavropoulos +1Learnability Distribution Shifts
UT Austin · Columbia University
Temporal Smoothness Doubly Robust Learning for Debiased Knowledge Tracing
May 7, 2026Peilin Zhan, Wei Chen, Weilin Chen +2Learnability Selection Bias
School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China
Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
May 6, 2026Anastasis Kratsios, A. Martina Neuman, Philipp PetersenLearnability In-Context Learning
McMaster University and the Vector Institute, Main St., Hamilton, L8S 4L8, Ontario, Canada · University of Vienna, Faculty of Mathematics, Kolingasse 14-16, 1090 Wien, Austria
Dual-branch Robust Unlearnable Examples
May 3, 2026Xianlong Wang, Hangtao Zhang, Wenbo Pan +4Unlearnable Examples Learnability
Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China · University of Pennsylvania, Philadelphia, USA · Huazhong University of Science and Technology, Wuhan, China +2
Robust Learning on Heterogeneous Graphs with Heterophily: A Graph Structure Learning Approach
Apr 30, 2026Yihan Zhang, Ercan E. KuruogluGraph Representation Learning Text-Attributed Graph
Shenzhen International Graduate School, Tsinghua University, Shenzhen, China
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Apr 29, 2026Jizhou Huang, Brendan JubaLearnability Np-Hard
Meta · Washington Universtiy in St. Louis
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Apr 28, 2026Oliver Kraus, Yash Sarrof, Yuekun Yao +2Transformer Architectures Chain-of-Thought Reasoning
1Saarland University · 2Ohio State University
Null Measurability at the Symmetrization Interface in VC Learning
Apr 27, 2026Dhruv GuptaProbability Measures Learnability
AI and Robotics Technology Park, Indian Institute of Science, Bengaluru
Learning to Think from Multiple Thinkers
Apr 27, 2026Nirmit Joshi, Roey Magen, Nathan Srebro +2Learnability Chain-of-Thought Reasoning
Toyota Technological Institute at Chicago. · Weizmann Institute of Science. · New York University.
On (not) learning the Möbius function
Apr 25, 2026Alexey PozdnyakovFinite Groups Learnability
Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
Apr 23, 2026Eleanor Wiesler, Trace BaxleyGraph Neural Networks Edge-Aware
1Harvard Department of Mathematics. · 2Harvard Department of Computer Science.
HABIT: Chrono-Synergia Robust Progressive Learning Framework for Composed Image Retrieval
Apr 20, 2026Zixu Li, Yupeng Hu, Zhiwei Chen +4Composed Image Retrieval Multimodal Retrieval
School of Software, Shandong University
Diverse Dictionary Learning
Apr 19, 2026Yujia Zheng, Zijian Li, Shunxing Fan +2Unsupervised Dictionary Learning Identifiability
CMU · MBZUAI · NYU
Tight Bounds for Learning Polyhedra with a Margin
Apr 16, 2026Shyamal Patel, Santosh VempalaO(\Bar{K}\Log N)$Polytopes
Columbia University · Georgia Tech
THEIA: Learning Complete Kleene Three-Valued Logic in a Pure-Neural Modular Architecture
Apr 13, 2026Augustus Haoyang LiLogic Multilayer Perceptrons
Irvine Valley College Irvine, CA, USA
Margin in Abstract Spaces
Mar 7, 2026Yair Ashlagi, Roi Livni, Shay Moran +1Metric Spaces Learnability
School of Electrical and Computer Engineering, Tel Aviv University. · Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion, and Google Research. · Departments of Mathematics, Technion.
Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining
Jan 27, 2026Yunwei Ren, Yatin Dandi, Florent Krzakala +1Deep Network Learnability
Princeton University · École Polytechnique Fédérale de Lausanne · University of California, Berkeley
Learnability Window in Gated Recurrent Neural Networks
Dec 5, 2025Lorenzo LiviRecurrent Neural Networks Learnability
OPIT – Open Institute of Technology
Anchor to Expand: Semantic Anchoring for Personalized Text-to-Image Diffusion Models
Nov 27, 2025Seoyun Yang, Gihoon Kim, Taesup KimText-To-Image Diffusion Models Image-Text Alignment
Graduate School of Data Science, Seoul National University
Pre-train to Gain: Robust Learning Without Clean Labels
Nov 25, 2025David Szczecina, Nicholas Pellegrino, Paul FieguthNoisy Labels Self-Supervised Learning
Systems Design Engineering University of Waterloo Waterloo, Ontario, Canada
Learning and Testing Convex Functions
Nov 14, 2025Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1Nonconvex Optimal Sample Complexity
Columbia University · Harvard University · MIT
Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
Nov 4, 2025David Kattermann, Lothar Sebastian KrappLearnability Tractability
Institute for Symbolic Artificial Intelligence, Johannes Kepler University Linz, Austria. · Department of Mathematics and Statistics, University of Konstanz, Germany. · Institute for the Interdisciplinary Study of Language Evolution, University of Zurich, Switzerland.
Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning
Jun 22, 2025Thomas Boudou, Batiste Le Bars, Nirupam Gupta +1Byzantine Attacks Learnability
PreMeDICaL team, Inria, Idesp, Inserm, Université de Montpellier, Montpellier, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France · Department of Computer Science, University of Copenhagen, Copenhagen, Danemark
Temporal horizons in forecasting: a performance-learnability trade-off
Jun 4, 2025Pau Vilimelis Aceituno, Jack William Miller, Noah Marti +2Autoregressive Model Dynamical Systems
Institute of Neuroinformatics, ETH Zürich and University of Zürich, Winterhurerstrasse 190, Zürich 8057, Switzerland · School of Computing, National Australian University, 108 North Rd, Acton ACT 2601, Australia · Unit of Land Change Science, Swiss Federal Research Institute for Forest, Snow and Landscape Zürcherstrasse 111, Birmensdorf 8903, Switzerland
Machine Unlearning via Information Theoretic Regularization
Feb 8, 2025Shizhou Xu, Thomas StrohmerMachine Unlearning Exact Unlearning
Department of Mathematics University of California Davis Davis, CA 95616-5270, USA · Department of Mathematics Center of Data Science and Artificial Intelligence Research University of California Davis Davis, CA 95616-5270, USA

Jun 16, 2026, cs.LGJ/K move · Enter open · S save

No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems

Khoat Than

Hanoi University of Science and Technology

Algorithmic Fairness Learnability Subgroups Learning-Augmented Algorithms Biases Fundamental Limits+1

Open paper AskPDF arXiv

In this paper, we establish a set of theoretical impossibility results, termed the No-Free-Fairness theorems, that identify three fundamental sources of disparity in learning systems. First, we show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity, yielding an inherent fairness--cost frontier. Second, we prove that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity, ruling out distribution-free fairness guarantees. More seriously, enforcing strict relative fairness creates a statistical bottleneck: achieving low cost may require exponentially many samples. Third, we show that limitations of the model class can independently induce disparity: if the model cannot represent accurate solutions for a subgroup, fairness remains unattainable regardless of data or training procedure. Overall, these results demonstrate that unfairness is not solely a consequence of biased data or suboptimal optimization, but arises from the intrinsic structure of decision problems, the constraints of finite data, and the expressivity of models. Our framework applies broadly beyond standard supervised learning, and suggests that achieving fairness requires explicit trade-offs and should be treated as a core design consideration.

Momentum

Related topics

Latest papers 126