Abstract
Nonconvex optimization is a cornerstone of modern artificial intelligence, yet it remains plagued by the "curse of dimensionality" and the prevalence of local optima. This paper presents RDIS (Recursive Decomposition into locally Independent Subspaces), a novel algorithm that leverages discrete AI decomposition techniques for continuous optimization. RDIS recursively partitions a problem into independent sub-problems by identifying cutset variables and simplifying the objective function through interval arithmetic. Theoretical analysis and empirical evaluations on Structure from Motion (SfM), protein folding, and synthetic multimodal functions show that RDIS can find global optima exponentially faster than traditional gradient-based methods with random restarts, often outperforming state-of-the-art baselines by several orders of magnitude.
Introduction
Many critical AI challenges, such as neural network training and protein structure prediction, are formulated as nonconvex optimization problems. These problems typically feature "rugged landscapes" with an exponential number of local minima, making global optimization difficult. While gradient descent and random restarts are common, they scale poorly as the number of variables increases. Conversely, branch-and-bound methods struggle with high-dimensional variable spaces.
The authors observe that many nonconvex problems possess a hidden "combinatorial structure" where variables interact only locally. RDIS is designed to exploit this structure, treating the "hardness" of nonconvex optimization as a combinatorial problem that can be solved via divide-and-conquer strategies.
The RDIS Algorithm
RDIS operates through a recursive loop designed to identify and exploit local independence among variables. The process is illustrated in Figure 1.
The algorithm follows five key steps:
- Variable Selection: Using hypergraph partitioning, RDIS identifies a "cutset" of variables. Fixing these variables decouples the remaining problem into independent components.
- Value Selection: Values are assigned to the cutset variables using standard subspace optimizers like Levenberg-Marquardt (LM).
- Simplification: Interval arithmetic is employed to determine if objective function terms become negligible under current assignments, effectively smoothing the landscape.
- Decomposition: The algorithm identifies independent components in the remaining variable space.
- Recursion and Base Case: RDIS calls itself recursively on each component until sub-problems are small enough to be solved directly by standard continuous optimizers.
This approach draws inspiration from DPLL-style SAT solvers and recursive conditioning in probabilistic inference, adapting these discrete techniques for continuous domains.
Experimental Evaluation
The authors evaluated RDIS against several baselines, including Levenberg-Marquardt (LM), Block-Coordinate Descent (BCD), and Conjugate Gradient Descent (CGD), across three domains:
- Structure from Motion (SfM): Using the "Ladybug" dataset (49 cameras, 7776 points), RDIS demonstrated superior performance in reconstructing 3D scenes. As shown in Figure 2, RDIS consistently found lower error values compared to LM and BCD-LM within a fixed time window.
- Protein Folding: On 21 proteins from the Protein Data Bank, RDIS outperformed CGD and BCD, finding lower energy configurations by exploiting the local interactions of atoms.
- High-dimensional Sinusoids: In synthetic tests, RDIS successfully escaped local minima that trapped all other baseline methods.
A key insight from the experiments was the impact of the approximation error ($\epsilon$). Allowing a small $\epsilon > 0$ during simplification acted as a smoothing mechanism, helping the algorithm ignore "micro-valleys" and focus on the global landscape, which improved overall results.
Discussion and Future Work
RDIS represents a significant step in bridging discrete combinatorial search and continuous optimization. By focusing on the combinatorial core of nonconvex problems, it achieves exponential speedups for locally decomposable functions.
Future research directions include developing formal convergence proofs for cases where $\epsilon > 0$, improving interval arithmetic bounds to trigger decomposition more frequently, and extending the framework to handle hard constraints and hybrid discrete-continuous variable spaces. Despite these open questions, RDIS provides a powerful new tool for tackling high-dimensional, rugged optimization landscapes in AI.
Summary updated