A general formulation to develop electromagnetic-based polynomial surrogate models in the frequency domain utilizing the multinomial theorem is presented in this paper. Our approach is especially suitable when the number of learning samples is very limited and no physics-based coarse model is available. We compare our methodology against four other surrogate modeling techniques: response surface modeling, support vector machines, generalized regression neural networks, and Kriging. Results confirm that our modeling approach has the best performance among these techniques when using a very small amount of learning base points on relatively small modeling regions. We illustrate our technique by developing a surrogate model for a substrate integrated waveguide interconnect with transitions to microstrip lines, a dual-band T-slot planar inverted-F handset antenna, and a high-speed package interconnect. Examples are simulated on a commercially available 3-D FEM simulator.