Properties of the Number of Iterations of a Feasible Solutions Algorithm

In recent years, statistical analyses, algorithms, and modeling have been constrained due to computational complexity. Further, the added complexity of relationships among response and explanatory variables, such as higher-order interaction effects, makes identifying predictors using standard statistical techniques difficult. These difficulties are only exacerbated in the case of small sample sizes in some studies. Recent analyses have targeted the identification of interaction effects in big data, but the development of methods to identify higher-order interaction effects has been limited by computational concerns. One recently studied method is the feasible solutions algorithm (FSA), a fast, flexible method that aims to find a set of statistically optimal models via a stochastic search algorithm. Although FSA has shown promise, its current limits include that the user must choose the number of times to run the algorithm. Here, we provide statistical guidance for this number of iterations by deriving a lower bound on the probability of obtaining the statistically optimal model in a number of iterations of FSA. For example, when considering a two-way interaction model, if you would like the probability of obtaining the statistically optimal solution to be at least 80%, then you would need to choose the number of random starts of FSA to be 40% of the number of possible explanatory variables in your data set. The performance of this bound is then tested on both simulated and real data. This work allows FSA users to make statistically informed choices about FSA that can improve data analysis techniques.