Abstract
We develop a framework for convexifying a fairly general class of optimization problems. Under additional assumptions, we analyze the suboptimality of the solution to the convexified problem relative to the original nonconvex problem and prove additive approximation guarantees. We then develop algorithms based on stochastic gradient methods to solve the resulting optimization problems and show bounds on convergence rates. We extend this framework to apply to a general class of discrete-time dynamical systems. In this context, our convexification approach falls under the well-studied paradigm of risk-sensitive Markov Decision Processes. We derive the first known model-based and model-free policy gradient optimization algorithms with guaranteed convergence to the optimal solution. Finally, we present numerical results validating our formulation in different applications.
Introduction
In the world of optimization, the fundamental divide is not between linear and nonlinear problems, but between convex and non-convex ones. Convex problems are computationally tractable because any local minimum is a global minimum. Non-convex problems, however, are often NP-hard, riddled with local traps, and highly sensitive to initialization. While "smoothing" (adding noise to an objective) is a common heuristic to simplify rugged landscapes, it rarely guarantees that the resulting problem is actually convex. This paper introduces a "Universal Convexification" framework that systematically transforms a broad class of non-convex problems into guaranteed convex ones by adopting a risk-averse perspective.
The Universal Convexification Framework
The proposed framework addresses objective functions $g(\theta)$ composed of a potentially non-convex component $f(\theta)$ and a quadratic regularizer $\frac{1}{2}\theta^T R \theta$. The transformation involves two key steps:
- Gaussian Perturbation: Instead of evaluating $f$ at a single point, the method considers the expected value of $f$ under Gaussian noise $\omega \sim \mathcal{N}(0, \Sigma)$.
- Risk-Aversion Transformation: An exponential transformation is applied to the cost, resulting in a new objective: $$f_\alpha(\theta) = \frac{1}{\alpha} \log \mathbb{E} [\exp(\alpha f(\theta + \omega))]$$ where $\alpha$ is the "risk factor."
The Breakthrough: The authors prove that if the risk factor is chosen such that $\alpha R \succeq \Sigma^{-1}$, the entire optimization problem becomes convex, regardless of the original function's shape. This "magic condition" ensures that global optimality is reachable via standard stochastic gradient methods.
As illustrated in Figure 1, the convexified version doesn't just find any minimum; it specifically targets robust minima. Narrow, deep "holes" in the cost landscape are ignored because they are sensitive to noise, while the algorithm prefers "wide" minima where the cost remains low even under slight parameter perturbations.
Experimental Validation
The framework was validated on several benchmarks, including the UCI Breast Cancer dataset and MNIST subsets.
Robust Classification
In binary classification tests, the convexified approach significantly outperformed standard Support Vector Machines (LibSVM) as the noise level in the data increased. This demonstrates superior robustness, as the method effectively ignores non-robust local features that degrade standard models.
Neural Network Training
On small-scale neural network tasks, standard backpropagation frequently became trapped in poor local minima, achieving only ~20% accuracy. In contrast, the convexified approach consistently found better solutions, reaching ~80% accuracy by navigating the smoothed, convexified landscape.
Discussion and Future Work
This framework provides a formal bridge between static optimization and control theory, allowing for the derivation of the first policy gradient algorithms for certain dynamical systems with guaranteed global convergence.
However, limitations remain. The use of an exponentiated objective function can lead to high variance in gradient estimates, which may slow down convergence. Furthermore, the method's inherent preference for robustness means it may bypass a very narrow global optimum in favor of a flatter, slightly higher-cost region. Future research will focus on scaling these techniques to massive deep learning models and exploring more sophisticated sampling algorithms to mitigate gradient variance.
Summary updated