As the COVID-19 outbreak evolves, accurate forecasting continues to play an extremely important role in informing policy decisions. In this paper, we present our continuous curation of a large data repository containing COVID-19 information from a range of sources. We use this data to develop predictions and corresponding prediction intervals for the short-term trajectory of COVID-19 cumulative death counts at the county-level in the United States up to two weeks ahead. Using data from January 22 to June 20, 2020, we develop and combine multiple forecasts using ensembling techniques, resulting in an ensemble we refer to as Combined Linear and Exponential Predictors (CLEP). Our individual predictors include county-specific exponential and linear predictors, a shared exponential predictor that pools data together across counties, an expanded shared exponential predictor that uses data from neighboring counties, and a demographics-based shared exponential predictor. We use prediction errors from the past five days to assess the uncertainty of our death predictions, resulting in generally-applicable prediction intervals, Maximum (absolute) Error Prediction Intervals (MEPI). MEPI achieves a coverage rate of more than 94% when averaged across counties for predicting cumulative recorded death counts two weeks in the future. Our forecasts are currently being used by the non-profit organization, Response4Life, to determine the medical supply need for individual hospitals and have directly contributed to the distribution of medical supplies across the country. We hope that our forecasts and data repository at this https URL can help guide necessary county-specific decision-making and help counties prepare for their continued fight against COVID-19.
Bio:
Bin Yu is Chancellor’s Distinguished Professor and Class of 1936 Second Chair in the Departments of Statistics and of Electrical Engineering & Computer Sciences at the University of California at Berkeley and a former chair of Statistics at UC Berkeley.
Yu's research focuses on practice, algorithm, and theory of statistical machine learning and causal inference. Her group is engaged in interdisciplinary research with scientists from genomics, neuroscience, and precision medicine. In order to augment empirical evidence for decision-making, they are investigating methods/algorithms (and associated statistical inference problems) such as dictionary learning, non-negative matrix factorization (NMF), EM and deep learning (CNNs and LSTMs), and heterogeneous effect estimation in randomized experiments (X-learner). Their recent algorithms include staNMF for unsupervised learning, iterative Random Forests (iRF) and signed iRF (s-iRF) for discovering predictive and stable high-order interactions in supervised learning, contextual decomposition (CD) and aggregated contextual decomposition (ACD) for interpretation of Deep Neural Networks (DNNs).
Yu is a member of the U.S. National Academy of Sciences and a fellow of the American Academy of Arts and Sciences. She was a Guggenheim Fellow in 2006, and the Tukey Memorial Lecturer of the Bernoulli Society in 2012. She was President of IMS (Institute of Mathematical Statistics) in 2013-2014 and the Rietz Lecturer of IMS in 2016. She received the E. L. Scott Award from COPSS (Committee of Presidents of Statistical Societies) in 2018. Moreover, Yu was a founding co-director of the Microsoft Research Asia (MSR) Lab at Peking University and is a member of the scientific advisory board at the UK Alan Turing Institute for data science and AI.
]]>As the COVID-19 outbreak evolves, accurate forecasting continues to play an extremely important role in informing policy decisions. In this paper, we present our continuous curation of a large data repository containing COVID-19 information from a range of sources. We use this data to develop predictions and corresponding prediction intervals for the short-term trajectory of COVID-19 cumulative death counts at the county-level in the United States up to two weeks ahead. Using data from January 22 to June 20, 2020, we develop and combine multiple forecasts using ensembling techniques, resulting in an ensemble we refer to as Combined Linear and Exponential Predictors (CLEP). Our individual predictors include county-specific exponential and linear predictors, a shared exponential predictor that pools data together across counties, an expanded shared exponential predictor that uses data from neighboring counties, and a demographics-based shared exponential predictor. We use prediction errors from the past five days to assess the uncertainty of our death predictions, resulting in generally-applicable prediction intervals, Maximum (absolute) Error Prediction Intervals (MEPI). MEPI achieves a coverage rate of more than 94% when averaged across counties for predicting cumulative recorded death counts two weeks in the future. Our forecasts are currently being used by the non-profit organization, Response4Life, to determine the medical supply need for individual hospitals and have directly contributed to the distribution of medical supplies across the country. We hope that our forecasts and data repository at this https URL can help guide necessary county-specific decision-making and help counties prepare for their continued fight against COVID-19.
Bio:
Bin Yu is Chancellor’s Distinguished Professor and Class of 1936 Second Chair in the Departments of Statistics and of Electrical Engineering & Computer Sciences at the University of California at Berkeley and a former chair of Statistics at UC Berkeley.
Yu's research focuses on practice, algorithm, and theory of statistical machine learning and causal inference. Her group is engaged in interdisciplinary research with scientists from genomics, neuroscience, and precision medicine. In order to augment empirical evidence for decision-making, they are investigating methods/algorithms (and associated statistical inference problems) such as dictionary learning, non-negative matrix factorization (NMF), EM and deep learning (CNNs and LSTMs), and heterogeneous effect estimation in randomized experiments (X-learner). Their recent algorithms include staNMF for unsupervised learning, iterative Random Forests (iRF) and signed iRF (s-iRF) for discovering predictive and stable high-order interactions in supervised learning, contextual decomposition (CD) and aggregated contextual decomposition (ACD) for interpretation of Deep Neural Networks (DNNs).
Yu is a member of the U.S. National Academy of Sciences and a fellow of the American Academy of Arts and Sciences. She was a Guggenheim Fellow in 2006, and the Tukey Memorial Lecturer of the Bernoulli Society in 2012. She was President of IMS (Institute of Mathematical Statistics) in 2013-2014 and the Rietz Lecturer of IMS in 2016. She received the E. L. Scott Award from COPSS (Committee of Presidents of Statistical Societies) in 2018. Moreover, Yu was a founding co-director of the Microsoft Research Asia (MSR) Lab at Peking University and is a member of the scientific advisory board at the UK Alan Turing Institute for data science and AI.
]]>Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Title of this talk: Inference and Uncertainty Quantification for Noise Matrix Completion
Abstract:
Noisy matrix completion aims at estimating a low-rank matrix given only partial and corrupted entries. Despite substantial progress in designing efficient estimation algorithms, it remains largely unclear how to assess the uncertainty of the obtained estimates and how to perform statistical inference on the unknown matrix (e.g. constructing a valid and short confidence interval for an unseen entry).
This talk takes a step towards inference and uncertainty quantification for noisy matrix completion. We develop a simple procedure to compensate for the bias of the widely used convex and nonconvex estimators. The resulting de-biased estimators admit nearly precise non-asymptotic distributional characterizations, which in turn enable optimal construction of confidence intervals/regions for, say, the missing entries and the low-rank factors. Our inferential procedures do not rely on sample splitting, thus avoiding unnecessary loss of data efficiency. As a byproduct, we obtain a sharp characterization of the estimation accuracy of our de-biased estimators, which, to the best of our knowledge, are the first tractable algorithms that provably achieve full statistical efficiency (including the preconstant). The analysis herein is built upon the intimate link between convex and nonconvex optimization.
This is joint work with Cong Ma, Yuling Yan, Yuejie Chi, and Jianqing Fan.
Bio: Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional statistics, convex and nonconvex optimization, statistical learning, and information theory. He received the 2019 AFOSR Young Investigator Award.
Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Title of this talk: Spectral Methods Meets Asymmetry: Two Recent Stories
Abstract: This talk is concerned with the interplay between asymmetry and spectral methods. Imagine that we have access to an asymmetrically perturbed low-rank data matrix. We attempt estimation of the low-rank matrix via eigen-decomposition --- an uncommon approach when dealing with non-symmetric matrices.
We provide two recent stories to demonstrate the advantages and effectiveness of this approach. The first story is concerned with top-K ranking from pairwise comparisons, for which the spectral method enables un-improvable ranking accuracy. The second story is concerned with matrix de-noising and spectral estimation, for which the eigen-decomposition method significantly outperforms the (unadjusted) SVD-based approach and is fully adaptive to heteroscedasticity without the need of careful bias correction.
The first part of this talk is based on joint work with Cong Ma, Kaizheng Wang, and Jianqing Fan; the second part of this talk is based on joint work with Chen Cheng and Jianqing Fan.
Bio: Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional statistics, convex and nonconvex optimization, statistical learning, and information theory. He received the 2019 AFOSR Young Investigator Award.
]]>Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Title of this talk: The projected power method: an efficient nonconvex algorithm for a joint discrete assignment from pairwise data
Abstract: Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete---and hence nonconvex---structure of the problem, computing the optimal assignment (e.g. maximum likelihood assignment) becomes intractable at first sight.
This paper makes progress towards efficient computation by focusing on a concrete joint discrete alignment problem---that is, the problem of recovering n discrete variables given noisy observations of their modulo differences. We propose a low-complexity and model-free procedure, which operates in a lifted space by representing distinct label values in orthogonal directions, and which attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error---and hence converges to the maximum likelihood estimate---in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the
practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.
This is joint work with Emmanuel Candes.
]]>Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Check https://triad.gatech.edu/events for more information.
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex
Title of this talk: Random initialization and implicit regularization in nonconvex statistical estimation
Abstract: Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation/learning problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require suitable initialization and proper regularization (e.g., trimming, regularized cost, projection) in order to guarantee fast convergence. For vanilla procedures such as gradient descent, however, the prior theory is often either far from optimal or completely lacks theoretical
guarantees.
This talk is concerned with a striking phenomenon arising in two nonconvex problems (i.e. phase retrieval and matrix completion): even in the absence of careful initialization, proper saddle escaping, and/or explicit regularization, gradient descent converges to the optimal solution within a logarithmic number of iterations, thus achieving near-optimal statistical and computational guarantees at once. All of this is achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data. As a byproduct, for noisy matrix completion, we demonstrate that gradient descent achieves near-optimal entrywise error control.
This is joint work with Cong Ma, Kaizheng Wang, Yuejie Chi, and Jianqing Fan
]]>Check https://triad.gatech.edu/events for more information.
Abstract: We consider the fundamental problem of solving random quadratic systems of equations in n variables, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning. A growing body of recent work has demonstrated the effectiveness of convex relaxation --- in particular, semidefinite programming --- for solving problems of this kind. However, the
computational cost of such convex paradigms is often unsatisfactory, which limits applicability to large-dimensional data.
This talk follows another route: by formulating the problem into nonconvex programs, we attempt to optimize the nonconvex objectives directly. We demonstrate that for certain unstructured models of quadratic systems, nonconvex optimization algorithms return the correct solution in linear time, as soon as the ratio between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems, and prove that our algorithms achieve a minimax optimal statistical accuracy. Numerical evidence suggests that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.
This is joint work with Emmanuel Candes.
Bio: Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional statistics, convex and nonconvex optimization, statistical learning, and
information theory. He received the 2019 AFOSR Young Investigator Award.
]]>
Check https://triad.gatech.edu/events for more information.
Title of this talk: The power of nonconvex optimization in solving random quadratic systems of equations
Abstract: We consider the fundamental problem of solving random quadratic systems of equations in n variables, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning. A growing body of recent work has demonstrated the effectiveness of convex relaxation --- in particular, semidefinite programming --- for solving problems of this kind. However, the computational cost of such convex paradigms is often unsatisfactory, which limits applicability to large-dimensional data.
This talk follows another route: by formulating the problem into nonconvex programs, we attempt to optimize the nonconvex objectives directly. We demonstrate that for certain unstructured models of quadratic systems, nonconvex optimization algorithms return the correct solution in linear time, as soon as the ratio between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems and prove that our algorithms achieve a minimax optimal statistical accuracy. Numerical evidence suggests that the computational cost of our algorithm is about four times that of solving a least-squares the problem of the same size.
This is joint work with Emmanuel Candes.
]]>This summer school will introduce participants to a theoretical foundation of data science, with a selection of application topics. The emphasis will be on foundational concepts from statistics, optimization, and signal processing, and applications of these techniques in developing cross-disciplinary research. Topics include optimization, high-dimensional statistics, uncertainty quantifications, signal processing, and various models. The summer school is sponsored by the NSF TRIPODS Institute at the Georgia Institute of Technology. See triad.gatech.edu for more information.
The summer school will cover lodging. The participants will be responsible for their travel expenses. The application deadline is Friday, May 24, 2019, and application decisions will be announced on Friday, May 31, 2019. We expect to admit 20-30 student participants from the applications.
The intended audience for the summer school is advanced graduate students and postdoctoral researchers with a background in statistics, computer science, mathematics or related fields.
This summer school will introduce participants to a theoretical foundation of data science, with a selection of application topics. The emphasis will be on foundational concepts from statistics, optimization, and signal processing, and applications of these techniques in developing cross-disciplinary research. Topics include optimization, high-dimensional statistics, uncertainty quantifications, signal processing, and various models. The summer school is sponsored by the NSF TRIPODS Institute at the Georgia Institute of Technology. See triad.gatech.edu for more information.
The summer school will cover lodging. The participants will be responsible for their travel expenses. The application deadline is Friday, May 24, 2019, and application decisions will be announced on Friday, May 31, 2019. We expect to admit 20-30 student participants from the applications.
The intended audience for the summer school is advanced graduate students and postdoctoral researchers with a background in statistics, computer science, mathematics or related fields.
Lecture 1) Survey on neural network structures and deep learning
There are many different types of neural networks that differ in complexity and the data types that can be processed. This lecture provides an overview and surveys the algorithms used to fit deep networks to data. We discuss different ideas that underly the existing approaches for a mathematical theory of deep networks.
Lecture 2) Theory for shallow networks
We start with the universal approximation theorem and discuss several proof strategies that provide some insights into functions that can be easily approximated by shallow networks. Based on this, a survey on approximation rates for shallow networks is given. It is shown how this leads to estimation rates. In the lecture, we also discuss methods that fit shallow networks to data.
Lecture 3) Advantages of additional layers
Why are deep networks better than shallow networks? We provide a survey of the existing ideas in the literature. In particular, we discuss localization of deep networks, functions that can be easily approximated by deep networks and finally discuss the Kolmogorov-Arnold representation theorem.
Lecture 4) Statistical theory for deep ReLU networks
We outline the theory underlying the recent bounds on the estimation risk of deep ReLU networks. In the lecture, we discuss specific properties of the ReLU activation function that relate to skipping connections and efficient approximation of polynomials. Based on this, we show how risk bounds can be obtained for sparsely connected networks.
Lecture 5) Energy landscape and open problems
To derive a theory for gradient descent methods, it is important to have some understanding of the energy landscape. In this lecture, an overview of existing results is given. The second part of the lecture is devoted to future challenges in the field. We describe important future steps needed for the future development of the statistical theory of deep networks.
Video link: https://smartech.gatech.edu/handle/1853/60958
]]>Video link: https://smartech.gatech.edu/handle/1853/60957
]]>The Data Science for Social Good Workshop will focus on the application of data science techniques to problems of significant societal impact, such as healthcare, data privacy, renewable energy, and transportation. Bringing together disciplines in Computer Science, Industrial and Systems Engineering and Public Policy, it will include research domains such as algorithmic fairness, mechanism design, artificial intelligence, simulation, machine learning and optimization. The schedule is designed for attendees to form meaningful connections, including 2 minute lightning talks as an icebreaker, and breakout sessions separated by academic stage (for mentoring) and research area (for technical discussions).
Advanced undergraduates or recent graduates considering graduate school in data science and related fields, including (but not limited to) computer science, economics, operations research, statistics, math, psychology, and public policy.
]]>Lecture 1) Survey on neural network structures and deep learning
There are many different types of neural networks that differ in complexity and the data types that can be processed. This lecture provides an overview and surveys the algorithms used to fit deep networks to data. We discuss different ideas that underly the existing approaches for a mathematical theory of deep networks.
Lecture 2) Theory for shallow networks
We start with the universal approximation theorem and discuss several proof strategies that provide some insights into functions that can be easily approximated by shallow networks. Based on this, a survey on approximation rates for shallow networks is given. It is shown how this leads to estimation rates. In the lecture, we also discuss methods that fit shallow networks to data.
Lecture 3) Advantages of additional layers
Why are deep networks better than shallow networks? We provide a survey of the existing ideas in the literature. In particular, we discuss localization of deep networks, functions that can be easily approximated by deep networks and finally discuss the Kolmogorov-Arnold representation theorem.
Lecture 4) Statistical theory for deep ReLU networks
We outline the theory underlying the recent bounds on the estimation risk of deep ReLU networks. In the lecture, we discuss specific properties of the ReLU activation function that relate to skipping connections and efficient approximation of polynomials. Based on this, we show how risk bounds can be obtained for sparsely connected networks.
Lecture 5) Energy landscape and open problems
To derive a theory for gradient descent methods, it is important to have some understanding of the energy landscape. In this lecture, an overview of existing results is given. The second part of the lecture is devoted to future challenges in the field. We describe important future steps needed for the future development of the statistical theory of deep networks.
See lectures slides at http://pub.math.leidenuniv.nl/~schmidthieberaj/GT.html
See the video at https://smartech.gatech.edu/handle/1853/60926
See the video at https://smartech.gatech.edu/handle/1853/60935
See the video at https://smartech.gatech.edu/handle/1853/60948
This time around we have invited several speakers from outside this region and are open to "longer distance" participants as well. There is some funding available (see registration form, priority is given to students). There will be a poster session on Saturday. Sunday afternoon is reserved for informal discussions.
]]>Speakers
Abstract: Modern learning algorithms, such as deep learning, have gained great successes in real applications. However, some of their empirical behaviors may not be interpreted within the classical statistical learning framework. For example, deep learning algorithms achieve small testing error even when the training error is zero, i.e., over-fitting. Another phenomenon is observed in image recognition applications where a hardly noticeable change of data may lead to a dramatic increase in misclassification rates. Inspired by these observations, we attempt to illustrate new theoretical insights for data-interpolation and adversarial testing using the very simple nearest neighbor algorithms. In particular, we prove statistical optimality of interpolated nearest neighbor algorithms. More surprisingly, it is discovered that the classification performance, under a proper interpolation, is even better than the best kNN in terms of multiplicative constant. As for adversarial testing, we demonstrate that different adversarial mechanisms lead to different phase transition phenomena of the misclassification rate in terms of its upper bound. Additionally, our technical analysis invented to deal with adversarial samples can also be applied to other variants of kNN, e.g. pre-processed 1NN and distributed-NN.
Bio: Guang Cheng is a Professor of Statistics at Purdue University. He received his Ph.D. in Statistics from the University of Wisconsin-Madison in 2006. His research interests include Big Data and High Dimensional Statistical Inferences, and more recently turned to Deep Learning and Reinforcement Learning. Cheng is the recipient of the NSF CAREER award, Noether Young Scholar Award and Simons Fellowship in Mathematics. Please visit his big data theory research group at http://www.science.purdue.edu/bigdata/
]]>
Bio: Guang Cheng is a Professor of Statistics at Purdue University. He received his PhD in Statistics from University of Wisconsin-Madison in 2006. His research interests include Big Data and High Dimensional Statistical Inferences, and more recently turn to Deep Learning and Reinforcement Learning. Cheng is the recipient of the NSF CAREER award, Noether Young Scholar Award and Simons Fellowship in Mathematics. Please visit his big data theory research group at http://www.science.purdue.edu/bigdata/
]]>Abstract: Although “big data” is ubiquitous in data science, one often faces challenges of “small data,” as the amount of data that can be taken or transmitted is limited by technical or economic constraints. To retrieve useful information from the insufficient amount of data, additional assumptions on the signal of interest are required, e.g. sparsity (having only a few non-zero elements). Conventional methods favor incoherent systems, in which any two measurements are as little correlated as possible. In reality, however, many problems are coherent. I will present two nonconvex approaches: one is the difference of the L1 and L2 norms and the other is the ratio of the two. The difference model works particularly well in the coherent regime, while the ratio is a scale-invariant metric that works better when underlying signals have large fluctuations in non-zero values. Various numerical experiments have demonstrated advantages of the proposed methods over the state-of-the-art. Applications, ranging from super-resolution to low-rank approximation, will be discussed.
Bio: Yifei Lou has been an Assistant Professor in the Mathematical Sciences Department, University of Texas Dallas, since 2014. She received her Ph.D. in Applied Math from the University of California Los Angeles (UCLA) in 2010. After graduation, she was a postdoctoral fellow at the School of Electrical and Computer Engineering Georgia Institute of Technology, followed by another postdoc training at the Department of Mathematics, University of California Irvine from 2012-2014. Her research interests include compressive sensing and its applications, image analysis (medical imaging, hyperspectral, imaging through turbulence), and (nonconvex) optimization algorithms.
]]>Bio: Sara van de Geer has been Full Professor at the Seminar for Statistics at ETH Zurich since September 2005. Her main field of research is mathematical statistics, with special interest in high-dimensional problems. Focus points are: empirical processes, curve estimation, machine learning, model selection, and non- and semiparametric statistics.
She is associate editor of Probability Theory and Related Fields, Journal of the European Mathematical Society, Scandinavian Journal of Statistics, Journal of Machine Learning Research, Statistical Surveys and Journal of Statistical Planning and Inference. She is a member of the Research Council of The Swiss National Science Foundation. She is a member of the International Statistical Institute and fellow of the Institute of Mathematical Statistics. She is correspondent of the Royal Dutch Academy of Sciences and member of Leopoldina German National Academy of Sciences. She is President of the Bernoulli Society.
]]>Bio: Sara van de Geer has been Full Professor at the Seminar for Statistics at ETH Zurich since September 2005. Her main field of research is mathematical statistics, with special interest in high-dimensional problems. Focus points are: empirical processes, curve estimation, machine learning, model selection, and non- and semiparametric statistics.
She is associate editor of Probability Theory and Related Fields, Journal of the European Mathematical Society, Scandinavian Journal of Statistics, Journal of Machine Learning Research, Statistical Surveys and Journal of Statistical Planning and Inference. She is a member of the Research Council of The Swiss National Science Foundation. She is a member of the International Statistical Institute and fellow of the Institute of Mathematical Statistics. She is correspondent of the Royal Dutch Academy of Sciences and member of Leopoldina German National Academy of Sciences. She is President of the Bernoulli Society.
]]>Bio: Sara van de Geer has been Full Professor at the Seminar for Statistics at ETH Zurich since September 2005. Her main field of research is mathematical statistics, with special interest in high-dimensional problems. Focus points are: empirical processes, curve estimation, machine learning, model selection, and non- and semiparametric statistics.
She is associate editor of Probability Theory and Related Fields, Journal of the European Mathematical Society, Scandinavian Journal of Statistics, Journal of Machine Learning Research, Statistical Surveys and Journal of Statistical Planning and Inference. She is a member of the Research Council of The Swiss National Science Foundation. She is a member of the International Statistical Institute and fellow of the Institute of Mathematical Statistics. She is correspondent of the Royal Dutch Academy of Sciences and member of Leopoldina German National Academy of Sciences. She is President of the Bernoulli Society.
]]>Lecture on Combinatorial Statistics
Abstract: In these lectures we discuss some statistical problems with an interesting combinatorial structure behind. We start by reviewing the "hidden clique" problem, a simple prototypical example with a surprisingly rich structure. We also discuss various "combinatorial" testing problems and their connections to high-dimensional random geometric graphs. Time permitting, we study the problem of estimating the mean of a random variable.
]]>Lecture on Combinatorial Statistics
Abstract: In these lectures we discuss some statistical problems with an interesting combinatorial structure behind. We start by reviewing the "hidden clique" problem, a simple prototypical example with a surprisingly rich structure. We also discuss various "combinatorial" testing problems and their connections to high-dimensional random geometric graphs. Time permitting, we study the problem of estimating the mean of a random variable.
]]>Lecture on Combinatorial Statistics
Abstract: In these lectures we discuss some statistical problems with an interesting combinatorial structure behind. We start by reviewing the "hidden clique" problem, a simple prototypical example with a surprisingly rich structure. We also discuss various "combinatorial" testing problems and their connections to high-dimensional random geometric graphs. Time permitting, we study the problem of estimating the mean of a random variable.
]]>Speakers: Afonso Bandeira, Christian Borgs, Rachel Cummings, Peter Frazier, Zaid Harchaoui, Stefanie Jegelka, Philippe Rigollet, Hanie Sedghi, Maehara Takanori, Tandy Warnow.
]]>Theoretical Foundation of Deep Learning 2018 Workshop website
]]>Abstract:
We study the $A$-optimal design problem where we are given vectors $v_1,\ldots, v_n\in \R^d$, an integer $k\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $\left(\sum_{i\in S} v_i v_i^{\top}\right)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics (\cite{pukelsheim2006optimal}) where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks~(\cite{joshi2009sensor}), sparse least squares regression~(\cite{BoutsidisDM11}), feature selection for $k$-means clustering~(\cite{boutsidis2013deterministic}), and matrix approximation~(\cite{de2007subset,de2011note,avron2013faster}). In this paper, we introduce \emph{proportional volume sampling} to obtain improved approximation algorithms for $A$-optimal design.
Given a matrix, proportional volume sampling involves picking a set of columns $S$ of size $k$ with probability proportional to $\mu(S)$ times $\det(\sum_{i \in S}v_i v_i^\top)$ for some measure $\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to \emph{approximate} independence properties of the measure $\mu$. We appeal to hard-core distributions as candidate distributions $\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\epsilon)$-approximation when $k=\Omega\left(\frac{d}{\epsilon}+\frac{1}{\epsilon^2}\log\frac{1}{\epsilon}\right)$ and $\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for $k\leq d$ and obtain a $k$-approximation. The last result also implies a restricted invertibility principle for the harmonic mean of singular values. We also show that the $A$-optimal design problem is $\NP$-hard to approximate within a fixed constant when $k=d$.
We study the $A$-optimal design problem where we are given vectors $v_1,\ldots, v_n\in \R^d$, an integer $k\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $\left(\sum_{i\in S} v_i v_i^{\top}\right)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics (\cite{pukelsheim2006optimal}) where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks~(\cite{joshi2009sensor}), sparse least squares regression~(\cite{BoutsidisDM11}), feature selection for $k$-means clustering~(\cite{boutsidis2013deterministic}), and matrix approximation~(\cite{de2007subset,de2011note,avron2013faster}). In this paper, we introduce \emph{proportional volume sampling} to obtain improved approximation algorithms for $A$-optimal design.
Given a matrix, proportional volume sampling involves picking a set of columns $S$ of size $k$ with probability proportional to $\mu(S)$ times $\det(\sum_{i \in S}v_i v_i^\top)$ for some measure $\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to \emph{approximate} independence properties of the measure $\mu$. We appeal to hard-core distributions as candidate distributions $\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\epsilon)$-approximation when $k=\Omega\left(\frac{d}{\epsilon}+\frac{1}{\epsilon^2}\log\frac{1}{\epsilon}\right)$ and $\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for $k\leq d$ and obtain a $k$-approximation. The last result also implies a restricted invertibility principle for the harmonic mean of singular values. We also show that the $A$-optimal design problem is $\NP$-hard to approximate within a fixed constant when $k=d$.
In this talk, I will give an overview of recent research that aims to remedy this situation. In particular, I will describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., support vector machines or batch gradient computation in neural networks). All of them have polynomial time algorithms, but despite an extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.
]]>