Must all supervised algorithms have (complexity) parameters? I have noticed that all commonly used supervised algorithms (decision tree, logistic regression, random forest, etc.) have some (hyper)parameters to tune (otherwise the model may underfit or overfit the data).
Does it mean that all supervised algorithms must have this kind of "complexity" parameter? Or, are there any algorithms that don't have any such parameter and may adapt to any data automatically?
 A: I believe these questions come from a slight misunderstanding.
First: hyper-parameters.
This depends entirely on how you look at the model and at what point you are willing to call some procedure by a different name. There are many classification techniques that have no parameters. Few examples: Linear Discriminant Analysis, Euclidean Distance classifier. However these models still have assumptions, you just cannot change them. Assumption of LDA is that the classes are normally distributed. Assumption of Euclidean distance classifier is no covariance between the features.
Second: Adapting to the data automatically.
Well there is no such thing as adapting to data automatically. Unless maybe a weird procedure where you are only willing to classify samples that are present in the training data and refuse to make a decision for any unseen sample.
So consider this weird classifier: you have two samples in your training set. They can be thought of as two points in space - and you have class labels for them. If you were to only make decision for these two points and refuse to classify any new points in between the two or slightly off one of them - that would be a method "adapting to the data" in some sense.
However when it comes the time to make decisions for points in-between the known data - to extrapolate - then the problems begin. You can never be 100% sure that you are making the correct decision for a point that you have never seen before in your training set. And here different models make different assumptions.
For example: almost all of them make an assumption that points near each other have to be of the same class. But this is not necessarily the case in general. So you have to select a model based on some knowledge about the data with your assumptions plugged-in. You can not have a model that "adapts to the data without any assumptions" as that would include the model that would consider all kinds of weird possibilities - even "white-noise-pattern" partitioning of the space into classes.
Also the more assumptions you make the more robust your model will be against overfitting but that is another subject matter.

In short:


*

*Hyper parameters - depends on where you draw the line between different model names.

*Adapting to the data - models always have assumptions and only adapt to the data within their confined hypothesis space.

A: First of all, "There is no silver bullet". And, I think, one can easily design a simple supervised algorithm without any hyper-parameters. Or, an off the shelf algorithm, Ordinary Least Squares (no regularization, i.e. not Ridge, Lasso or ElasticNet etc. or a cost function choice, polynomial features (which actually changes the model) etc.) doesn't have any hyper-parameters. However, is it really good to have an algorithm without giving you much choice? These hyper-parameters are present because they were needed (e.g. let's add some regularization term to OLS).
Hyper-parameters, in general, add more power to the algorithm, enabling us to tweak it to conform our data. This power comes with a price of course, i.e. the effort we spend to tune it. Popular and successful ML algorithms have many hyper-parameters for example, e.g. XGBoost, Neural Nets in general.
Real data, in general, is much more complex than data simulated from simpler mathematical models; and this requires further effort for the choice of the algorithm and hyper-parameters. I personally witnessed the comparison of simulated human DNA vs. real DNA, in which the simulated data almost never possess novelty. This makes the hyper-parameter tuning problem even harder, i.e. an algorithm adapting to the data and making choices accordingly.
There are tools that try to make your life easier, by trying possible algorithms, hyper-parameters etc. given your data, e.g. AutoML, H2O. But, this could evolve into another discussion I guess.
A: The best adaptation to the actual data used to fit the model comes with just the data term without any regularization. Regularization term favours certain solutions like lower l2 norm. Adding this constraint comes at the expense of higher error in fitting the data. But this "biased" model (eg, towards lower l2-norm solutions) often have less variance. That is, we will obtain a roughly similar model if we take another random sample of the data. Solutions of models not biased by regularization depend a lot on the particular data used to fit them. That is known as overfitting and as consequence one model fitted using one subset of the data will not hold well in another subset. That is, has a high variability. That is particularly the case as dimensionality increases. With eg, 1000 samples in 2 dimensions you may not experience the variance problem and non-regularized models fitted in one subset may hold in other subsets (ie, without recomputing the model) with comparable error to the first. But as soon as you increase dimensions, the high variance problem (ie, overfitting) appears and you need regularization to reduce this variance, at the cost of adding bias (ie, worse fitting to the actual subset used to compute the model). 
