Daniil Dmitriev

I am a postdoc at the University of Pennsylvania, hosted by Yuting Wei in the Department of Statistics and Data Science at the Wharton School.

My research interests lie at the intersection of mathematics, machine learning, and theoretical computer science, with a current focus on understanding the interplay between structure and randomness in algorithm analysis.

I completed my PhD at ETH Zurich, advised by Afonso Bandeira and Fanny Yang, and supported by the ETH AI Center and ETH FDS initiative.

In Fall 2024, I visited Simons Institute for the Theory of Computing at UC Berkeley, for the program Modern paradigms in generalization.

I have a MS from EPFL, where I worked with Lenka Zdeborová and Martin Jaggi, and a BS from MIPT, where I worked with Maksim Zhukovskii.

Google Scholar  /  CV  /  GitHub  /  LinkedIn  /  X  /  Blue sky

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

We analyze two noising processes for score-based discrete diffusion models: uniform and absorbing. For the uniform noising process, we prove an upper bound for the number of sampling steps scaling linearly with the ambient dimension and logarithmically with the vocabulary size. This is achieved with a tau-leaping sampler, for which we show a matching lower bound.
For the absorbing noising process, we show an upper bound that scales (up to logarithmic factors) with the effective total correlation of the distribution, which potentially can be sublinear in the ambient dimension, or even constant for certain structured distributions.

Learning in an echo chamber: online learning with replay adversary

We propose a new online learning variant in which the learner might receive samples labelled via its own past models. Our results include upper and lower bounds against both adaptive and stochastic adversaries.

The Lovász number of random circulant graphs

We provide lower and upper bounds for the expected value of the Lovász theta number of random circulant graphs. Circulant graphs are a class of structured graphs where connectivity depends only on the difference between the vertex labels.

Robust mixture learning when outliers overwhelm small groups

We propose an efficient meta-algorithm for recoving means of a mixture model in the presence of large additive contaminations.

On the growth of mistakes in differentially private online learning: a lower bound perspective

We prove that for a certain class of algorithms, the number of mistakes for online learning under differential privacy constraint must grow logarithmically with the time horizon.

Asymptotics of learning with deep structured (random) features

We derive a deterministic equivalent for the generalization error of general Lipschitz functions. Furthermore, we prove a linearization formula for a sample covariance matrix of a structured random feature model with two hidden layers.

Greedy heuristics and linear relaxations for the random hitting set problem

We prove that the standard greedy algorithm is order-optimal for the hitting set problem in the random bernoulli case.

Deterministic equivalent and error universality of deep random features learning

We rigorously establish Gaussian universality for the test error in ridge regression in deep networks with frozen intermediate layers.

On monotonicity of Ramanujan function for binomial random variables

We analyze properties of the CDF of binomial random variable near its median.

Dynamic model pruning with feedback

We propose a novel model compression method that generates a sparse trained model without an additional overhead.

Invited Talks

Teaching and Service