  Change point estimation in its offline version is traditionally performed by
optimizing over the data set of interest, by considering each data point as the
true location parameter and computing a data fit criterion. Subsequently, the
data point that minimizes the criterion is declared as the change point
estimate. For estimating multiple change points, the procedures are analogous
in spirit, but significantly more involved in execution. Since change-points
are local discontinuities, only data points close to the actual change point
provide useful information for estimation, while data points far away are
superfluous, to the point where using only a few points close to the true
parameter is just as precise as using the full data set. Leveraging this
"locality principle", we introduce a two-stage procedure for the problem at
hand, which in the 1st stage uses a sparse subsample to obtain pilot estimates
of the underlying change points, and in the 2nd stage refines these estimates
by sampling densely in appropriately defined neighborhoods around them. We
establish that this method achieves the same rate of convergence and even
virtually the same asymptotic distribution as the analysis of the full data,
while reducing computational complexity to O(N^0.5) time (N being the length of
data set), as opposed to at least O(N) time for all current procedures, making
it promising for the analysis on exceedingly long data sets with adequately
spaced out change points. The main results are established under a signal plus
noise model with independent and identically distributed error terms, but
extensions to dependent data settings, as well as multiple stage (>2)
procedures are also provided. The performance of our procedure -- which is
coined "intelligent sampling" -- is illustrated on both synthetic and real
Internet data streams.
