We develop algorithms for writing a polynomial as sums of powers of low\ndegree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can\nbe written as $$f = c_1Q_1^{m} + \\ldots + c_s Q_s^{m},$$ where each $c_i\\in\n\\mathbb{F}^{\\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m\n= d$. In this paper, we give a $\\text{poly}((ns)^t)$-time learning algorithm\nfor finding the $Q_i$'s given (black-box access to) $f$, if the $Q_i's$ satisfy\ncertain non-degeneracy conditions and $n$ is larger than $d^2$. The set of\ndegenerate $Q_i$'s (i.e., inputs for which the algorithm does not work) form a\nnon-trivial variety and hence if the $Q_i$'s are chosen according to any\nreasonable (full-dimensional) distribution, then they are non-degenerate with\nhigh probability (if $s$ is not too large).\n Our algorithm is based on a scheme for obtaining a learning algorithm for an\narithmetic circuit model from a lower bound for the same model, provided\ncertain non-degeneracy conditions hold. The scheme reduces the learning problem\nto the problem of decomposing two vector spaces under the action of a set of\nlinear operators, where the spaces and the operators are derived from the input\ncircuit and the complexity measure used in a typical lower bound proof. The\nnon-degeneracy conditions are certain restrictions on how the spaces decompose.\n