NON-SPARSE HIGH-DIMENSIONAL STATISTICS AND ITS APPLICATIONSMASAAKI IMAIZUMI1,2
1 The University of Tokyo, 2 RIKEN Advanced Intelligence ProjectAbstract. In this talk, we present several results in non-sparse high-dimensional statistics. Specifically, the generalization and Bayesian estimation of high-dimensional linear regression models,statistical inference for high-dimensional generalized linear models, and the regret analysis on contextual bandit problems applying high-dimensional linear models. The analysis in these studies uses
the theory of benign overﬁtting using spectrum, the risk analysis using the convex Gaussian minimax
theorem, and the statistical inference using approximate message propagation methods.

1. Outline
1.1. Linear Regression. We consider a linear regression problem with 𝑝-dimensional covariates
𝑛 of a covariate 𝑋 ∈ R 𝑝 and aand a parameter. Suppose that we observe i.i.d. 𝑛 pairs {(𝑋𝑖 , 𝑌𝑖 )}𝑖=1
𝑖target variable 𝑌𝑖 ∈ R generated from the following linear model with the true parameter 𝜃 0 ∈ R 𝑝 :𝑌𝑖 = ⟨𝑋𝑖 , 𝜃 0 ⟩ + 𝜉𝑖 , 𝑖 = 1, ..., 𝑛,where 𝜉𝑖 is a centered noise variable. Let Σ = E[𝑋𝑖 𝑋𝑖⊤ ] be a covariance matrix of the covariate.
The goal of this problem is to estimate the parameter 𝜃 0 from the observations. Here, we consider
the high-dimensional setting, speciﬁcally, we consider 𝑝 ≫ 𝑛 or where 𝑝 = ∞ regardless of 𝑛.
Also, we do not impose the assumption of sparsity on the true parameter 𝜃 0 . In this setting, thenotion of benign overﬁtting is actively studied.
We investigate whether benign overﬁtting-like phenomena occur in situations in which we relax
key assumptions in this foundational model. [NI22] considers the case where the covariates aredependent in the sample direction and shows that similar benign overﬁtting occurs depending on
the strength of the dependence. [WI23] develops an informative prior distribution that allows
for a Bayesian estimator and its distribution approximation that is valid even in non-sparse highdimensions. [TI23] considers that the noise 𝜉𝑖 is dependent on the covariance and gives conditions
for the estimation error convergence, by utilizing the Gaussian minimax inequality.
1.2. Generalized Linear Regression. We next consider the generalized linear model (GLM):
for a pair (𝑋, 𝑌 ) of 𝑝-dimensional random features 𝑋 and random responses 𝑌 , we consider thefollowing modelE[𝑌 | 𝑋 = 𝑥] = 𝑔(𝑥 ⊤ 𝛽), ∀𝑥 ∈ R 𝑝 ,1(1)where 𝑔 : R → R is an inverse link function that monotonically increases, and 𝛽 = (𝛽1 , . . . , 𝛽 𝑝 ) ⊤ ∈𝑛
R 𝑝 is an unknown deterministic coeﬃcient vector. Suppose that we observe i.i.d. 𝑛 pairs {(𝑋𝑖 , 𝑌𝑖 )}𝑖=1
of a feature vector 𝑋𝑖 ∈ R 𝑝 and a target variable 𝑌𝑖 ∈ Y that follow the GLM (1), where Y is aresponse space, such as R, R+ , {0, 1}, {0, 1, 2, . . .}, and so on.
We consider the proportional high-dimensional regime: we are particularly interested in theproportional limit of the coeﬃcient dimension 𝑝 and sample size 𝑛:𝑛, 𝑝 → ∞ and 𝑝/𝑛 → ∃𝜅 ∈ (0, ∞).
In this regime, for the logistic regression as the special case, statistical inference on 𝛽 has been
actively studied without the sparsity of 𝛽.
[SUI23] develops a methodology for statistical inference for a broad class of GLMs, by deriving
the asymptotic normality of an estimator. This method is based on the analysis of a state evolution
equation by a vector approximate massage passiong (VAMP) and its application to statistical models.
1.3. Bandit with Linear Context. We study a bandit problem with 𝐾 arms associated with a linear
model for its rewards with 𝑝-dimensional context vectors. For each round 𝑡 ∈ [𝑇] := {1, 2, ..., 𝑇 }and arm 𝑖 ∈ [𝐾], we deﬁne a context 𝑋𝑡(𝑖) which is a 𝑝-dimensional zero-mean sub-Gaussian vector,
which is independent among rounds 𝑡. An agent chooses an arm 𝐼 (𝑡) ∈ [𝐾] based on 𝑋𝑡(𝑖) of all
the arms 𝑘 ∈ [𝐾], and then observes a reward that follows a linear model as shown in𝑌 (𝐼 (𝑡)) = ⟨𝑋 (𝐼 (𝑡)) , 𝜃 𝐼 (𝑡) ⟩ + 𝜉 (𝑡).
The unknown true parameters 𝜃 (𝑖) for each arm 𝑖 ∈ [𝐾] lie in a parameter space R 𝑝 , and theindependent sub-Gaussian noise 𝜉 (𝑡) with zero mean and variance 𝜎 2 > 0. We deﬁne 𝑖 ∗ (𝑡) :=argmax𝑖∈[𝐾] ⟨𝑋𝑡(𝑖) , 𝜃 (𝑖) ⟩ as the (ex ante) optimal arm at round 𝑡.
Our goal is to design an algorithm that maximizes the total reward, which is equivalent tominimizing the following expected regret. [KI23] considers the high-dimensional setting 𝑝 ≫ 𝑛 or𝑝 = ∞ without the sparsity, then derive a novel explore-then-commit strategy to achieve minimize
the expected regret.
References[KI23] Junpei Komiyama and Masaaki Imaizumi. High-dimensional contextual bandit problem
without sparsity. Advances in Neural Information and Processing Systems, 2023.
[NI22] Shogo Nakakita and Masaaki Imaizumi. Benign overﬁtting in time series linear modelwith over-parameterization. arXiv preprint arXiv:2204.08369, 2022.
[SUI23] Kazuma Sawaya, Yoshimasa Uematsu, and Masaaki Imaizumi. Feasible adjustments ofstatistical inference in high-dimensional generalized linear models. 2023.
[TI23] Toshiki Tsuda and Masaaki Imaizumi. Benign overﬁtting of non-sparse high-dimensional
linear regression with correlated noise. arXiv preprint arXiv:2304.04037, 2023.
[WI23] Tomoya Wakayama and Masaaki Imaizumi. Bayesian analysis for over-parameterized
linear model without sparsity. arXiv preprint arXiv:2305.15754, 2023.
2