28 citations · 127 across the 46 of their papers we have counts for
9 papers · 1 filter
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…