Is it possible to perform multiclass classification on data where the number of features is less than the number of target variables? Do you have any suggestions on how to address a problem where I have 2000 target variables?
Of course. It only depends if those features are informative enough for the task at hand. In order to better understand the phenomenon, you can imagine 2 features displayed as points in a 2D plane. The number of possible target classes goes up to the number of clusters you can find in that plane.
About the suggestion, I can only recommend the utilisation of a non-linear classifier.