I am learning about machine learning and one of the things that still not clear in my mind is how classification is done via optimization? In the couple of papers I read I just don't get how authors manage to model their problems, how does minimizing a function lead to clustering or classification, how do they know they are dealing with the right function?
Solved – What’s the link between optimization and classification
classificationmachine learningoptimization
Related Solutions
Your understanding is correct.
BO inherently measures the uncertainty of regions of your search space. And the acquisition function governs the tradeoff between exploring a point in a region with high uncertainty versus exploring further in a region with lower uncertainty, but a higher value.
By contrast, vanilla regression models assume equal variance - while you can locate the maximum of a polynomial model within some box, the search will be excessively local and not have a great exploration-exploitation tradeoff.
But this just repeats what you already know.
Typical mean functions in BO (and GPs generally) are either 0 or another constant, with all of the heavy-lifting is done by the kernel function. This is mostly a computational trick, because in this case predictions are easily made via linear algebra; otherwise, you have to resort to simulation.
The Jones 1998 paper compares GP and polynomial regression on page 464. This is not strictly the same model that you propose (choosing polynomial terms by CV), but it's consistent with your aims.
You are looking at top level algorithm flow charts. Some of the individual steps in the flow chart may merit their own detailed flow charts. However, in published papers having an emphasis on brevity, many details are often omitted. Details for standard inner optimization problems, which are considered to be "old hat" may not be provided at all.
The general idea is that optimization algorithms may require the solution of a series of generally easier optimization problems. It's not uncommon to have 3 or even 4 levels of optimization algorithms within a top level algorithm, although some of them are internal to standard optimizers.
Even deciding when to terminate an algorithm (at one of the hierarchial levels) may require solving a side optimization problem. For instance, a non-negatively constrained linear least squares problem might be solved to determine the Lagrange multipliers used to evaluate the KKT optimality score used to decide when to declare optimality.
If the optimization problem is stochastic or dynamic, there may be yet additional hierarchial levels of optimization.
Here's an example. Sequential Quadratic Programming (SQP). An initial optimization problem is treated by iteratively solving the Karush-Kuhn-Tucker optimality conditions, starting from an initial point with an objective which is a quadratic approximation of the Lagrangian of the problem, and a linearization of the constraints. The resulting Quadratic Program (QP) is solved. The QP which was solved either has trust region constraints, or a line search is conducted from the current iterate to the solution of the QP, which is itself an optimization problem, in order to find the next iterate. If a Quasi-Newton method is being used, an optimization problem has to be solved to determine the Quasi-Newton update to the Hessian of the Lagrangian - usually this is a closed form optimization using closed form formulas such as BFGS or SR1, but it could be a numerical optimization. Then the new QP is solved, etc. If the QP is ever infeasible, including to start, an optimization problem is solved to find a feasible point. Meanwhile, there may be one or two levels of internal optimization problems being called inside the QP solver. At the end of each iteration, a non-negative linear least squares problem might be solved to determine the optimality score. Etc.
If this is a mixed integer problem, then this whole shebang might be performed at each branching node, as part of a higher level algorithm. Similarly for a global optimizer - a local optimization problem is used to produce an upper bound on the globally optimal solution, then a relaxation of some constraints is done to produce a lower bound optimization problem. Thousands or even millions of "easy" optimization problems from branch and bound might be solved in order to solve one mixed integer or global optimization problem.
This should start to give you an idea.
Edit: In response to the chicken and egg question which was added to the question after my answer: If there's a chicken and egg problem, then it's not a well-defined practical algorithm. In the examples I gave, there is no chicken and egg. Higher level algorithm steps invoke optimization solvers, which are either defined or already exist. SQP iteratively invokes a QP solver to solve sub-problems, but the QP solver solves an easier problem, QP, than the original problem. If there is an even higher level global optimization algorithm, it may invoke an SQP solver to solve local nonlinear optimization subproblems, and the SQP solver in turn calls a QP solver to solve QP subproblems. No chiicken and egg.
Note: Optimization opportunities are "everywhere". Optimization experts, such as those developing optimization algorithms, are more likely to see these optimization opportunities, and view them as such, than the average Joe or Jane. And being algorithmically inclined, quite naturally they see opportunities for building up optimization algorithms out of lower-level optimization algorithms. Formulation and solution of optimization problems serve as building blocks for other (higher level) optimization algorithms.
Edit 2: In response to bounty request which was just added by the OP. The paper describing the SQP nonlinear optimizer SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf specifically mentions the QP solver SQOPT, which is separately documented, as being used to solve QP subproblems in SNOPT.
Best Answer
Optimization in classification tasks
I would suggest to start to check the 0-1 loss, which is the goal of the classification task. In other words, the objective of the classifier is trying to classify objects "correctly" / minimizing the wrong classifications or 0-1 loss.
In real world problems 0-1 loss is hard to optimize directly, therefore there are other loss functions to "approximate" 0-1 loss. (A related discussion can be found here: What are the impacts of choosing different loss functions in classification to approximate 0-1 loss) Logistic loss is one of them. And the classifier based on logistic loss is logistic regression.
Optimization in clustering tasks
The goal of clustering is putting objects into groups/clusters. But what grouping strategy is good? This is the essential question answered by the optimization formulation.
In generally, we want objects in one group are "similar" to each other and between groups are "different". The optimization objective is trying to "maximize" the similarity within groups and "maximize" the difference between groups.