28 citations · 127 across the 46 of their papers we have counts for
54 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…
Learning-Enabled Estimation: Tight Characterizations under Sample Selection Biases
Vikram Kher, Jane H. Lee, Anay Mehrotra +1
When can we learn from biased samples? We study regression when outcomes are observed only after passing through selection filters that depend on both covariates and outcomes thems…
Surprises in Proper Positive-Only Learning
Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1
Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, bu…
Restoring Incentive Compatibility in Two-Stage Energy Markets with Prosumers
Nikolas Koumpis, Koushik Kar, Leandros Tassiulas +1
A central challenge in modern energy market design is the formulation of a strategy-proof imbalance settlement layer that secures both the economic efficiency of the institution an…
Improved Guarantees for Heterogeneous Treatment-Effect Estimation via Matrix Completion
Anay Mehrotra, Phuc Tran, Van H. Vu +1
A central goal of modern causal inference is estimating heterogeneous treatment effects to answer questions like "how does an intervention affect each unit," rather than only on av…
What is Learnable in Valiant's Theory of the Learnable?
Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1
Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only posit…
A Note on Non-Negative -Approximating Polynomials
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis
-Approximating polynomials, i.e., polynomials that approximate indicator functions in -norm under certain distributions, are widely used in computational learning theory.…
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…
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…
Prediction-Augmented Trees for Reliable Statistical Inference
Vikram Kher, Argyris Oikonomou, Manolis Zampetakis
The remarkable success of machine learning (ML) in predictive tasks has led scientists to incorporate ML predictions as a core component of the scientific discovery pipeline. This…
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…
Private Statistical Estimation via Truncation
Manolis Zampetakis, Felix Zhou
We introduce a novel framework for differentially private (DP) statistical estimation via data truncation, addressing a key challenge in DP estimation when the data support is unbo…
Smoothed Analysis of Learning from Positive Samples
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis
Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positive samples and aims to learn a classifier with low error. Prev…
Fixed Point Computation: Beating Brute Force with Smoothed Analysis
Idan Attias, Yuval Dagan, Constantinos Daskalakis +2
We propose a new algorithm that finds an -approximate fixed point of a smooth function from the -dimensional unit ball to itself. We use the general framew…
On the Hardness of Learning One Hidden Layer Neural Networks
Shuchen Li, Ilias Zadik, Manolis Zampetakis
In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from . We show that this learning problem is hard under standard c…
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…
Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis
We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set . Kontonis, Tzamos, and Zampetakis (FOCS…
Hypercontractivity and factorial moment scaling in the symmetry broken phase
Athanasios Brofas, Manolis Zampetakis, Fotios Diakonos
The search for remnants of the QCD chiral critical point is a central objective of current and future high-energy ion collision experiments. Previous studies suggest that a scaling…
Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld +4
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well a…
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.…
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…
Tree of Attacks: Jailbreaking Black-Box LLMs Automatically
Anay Mehrotra, Manolis Zampetakis, Paul Kassianik +4
While Large Language Models (LLMs) display versatile functionality, they continue to generate harmful, biased, and toxic content, as demonstrated by the prevalence of human-designe…
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…
Sorting from Crowdsourced Comparisons using Expert Verifications
Ellen Vitercik, Manolis Zampetakis, David Zhang
We introduce a novel noisy sorting model motivated by the Just Noticeable Difference (JND) model from experimental psychology. The goal of our model is to capture the low quality o…