We present a polynomial-time algorithm for online differentially private synthetic data generation. For a data stream within the hypercube [0,1]^d and an infinite time horizon, we develop an online algorithm that generates a differentially private synthetic dataset at each time t. This algorithm achieves a near-optimal accuracy bound in the 1-Wasserstein distance.

We present Fuk-Nagaev - type inequality for the sums of independent self-adjoint operators. This bound could be viewed as an extension of the well known “Matrix Bernstein” inequality to the case of operators with heavy-tailed norms. As a corollary, we deduce Rosenthal moment inequality that improves upon the previously known versions even in the scalar case. Finally, we will discuss applications of these bounds to the covariance estimation problem. 

We will discuss a problem concerning random frames which arises in signal processing. A frame is an overcomplete set of vectors in the n-dimensional linear space which allows a robust decomposition of any vector in this space as a linear combination of these vectors. Random frames are used in signal processing as a means of encoding since the loss of a fraction of coordinates does not prevent the recovery. We will discuss a question when a random frame contains a copy of a nice (almost orthogonal) basis.

Despite the probabilistic nature of this problem it reduces to a completely deterministic question of existence of approximately Hadamard matrices.  An n by n matrix with plus-minus 1 entries is called Hadamard if it acts on the space as a scaled isometry. Such matrices exist in some, but not in all dimensions. Nevertheless, we will construct plus-minus 1 matrices of every size which act as approximate scaled isometries. This construction will bring us back to probability as we will have to combine number-theoretic and probabilistic methods.

Joint work with Xiaoyu Dong.

AI today can pass the Turing test and is in the process of transforming science, technology, society, humans, and beyond.
Surprisingly, modern AI is built out of two very simple and old ideas, rebranded as deep learning: neural networks and
gradient descent learning. When a typical feed-forward neural network is trained by gradient descent, with an L2 regularizer
to avoid overly large synaptic weights, a strange phenomenon occurs: at the optimum, each neuron becomes "balanced"
in the sense that the L2 norm of its incoming synaptic weights becomes equal to the L2 norm of its outgoing synaptic weights. We develop a theory that explains this phenomenon and exposes its generality. Balance emerges with a variety of activation functions, a variety of regularizers including all Lp regularizers, and a variety of networks including recurrent networks. A simple local balancing algorithm can be applied to any neuron and at any time, instead of just at the optimum. Most remarkably, stochastic iterated application of the local balancing algorithm always converges to a unique, globally balanced, state.