Georgia Institute of Technology College of Sciences

Optimization problems arising in decentralized multi-agent systems have gained significant attention in the context of cyber-physical, communication, power, and robotic networks combined with privacy preservation, distributed data mining and processing issues. The distributed nature of the problems is inherent due to partial knowledge of the problem data (i.e., a portion of the cost function or a subset of the constraints is known to different entities in the system), which necessitates costly communications among neighboring agents. In this talk, we present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems which can significantly reduce the number of inter-node communications. Our major contribution is the development of decentralized communication sliding methods, which can skip inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions.This is a joint work with Guanghui (George) Lan and Yi Zhou.

We present algorithms for performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Our interpolation algorithms use as a substep an algorithm that originally is by R. Prony from the French Revolution (Year III, 1795) for interpolating exponential sums and which is rediscovered to decode digital error correcting BCH codes over finite fields (1960). Since Prony's algorithm is quite simple, we will give a complete description, as an alternative for Lagrange/Newton interpolation for sparse polynomials. When very few errors in the evaluations are permitted, multiple sparse interpolants are possible over finite fields or the complex numbers, but not over the real numbers. The problem is then a simple example of list-decoding in the sense of Guruswami-Sudan. Finally, we present a connection to the Erdoes-Turan Conjecture (Szemeredi's Theorem). This is joint work with Clement Pernet, Univ. Grenoble.

Estimation of the covariance matrix has attracted significant attention of the statistical research community over the years, partially due to important applications such as Principal Component Analysis. However, frequently used empirical covariance estimator (and its modifications) is very sensitive to outliers, or ``atypical’’ points in the sample. As P. Huber wrote in 1964, “...This raises a question which could have been asked already by Gauss, but which was, as far as I know, only raised a few years ago (notably by Tukey): what happens if the true distribution deviates slightly from the assumed normal one? As is now well known, the sample mean then may have a catastrophically bad performance…” Motivated by Tukey's question, we develop a new estimator of the (element-wise) mean of a random matrix, which includes covariance estimation problem as a special case. Assuming that the entries of a matrix possess only finite second moment, this new estimator admits sub-Gaussian or sub-exponential concentration around the unknown mean in the operator norm. We will present extensions of our approach to matrix-valued U-statistics, as well as applications such as the matrix completion problem. Part of the talk will be based on a joint work with Xiaohan Wei.

In this talk we will discuss several ways to construct new convex bodies out of old ones. We will start by defining various methods of "averaging" convex bodies, both old and new. We will explain the relationships between the various definitions and their connections to basic conjectures in convex geometry. We will then discuss the power operation, and explain for example why every convex body has a square root, but not every convex body has a square. If time permits, we will briefly discuss more complicated constructions such as logarithms. The talk is based on joint work with Vitali Milman.