Before introducing quantum machine learning, I strongly suggest that understanding important algorithms like Grover search and quantum Fourier transformation might be critical subroutines for quantum machine learning algorithms. So, if you are not quite familiar with quantum computing, some of the quantum machine learning algorithms might be confusing.
This interesting thesis P. Shor has written is recommended. In this paper, Shor proposed three major directions that quantum computing might provide speedup. We can categorize the quantum machine learning into the direction that polynomial speedup for P problems.
There are branches of studies combining machine learning and quantum computing. They can be mainly divided into 2 parts: quantum computing implementation of machine learning algorithms(in this phase, some of the features may not be identical) and machine learning methods to facilitate quantum computing. What you are asking seems more likely the first parts, thus I'll focus on that while the 2nd part will be mentioned).
When implementing machine learning algorithms on a quantum computer, the classical computer is absolutely needed(to control the quantum operation, e. g., turn on or turn off a specific laser pulse, and maybe data processing, e. g., to analyze the statics of the measurement results).
Sometimes the quantum computer(or the quantum annealer) might only be a subroutine. For example, this Lockheed Martin research used quantum annealing to do the Gibbs sampling(they used their D-Wave quantum annealer to train a deep belief network, composed of 4 restricted Boltzmann machines, and the database is a coarse-grained MNIST), and compared with the conditional method, the contrastive divergence(CD), there is a significant improvement. Since after the Gibbs sampling(either quantum annealing or CD), fine-tuning the weight is still needed, so the quantum computing in this work is a subroutine.
Then I move on to works that quantum computing plays most of the job, supervised and unsupervised learning are both contained.
For supervised learning, first, let's talk about the neural network. The multi-layer and multi-node structure of the neural network enables it to deal with multiple hidden structures while the non-linear activation function makes the learning of the non-linear phenomenon possible. So this contradicts quantum mechanics tremendously since the quantum mechanics should be linear(there are also suggestions that the attenuation of light is non-linear and thus optical quantum computer might provide this ability, see the later cited paper). And in the meantime, the adjustment of the weights( the weights can be expressed as unitary operations) following the formula $\hat w_j(t+1)=\hat w_j(t)+\eta(|d\rangle-|y(y)\rangle)\langle x_j|$ isn't unitary-preserving since matrices composed of the addition of unitary matrices may not be unitary, see this paper as the reference. So I think using a quantum neural network to classify classical data, like MNIST, is impossible.
But on the contrary, there are also quantum data. Quantum data is something like unitary matrices that describe quantum states, and thus pairs of density matrices may depict an unknown quantum operation $|\psi\rangle\langle\psi|=U|\phi\rangle\langle\phi|U^\dagger$. A quantum neural network is sufficient to learn the unknown operation, and but it is inefficient(no faster than an already inefficient quantum process tomography).
For both supervised and unsupervised learning, this paper gives some analysis. The paper introduced algorithms for quantum k-NN and quantum support vector machine and the main speedup is to accelerate the calculation of classical distances. In the meantime, this paper gives a handful of algorithms that teaches you how to use Grover search to faster the unsupervised algorithms.
There is also the quantum mechanical implementation of decision tree algorithms(see this paper). The method may be peculiar for beginners, it is the quantum random walk(although it is the quantum generalization of random walk, I still think these two are not alike).
Finally, machine learning facilitated quantum computing. First, there is a recent study that utilizes a machine learning algorithm(I haven't seen the paper so I do not know which algorithm they used) to achieve a Toffoli gate with higher fidelity. This work is called CRAB, it accepts multiple methods to optimize the quantum control of real quantum experiments, the gradient descent(BFGS, BGD) is included.
The above is all I know, and I hope this might be helpful.