Manolis Zampetakis

NeurIPS Conference 2025 Conference Paper

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 unbounded. Traditional approaches rely on problem-specific sensitivity analysis, limiting their applicability. By leveraging techniques from truncated statistics, we develop computationally efficient DP estimators for exponential family distributions, including Gaussian mean and covariance estimation, achieving near-optimal sample complexity. Previous works on exponential families only consider bounded or one-dimensional families. Our approach mitigates sensitivity through truncation while carefully correcting for the introduced bias using maximum likelihood estimation and DP stochastic gradient descent. Along the way, we establish improved uniform convergence guarantees for the log-likelihood function of exponential families, which may be of independent interest. Our results provide a general blueprint for DP algorithm design via truncated statistics.

ICML Conference 2025 Conference Paper

Safely Learning Optimal Auctions: A Testable Learning Framework for Mechanism Design

• Vikram Kher
• Manolis Zampetakis

When can the distributional assumptions of theorems and learning algorithms be trusted? Inspired by this question, Rubinfeld and Vasilyan (2023) initiated the study of testable learning. In this schema, we always learn one of the following two things: either we have achieved the desired accuracy regardless of whether the distributional assumptions are satisfied, or the input distribution does not satisfy the original distributional assumptions. Motivated by the challenge of relying on strong distributional assumptions in many theorems in mechanism design, we develop a testable learning framework for mechanism design. Traditional models in mechanism design assume that value distributions satisfy some notion of regularity. Unfortunately, testing regularity is not possible in the original testable learning framework as we show. To bypass this impossibility, we propose a regularized version of the testable learning framework. Under this framework, we always learn one of the following two things: either we achieve high revenue compared to the best possible revenue of any regular distribution close to the input distribution, or the input distribution does not satisfy regularity. We then use this framework to provide: 1) a tester-learner pair for revenue optimal mechanisms, 2) a tester for whether the fundamental Bulow-Klemperer Theorem (Bulow and Klemperer 1996) is applicable to a given dataset, and 3) a tester to confirm the existence of an anonymous reserve price that results in the anonymous price auction securing a constant fraction of the optimal revenue.

FOCS Conference 2024 Conference Paper

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'19) gave an algorithm for finding parameters for the special case of Gaussian distributions with diagonal covariance matrix. Recently, Diakonikolas, Kane, Pittas, and Zarifis (COLT'24) showed that an exponential dependence on the inverse of the accuracy parameter is necessary even when the set belongs to some well-behaved classes. These works leave the following open problems which we address in this work: Can we estimate the parameters of any Gaussian or even extend the results beyond Gaussians? Can we design polynomial-time algorithms when for simple sets such as a halfspace? Toward the first question, we provide an estimation algorithm for any exponential family that satisfies some structural assumptions and any unknown set that is approximable by polynomials. This result has two important applications: (a)The first algorithm for estimating arbitrary Gaussian distributions (even with non-diagonal covariance matrix) from samples truncated to unknown set; and (b)The first algorithm for linear regression with unknown truncation and Gaussian features. To address the second question, we provide an algorithm with polynomial sample and time complexity that works for a set of exponential families (that contains multivariate Gaussians) when the unknown survival set is a halfspace or an axis-aligned rectangle. 1 1 A preliminary version of this paper incorrectly claimed the result for finite unions of axis-aligned rectangles. The result only holds for a single axis-aligned rectangle. This is the first fully polynomial time algorithm for estimation with an unknown truncation set. Along the way, we develop new tools that may be of independent interest, including: (c)The first polynomial time algorithm for learning halfspaces using only positive examples when the samples have an unknown Gaussian distribution; and (d)A reduction from PAC learning with positive and unlabeled samples to PAC learning with positive and negative samples that is robust to certain covariate shifts.

IJCAI Conference 2024 Conference Paper

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

• Emanuel Tewolde
• Brian Hu Zhang
• Caspar Oesterheld
• Manolis Zampetakis
• Tuomas Sandholm
• Paul Goldberg
• Vincent Conitzer

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 as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes PPAD, PLS, Σ_2^P, ∃R, and ∃∀R.

NeurIPS Conference 2024 Conference Paper

Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models

• Alkis Kalavasis
• Amin Karbasi
• Argyris Oikonomou
• Katerina Sotiraki
• Grigoris Velegkas
• Manolis Zampetakis

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. We investigate the threat posed by undetectable backdoors, as defined in Goldwasser et al. [2022], in models developed by insidious external expert firms. When such backdoors exist, they allow the designer of the model to sell information on how to slightly perturb their input to change the outcome of the model. We develop a general strategy to plant backdoors to obfuscated neural networks, that satisfy the security properties of the celebrated notion of indistinguishability obfuscation. Applying obfuscation before releasing neural networks is a strategy that is well motivated to protect sensitive information of the external expert firm. Our method to plant backdoors ensures that even if the weights and architecture of the obfuscated model are accessible, the existence ofthe backdoor is still undetectable. Finally, we introduce the notion of undetectable backdoors to language models and extend our neural network backdoor attacks to such models based on the existence of steganographic functions.

NeurIPS Conference 2024 Conference Paper

Tree of Attacks: Jailbreaking Black-Box LLMs Automatically

• Anay Mehrotra
• Manolis Zampetakis
• Paul Kassianik
• Blaine Nelson
• Hyrum Anderson
• Yaron Singer
• Amin Karbasi

While Large Language Models (LLMs) display versatile functionality, they continue to generate harmful, biased, and toxic content, as demonstrated by the prevalence of human-designed jailbreaks. In this work, we present Tree of Attacks with Pruning (TAP), an automated method for generating jailbreaks that only requires black-box access to the target LLM. TAP utilizes an attacker LLM to iteratively refine candidate (attack) prompts until one of the refined prompts jailbreaks the target. In addition, before sending prompts to the target, TAP assesses them and prunes the ones unlikely to result in jailbreaks, reducing the number of queries sent to the target LLM. In empirical evaluations, we observe that TAP generates prompts that jailbreak state-of-the-art LLMs (including GPT4-Turbo and GPT4o) for more than 80% of the prompts. This significantly improves upon the previous state-of-the-art black-box methods for generating jailbreaks while using a smaller number of queries than them. Furthermore, TAP is also capable of jailbreaking LLMs protected by state-of-the-art guardrails, e. g. , LlamaGuard.

JMLR Journal 2023 Journal Article

First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems

• Michael I. Jordan
• Tianyi Lin
• Manolis Zampetakis

We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) in which the strategy sets for each player are defined by the equality and inequality constraints that may depend on the choices of rival players. While the asymptotic global convergence and local convergence rate of certain algorithms have been extensively investigated, the iteration complexity analysis is still in its infancy. This paper provides two first-order algorithms based on quadratic penalty method (QPM) and augmented Lagrangian method (ALM), respectively, with an accelerated mirror-prox algorithm as the solver in each inner loop. We show the nonasymptotic convergence rate for these algorithms. In particular, we establish the global convergence guarantee for solving monotone and strongly monotone NGNEPs and provide the complexity bounds expressed in terms of the number of gradient evaluations. Experimental results demonstrate the efficiency of our algorithms in practice. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

STOC Conference 2023 Conference Paper

What Makes a Good Fisherman? Linear Regression under Self-Selection Bias

• Yeshwanth Cherapanamjeri
• Constantinos Daskalakis
• Andrew Ilyas
• Manolis Zampetakis

In the classical setting of self-selection, the goal is to learn k models simultaneously, from observations ( x ( i ) , y ( i ) ) where y ( i ) is the output of one of k underlying models on input x ( i ) . In contrast to mixture models, where we observe the output of a randomly selected model (and therefore the selection of which model is observed is exogenous ), in self-selection models the observed model depends on the realized outputs of the underlying models themselves, as determined by some known selection criterion (e.g., we might observe the highest output, the smallest output, or the median output of the k models), and is thus endogenous . In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics (going back to the works of Roy, Gronau, Lewis, Heckman, and others) and many applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly(1/ε, k , d ) sample and time complexity to estimate all model parameters to accuracy ε in d dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied max self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general k we provide an algorithm with poly( d )· exp(poly( k )) sample and time complexity to estimate the regression parameters up to error 1/poly( k ), and (3) for k = 2 we provide an algorithm for any error ε and poly( d , 1/ε) sample and time complexity.

SODA Conference 2021 Conference Paper

A Topological Characterization of Modulo- p Arguments and Implications for Necklace Splitting

• Aris Filos-Ratsikas
• Alexandros Hollender
• Katerina Sotiraki
• Manolis Zampetakis

The classes PPA- p have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with p thieves, for prime p. However, these classes were not known to have complete problems of a topological nature, which impedes any progress towards settling the complexity of the Necklace Splitting problem. On the contrary, topological problems have been pivotal in obtaining completeness results for PPAD and PPA, such as the PPAD-completeness of finding a Nash equilibrium [18, 15] and the PPA-completeness of Necklace Splitting with 2 thieves [24]. In this paper, we provide the first topological characterization of the classes PPA- p. First, we show that the computational problem associated with a simple generalization of Tucker's Lemma, termed p - polygon -T ucker, as well as the associated Borsuk-Ulam-type theorem, p - polygon -B orsuk -U lam, are PPA- p -complete. Then, we show that the computational version of the well-known BSS Theorem [8], as well as the associated BSS-T ucker problem are PPA- p -complete. Finally, using a different generalization of Tucker's Lemma (termed ℤ p - star -T ucker ), which we prove to be PPA- p -complete, we prove that p -thief Necklace Splitting is in PPA- p. This latter result gives a new combinatorial proof for the Necklace Splitting theorem, the only proof of this nature other than that of Meunier [42]. All of our containment results are obtained through a new combinatorial proof for ℤ p -versions of Tucker's lemma that is a natural generalization of the standard combinatorial proof of Tucker's lemma by Freund and Todd [27]. We believe that this new proof technique is of independent interest.

STOC Conference 2021 Conference Paper

The complexity of constrained min-max optimization

• Constantinos Daskalakis
• Stratis Skoulakis
• Manolis Zampetakis

Despite its important applications in Machine Learning, min-max optimization of objective functions that are nonconvex-nonconcave remains elusive. Not only are there no known first-order methods converging to even approximate local min-max equilibria (a.k.a. approximate saddle points), but the computational complexity of identifying them is also poorly understood. In this paper, we provide a characterization of the computational complexity as well as of the limitations of first-order methods in this problem. Specifically, we show that in linearly constrained min-max optimization problems with nonconvex-nonconcave objectives an approximate local min-max equilibrium of large enough approximation is guaranteed to exist, but computing such a point is PPAD-complete. The same is true of computing an approximate fixed point of the (Projected) Gradient Descent/Ascent update dynamics, which is computationally equivalent to computing approximate local min-max equilibria. An important byproduct of our proof is to establish an unconditional hardness result in the Nemirovsky-Yudin 1983 oracle optimization model, where we are given oracle access to the values of some function f : P → [−1, 1] and its gradient ∇ f , where P ⊆ [0, 1] d is a known convex polytope. We show that any algorithm that uses such first-order oracle access to f and finds an ε-approximate local min-max equilibrium needs to make a number of oracle queries that is exponential in at least one of 1/ε, L , G , or d , where L and G are respectively the smoothness and Lipschitzness of f . This comes in sharp contrast to minimization problems, where finding approximate local minima in the same setting can be done with Projected Gradient Descent using O ( L /ε) many queries. Our result is the first to show an exponential separation between these two fundamental optimization problems in the oracle model.

FOCS Conference 2019 Conference Paper

Efficient Truncated Statistics with Unknown Truncation

• Vasilis Kontonis
• Christos Tzamos
• Manolis Zampetakis

We study the problem of estimating the parameters of a Gaussian distribution when samples are only shown if they fall in some (unknown) set. This core problem in truncated statistics has long history going back to Galton, Lee, Pearson and Fisher. Recent work by Daskalakis et al. (FOCS'18), provides the first efficient algorithm that works for arbitrary sets in high dimension when the set is known, but leaves as an open problem the more challenging and relevant case of unknown truncation set. Our main result is a computationally and sample efficient algorithm for estimating the parameters of the Gaussian under arbitrary unknown truncation sets whose performance decays with a natural measure of complexity of the set, namely its Gaussian surface area. Notably, this algorithm works for large families of sets including intersections of halfspaces, polynomial threshold functions and general convex sets. We show that our algorithm closely captures the tradeoff between the complexity of the set and the number of samples needed to learn the parameters by exhibiting a set with small Gaussian surface area for which it is information theoretically impossible to learn the true Gaussian with few samples.

STOC Conference 2018 Conference Paper

A converse to Banach's fixed point theorem and its CLS-completeness

• Constantinos Daskalakis
• Christos Tzamos
• Manolis Zampetakis

Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games.

FOCS Conference 2018 Conference Paper

Efficient Statistics, in High Dimensions, from Truncated Samples

• Constantinos Daskalakis
• Themis Gouleakis
• Christos Tzamos
• Manolis Zampetakis

We provide an efficient algorithm for the classical problem, going back to Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate normal distribution from truncated samples. Truncated samples from a d-variate normal N(mu, Sigma) means a samples is only revealed if it falls in some subset S of the d-dimensional Euclidean space; otherwise the samples are hidden and their count in proportion to the revealed samples is also hidden. We show that the mean mu and covariance matrix Sigma can be estimated with arbitrary accuracy in polynomial-time, as long as we have oracle access to S, and S has non-trivial measure under the unknown d-variate normal distribution. Additionally we show that without oracle access to S, any non-trivial estimation is impossible.

FOCS Conference 2018 Conference Paper

PPP-Completeness with Connections to Cryptography

• Katerina Sotiraki
• Manolis Zampetakis
• Giorgos Zirdelis

Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS, a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i. e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense. Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.

SODA Conference 2017 Conference Paper

Faster Sublinear Algorithms using Conditional Sampling

• Themis Gouleakis
• Christos Tzamos
• Manolis Zampetakis