To clarify, you have at least one observation in every possible category combination, but you only want to perform analysis on a subset of the total data, and are trying to decide how to choose which points to keep and which points to throw away?
I think the right approach here will depend strongly on what your hypothesis
h is, what sort of statistical tests you want to run, and what your loss function is. If you're trying to answer a question which can be answered by the number of datapoints in each combination, for example, or by the mean and stdev of some continuous variable for each combination, reducing the size of your data by sampling will only hurt your analysis.
If you're trying to learn a classifier, for example, a classic question is whether to train on a set with equal numbers of all possible classes or with the underlying class distribution found in the wild. The first will train a "superior" classifier, especially if its prior on class membership is later reset to the actual distribution in the wild, by most reasonable loss functions. But is your loss function one of the ones where this is better?
You might also want to look into design of experiments, combinatorial design in particular, which is trying to solve a symmetrical problem--starting with no data but being able to choose the various values, what set of points should we test to get as much information as possible about the underlying functions?