11 papers
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju
Optimal learners are tailored to exploit the i.i.d.\ data assumption underlying the classic PAC model. What if an i.i.d.\ training sample were corrupted with correctly labeled exam…
On Agnostic PAC Learning in the Small Error Regime
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the ag…
Proper Learnability and the Role of Unlabeled Data
Julian Asilis, Siddartha Devic, Shaddin Dughmi +2
Proper learning refers to the setting in which learners must emit predictors in the underlying hypothesis class , and often leads to learners with simple algorithmic forms (e.g.…
Semi-Random Graphs, Robust Asymmetry, and Reconstruction
Julian Asilis, Xi Chen, Dutch Hansen +1
The Graph Reconstruction Conjecture famously posits that any undirected graph on at least three vertices is determined up to isomorphism by its family of (unlabeled) induced subgra…
Understanding Aggregations of Proper Learners in Multiclass Classification
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Multiclass learnability is known to exhibit a properness barrier: there are learnable classes which cannot be learned by any proper learner. Binary classification faces no such bar…
Resa: Transparent Reasoning Models via SAEs
Shangshang Wang, Julian Asilis, Ãmer Faruk Akgül +4
How cost-effectively can we elicit strong reasoning in language models by leveraging their underlying representations? We answer this question with Resa, a family of 1.5B reasoning…