We consider the variable selection problem in linear regression. Suppose that we have a set of random variables $X_1,...,X_m,Y,ε$ such that $Y=\sum_{k\in π}α_kX_k+ε$ with $π\subseteq \{1,...,m\}$ and $α_k\in {\mathbb R}$ unknown, and $ε$ is independent of any linear combination of $X_1,...,X_m$. Given actually emitted $n$ examples $\{(x_{i,1}...,x_{i,m},y_i)\}_{i=1}^n$ emitted from $(X_1,...,X_m, Y)$, we wish to estimate the true $π$ using information criteria in the form of $H+(k/2)d_n$, where $H$ is the likelihood with respect to $π$ multiplied by -1, and $\{d_n\}$ is a positive real sequence. If $d_n$ is too small, we cannot obtain consistency because of overestimation. For autoregression, Hannan-Quinn proved that, in their setting of $H$ and $k$, the rate $d_n=2\log\log n$ is the minimum satisfying strong consistency. This paper solves the statement affirmative for linear regression as well which has a completely different setting.