In this paper, we study two general semi-infinite programming problems by means of a randomized strategy based on statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by the control community. The first main contribution of this paper is to demonstrate that this is not necessarily the case. Utilizing as a starting point one-sided results from statistical learning theory, we obtain bounds on the number of required samples that are manageable for "reasonable" values of probabilistic confidence and accuracy. In particular, we show that the number of required samples grows with the accuracy parameter epsilon as 1/epsilon in 1/epsilon, and this is a significant improvement when compared to the existing bounds which depend on 1/epsilon(2) ln 1/epsilon(2). Secondly, we present new results for optimization and feasibility problems involving Boolean expressions consisting of polynomials. In this case, when the accuracy parameter is sufficiently small, an explicit bound that only depends on the number of decision variables, and on the confidence and accuracy parameters is presented. For convex optimization problems, we also prove that the required sample size is inversely proportional to the accuracy for fixed confidence. Thirdly, we propose a randomized algorithm that provides a probabilistic solution circumventing the potential conservatism of the bounds previously derived.