Abstract
Convex Relaxation Regression (CoRR) is a novel black-box optimization framework designed to solve difficult non-convex problems by "learning" their convex envelopes. By fitting a convex surrogate function to random samples of a complex landscape, CoRR transforms a challenging global search into a provably efficient convex optimization problem. This approach allows for global optimization that scales gracefully with dimensionality, bypassing the traditional "curse of dimensionality."
Introduction
Optimization is the engine of modern machine learning, yet most standard algorithms are designed for convex landscapes—smooth, bowl-shaped surfaces where every downhill step leads to a single global minimum. Real-world problems, such as training deep neural networks or reinforcement learning, are typically non-convex, characterized by deceptive local minima and rugged plateaus where local search methods frequently get trapped.
Existing solutions generally fall into two categories: fast local search methods that lack global guarantees, and exhaustive global search methods (like grid search) that suffer from exponential slowdown as the number of variables increases. A more elegant alternative is convex relaxation, which involves deriving a convex surrogate that approximates the original function. However, this traditionally requires deep mathematical insight and manual derivation for every new problem. CoRR automates this process by learning a convex relaxation directly from black-box function samples.
The CoRR Framework
The core objective of CoRR is to estimate the convex envelope—the tightest possible convex lower bound of a function. The global minimum of the convex envelope is guaranteed to coincide with the global minimum of the original function. The CoRR algorithm implements this via a three-step process:
- Sampling: The unknown function $f(x)$ is evaluated at $T$ random points.
- Constrained Regression: A convex function is fitted to these samples. The algorithm uses a constrained $\ell_1$ regression to minimize the error between the surrogate and the samples, subject to a constraint on the surrogate's average value, parameterized by $\mu$.
- 1D Search: The "tightness" of the envelope depends on the parameter $\mu$. The algorithm performs a simple one-dimensional search to identify the $\mu$ that results in the lowest function value at the surrogate's minimum.
Unlike traditional methods that explore the space incrementally, CoRR adopts a global perspective, using regression to reconstruct the underlying global structure from sparse samples.
Experimental Evaluation
The researchers evaluated CoRR on several high-dimensional non-convex benchmark functions:
- Salomon Function: A "rippled" landscape with many local minima.
- Griewank Function: A landscape with complex, high-frequency noise components.
- Langerman Function: A landscape featuring several deep, narrow pockets.
These benchmarks represent "worst-case" scenarios for local search algorithms and are standard for stress-testing global optimization frameworks.
Key Results and Insights
- Dimensionality Robustness: In tests on the Salomon function, traditional global optimizers like Simulated Annealing failed once dimensions exceeded 10. CoRR successfully identified the global minimum in up to 100 dimensions.
- Theoretical Convergence: The authors proved that the algorithm converges to the global optimizer with an error of $O(T^{-\alpha})$, where $T$ is the number of samples. This polynomial rate suggests CoRR can bypass the exponential slowdown typically associated with global optimization.
- The "Floor" Concept: CoRR demonstrates that modeling the entire complex function is unnecessary; one only needs to find its "convex floor." Once a convex surrogate is established, efficient tools like gradient descent can find the bottom instantly.
- Hybrid Success: While CoRR identifies the general area of the global minimum, it may lack extreme precision. Combining CoRR with a local search "polishing" step (such as Quasi-Newton) leads to perfect reconstruction of the global minimum.
Limitations and Future Directions
CoRR's performance is currently dependent on the choice of basis functions (e.g., quadratics). If the true convex envelope cannot be well-approximated by the chosen class, the algorithm's effectiveness is reduced. Future work aims to incorporate dictionary learning to automatically discover optimal basis functions and adaptive sampling to reduce the number of evaluations required by focusing on areas where the surrogate is lowest.
Summary updated