What is the difference between loss function and MLE? I am trying to learn Machine Learning and I am not exactly sure what these terms entail. I know the likelihood is a function in terms of the parameters to be learned and we want to maximize it, but I also know we fit a model using a loss function...
Can someone give examples of each under different modes (e.g. what is the MLE in a Discrete Naive Bayes or in Logistic Regression), also how they are related to the loss functions?
 A: Loss
In machine learning applications, such as neural networks, the loss function is used to assess the goodness of fit of a model. For instance, consider a simple neural net with one neuron and linear (identity) activation that has one input $x$ and one output $y$:
$$y=b+wx$$
We train this NN on the sample dataset: $(x_i,y_i)$ with $i=1,\dots,n$ observations. The training is trying different values of parameters $b,w$ and checking how good is the fit using the loss function. Suppose, that we want to use the quadratic cost:
$$C(e)=e^2$$
Then we have the following loss:
$$Loss(b,w|x,y)=\frac 1 n \sum_{i=1}^n C(y_i-b-wx_i)$$
Learning means minimizing this loss:
$$\min_{b,w} Loss(b,w|x,y)$$
MLE connection
You can pick the loss function which ever way you want, or fits your problem. However, sometimes the loss function choice follows the MLE approach to your problem. For instance, the quadratic cost and the above loss function are natural choices if you deal with Gaussian linear regression. Here's how.
Suppose that somehow you know that the true model is $$y=b+wx+\varepsilon$$ with $\varepsilon\sim\mathcal N(0,\sigma^2)$ - random Gaussian error with a constant variance. If this is truly the case then it happens so that the MLE of the parameters $b,w$ is the same as the optimal solution using the above NN with quadratic cost (loss).
Note, that in NN you're not obliged to always pick cost (loss) function that matches some kind of MLE approach. Also, although I described this approach using the neural networks, it applies to other statistical learning techniques in machine learning and beyond.
A: *

*In machine leanring, many people do not talk about assumptions (for example residual to be Gaussian) too much. And many people view the problem is a deterministic problem, where (large amount of) data is given, and we want to minimize the loss.

*In classical statistics literature, usually the data is not too many, and people talk about the probabilistic interpretation of the model, where there are many probabilistic assumptions (such as residual to be Gaussian). With probabilistic assumptions, the likelihood can be calculated and the loss function can be negative likelihood instead of (or as a proxy of) minimizing mis classification rate.

*It is also interesting to think about generative model vs discriminative model perspective. Maximize likelihood is usually coming from generative model, and minimize loss is usually coming from discriminative model.
A: A loss function is a measurement of model misfit as a function of the model parameters. Loss functions are more general than solely MLE.
MLE is a specific type of probability model estimation, where the loss function is the (log) likelihood. To paraphrase Matthew Drury's comment, MLE is one way to justify loss functions for probability models.
A: 
Can someone give examples of each under different modes (e.g. what is
  the MLE in a Discrete Naive Bayes or in Logistic Regression), also how
  they are related to the loss functions?

When we deal with machine learning algorithms we are:
1) specifying a probabilistic model that has parameters. For example the parameters in logistic regression and naive bayes in this answer.
2) learning the value of those parameters from data(sometimes maybe from some experts). Normally there are two methods: Maximum Likelihood Estimation(MLE) and Maximum A Prosteriori(MAP). And the key point of MLE is that after training the learned parameters can make the observed data the most likely: $\theta_{ML}=\arg \max E_{x\sim \hat p_{data}}\log p_{model}(x; \theta)$. Source: Deep Learning Book 5.5. For an example you can see the 4.2 of this tutorial.         
To get the parameters that can make the observed data most likely we need to get the likelihood function and to optimize the value of it by tuning the parameters. $L(\theta)=\prod_{i=1}^n f(X_i|\theta)$. 
Other references: Stanford CS109 Parameter Estimation
