Abstract
Gradient Langevin dynamics and a variety of its variants have attracted increasing attention owing to their convergence towards the global optimal solution, initially in the unconstrained convex framework while recently even in convex constrained non-convex problems. In the present work, we extend those frameworks to non-convex problems on a non-convex feasible region with a global optimization algorithm built upon reflected gradient Langevin dynamics and derive its convergence rates. By effectively making use of its reflection at the boundary in combination with the probabilistic representation for the Poisson equation with the Neumann boundary condition, we present promising convergence rates, particularly faster than the existing one for convex constrained non-convex problems.
Introduction
Optimization is fundamental to machine learning, yet navigating non-convex landscapes remains a significant challenge. Standard algorithms often become trapped in local minima—valleys that appear optimal but are not the global lowest point. Gradient Langevin Dynamics (GLD) addresses this by introducing stochastic noise, providing the "energy" necessary to escape local pits and find the global minimum.
However, the introduction of constraints—restricting solutions to a specific region $K$—adds substantial complexity, especially when $K$ is non-convex (e.g., a spherical shell). Traditional "Projected" GLD (PGLD) methods, which push points back into the feasible region, often suffer from suboptimal convergence rates and theoretical gaps. This paper introduces Reflected Gradient Langevin Dynamics (RGLD) to bridge this gap, offering a robust framework for global optimization in non-convex constrained environments.
Reflected Gradient Langevin Dynamics (RGLD)
The RGLD algorithm introduces two key innovations to handle non-convex constraints effectively:
- Reflection over Projection: Instead of projecting an out-of-bounds point to the nearest edge, RGLD reflects it back into the interior. If $X'$ is outside the boundary and $P_K(X')$ is its projection, the new point is defined as $2P_K(X') - X'$. This reflection preserves a mathematical symmetry that projection destroys, allowing for better error cancellation in theoretical proofs.
- Rademacher Noise: The authors replace standard Gaussian noise with bounded Rademacher noise (random variables taking values $\pm 1$). This choice prevents extreme jumps far outside the feasible region, ensuring the reflection operation remains well-defined and stable near non-convex boundaries.
To derive convergence rates, the authors utilized the Poisson equation with Neumann boundary conditions. This approach allows for a precise representation of discretization error, effectively canceling out second-order terms and leading to sharper convergence bounds.
Theoretical Convergence Rates
A primary contribution of this work is the derivation of a significantly improved convergence rate. The authors establish a rate of $\tilde{O}(d^3 \lambda_*^{-3} \epsilon^{-3})$, where $d$ is the dimension and $\epsilon$ is the error tolerance. This represents a major advancement over previous state-of-the-art methods for constrained non-convex problems, which typically achieved rates around $\tilde{O}(d^4 \lambda_*^{-1} \epsilon^{-4})$.
Empirical Performance
The algorithm was evaluated on challenging synthetic benchmarks, including a 2D Gaussian Mixture with 25 local minima constrained within a spherical shell, and low-rank matrix factorization problems.
In numerical experiments, standard Projected Gradient (PG) descent frequently failed by getting trapped in local minima. In contrast, RGLD successfully explored the non-convex domain and consistently identified the global minimum. Furthermore, in matrix factorization tasks across dimensions $d=100$ to $d=1000$, RGLD reached lower objective values more rapidly than traditional projected approaches.
Conclusion and Future Work
RGLD narrows the efficiency gap between constrained and unconstrained non-convex optimization. While the current theory requires high boundary smoothness ($C^5$), future work aims to extend these results to regions with sharp corners, such as boxes or simplices. Additionally, extending the analysis to stochastic gradients (SGLD) would further enhance its applicability to large-scale deep learning problems. The behavior of the spectral gap ($\lambda_*$) in high-dimensional non-convex regions also remains a fertile ground for future probabilistic research.
Summary updated