[TBD]Role of convexity in machine learning

Introduction

Laymen explanation

k-means, a popular clustering ML algorithm gives convex clusters. ML algorithm also uses convex function to ensure that it achieves global minima. If you are interested for knowing more application, then this document helps.

Technical explanation

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points, it contains the whole line segment that joins them.

A convex function is a real-valued function defined on an interval with the property that its epigraph (the set of points on or above the graph of the function) is a convex set.

Non-convex set

Role in machine learning

If a loss function is convex, then the ML algorithm is guaranteed to attain global minima. Refer here for more detail.

Method to test if a function is convex

Mathematical way

A function is convex iff its second derivative f′′(x) is non-negative. For functions with multiple variables, Hessian should be a positive semidefinite matrix.

Convex optimisation

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms,[1] whereas mathematical optimization is in general NP-hard.

The following are useful properties of convex optimization problems:[14][12]

• every local minimum is a global minimum;

• the optimal set is convex;

• if the objective function is strictly convex, then the problem has at most one optimal point.

Convex optimizations are "easier to solve", and we have a lot of reliably algorithm to solve.

Reference

https://en.wikipedia.org/wiki/Convex_set

https://sites.google.com/site/jbsakabffoi12449ujkn/home/machine-intelligence/role-of-k-means-in-machine-learning-1

https://en.wikipedia.org/wiki/Convex_optimization

https://stats.stackexchange.com/questions/324981/why-study-convex-optimization-for-theoretical-machine-learning

https://images.app.goo.gl/zh6EZ8wAvemRpZ6f6

https://www.cse.iitk.ac.in/users/rmittal/prev_course/s14/notes/lec8.pdf