What is the definiton of a learning algorithm? I struggle to understand what is a learning algorithm. For example, lets say that $y$ is a function of $x$ but we don't know $f(x)$.
A learning algorithm is an approach to estimate $f$. That is, given some training data $\mathcal{D}$, the algorithm returns an estimate of $f$, $\hat{f} = \mathcal{A}(\mathcal{D})$.
In order to return $\hat{f}$, the algorithm must minimize some loss function $\mathcal{L}$. The set of all functions that the learning algorithm can return is the hypothesis space $\mathcal{H}$ and we can view training as the following optimization problem:
$$ \hat{f} = \underset{h \in \mathcal{H}}{\arg \min\,} L $$
In the case of linear regression algorithm, $\mathcal{H}$ contains all the possible lines. In the case of decision tree algorithm, $\mathcal{H}$ contains all the possible partitions.
What I don't get is that (in case of linear regression) it is the gradient descent algorithm which solves the optimization problem (same for neural networks). Similarly, in case of decision trees is the top-down greedy approach that finds the best partition.
Why gradient descent is not considered a learning algorithm while neural networks are?

Gradient descent is an optimization algorithm. It finds a minimum of a function. It doesn't need any data, the function can be a mathematical function like $f(x) = x^2$. So, gradient descent does not "learn" anything from the data. A neural network is an algorithm that includes an optimization element (e.g. gradient descent), the loss function, and other elements that together enable it to learn from the data.
