  Variable selection in high-dimensional spaces is a pervasive challenge in
contemporary scientific exploration and decision-making. However, existing
approaches that are known to enjoy strong statistical guarantees often struggle
to cope with the computational demands arising from the high dimensionality. To
address this issue, we propose a novel Laplace approximation method based on Le
Cam's one-step procedure (\textsf{OLAP}), designed to effectively tackles the
computational burden. Under some classical high-dimensional assumptions we show
that \textsf{OLAP} is a statistically consistent variable selection procedure.
Furthermore, we show that the approach produces a posterior distribution that
can be explored in polynomial time using a simple Gibbs sampling algorithm.
Toward that polynomial complexity result, we also made some general, noteworthy
contributions to the mixing time analysis of Markov chains. We illustrate the
method using logistic and Poisson regression models applied to simulated and
real data examples.
