Leveraging Non-uniformity in First-order Non-convex Optimization

Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvári, Dale Schuurmans

Abstract: Classical global convergence results for first-order methods rely on uniform smoothness and the Łojasiewicz inequality. Motivated by properties of objective functions that arise in machine learning, we propose a non-uniform refinement of these notions, leading to Non-uniform Smoothness (NS) and Non-uniform Łojasiewicz inequality (NŁ). The new definitions inspire new geometry-aware first-order methods that are able to converge to global optimality faster than the classical $\Omega(1/t^2)$ lower bounds. To illustrate the power of these geometry-aware methods and their corresponding non-uniform analysis, we consider two important problems in machine learning: policy gradient optimization in reinforcement learning (PG), and generalized linear model training in supervised learning (GLM). For PG, we find that normalizing the gradient ascent method can accelerate convergence to $O(e^{-t})$ while incurring less overhead than existing algorithms. For GLM, we show that geometry-aware normalized gradient descent can also achieve a linear convergence rate, which significantly improves the best known results. We additionally show that the proposed geometry-aware descent methods escape landscape plateaus faster than standard gradient descent. Experimental results are used to illustrate and complement the theoretical findings.

Introduction

In classical optimization theory, convergence guarantees often rely on two restrictive assumptions: Uniform Smoothness, where the landscape's curvature is bounded by a single global constant ($\beta$), and the Uniform Łojasiewicz Inequality, where the gradient remains sufficiently large relative to the distance to the optimum. However, real-world machine learning landscapes—particularly in reinforcement learning and deep learning—frequently exhibit non-uniformity, characterized by flat plateaus and sharp valleys where these global constants fail to capture local geometry accurately.

Standard theory often produces pessimistic convergence bounds (like $\Omega(1/t^2)$) because it must account for the worst-case curvature across the entire landscape. This paper bridges the gap between theory and practice by introducing a framework that adapts to the local geometry of the objective function.

Theoretical Framework: NS and NŁ

The authors propose a refined analysis based on two new definitions:

  • Non-uniform Smoothness (NS): Instead of a fixed constant $\beta$, the smoothness $\beta(\theta)$ is a function of the current parameters, allowing the theory to adapt to local curvature.
  • Non-uniform Łojasiewicz (NŁ) Inequality: Similarly, the gradient dominance coefficient $C(\theta)$ is allowed to vary locally.
Venn diagram illustrating the relationship between non-uniform properties (NS, NŁ) and classical convexity.

As shown in the figure above, these properties encompass a wide range of functions, including those that are non-convex. By leveraging these local properties, the authors develop Geometry-aware Normalized Gradient Descent (GNGD). Unlike standard Gradient Descent (GD), which uses a fixed or decaying step size, GNGD adapts its step size to $1/\beta(\theta)$.

Key Insights and Results

By accounting for local non-uniformity, the authors prove that algorithms can achieve linear convergence ($O(e^{-ct})$), shattering the sub-linear limits ($O(1/t)$ or $O(1/\sqrt{t})$) previously thought to be the limit for these non-convex problems.

Reinforcement Learning and GLMs

The framework was applied to two critical domains:

  1. Policy Gradient (PG) in RL: The value function naturally satisfies NS and NŁ properties. The authors improved the convergence rate from $O(1/t)$ to a global linear rate $O(e^{-ct})$.
  2. Generalized Linear Models (GLMs): The Mean Squared Error (MSE) for GLMs, while non-convex, fits the non-uniform regime. GNGD improves the best-known results from $O(1/\sqrt{t})$ to a linear rate.
MSE landscape in GLM and the corresponding sub-optimality comparison between GD and GNGD.

As illustrated in the GLM landscape, standard GD often gets stuck on plateaus where uniform constants become extreme. Normalization allows GNGD to "jump" through these flat regions significantly faster, as evidenced by the sharp drop in sub-optimality compared to the stagnant performance of GD.

Conclusion

This work provides a rigorous mathematical foundation for popular machine learning heuristics like gradient clipping and normalization. By moving beyond uniform assumptions, the authors demonstrate that geometry-aware methods can escape plateaus and achieve superior convergence rates. Future work includes extending this analysis to stochastic settings (SGD) and complex, over-parameterized deep neural networks.

Summary updated

Abstract

Classical global convergence results for first-order methods rely on uniform smoothness and the \L{}ojasiewicz inequality. Motivated by properties of objective functions that arise in machine learning, we propose a non-uniform refinement of these notions, leading to \emph{Non-uniform Smoothness} (NS) and \emph{Non-uniform \L{}ojasiewicz inequality} (N\L{}). The new definitions inspire new geometry-aware first-order methods that are able to converge to global optimality faster than the classical $\Omega(1/t^2)$ lower bounds. To illustrate the power of these geometry-aware methods and their corresponding non-uniform analysis, we consider two important problems in machine learning: policy gradient optimization in reinforcement learning (PG), and generalized linear model training in supervised learning (GLM). For PG, we find that normalizing the gradient ascent method can accelerate convergence to $O(e^{-t})$ while incurring less overhead than existing algorithms. For GLM, we show that geometry-aware normalized gradient descent can also achieve a linear convergence rate, which significantly improves the best known results. We additionally show that the proposed geometry-aware descent methods escape landscape plateaus faster than standard gradient descent. Experimental results are used to illustrate and complement the theoretical findings.
BibTeX
@inproceedings{mei2021leveraging,
  author = {Jincheng Mei and Yue Gao and Bo Dai and Csaba Szepesvári and Dale Schuurmans},
  title = {{Leveraging Non-uniformity in First-order Non-convex Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=r9LZ12Q59xq},
}
Figure