Global Minimum and Local Minima
How Gradient Descent Gets Lost in Local Minima — The Challenge of Non-Convex Optimization
Optimization · Gradient DescentCore Formulas
In Machine Learning, training a model is usually equivalent to minimizing a loss function. When the loss function is non-convex, gradient descent may converge to a local minimum rather than the global minimum. This demo uses a specific non-convex function \( f(x) \) to illustrate this phenomenon.
Example function: $$f(x) = \frac{1}{4}x^4 - \frac{2}{3}x^3 - \frac{1}{2}x^2 + 2x$$
Derivative: $$f'(x) = x^3 - 2x^2 - x + 2 = (x-1)(x+1)(x-2)$$
Gradient descent update: $$x_{t+1} = x_t - \alpha \cdot f'(x_t)$$
Second-order condition: $$f''(x) = 3x^2 - 4x - 1, \quad \text{if } f''(x^*) > 0 \text{ then } x^* \text{ is a local minimum}$$
Extremum points: $$\text{Local minima: } x = -1 \ (\text{global minimum}), \quad x = 2 \ (\text{local minimum}); \quad \text{Local maximum: } x = 1$$
Parameters
Interactive Simulation
Set the initial point x₀ and the learning rate α, and click "Run Gradient Descent" to observe the iteration path. Different initial points may converge to different local minima—this is precisely the core challenge of non-convex optimization.
Parameter Controls
Function Curve and Gradient Descent Path
Standard Introduction
In Machine Learning, training a model is usually transformed into an optimization problem: finding a set of parameters that minimizes the loss function. When the loss function is convex, any local minimum is also the global minimum, and algorithms such as gradient descent can be guaranteed to converge to the global optimum. However, the loss functions of many modern deep learning models are non-convex, containing multiple local minima, saddle points, and even flat regions. This means the optimization algorithm may get trapped in a local minimum and fail to find the global minimum.
The global minimum is the point of minimum value of the loss function over the entire parameter space and is the ideal goal of optimization. A local minimum is a point of minimum value within some neighborhood, but a lower function value may exist over a larger range. In deep learning, due to the non-convexity and high dimensionality of the loss function, finding the global minimum is usually infeasible. However, in practice it has been found that many local minima correspond to sufficiently low loss values, and the model can still achieve good generalization performance. Therefore, studying the properties of local minima and how to avoid bad local minima is an important topic in the field of optimization.
Plain-Language Introduction
Imagine you are in a rolling mountainous area, blindfolded, wanting to walk to the lowest valley. You can only judge the direction from the slope under your feet: if you feel you are going downhill, take a step down; if you feel you are going uphill, change direction. This is gradient descent.
If you stand on a hillside and keep walking down along the slope, you will eventually reach a valley. But the problem is, this valley may just be a small pit rather than the lowest point of the entire mountain range. You are trapped in a "local minimum." To find the true lowest point (the "global minimum"), you may need to start from different positions, or have some way to jump out of the small pit.
In Machine Learning, model training is like searching for the lowest point in a mountainous area. The loss function is the terrain, and the parameters are your position. Gradient descent may only find a local minimum, but fortunately, in deep learning, many local minima are actually good enough. This is also one of the reasons why neural networks can be trained successfully.
What Problem Does It Solve
The concepts of global minimum and local minima help us understand the limitations and challenges of optimization algorithms. They explain why, in some problems, algorithms such as gradient descent may fail to converge to the optimal solution. By identifying the terrain features of the loss function, researchers can design better initialization methods, optimization algorithms, and network structures.
Specifically, this problem has driven the development of the following techniques:
1. Better initialization: such as Xavier and He initialization, which make the initial point more likely to lie in a good region of the loss function, reducing the probability of falling into a bad local minimum.
2. Improved optimization algorithms: such as momentum methods and Adam, which help the algorithm escape shallow local minima or saddle points.
3. Regularization and batch normalization: which change the terrain of the loss function, making it smoother and reducing the number of undesirable local minima.
4. Stochastic gradient descent: the noise introduced by using a mini-batch of data each time gives the algorithm a certain probability of escaping a local minimum.
Why It Matters
Understanding the global minimum and local minima is crucial for training reliable Machine Learning models. Although in deep learning local minima are not always harmful, some local minima may cause a significant drop in model performance. For example, in transfer learning or small-sample scenarios, a bad local minimum may lead to catastrophic forgetting or overfitting.
In addition, in traditional Machine Learning models (such as logistic regression and support vector machines), the loss function is usually convex, so the global minimum and local minima coincide. But with the development of deep learning, non-convex optimization has become the norm, and researchers must understand the impact of local minima and develop corresponding coping strategies.
From a theoretical perspective, non-convex optimization is a frontier problem in the current field of optimization. Although it has been shown that under certain conditions (such as over-parameterized neural networks) gradient descent can converge to the global minimum, in general, global convergence remains an open problem. Therefore, understanding the properties of local minima is of great significance for advancing optimization theory.
Application Scenarios
Deep learning training Reinforcement learning Generative models Hyperparameter optimization Traditional Machine Learning
The concepts of global minimum and local minima are especially prominent in the following scenarios:
Deep learning training: almost all deep neural networks are non-convex, and the training process is essentially about finding a good local minimum.
Reinforcement learning: the reward function in policy optimization is usually highly non-convex, and it is easy to get stuck in a locally optimal policy.
Generative models: during the training of models such as GANs, the loss function terrain of the generator and discriminator is complex, with multiple local minima.
Hyperparameter optimization: when searching for the best hyperparameters, the objective function is often non-convex and requires global optimization algorithms (such as Bayesian optimization) to avoid local minima.
Traditional Machine Learning: although many classic models are convex, some (such as matrix factorization) are also non-convex.
Limitations and Drawbacks
1. Difficulty guaranteeing finding the global minimum: for general non-convex functions, gradient descent cannot guarantee convergence to the global minimum.
The convergence point of the algorithm depends on factors such as the initial position and the learning rate.
2. Local minima may have poor performance: although many local minima perform well in deep learning,
some local minima may cause a significant drop in model performance, especially when data is insufficient or the model is inappropriate.
3. Increased optimization difficulty: non-convex optimization problems are usually harder to solve than convex optimization problems, requiring more tuning and computational resources.
4. Lack of theoretical guarantees: for most non-convex optimization problems, we lack rigorous theoretical guarantees regarding convergence speed and the quality of the final solution.
5. Possible overfitting: even if the global minimum is found, it may overfit the training data, leading to poor generalization performance.
Therefore, in deep learning, a local minimum sometimes has better generalization ability than the global minimum.
Despite these challenges, gradient descent and its variants remain the most effective methods for training neural networks. Through reasonable initialization and optimization strategies, we can obtain sufficiently good solutions.