The type of power analysis you seem to be referring to is: make some assumptions about the distribution of variables, the effect size, etc., and then ask how many samples you'd need to have a (say) 80% probability of detecting an effect of that magnitude.
There are in fact many results of a similar flavor in ML theory. For instance, here's one for SVMs (rephrased from Corollary 15.7 of Shalev-Shwartz and Ben-David, Understanding Machine Learning):
$\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator{\sign}{sign}
\newcommand{\x}{\mathbf x}
\newcommand{\X}{\mathcal X}
\newcommand{\D}{\mathcal D}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\w}{\mathbf w}
\newcommand{\u}{\mathbf u}
$
Let $\D$ be a distribution over $\X \times \{-1, 1\}$, where $\X = \{ \x : \norm\x \le \rho \}$. Consider running Soft-SVM (with no bias term) on a training set $S \sim \D^m$ and let $A(S)$ be the solution of Soft-SVM:
$$A(s) = \argmin_{\mathbf w} \lambda \norm\w^2 + L_S^\mathit{hinge}(\w)$$
where $$L_S^\mathrm{hinge}(\w) = \frac1m \sum_{i=1}^m \max\{0, 1 - y \, \langle \w, \x_i \rangle \} .$$
Then, for every $B > 0$, if we set $\lambda = \sqrt{2 \rho^2 / (B^2 m)}$, then
$$
\E_{S \sim \D^m}[ L_\D^{0-1}(A(S)) ]
\le \E_{S \sim \D^m}[ L_\D^\mathit{hinge}(A(S)) ]
\le \min_{\w : \norm\w \le B} L_\D^\mathrm{hinge}(\w) + \sqrt{\frac{8 \rho^2 B^2}{m}}
,$$
where $L_\D^\mathit{hinge}(\w) = \E_{S \sim \D} L_S^\mathit{hinge}(\w)$,
and $L_\D^{0-1}(\w) = \E_{(\x, y) \sim \D} \left[ \begin{cases}0 & \sign(\langle \w, \x \rangle) = y \\ 1 & \text{otherwise} \end{cases} \right]$ is just the error rate of $\w$.
That is,
- The error rate of our SVM is no worse than its hinge loss performance: this is just because for any predictor, $L^{0-1} \le L^\mathit{hinge}$. If the prediction is the wrong sign so that 0-1 loss is 1, then the hinge loss is at least 1; if the prediction is the right sign so that 0-1 loss is 0, the hinge loss is between 0 and 1.
- The expected hinge loss performance of our SVM is not too much worse than the hinge loss for the best-possible SVM of norm at most $B$: the gap is at most $2 \rho B \sqrt{2 / m}$.
(There are similar results for high-probability bounds on the accuracy, and requiring the offset to be 0 is just a convenience; adding 1 to the kernel and centering the labels generally accounts for it, but there are presumably bounds out there explicitly incorporating the offset as well.)
Now, because it's a generic bound, its numerical value is probably quite loose on any particular problem. But even if we accept that it will be quite conservative: how do we know the best possible hinge loss for a given $B$, and then trade that off with the other term to find the best value of the overall bound?
The same kind of issues hold in power analysis for linear regression – what do we think the effect size might be? But it's often easier to reason about effect size than about the best hinge loss at a given norm. It might be easier to make a guess about accuracy, but unfortunately, I'm pretty sure no comparable bounds are available with the best-possible accuracy/0-1 loss on the right-hand side.
(Finding the best linear predictor w.r.t. 0-1 loss is NP-hard, while SVMs are in P, so if you find such a bound, please let me know!)
In practice, then, the method in machine learning is almost always "try it and see how well you do on a validation set." People develop a rough intuition – you can't train a 44,654,504-parameter ResNet-101 on 60,000-image MNIST, but you can on 1,200,000-image ImageNet. But we don't really theoretically understand why this is true; it's a very active current area of research.
