Yuval Dagan

STOC Conference 2025 Conference Paper

Breaking the T^(2/3) Barrier for Sequential Calibration

• Yuval Dagan
• Constantinos Daskalakis
• Maxwell Fishelson
• Noah Golowich
• Robert Kleinberg
• Princewill Okoroafor

NeurIPS Conference 2024 Conference Paper

Dimension-free Private Mean Estimation for Anisotropic Distributions

• Yuval Dagan
• Michael Jordan
• Xuelin Yang
• Lydia Zakynthinou
• Nikita Zhivotovskiy

We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over $\mathbb{R}^d$ suffer from a curse of dimensionality, as they require $\Omega(d^{1/2})$ samples to achieve non-trivial error, even in cases where $O(1)$ samples suffice without privacy. This rate is unavoidable when the distribution is isotropic, namely, when the covariance is a multiple of the identity matrix. Yet, real-world data is often highly anisotropic, with signals concentrated on a small number of principal components. We develop estimators that are appropriate for such signals---our estimators are $(\varepsilon, \delta)$-differentially private and have sample complexity that is dimension-independent for anisotropic subgaussian distributions. Given $n$ samples from a distribution with known covariance-proxy $\Sigma$ and unknown mean $\mu$, we present an estimator $\hat{\mu}$ that achieves error, $\|\hat{\mu}-\mu\|_2\leq \alpha$, as long as $n\gtrsim \text{tr}(\Sigma)/\alpha^2+ \text{tr}(\Sigma^{1/2})/(\alpha\varepsilon)$. We show that this is the optimal sample complexity for this task up to logarithmic factors. Moreover, for the case of unknown covariance, we present an algorithm whose sample complexity has improved dependence on the dimension, from $d^{1/2}$ to $d^{1/4}$.

STOC Conference 2024 Conference Paper

From External to Swap Regret 2. 0: An Efficient Reduction for Large Action Spaces

• Yuval Dagan
• Constantinos Daskalakis
• Maxwell Fishelson
• Noah Golowich

We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour and Stoltz-Lugosi in that it does not require finiteness of the space of actions. We show that, whenever there exists a no-external-regret algorithm for some hypothesis class, there must also exist a no-swap-regret algorithm for that same class. For the problem of learning with expert advice, our result implies that it is possible to guarantee that the swap regret is bounded by є after (log N ) Õ(1/є) rounds and with O ( N ) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stoltz-Lugosi require at least Ω( N /є 2 ) rounds and at least Ω( N 3 ) total computational cost. Our result comes with an associated lower bound, which—in contrast to that of Blum-Mansour—holds for oblivious and ℓ 1 -constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be Ω( N /є 2 ) or exponential in 1/є. Our reduction implies that, if no-regret learning is possible in some game, then this game must have approximate correlated equilibria , of arbitrarily good approximation. This strengthens the folklore implication of no-regret learning that approximate coarse correlated equilibria exist. Importantly, it provides a sufficient condition for the existence of approximate correlated equilibrium which vastly extends the requirement that the action set is finite or the requirement that the action set is compact and the utility functions are continuous, allowing for games with finite Littlestone or finite sequential fat shattering dimension, thus answering a question left open in “Fast rates for nonparametric online learning: from realizability to learning in games” and “ Online learning and solving infinite games with an ERM oracle”. Moreover, it answers several outstanding questions about equilibrium computation and/or learning in games. In particular, for constant values of є: (a) ‍we show that є-approximate correlated equilibria in extensive-form games can be computed efficiently, advancing a long-standing open problem for extensive-form games; see e.g. ‍“ Extensive-form correlated equilibrium: Definition and computational complexity” and “ Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games”; (b) ‍we show that the query and communication complexities of computing є-approximate correlated equilibria in N -action normal-form games are N · poly log( N ) and poly log N respectively, advancing an open problem of “Informational Bounds on Equilibria”; (c) we show that є-approximate correlated equilibria of sparsity poly log N can be computed efficiently, advancing an open problem of “Simple Approximate Equilibria in Large Games”; (d) finally, we show that in the adversarial bandit setting, sublinear swap regret can be achieved in only Õ( N ) rounds, advancing an open problem of “From External to Internal Regret” and “Tight Lower Bound and Efficient Reduction for Swap Regret”.

NeurIPS Conference 2024 Conference Paper

Maximizing utility in multi-agent environments by anticipating the behavior of other learners

• Angelos Assos
• Yuval Dagan
• Constantinos Daskalakis

Learning algorithms are often used to make decisions in sequential decision-making environments. In multi-agent settings, the decisions of each agent can affect the utilities/losses of the other agents. Therefore, if an agent is good at anticipating the behavior of the other agents, in particular how they will make decisions in each round as a function of their experience that far, it could try to judiciously make its own decisions over the rounds of the interaction so as to influence the other agents to behave in a way that ultimately benefits its own utility. In this paper, we study repeated two-player games involving two types of agents: a learner, which employs an online learning algorithm to choose its strategy in each round; and an optimizer, which knows the learner's utility function and the learner's online learning algorithm. The optimizer wants to plan ahead to maximize its own utility, while taking into account the learner's behavior. We provide two results: a positive result for repeated zero-sum games and a negative result for repeated general-sum games. Our positive result is an algorithm for the optimizer, which exactly maximizes its utility against a learner that plays the Replicator Dynamics --- the continuous-time analogue of Multiplicative Weights Update (MWU). Additionally, we use this result to provide an algorithm for the optimizer against MWU, i. e. ~for the discrete-time setting, which guarantees an average utility for the optimizer that is higher than the value of the one-shot game. Our negative result shows that, unless P=NP, there is no Fully Polynomial Time Approximation Scheme (FPTAS) for maximizing the utility of an optimizer against a learner that best-responds to the history in each round. Yet, this still leaves open the question of whether there exists a polynomial-time algorithm that optimizes the utility up to $o(T)$.

NeurIPS Conference 2023 Conference Paper

Ambient Diffusion: Learning Clean Distributions from Corrupted Data

• Giannis Daras
• Kulin Shah
• Yuval Dagan
• Aravind Gollakota
• Alex Dimakis
• Adam Klivans

We present the first diffusion-based framework that can learn an unknown distribution using only highly-corrupted samples. This problem arises in scientific applications where access to uncorrupted samples is impossible or expensive to acquire. Another benefit of our approach is the ability to train generative models that are less likely to memorize any individual training sample, since they never observe clean training data. Our main idea is to introduce additional measurement distortion during the diffusion process and require the model to predict the original corrupted image from the further corrupted image. We prove that our method leads to models that learn the conditional expectation of the full uncorrupted image given this additional measurement corruption. This holds for any corruption process that satisfies some technical conditions (and in particular includes inpainting and compressed sensing). We train models on standard benchmarks (CelebA, CIFAR-10 and AFHQ) and show that we can learn the distribution even when all the training samples have 90\% of their pixels missing. We also show that we can finetune foundation models on small corrupted datasets (e. g. MRI scans with block corruptions) and learn the clean distribution without memorizing the training set.

NeurIPS Conference 2023 Conference Paper

Consistent Diffusion Models: Mitigating Sampling Drift by Learning to be Consistent

• Giannis Daras
• Yuval Dagan
• Alex Dimakis
• Constantinos Daskalakis

Imperfect score-matching leads to a shift between the training and the sampling distribution of diffusion models. Due to the recursive nature of the generation process, errors in previous steps yield sampling iterates that drift away from the training distribution. However, the standard training objective via Denoising Score Matching (DSM) is only designed to optimize over non-drifted data. To train on drifted data, we propose to enforce a \emph{Consistency} property (CP) which states that predictions of the model on its owngenerated data are consistent across time. Theoretically, we show that the differential equation that describes CP together with the one that describes a conservative vector field, have a unique solution given some initial condition. Consequently, if the score is learned well on non-drifted points via DSM (enforcing the true initial condition) then enforcing CP on drifted points propagates true score values. Empirically, we show that enforcing CP improves the generation quality for conditional and unconditional generation on CIFAR-10, and in AFHQ and FFHQ. We open-source our code and models: https: //github. com/giannisdaras/cdm.

ICML Conference 2022 Conference Paper

Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems

• Giannis Daras
• Yuval Dagan
• Alexandros G. Dimakis
• Constantinos Daskalakis

We prove fast mixing and characterize the stationary distribution of the Langevin Algorithm for inverting random weighted DNN generators. This result extends the work of Hand and Voroninski from efficient inversion to efficient posterior sampling. In practice, to allow for increased expressivity, we propose to do posterior sampling in the latent space of a pre-trained generative model. To achieve that, we train a score-based model in the latent space of a StyleGAN-2 and we use it to solve inverse problems. Our framework, Score-Guided Intermediate Layer Optimization (SGILO), extends prior work by replacing the sparsity regularization with a generative prior in the intermediate layer. Experimentally, we obtain significant improvements over the previous state-of-the-art, especially in the low measurement regime.

STOC Conference 2021 Conference Paper

Adversarial laws of large numbers and optimal regret in online classification

• Noga Alon
• Omri Ben-Eliezer
• Yuval Dagan
• Shay Moran
• Moni Naor
• Eylon Yogev

Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable . Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone’s dimension , thus resolving the main open question from Ben-David, Pál, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).

STOC Conference 2021 Conference Paper

Learning Ising models from one or multiple samples

• Yuval Dagan
• Constantinos Daskalakis
• Nishanth Dikkala
• Anthimos Vardis Kandiros

There have been two main lines of work on estimating Ising models: (1) estimating them from multiple independent samples under minimal assumptions about the model's interaction matrix ; and (2) estimating them from one sample in restrictive settings. We propose a unified framework that smoothly interpolates between these two settings, enabling significantly richer estimation guarantees from one, a few, or many samples. Our main theorem provides guarantees for one-sample estimation, quantifying the estimation error in terms of the metric entropy of a family of interaction matrices. As corollaries of our main theorem, we derive bounds when the model's interaction matrix is a (sparse) linear combination of known matrices, or it belongs to a finite set, or to a high-dimensional manifold. In fact, our main result handles multiple independent samples by viewing them as one sample from a larger model, and can be used to derive estimation bounds that are qualitatively similar to those obtained in the afore-described multiple-sample literature. Our technical approach benefits from sparsifying a model's interaction network, conditioning on subsets of variables that make the dependencies in the resulting conditional distribution sufficiently weak. We use this sparsification technique to prove strong concentration and anti-concentration results for the Ising model, which we believe have applications beyond the scope of this paper.

ICML Conference 2021 Conference Paper

Statistical Estimation from Dependent Data

• Anthimos Vardis Kandiros
• Yuval Dagan
• Nishanth Dikkala
• Surbhi Goel
• Constantinos Daskalakis

We consider a general statistical estimation problem wherein binary labels across different observations are not independent conditioning on their feature vectors, but dependent, capturing settings where e. g. these observations are collected on a spatial domain, a temporal domain, or a social network, which induce dependencies. We model these dependencies in the language of Markov Random Fields and, importantly, allow these dependencies to be substantial, i. e. do not assume that the Markov Random Field capturing these dependencies is in high temperature. As our main contribution we provide algorithms and statistically efficient estimation rates for this model, giving several instantiations of our bounds in logistic regression, sparse logistic regression, and neural network regression settings with dependent data. Our estimation guarantees follow from novel results for estimating the parameters (i. e. external fields and interaction strengths) of Ising models from a single sample.

STOC Conference 2020 Conference Paper

Interaction is necessary for distributed learning with privacy or communication constraints

• Yuval Dagan
• Vitaly Feldman

Local differential privacy (LDP) is a model where users send privatized data to an untrusted central server whose goal it to solve some data analysis task. In the non-interactive version of this model the protocol consists of a single round in which a server sends requests to all users then receives their responses. This version is deployed in industry due to its practical advantages and has attracted significant research interest.

STOC Conference 2017 Conference Paper

Twenty (simple) questions

• Yuval Dagan
• Yuval Filmus
• Ariel Gabizon
• Shay Moran