Feature selection is not always necessary. I approach it with a number of questions/decisions:
- Does feature selection make sense for the type of data at hand, i.e. can we expect from our knowledge about the application and data generation processes that there are substantial numbers of features that do not carry information?
In my case, I often work with spectroscopic data. The physics behind the measurements imply that the information I'm after is likely "spread out" over many variates/features. Feature selection doesn't make much sense here, but again physics and chemistry mean that feature compression e.g. by PCA would be a sensible approach.
OTOH, consider gene microarray data. Here we usually expect most features to carry noise only, thus feature selection is a sensible approach.
If it is sensible,
- Can we do (part of) the feature selection by external knowledge? If so, removing them immediately is very powerful since we get a feature reduction without any "cost" in sample size.
E.g. for said spectroscopic data, I sometimes know from physics, chemistry and the way the measurement instrument is set up that certain ranges of features do not carry information. I cut them out as part of the pre-processing of the data.
If we still want to remove more features after this step,
Can we afford data-driven feature selection? How much?
Data-driven feature selection is IHMO best discussed as part of general hyperparameter optimization, and it will often be set up in a way that hugely extends the hyperparameter search space.
One (the) key factor for data-driven hyperparameter selection is IMHO the uncertainty on the performance estimate. This depends on the absolute number of tested cases. Model instability also adds to this uncertainty, so also available cases relative to number of features enters, but indirectly and moreover we can make sure (by resampling, e.g. repeated CV) that it is not the dominating source of uncertainty. Uncertainty also depends on the chosen figure of merit. Proper scoring rules are much better suitable for optimization than proportion-type figures of merit such as accuracy in various ways, and in my experience they tend to have lower variance uncertainty (that is not guaranteed, but you can have a guarantee that they are anyways no worse).
When deciding whether one model is better than another (= the baseline model), and for both the performance is known only with uncertainty, that's something that
statistical tests are good for. (For your accuracy, e.g. McNemar's test). The number of features among you search enters at this stage: you'll need to take the number of model comparisons you perform into account, and this will likely increase with the number of features among which you search, also depending on your search heuristic.
I don't think one can sensibly express these dependencies as a simple sample size to feature ratio, though.
For your scenario (accuracy, 500 test cases, 80 features among which to select), you cannot afford data-driven feature selection.
I arrive at this conclusion based on some back-of-the envelope calculations with McNemar's test. You may say that the baseline model is too good to allow reliable detection of better models at the given sample size of 500. You may get that for a very few comparisons, but not for anything you'd expect for searchning among 80 features.
If you nevertheless choose the apparently best model, that is likely to be overfit: the apparent improvement is more likely due to accidentally favorable train/test splits than to true improvement.
You may take another approach, though, and let e.g. LASSO regularization take care of feature selection without the need for model comparisons.