SOME RECENT RESULTS IN MODEL SELECTION - Quantitative Medical Data Analysis Using Mathematical Tools and Statistical Techniques - page 26

in model selection require solving NP-hard problems. Hence, in
general, there is no ecient algorithmic solution.
In fact, the state-of-the-art algorithm in solving this problem is still
the leaps-and-bounds [18], which was proposed in 70's and basically
utilizes the branch-and-bound technique that is widely used in com-
binatorial optimization. There are some recent improvements; for
example LBOT 38 . However, when the number of predictors is more
than 40 to 50, most of these methods will take intolerable amount
of time.
In applied mathematics, it is found that even though some problems
are NP-hard in general, there are special cases, under which they
are solvable in polynomial time. A case that has been cited for
many times is Donoho and Huo 11 . This motivates us to search for
special conditions, which (a) can be veried in polynomial time and
(b) indicate that a model selection problem has polynomial time
solution.
The above leads to the action: nding a group of conditions, which
help to identify solvable model selection problem. See some initial
results in [28].
The above diers from many existing works in the following way: we
consider the computational aspect, in particular the solvability of model
selection problems, assuming that the model selection criteria are based
on a prexed class of optimization problems; while other works may em-
phasize more on the statistical properties of the results of model selection
approaches, as we will summarize in Section 5.
Another dierence (from many existing statistically algorithmic papers)
is that instead of considering a particular numeric method, we abstract
them into two types of problems: (P0) and (P1), which will be dened
in the next section. Instead of nding an ecient algorithm for either of
them, we consider when do these two problems have the identical solutions.
Such an equivalence is argued to establish an ecient algorithm to solve
the model selection problem. More details will be articulated.
As a fundamental tool, progress in model selection is likely to improve
the methodologies in biostatistics. This paper does not focus on biostatis-
tical applications in particular.
This chapter is organized as follows. We give an overview of our perspec-
tive in Section 2. Details on related literature and formulation are presented
in Section 3. In Section 4, we use two extreme examples to illustrate the