With power becoming the dominant limiter of advanced nm-scale designs, the need to make early and accurate predictions gains importance. Further, due to the dominance of interconnect in such designs, the impact of physical design decisions on power grows as well. However, performing detailed power estimation including interconnect parasitics can be time consuming with current generation EDA tools. In this paper, we evaluate the accuracy and efficiency of alternative approaches to power estimation that leverage machine learning techniques to bridge the gap first between simple and complex simulation schemes and second between logic level (pre-Physical Design) and physical level (post-Physical Design). We demonstrate that a careful matching of simulation granularity and machine learning techniques can lead to a significant reduction in effort with only modest degradation in accuracy.