There are some minor issues with your understanding, and I think it would help to clarify exactly what is being maximised, together with what is not being maximised.
Loss function.
I am going through Bishop's book and especially SVM. I am trying to understand the logic behind minimizing the specific loss $\frac{1}{2} \lVert \mathbf{w} \rVert^2$ with respect to $\mathbf{w}$.
The objective function you are minimising, $\frac{1}{2} \lVert \mathbf{w} \rVert^2$, is not a loss function, but is motivated by geometric considerations (i.e. maximum margin classification).
However, if you want to view this through the lens of minimising loss/error, then $\frac{1}{2} \lVert \mathbf{w} \rVert^2$ is a regularisation term. See equation (7.19), which states that you are minimising an error function $E_{\infty}(y(\mathbf{x}_n) t_n - 1)$, with the term $\frac{1}{2} \lVert \mathbf{w} \rVert^2$ acting as a quadratic regulariser. Where the error function $E_{\infty}(z)$ is $0$ if $z \geq 0$ and $\infty$ otherwise.
Maximum-margin classification.
On page 327, in 7.3 we want to maximize the distance from the margin for all the data samples $\mathbf{x}_n$. Actually, we want these samples that have the minimum distance to the margin (and the margin to be maximized).
There are some issues with this statement. You are choosing your classifier/estimating $\mathbf{w}$ by maximising the margin*. Where the margin is the perpendicular distance between the decision boundary and the closest point (for that particular parametrisation $\mathbf{w}, b$). Alternatively, you can think of the margin as the minimum perpendicular distance from the decision boundary over all $n$ training data points (for a particular parametrisation).
So maximum-margin classification can be viewed as maximising the minimal perpendicular distance between the decision hyperplane and all the data points. Noting that we maximise the margin with respect to $\mathbf{w}$ and that we choose the minimal distance over all $n$ data points, we have:
$$\underset{\mathbf{w}, b}{\text{argmax}} \underbrace{\left\{\underset{n}{\min} \frac{t_n \mathbf{w}^T\boldsymbol{\phi} (\mathbf{x}_n) + b}{\lVert \mathbf{w} \rVert} \right\}}_{\text{margin}} = \underset{\mathbf{w}, b}{\text{argmax}} \left \{ \frac{1}{\lVert \mathbf{w} \rVert } \left[\underset{n}{\min} t_n \mathbf{w}^T\boldsymbol{\phi} (\mathbf{x}_n) + b )\right] \right \}$$
Which yields equation (7.3).
Specification as a quadratic programming problem.
We want to "translate" the above problem into one that is more amenable to methods in convex optimisation, and all of the steps from equation (7.3) onwards are motivated by this.
Then, why 7.4 and 7.5 are true? What is the logic behind it?
As we are assuming linear separability in the hard-margin SVM, there will by definition exist at least one point that is closest to the decision boundary. To make things more explicit, call this closest point $\mathbf{x}_k$. This is the point which satisfies the minimisation inside the square parentheses above, for a particular value of $\mathbf{w}, b$. For this particular point, we choose a rescaling constant so as to make (7.4) true, that is, for point $\mathbf{x}_k$ only, we have:
$$t_k(\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_k) + b) = 1$$
As this point $\mathbf{x}_k$ is the closest to the decision boundary, carrying out the rescaling renders (7.5) true for all data points (in the training set):
$$t_n(\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n) + b) \geq 1 \quad \forall \space n$$
Now the above are specified as constraints. And we solve the following quadratic programming problem:
$$\underset{\mathbf{w}, b}{\text{argmin}} \space \frac{1}{2} \lVert \mathbf{w} \rVert^2 \quad \text{s.t.} \quad t_n(\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n) + b) \geq 1 \quad \forall \space n$$
Where the outer maximisation over $\mathbf{w}$ in (7.3) becomes minimisation as maximising $1 / \lVert \mathbf{w} \rVert$ is the same maximising $\lVert \mathbf{w} \rVert^2$, and a computational convenience factor of $1/2$ is introduced (it makes no difference to the optimisation).
Further queries from comments below.
For your first comment (loss function) is this what you are referring to stats.stackexchange.com/a/179027/41847?
Firstly, Bishop refers to loss and error interchangeably. And yes, that thread provides examples of common loss functions. However, I would be careful about automatically associating loss and error functions with one data point - in my view it is the responsibility of the author to clarify the context of how they are using the term loss function (e.g. over one data point, over the whole dataset, whether the loss function over the training set is a simple additive sum of per data point loss functions etc.).
Furthermore, I would remark that in many of the presentations of SVM I have seen, it is only Bishop who specifies that hard-margin SVM minimises an error function which takes the form $E_{\infty}(z) = 0$ if $z \geq 0$ and $\infty$ otherwise. Many other presentations, which I refer you to in the references, omit even mentioning whether hard-margin SVM minimises any kind of loss. You will find that it is much more common for these presentations to refer to minimisation of hinge-loss for the soft-margin SVM case.
Intuitively, a loss function $L(y, \hat{y}(\mathbf{x}))$ is just a way of encoding how we want to penalise deviations of a prediction $\hat{y}$ from its "true value" $y$ (i.e. that which is given to you in the training data). If you are statistician, you will be concerned with deviations of an estimator from the "true" parameter. We can choose specific functional forms for this loss function (e.g. squared-error/$L_2$ loss, hinge-loss, cross-entropy loss etc.) depending on how we want to codify these deviations, which is dependent on our problem.
Secondly, I do not really understand why we pick a value equal to 1 in 7.4 and consequently in 7.5. What exactly this 1 stand for? Is it just a value that we pick and due to re-scaling property we can assume that we can make it true?
Yes you are correct on both counts. Rescaling so as to make $t_k(\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_k) + b) = 1$ is in a certain sense fairly arbitrary - see Hastie et al. (2009). And yes, we can make it true in context of linear separability of the data, which we have assumed.
However, there is a certain logic to this arbitrariness which requires a more nuanced account than Bishop has given in getting to equations (7.4) and (7.5) - many presentations make a distinction between functional and geometric margins, see the elementary textbook by Deisenroth, Faisal (2019), which is very clear.
References for further reading.
I've found it extremely useful when I have studied ML to consult multiple reputable sources on the same topic to develop a holistic understanding - every author will choose to emphasise certain facets that are missed in other presentations. You would be surprised, unless you are a seasoned mathematician (which I am not), just how much even a small notational change in a different presentation can throw your understanding, if it is the case that your understanding is fragile. Here are some selected references to assist which are useful in the senses I have outlined above. The last is a more specialised text only covering SVMs, but will probably suffice at the level you are looking for (there are more advanced texts, or the original papers and monographs by the progenitors of this algorithm, Vladimir Vapnik, but are probably not useful unless you want to dig into some of the statistical learning theory/generalisation error bound/VC theory to rationalise the use of SVMs).
- Elements of Statistical Learning, Hastie et al. (2009).
- Mathematics for Machine Learning, Deisenroth and Faisal (2019).
- An Introduction to Support Vector Machines, Cristianini, Shawe-Taylor (2013).
