Suppose you have 500,000 possible factors that could effect your response variable 'profit'. What is the best way to deal with this data set and how large should the data set be for analysis to be valid? I know there are a number of ways for dimension reduction such as PCA, but are there more 'practical methods' for dimensionality reduction? Also, if I wanted to use all 500,000 factors, how large should n be? I know you can model with P>n but is there a threshold?
This is a very open-ended question and in many cases I think domain knowledge will play a crucial role. Having said that, I think that it will be well-worth your time to check the Royal Society's Philosophical Transactions A theme issue on Statistical challenges of high-dimensional data.
In general everything revolves around penalised estimators (eg. LASSO), appropriate dimension reduction (eg. PCA) and/or intelligent information criteria (eg. AICc). Do not expect a silver bullet approach (eg. boosting) to solve all your problems. In the end of the day, all models are represent our intrinsic understanding of the problem's nature. If we have nearly no understanding of what we try to solve/model and we simply dump data in and hope for the best there is a good chance we will get meaningless answers.
There are no such hard and fast rules and this is wholly dependent upon the nature of the data. Part of your job is to use various algorithms and methods on the data to determine what this nature is, and guide you in the selection of the best techniques for your data and given problem.
I can't even fathom what 500k features for "profit" would be. The question is so undefined and broad as to be meaningless.
I don't know of any thumb rule for n given number of factors, but there is a thumb rule that for choosing a statistically sound sample for model the size should be at least sqrt(n) if n is you total number of observations in data. In that sense your 'n' should be atleast greater than P-squared to make sense (and preferably 2 times P-squared to have a good training and validation set).
Apart from dimensionality reduction you can also you ensemble methods, where you construct multiple models with various randomly chosen subsets of your 500,000 variables...
Check out this answer... How to build a predictive model that uses only a subset of training factors , for testing?
Tree methods are in general not that much affected by bogus predictors. After using a tree method it is possible to request the most important variables. In this way it is possible to select a usable subset of parameters. From there you could use those predictors in different models.
Having said all that: 500k predictors is a lot. The chance of spurious correlations is considerable. Make sure you have some cross-validation procedure in place.