Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper

Abram L. Friesen, Pedro M. Domingos

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 RDIS recursive loop: variable selection via cutsets, assignment, simplification using interval arithmetic, and decomposition into independent sub-problems.

The algorithm follows five key steps:

  1. Variable Selection: Using hypergraph partitioning, RDIS identifies a "cutset" of variables. Fixing these variables decouples the remaining problem into independent components.
  2. Value Selection: Values are assigned to the cutset variables using standard subspace optimizers like Levenberg-Marquardt (LM).
  3. Simplification: Interval arithmetic is employed to determine if objective function terms become negligible under current assignments, effectively smoothing the landscape.
  4. Decomposition: The algorithm identifies independent components in the remaining variable space.
  5. 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.
Performance comparison on the Structure from Motion (SfM) task. RDIS finds significantly lower minimum values (error) compared to standard LM and BCD-LM as the problem scale increases.

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

Abstract

Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing standard convex techniques to find only local optima, even with extensions like random restarts and simulated annealing. We observe that, in many cases, the local modes of the objective function have combinatorial structure, and thus ideas from combinatorial optimization can be brought to bear. Based on this, we propose a problem-decomposition approach to nonconvex optimization. Similarly to DPLL-style SAT solvers and recursive conditioning in probabilistic inference, our algorithm, RDIS, recursively sets variables so as to simplify and decompose the objective function into approximately independent sub-functions, until the remaining functions are simple enough to be optimized by standard techniques like gradient descent. The variables to set are chosen by graph partitioning, ensuring decomposition whenever possible. We show analytically that RDIS can solve a broad class of nonconvex optimization problems exponentially faster than gradient descent with random restarts. Experimentally, RDIS outperforms standard techniques on problems like structure from motion and protein folding.
BibTeX
@inproceedings{friesen2015recursive,
  author = {Abram L. Friesen and Pedro M. Domingos},
  title = {{Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=S1-UkQfuZB},
}
Figure