TL;DR
This paper introduces a framework to transform a broad class of non-convex optimization problems into guaranteed convex ones by adopting a "risk-averse" perspective. By combining Gaussian smoothing with an exponential cost transformation, the authors provide a "magic condition" ($\alpha R \succeq \Sigma^{-1}$) that ensures global optimality is reachable via standard stochastic gradient methods.
What Problem Does This Paper Address?
In the world of optimization, the "great watershed" isn't between linear and nonlinear problems, but between convex and non-convex ones. Convex problems are easy: any local minimum is a global minimum, and we have efficient algorithms to find them. Non-convex problems are nightmares: they are often NP-hard, riddled with local traps, and sensitive to initialization.
While "smoothing" (adding noise to an objective function) is a common heuristic to simplify rugged landscapes, it rarely guarantees that the resulting problem is actually convex. The authors tackle this head-on, asking: Can we systematically transform a non-convex problem into a convex one while maintaining a provable relationship to the original goal?
Methods
The authors propose a "Universal Convexification" framework. They start with a general objective function $g(\theta)$ decomposed into a potentially nasty non-convex part $f(\theta)$ and a quadratic "regularizer" or "control cost" $\frac{1}{2}\theta^T R \theta$.
The core technique involves two steps:
- Gaussian Perturbation: Instead of evaluating $f$ at a point, they look at the expected value of $f$ under Gaussian noise $\omega \sim \mathcal{N}(0, \Sigma)$.
- Risk-Aversion Transformation: They apply an exponential transformation 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: They prove (Theorem 3.1) that if you choose a high enough risk factor $\alpha$ such that $\alpha R \succeq \Sigma^{-1}$, the entire optimization problem becomes convex, regardless of how non-convex the original $f(\theta)$ was.
To solve this, they adapt Stochastic Gradient Descent (SGD). Because the objective involves an expectation, they use an exponentiated gradient estimator that allows them to sample the noise and converge to the global optimum of the transformed problem.
Datasets
The authors validated their framework on several benchmarks:
- UCI Breast Cancer Dataset: Used for binary classification tasks to compare against Support Vector Machines (SVM).
- MNIST (Subset): A randomly selected subset of the famous handwritten digit dataset was used to test neural network training.
- Synthetic 1D Regression: A toy problem used to visualize how the method avoids local minima that trap standard backpropagation.
Key Insights and Ideas
- The Robustness Trade-off: The convexified version doesn't just find any minimum; it specifically finds robust minima. Narrow, deep "holes" in the cost landscape are ignored because they are sensitive to noise. The algorithm prefers "wide" minima where the cost stays low even if the parameters are slightly perturbed.
- Universal Applicability: The condition for convexity depends only on the relationship between the risk factor ($\alpha$), the regularizer ($R$), and the noise ($\Sigma$). It does not depend on the specific shape of the non-convex function $f$, provided $f$ is bounded.
- Control Theory Bridge: The authors show this isn't just for static optimization. It maps directly onto Risk-Sensitive Markov Decision Processes (MDPs). This allows them to derive the first policy gradient algorithms for certain dynamical systems that are guaranteed to converge to a global optimum.
Key Results
- Guaranteed Convexity: The paper provides a formal proof that non-convex problems can be made convex via risk-aversion.
- Suboptimality Bounds: They provide theoretical bounds (Theorem 3.2 and 3.4) showing that if the original function $f$ is Lipschitz continuous, the gap between the "convex surrogate" solution and the true optimum is controlled and predictable.
- Classification Performance: In binary classification tests, the "Convexified Approach" significantly outperformed standard LibSVM as the noise level in the data increased, demonstrating superior robustness (see Figure 2 in the paper).
- Neural Network Training: On small-scale neural net tasks, standard backpropagation frequently got stuck in poor local minima (achieving ~20% accuracy), while the convexified approach consistently found better solutions (reaching ~80% accuracy) by navigating the smoothed, convexified landscape (see Figure 3a).
Limitations and Future Work
- Gradient Variance: The use of an exponentiated objective function can lead to high variance in gradient estimates. This can slow down convergence, requiring many samples or more sophisticated sampling techniques (like MCMC).
- The "Robustness" Assumption: The method works best when the "true" solution to the original problem is somewhat robust. If the global optimum is a very narrow spike, this method will intentionally ignore it in favor of a flatter, slightly higher-cost region.
- Scaling: While demonstrated on small neural nets and classification, scaling the exponentiated gradient to massive, modern deep learning models remains a challenge for future research. The authors suggest exploring better sampling algorithms to mitigate this.
Summary updated