2 citations · 8 across the 30 of their papers we have counts for
18 papers · 1 filter
Query Feedback and Teaching for Stable and Certifiable Language Generation
Farnam Mansouri, Alireza F. Pour, Grigoris Velegkas +1
Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We…
Efficient Online Inverse Optimization with Regret
Yang Cai, Anupam Gupta, Vineet Gupta +7
We give a deterministic algorithm for online inverse linear optimization with regret , uniform in the horizon and time per round. A bound of this order was obtaine…
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran +1
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 ge…
On Union-Closedness of Language Generation
Steve Hanneke, Amin Karbasi, Anay Mehrotra +1
We investigate language generation in the limit - a model by Kleinberg and Mullainathan [NeurIPS 2024] and extended by Li, Raman, and Tewari [COLT 2025]. While Kleinberg and Mullai…
(Im)possibility of Automated Hallucination Detection in Large Language Models
Amin Karbasi, Omar Montasser, John Sous +1
Is automated hallucination detection possible? In this work, we introduce a theoretical framework to analyze the feasibility of automatically detecting hallucinations produced by l…
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…
On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
We study language generation in the limit - introduced by Kleinberg and Mullainathan [KM24] - building on classical works of Gold [Gol67] and Angluin [Ang79]. [KM24]'s main result…
On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
Specifying all desirable properties of a language model is challenging, but certain requirements seem essential. Given samples from an unknown language, the trained model should pr…
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…
Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
Alkis Kalavasis, Amin Karbasi, Argyris Oikonomou +3
As ML models become increasingly complex and integral to high-stakes domains such as finance and healthcare, they also become more susceptible to sophisticated adversarial attacks.…
On the Computational Landscape of Replicable Learning
Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas +1
We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022]. Motivated by a recent line of work t…
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen +2
We provide efficient replicable algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and S…
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Idan Attias, Steve Hanneke, Alkis Kalavasis +2
In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had establi…
Statistical Indistinguishability of Learning Algorithms
Alkis Kalavasis, Amin Karbasi, Shay Moran +1
When two different parties use the same learning rule on their own data, how can we test whether the distributions of the two outcomes are similar? In this paper, we study the simi…
Replicability in Reinforcement Learning
Amin Karbasi, Grigoris Velegkas, Lin F. Yang +1
We initiate the mathematical study of replicability as an algorithmic property in the context of reinforcement learning (RL). We focus on the fundamental setting of discounted tabu…
Replicable Clustering
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni +2
We design replicable algorithms in the context of statistical clustering under the recently introduced notion of replicability from Impagliazzo et al. [2022]. According to this def…
Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
Alkis Kalavasis, Grigoris Velegkas, Amin Karbasi
In this paper we study the problem of multiclass classification with a bounded number of different labels , in the realizable setting. We extend the traditional PAC model to a)…
Replicable Bandits
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi +3
In this paper, we introduce the notion of replicable policies in the context of stochastic bandits, one of the canonical problems in interactive learning. A policy in the bandit en…