High-dimensional Statistical Learning over Networks: Algorithms, Guarantees, and Trade-offs

Interdisciplinary Areas: Data and Engineering Applications

Project Description

There is growing interest in large-scale machine learning and optimization over decentralized networks, e.g., in the context of federated learning. This project targets distributed learning and optimization over meshed networks, where no centralized coordination is present - these computational architectures are more compliant with future edge-computing systems. Motivated by big-data applications, we consider so-called high-dimensional statistical models: the number of decision variables is of the same order as, or exceeds, the total sample size over the network. The goal is to exploit latent low-dimensional structures in the network data (e.g., sparsity, low-rank) to achieve statistical consistency in a resource-efficient manner.
While statistical-computational guarantees of centralized high-dimensional learning are well studied, our understanding in the network setting is unsatisfactory, even for simple learning tasks: (i) distributed schemes, designed and performing well in the low dimensional regime, can break down dramatically in the high-dimensional case; and (ii) existing convergence studies fail to provide useful predictions; they are in fact confuted by experiments. This project aims at filling this gap by designing distributed algorithms for high-dimensional M-(nonconvex) estimation problems over meshed networks while revealing trade-offs in the statistical error, computational complexity, and communication costs
Start Date
Postdoc Qualifications
We are seeking candidates that have a record of scholarship under the rubric of "computational optimization" and statistics. Candidates may come from different backgrounds, such as operations research, statistics, electrical engineering, computer science or a related field. All applicants must have strong mathematical and computing skills. Prior knowledge in stochastic programming is a plus.  Applicants should possess a Ph.D. in Mathematics, Operation Research, Statistics, Electrical Engineering, or other relevant fields. Applicants are expected to be outstanding, intellectually curious researchers at an early stage of their scholarly career.
Gesualdo Scutari, gscutari@purdue.edu, School of Industrial Engineering, url: https://engineering.purdue.edu/~gscutari/
Raghu Pasupathy, pasupath@purdue.edu, Department of Statistics, url: https://web.ics.purdue.edu/~pasupath/ 
Y. Sun, A. Daneshmand, and G. Scutari, "Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation," SIAM J. Optim,  https://arxiv.org/pdf/1905.02637.pdf
 A. Daneshmand, G. Scutari, and Vyacheslav Kungurtsev, "Second-Order Guarantees of Distributed Gradient Algorithms", SIAM J. Optim., 30(4), 3029-3068, 202
 G. Scutari and Y. Sun, "Distributed nonconvex constrained optimization over time-varying digraphs," Mathematical Programming, vol. 176, pages497-544(2019)
 R. Pasupathy and Y. Song. "Adaptive Retrospective Approximation for Solving Two-Stage Stochastic Programs," SIAM Journal on Optimization, to appear.
 R. Pasupathy, P. W. Glynn, S. Ghosh, and F. S. Hashemi. "On sampling rates in simulation-based recursions," SIAM Journal on Optimization, 28(1): 45--73. 2018.