Chao Gao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Chao Gao has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
Anderson Y. Zhang
3 shared publicationsAnderson Y Zhang
University of Pennsylvania Department of Statistics and Data Science Philadelphia, PA 19104, USA
2 shared publications- Fang Han
Department of Statistics University of Washington 98195 Seattle WA USA
2 shared publications - John Lafferty
Department of Statistics & Data Science Yale University
2 shared publications - Subhodh Kotekal
Department of Statistics, The University of Chicago, Chicago, IL, USA
2 shared publications - Zhao Ren
Department of Statistics, University of Pittsburgh
2 shared publications
Latest Publications
- Open Access
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a distribution $(x, y)$ on $\mathbb{R}^d \times \mathbb{R}$ with $x \sim \mathcal{N}(0,\mathbf{I}_d)$ and $y = x^\top β+ z$, where $z$ is drawn independently of $x$ from an unknown distribution $E$. Moreover, $z$ satisfies $\mathbb{P}_E[z = 0] = α>0$. The goal is to accurately recover the regressor $β$ to small $\ell_2$-error. Ignoring computational considerations, this problem is known to be solvable using $O(d/α)$ samples. On the other hand, the best known polynomial-time algorithms require $Ω(d/α^2)$ samples. Here we provide formal evidence that the quadratic dependence in $1/α$ is inherent for efficient algorithms. Specifically, we show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $\tildeΩ(d^{1/2}/α^2)$.Open AccessInformation-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a distribution $(x, y)$ on $\mathbb{R}^d \times \mathbb{R}$ with $x \sim \mathcal{N}(0,\mathbf{I}_d)$ and $y = x^\top β+ z$, where $z$ is drawn independently of $x$ from an unknown distribution $E$. Moreover, $z$ satisfies $\mathbb{P}_E[z = 0] = α>0$. The goal is to accurately recover the regressor $β$ to small $\ell_2$-error. Ignoring computational considerations, this problem is known to be solvable using $O(d/α)$ samples. On the other hand, the best known polynomial-time algorithms require $Ω(d/α^2)$ samples. Here we provide formal evidence that the quadratic dependence in $1/α$ is inherent for efficient algorithms. Specifically, we show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $\tildeΩ(d^{1/2}/α^2)$. - 14 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (3) , 2075-2103
Optimal Estimation of the Null Distribution in Large-Scale Inference
The advent of large-scale inference has spurred reexamination of conventional statistical thinking. In a series of highly original articles, Efron persuasively illustrated the danger for downstream inference in assuming the veracity of a posited null distribution. In a Gaussian model for n many z-scores with at most $k \lt \frac {n}{2}$ nonnulls, Efron suggests estimating the parameters of an empirical null $N(\theta , \sigma ^{2})$ instead of assuming the theoretical null $N(0, 1)$ . Looking to the robust statistics literature by viewing the nonnulls as outliers is unsatisfactory as the question of optimal rates is still open; even consistency is not known in the regime $k \asymp n$ which is especially relevant to many large-scale inference applications. However, provably rate-optimal robust estimators have been developed in other models (e.g. Huber contamination) which appear quite close to Efron’s proposal. Notably, the impossibility of consistency when $k \asymp n$ in these other models may suggest the same major weakness afflicts Efron’s popularly adopted recommendation. A sound evaluation thus requires a complete understanding of information-theoretic limits. We characterize the regime of k for which consistent estimation is possible, notably without imposing any assumptions at all on the nonnull effects. Unlike in other robust models, it is shown consistent estimation of the location parameter is possible if and only if $\frac {n}{2} {-} k = \omega (\sqrt {n})$ , and of the scale parameter in the entire regime $k \lt \frac {n}{2}$ . Furthermore, we establish sharp minimax rates and show estimators based on the empirical characteristic function are optimal by exploiting the Gaussian character of the data.
- 14 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (3) , 2075-2103
Optimal Estimation of the Null Distribution in Large-Scale Inference
The advent of large-scale inference has spurred reexamination of conventional statistical thinking. In a series of highly original articles, Efron persuasively illustrated the danger for downstream inference in assuming the veracity of a posited null distribution. In a Gaussian model for n many z-scores with at most $k \lt \frac {n}{2}$ nonnulls, Efron suggests estimating the parameters of an empirical null $N(\theta , \sigma ^{2})$ instead of assuming the theoretical null $N(0, 1)$ . Looking to the robust statistics literature by viewing the nonnulls as outliers is unsatisfactory as the question of optimal rates is still open; even consistency is not known in the regime $k \asymp n$ which is especially relevant to many large-scale inference applications. However, provably rate-optimal robust estimators have been developed in other models (e.g. Huber contamination) which appear quite close to Efron’s proposal. Notably, the impossibility of consistency when $k \asymp n$ in these other models may suggest the same major weakness afflicts Efron’s popularly adopted recommendation. A sound evaluation thus requires a complete understanding of information-theoretic limits. We characterize the regime of k for which consistent estimation is possible, notably without imposing any assumptions at all on the nonnull effects. Unlike in other robust models, it is shown consistent estimation of the location parameter is possible if and only if $\frac {n}{2} {-} k = \omega (\sqrt {n})$ , and of the scale parameter in the entire regime $k \lt \frac {n}{2}$ . Furthermore, we establish sharp minimax rates and show estimators based on the empirical characteristic function are optimal by exploiting the Gaussian character of the data.
- 3 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (12) , 8892-8928
Minimax Signal Detection in Sparse Additive Models
Sparse additive models are an attractive choice in circumstances calling for modelling flexibility in the face of high dimensionality. We study the signal detection problem and establish the minimax separation rate for the detection of a sparse additive signal. Our result is nonasymptotic and applicable to the general case where the univariate component functions belong to a generic reproducing kernel Hilbert space. Unlike the estimation theory, the minimax separation rate reveals a nontrivial interaction between sparsity and the choice of function space. We also investigate adaptation to sparsity and establish an adaptive testing rate for a generic function space; adaptation is possible in some spaces while others impose an unavoidable cost. Finally, adaptation to both sparsity and smoothness is studied in the setting of Sobolev space, and we correct some existing claims in the literature.
- 3 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (12) , 8892-8928
Minimax Signal Detection in Sparse Additive Models
Sparse additive models are an attractive choice in circumstances calling for modelling flexibility in the face of high dimensionality. We study the signal detection problem and establish the minimax separation rate for the detection of a sparse additive signal. Our result is nonasymptotic and applicable to the general case where the univariate component functions belong to a generic reproducing kernel Hilbert space. Unlike the estimation theory, the minimax separation rate reveals a nontrivial interaction between sparsity and the choice of function space. We also investigate adaptation to sparsity and establish an adaptive testing rate for a generic function space; adaptation is possible in some spaces while others impose an unavoidable cost. Finally, adaptation to both sparsity and smoothness is studied in the setting of Sobolev space, and we correct some existing claims in the literature.
- 31 January 2023
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 12 (2) , 1073-1140
Uncertainty quantification in the Bradley–Terry–Luce model
The Bradley–Terry–Luce (BTL) model is a benchmark model for pairwise comparisons between individuals. Despite recent progress on the first-order asymptotics of several popular procedures, the understanding of uncertainty quantification in the BTL model remains largely incomplete, especially when the underlying comparison graph is sparse. In this paper, we fill this gap by focusing on two estimators that have received much recent attention: the maximum likelihood estimator (MLE) and the spectral estimator. Using a unified proof strategy, we derive sharp and uniform non-asymptotic expansions for both estimators in the sparsest possible regime (up to some poly-logarithmic factors) of the underlying comparison graph. These expansions allow us to obtain: (i) finite-dimensional central limit theorems for both estimators; (ii) construction of confidence intervals for individual ranks; (iii) optimal constant of $\ell _2$ estimation, which is achieved by the MLE but not by the spectral estimator. Our proof is based on a self-consistent equation of the second-order remainder vector and a novel leave-two-out analysis.- 31 January 2023
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 12 (2) , 1073-1140
Uncertainty quantification in the Bradley–Terry–Luce model
The Bradley–Terry–Luce (BTL) model is a benchmark model for pairwise comparisons between individuals. Despite recent progress on the first-order asymptotics of several popular procedures, the understanding of uncertainty quantification in the BTL model remains largely incomplete, especially when the underlying comparison graph is sparse. In this paper, we fill this gap by focusing on two estimators that have received much recent attention: the maximum likelihood estimator (MLE) and the spectral estimator. Using a unified proof strategy, we derive sharp and uniform non-asymptotic expansions for both estimators in the sparsest possible regime (up to some poly-logarithmic factors) of the underlying comparison graph. These expansions allow us to obtain: (i) finite-dimensional central limit theorems for both estimators; (ii) construction of confidence intervals for individual ranks; (iii) optimal constant of $\ell _2$ estimation, which is achieved by the MLE but not by the spectral estimator. Our proof is based on a self-consistent equation of the second-order remainder vector and a novel leave-two-out analysis.- Open Access
Uncertainty quantification in the Bradley-Terry-Luce model
The Bradley-Terry-Luce (BTL) model is a benchmark model for pairwise comparisons between individuals. Despite recent progress on the first-order asymptotics of several popular procedures, the understanding of uncertainty quantification in the BTL model remains largely incomplete, especially when the underlying comparison graph is sparse. In this paper, we fill this gap by focusing on two estimators that have received much recent attention: the maximum likelihood estimator (MLE) and the spectral estimator. Using a unified proof strategy, we derive sharp and uniform non-asymptotic expansions for both estimators in the sparsest possible regime (up to some poly-logarithmic factors) of the underlying comparison graph. These expansions allow us to obtain: (i) finite-dimensional central limit theorems for both estimators; (ii) construction of confidence intervals for individual ranks; (iii) optimal constant of $\ell_2$ estimation, which is achieved by the MLE but not by the spectral estimator. Our proof is based on a self-consistent equation of the second-order remainder vector and a novel leave-two-out analysis.Open AccessUncertainty quantification in the Bradley-Terry-Luce model
The Bradley-Terry-Luce (BTL) model is a benchmark model for pairwise comparisons between individuals. Despite recent progress on the first-order asymptotics of several popular procedures, the understanding of uncertainty quantification in the BTL model remains largely incomplete, especially when the underlying comparison graph is sparse. In this paper, we fill this gap by focusing on two estimators that have received much recent attention: the maximum likelihood estimator (MLE) and the spectral estimator. Using a unified proof strategy, we derive sharp and uniform non-asymptotic expansions for both estimators in the sparsest possible regime (up to some poly-logarithmic factors) of the underlying comparison graph. These expansions allow us to obtain: (i) finite-dimensional central limit theorems for both estimators; (ii) construction of confidence intervals for individual ranks; (iii) optimal constant of $\ell_2$ estimation, which is achieved by the MLE but not by the spectral estimator. Our proof is based on a self-consistent equation of the second-order remainder vector and a novel leave-two-out analysis. - 6 August 2022
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 12 (2) , 591-632
Optimal orthogonal group synchronization and rotation group synchronization
We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$ where $W_{ij}$ is a Gaussian random matrix and $Z_i^*$ is either an orthogonal matrix or a rotation matrix, and each $Y_{ij}$ is observed independently with probability $p$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.- 6 August 2022
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 12 (2) , 591-632
Optimal orthogonal group synchronization and rotation group synchronization
We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$ where $W_{ij}$ is a Gaussian random matrix and $Z_i^*$ is either an orthogonal matrix or a rotation matrix, and each $Y_{ij}$ is observed independently with probability $p$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (8) , 5374-5390
SDP Achieves Exact Minimax Optimality in Phase Synchronization
We study the phase synchronization problem with noisy measurements $Y=z^{*}z^{* { \mathrm {\scriptscriptstyle H} }}+\sigma W\in \mathbb {C}^{n\times n}$ , where $z^{*}$ is an $n$ -dimensional complex unit-modulus vector and $W$ is a complex-valued Gaussian random matrix. It is assumed that each entry $Y_{jk}$ is observed with probability $p$ . We prove that an SDP relaxation of the MLE achieves the error bound $(1+o(1))\frac {\sigma ^{2}}{2np}$ under a normalized squared $\ell _{2}$ loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent non-convex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for $\mathbb {Z}_{2}$ synchronization, and we achieve the minimax optimal error $\exp \left ({-(1-o(1))\frac {np}{2\sigma ^{2}}}\right)$ with a sharp constant in the exponent.
- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (8) , 5374-5390
SDP Achieves Exact Minimax Optimality in Phase Synchronization
We study the phase synchronization problem with noisy measurements $Y=z^{*}z^{* { \mathrm {\scriptscriptstyle H} }}+\sigma W\in \mathbb {C}^{n\times n}$ , where $z^{*}$ is an $n$ -dimensional complex unit-modulus vector and $W$ is a complex-valued Gaussian random matrix. It is assumed that each entry $Y_{jk}$ is observed with probability $p$ . We prove that an SDP relaxation of the MLE achieves the error bound $(1+o(1))\frac {\sigma ^{2}}{2np}$ under a normalized squared $\ell _{2}$ loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent non-convex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for $\mathbb {Z}_{2}$ synchronization, and we achieve the minimax optimal error $\exp \left ({-(1-o(1))\frac {np}{2\sigma ^{2}}}\right)$ with a sharp constant in the exponent.
- 14 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (12) , 8236-8247
Exact Minimax Estimation for Phase Synchronization
We study the phase synchronization problem with measurements Y = z*z*H + σW ∈ Cn×n, where z* is an n-dimensional complex unit-modulus vector and W is a complexvalued Gaussian random matrix. It is assumed that each entry Yjk is observed with probability p. We prove that the minimax lower bound of estimating z* under the squared ℓ2 loss is (1-o(1)) σ2/2p. We also show that both generalized power method and maximum likelihood estimator achieve the error bound (1 + o(1)) σ2/2p. Thus, σ2/2p is the exact asymptotic minimax error of the problem. Our upper bound analysis involves a precise characterization of the statistical property of the power iteration. The lower bound is derived through an application of van Trees’ inequality.
- 14 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (12) , 8236-8247
Exact Minimax Estimation for Phase Synchronization
We study the phase synchronization problem with measurements Y = z*z*H + σW ∈ Cn×n, where z* is an n-dimensional complex unit-modulus vector and W is a complexvalued Gaussian random matrix. It is assumed that each entry Yjk is observed with probability p. We prove that the minimax lower bound of estimating z* under the squared ℓ2 loss is (1-o(1)) σ2/2p. We also show that both generalized power method and maximum likelihood estimator achieve the error bound (1 + o(1)) σ2/2p. Thus, σ2/2p is the exact asymptotic minimax error of the problem. Our upper bound analysis involves a precise characterization of the statistical property of the power iteration. The lower bound is derived through an application of van Trees’ inequality.
- Open Access
Bayesian Model Selection with Graph Structured Sparsity
We propose a general algorithmic framework for Bayesian model selection. A spike-and-slab Laplacian prior is introduced to model the underlying structural assumption. Using the notion of effective resistance, we derive an EM-type algorithm with closed-form iterations to efficiently explore possible candidates for Bayesian model selection. The deterministic nature of the proposed algorithm makes it more scalable to large-scale and high-dimensional data sets compared with existing stochastic search algorithms. When applied to sparse linear regression, our framework recovers the EMVS algorithm [Rockova and George, 2014] as a special case. We also discuss extensions of our framework using tools from graph algebra to incorporate complex Bayesian models such as biclustering and submatrix localization. Extensive simulation studies and real data applications are conducted to demonstrate the superior performance of our methods over its frequentist competitors such as $\ell_0$ or $\ell_1$ penalization.Open AccessBayesian Model Selection with Graph Structured Sparsity
We propose a general algorithmic framework for Bayesian model selection. A spike-and-slab Laplacian prior is introduced to model the underlying structural assumption. Using the notion of effective resistance, we derive an EM-type algorithm with closed-form iterations to efficiently explore possible candidates for Bayesian model selection. The deterministic nature of the proposed algorithm makes it more scalable to large-scale and high-dimensional data sets compared with existing stochastic search algorithms. When applied to sparse linear regression, our framework recovers the EMVS algorithm [Rockova and George, 2014] as a special case. We also discuss extensions of our framework using tools from graph algebra to incorporate complex Bayesian models such as biclustering and submatrix localization. Extensive simulation studies and real data applications are conducted to demonstrate the superior performance of our methods over its frequentist competitors such as $\ell_0$ or $\ell_1$ penalization. - 15 May 2020
- Published by Oxford University Press (OUP) in Biometrika
- Vol. 107 (2) , 281-284
Discussion of ‘Network cross-validation by edge sampling’
- 15 May 2020
- Published by Oxford University Press (OUP) in Biometrika
- Vol. 107 (2) , 281-284
Discussion of ‘Network cross-validation by edge sampling’