2 citations · 6 across the 31 of their papers we have counts for
21 papers · 1 filter
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…
Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis +2
Coarse data arise when learners observe only partial information about samples; namely, a set containing the sample rather than its exact value. This occurs naturally through measu…
Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusion
Kulin Shah, Alkis Kalavasis, Adam R. Klivans +1
There is strong empirical evidence that the state-of-the-art diffusion modeling paradigm leads to models that memorize the training set, especially when the training set is small.…
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…
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…
Transfer Learning Beyond Bounded Density Ratios
Alkis Kalavasis, Ilias Zadik, Manolis Zampetakis
We study the fundamental problem of transfer learning where a learning algorithm collects data from some source distribution but needs to perform well with respect to a differe…
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…
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
Constantine Caramanis, Dimitris Fotakis, Alkis Kalavasis +2
Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network…
Learning Hard-Constrained Models with One Sample
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
We consider the problem of estimating the parameters of a Markov Random Field with hard-constraints using a single sample. As our main running examples, we use the -SAT and the…
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…
Perfect Sampling from Pairwise Comparisons
Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
In this work, we study how to efficiently obtain perfect samples from a discrete distribution given access only to pairwise comparisons of elements of its support. Sp…
Learning and Covering Sums of Independent Random Variables with Unbounded Support
Alkis Kalavasis, Konstantinos Stavropoulos, Manolis Zampetakis
We study the problem of covering and learning sums of independent integer-valued random variables (SIIRVs) with unbounded, or even infinite, support.…
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…
Label Ranking through Nonparametric Regression
Dimitris Fotakis, Alkis Kalavasis, Eleni Psaroudaki
Label Ranking (LR) corresponds to the problem of learning a hypothesis that maps features to rankings over a finite set of labels. We adopt a nonparametric regression approach to L…
Efficient Algorithms for Learning from Coarse Labels
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis +1
For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the…
Aggregating Incomplete and Noisy Rankings
Dimitris Fotakis, Alkis Kalavasis, Konstantinos Stavropoulos
We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the classic…
Efficient Parameter Estimation of Truncated Boolean Product Distributions
Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
We study the problem of estimating the parameters of a Boolean product distribution in dimensions, when the samples are truncated by a set accessible thr…