Could you explain how wavelet decompositions/transforms could be used to learn a predictive model? In other words: given a labeled dataset D = {x_i, y_i}, a function F(x) = y, where x is input data (pixels, credit scores, etc), and y are target labels (object labels, investment risk, etc.).

I'm not very well-versed with wavelet methods. But in computer vision and image processing, I've seen people apply wavelet transforms to images, extract the wavelet coefficients, and use the coefficients as the image feature representation. Then, these coefficients would typically be fed to a traditional machine learning classifier, ie nearest neighbor, SVM, etc.

In other words, I've seen wavelet transforms used as feature extractors. I haven't seen wavelet transforms used to actually learn the predictive model F(x).

Gradient boosting, on the other hand, is learning the predictive model F(x).

Said in another way: gradient boosting is learning F(x) = y.

Wavelet transforms learn g(x) = x^{hat}, such that F(g(x)) = y is "easier" to learn.

I hope I'm explaining things clearly - sorry in advance if I made any mistakes, particularly in my understanding of wavelet transforms/decompositions.

Can wavelet decompose be trained for classification of feature vectors with many dimensions?

Yes that is what they are for. In this case you probably don't even really need wavelets and you can just use a Fourier transform

Fourier transform is not a classification mechanism. You can transform something into frequency domain, but that doesn't inform you which frequencies are most relevant in classifying samples.