Introduction
Optimizing non-convex functions is a fundamental challenge in machine learning and engineering, as standard gradient-based techniques frequently converge to sub-optimal local minima. While convex relaxation—the process of replacing a non-convex objective with a convex surrogate—offers a path to global optimality, it traditionally requires manual, problem-specific derivation. Convex Relaxation Regression (CoRR) introduces an automated, "black-box" framework for global optimization by learning the convex envelope of a function directly from samples.
Methodology: Convex Relaxation Regression (CoRR)
CoRR treats the search for a convex relaxation as a regression problem. The algorithm operates in three primary stages:
- Sampling: The target non-convex function $f$ is evaluated at $T$ random points within the domain.
- Learning the Envelope: Instead of fitting the function $f$ exactly, CoRR fits a convex surrogate to the sampled points. This is achieved via constrained $\ell_1$ regression, seeking a linear combination of convex basis functions (e.g., quadratics) that remains below the samples while maintaining maximum "tightness."
- Global Optimization: The resulting convex surrogate is minimized using efficient, standard convex optimization tools.
A critical component of this process is the tuning of a parameter $\mu$, which represents the expected value of the surrogate. As shown in Figure 1, the choice of $\mu$ determines whether the surrogate underestimates or overestimates the function. The "CoRR" setting identifies the optimal $\mu$ where the surrogate's minimum most accurately coincides with the global minimum of the original function.
Experimental Evaluation
The authors evaluated CoRR against several standard multi-modal benchmark functions, including the Salomon (S1, S2), Langerman (L), and Griewank (G) functions. These landscapes are characterized by numerous local minima designed to trap local search methods.
Key Results
- High-Dimensional Performance: On the Salomon function, CoRR significantly outperformed traditional methods like Quasi-Newton (QN) and Simulated Annealing (SA) in dimensions greater than 10. While QN and SA often stalled in local minima, CoRR consistently approached the global center.
- Sample Efficiency: For smooth landscapes like the Langerman function, CoRR achieved near-perfect reconstruction of the global minimum with as few as 200 samples.
- Hybrid Optimization: CoRR is particularly effective as a "warm-start" mechanism. By using the CoRR result as an initial point for a local search method (e.g., Quasi-Newton), the researchers achieved machine-precision accuracy across complex benchmarks.
Discussion and Future Work
CoRR provides a theoretical "safety net" through provable polynomial convergence rates, a feature lacking in many heuristic global optimizers. However, several avenues for improvement remain:
- Basis Function Selection: While quadratic bases are effective for many smooth functions, more complex landscapes may require higher-degree polynomials or exponential bases.
- Adaptive Sampling: Moving beyond i.i.d. sampling to adaptive strategies could further reduce the sample complexity required to find the envelope.
- Dictionary Learning: Future work could explore automatically learning the optimal basis functions for a given class of problems, reducing the reliance on pre-defined function classes.
By reframing global optimization as a regression task, CoRR offers a general-purpose, automated approach to solving complex non-convex problems without requiring explicit knowledge of the function's internal structure.
Summary updated