Are there any power calculation formulas for ML methods beyond Logistic Regression? Are there any power calculation formulas for ML methods (for binary classification) beyond Logistic Regression? (also well beyond the laughable rule of thumb 10 instances per variable)
I've done a naive google search and can't find anything.
I'd expect there to be a different calculation for but maybe there is a  kind of general analysis based simply on number of features.
Maybe linear SVMs, no kernel, have a comparable power calc formula?
I'm interested in anything, Decision Trees, k-Nearest Neighbors, Naive Bayes, etc.
As complex as Deep Neural Networks seem to be, with the multiplicity of parameters they have, maybe they can be analyzed as a network of stacked Linear Regression?
 A: 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.
A: Power analysis refers to calculating power of a hypothesis test

The power of a binary hypothesis test is the probability that the test
rejects the null hypothesis ( $H_{0}$) when a specific alternative
hypothesis ( $H_{1}$ ) is true

In machine learning you make no hypothesis, are not interested in testing them, and don't have any hypothesis tests available. Since there's no hypothesis tests, there is no power analysis. You can make power analysis for the hypothesis tests related to logistic regression, because logistic regression is a statistical model that is also used in machine learning as a classifier. That is not the case for other machine learning models. Moreover, even if you were using logistic regression for making predictions, rather then inference, you would not do any power analysis. Finally, power analysis for logistic regression would not tell you how accurate the predictions would be.
This is also not really a case in machine learning. In machine learning we do not care about "minimal sample size", as machine learning models are are usually used with large datasets. For small dataset, you would usually use simple algorithms like logistic regression, because with more complicated ones you risk overfitting.
As about being "confident in the classification your ML model creates", this is judged by using things like cross validation. What machine learning models do, is they learn to recognize patterns in the data and make predictions given the familiar patterns. Whatever data you give them, they will always find some patterns and make some predictions. If the data is garbage, they will give you garbage predictions.
You may also want to read the The Two Cultures: statistics vs. machine learning? thread to learning about differences between statistics and machine learning.
