2 citations · 6 across the 31 of their papers we have counts for
33 papers
CLS Hardness of 2D Min-Max Optimization with Product Constraints
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis +1
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For…
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…
Linear Regression with Unknown Truncation Beyond Gaussian Features
Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis +1
In truncated linear regression, samples are shown only when the outcome falls inside a certain survival set and the goal is to estimate the unknown -dimens…
Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li +1
In this work, we give a time and sample algorithm for efficiently learning the parameters of a mixture of spherical distributions in dimensions. Unlike al…
What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness
Yang Cai, Alkis Kalavasis, Katerina Mamali +2
Most of the widely used estimators of the average treatment effect (ATE) in causal inference rely on the assumptions of unconfoundedness and overlap. Unconfoundedness requires that…
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases
Alkis Kalavasis, Anay Mehrotra, Felix Zhou
We revisit the problem of estimating linear regressors with self-selection bias in dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskala…
DDPM Score Matching and Distribution Learning
Sinho Chewi, Alkis Kalavasis, Anay Mehrotra +1
Score estimation is the backbone of score-based generative models (SGMs), especially denoising diffusion probabilistic models (DDPMs). A key result in this area shows that with acc…
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…
Computational Lower Bounds for Regret Minimization in Normal-Form Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game…
Barriers to Welfare Maximization with No-Regret Learning
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE)…
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…
Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening
Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis
Inverse propensity-score weighted (IPW) estimators are prevalent in causal inference for estimating average treatment effects in observational studies. Under unconfoundedness, give…
On Sampling from Ising Models with Spectral Constraints
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
We consider the problem of sampling from the Ising model when the underlying interaction matrix has eigenvalues lying within an interval of length . Recent work in this setting…
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…
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm +1
Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have reveal…
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…