Recursive Decomposition for Nonconvex Optimization

Abram L. Friesen, Pedro Domingos

TL;DR

RDIS (Recursive Decomposition into Independent Subspaces) is a novel optimization algorithm that brings the power of discrete problem-solving—like SAT solvers—to the continuous, nonconvex world. By recursively fixing "key" variables to break complex objective functions into smaller, independent sub-problems, RDIS achieves exponential speedups over standard gradient descent methods in challenging domains like protein folding and computer vision.

What Problem Does This Paper Address?

Optimization is the heartbeat of modern AI, powering everything from robotic path planning to training deep neural networks. When a problem is "convex" (shaped like a bowl), finding the bottom is easy. However, most real-world problems are "nonconvex," featuring a rugged landscape with an exponential number of "local optima"—traps that look like the best solution locally but are far from the global best.

Standard approaches like gradient descent with random restarts or simulated annealing often fail because they treat the optimization landscape as a single, monolithic entity. They don't exploit the underlying combinatorial structure of the problem. For example, in protein folding, moving one end of a long molecule might have zero effect on the other end, yet standard optimizers try to solve for the whole chain simultaneously.

Methods

The authors introduce RDIS, which treats continuous optimization as a recursive decomposition task. The process works as follows:

  1. Variable Selection: The algorithm identifies a small subset of variables ($x_C$) that act as a "cutset." If these variables are fixed, the rest of the problem graph breaks into independent pieces. RDIS uses hypergraph partitioning to find these optimal cuts.
  2. Value Selection: A "subspace optimizer" (like Levenberg-Marquardt or Conjugate Gradient) is called to assign values to these cutset variables.
  3. Simplification & Decomposition: Using interval arithmetic, RDIS identifies terms in the objective function that become negligible or constant given the current variable assignments. It then physically breaks the objective function into independent sub-functions.
  4. Recursion: The algorithm calls itself on each independent sub-function. This continues until the sub-problems are small enough to be solved directly by standard continuous optimizers.
Figure 1: Visualization of RDIS decomposing the objective func- tion. Vertices (circles) represent variables and edges connect each pair of variables in a term. Left: RDIS selects xC (shaded oval). Middle: The function during simplification. Thick edges indicate simplifiable terms. Assigned variables are constant and have been removed. Right: The function after decomposition.

This "divide and conquer" strategy is reminiscent of DPLL-style SAT solvers, but adapted for the continuous domain.

Datasets

The authors evaluated RDIS against standard baselines on three distinct types of problems:

  • Structure from Motion (SfM): Specifically "bundle adjustment," using the Ladybug dataset (49 cameras and over 7,000 points). This involves reconstructing 3D scenes from 2D images.
  • High-dimensional Sinusoid: A synthetic, highly multimodal test function designed to stress-test an optimizer's ability to escape local minima.
  • Protein Folding: Sidechain placement for 21 different proteins selected from the Protein Data Bank (PDB), with sizes ranging from 257 to 943 variables.

Key Insights and Ideas

  • Exploiting Local Structure: While a problem might not be decomposable globally, it often is locally. Fixing just a few variables can cause the rest of the system to decouple, allowing for massive computational savings.
  • The Power of Nested Restarts: Because RDIS is recursive, it performs restarts at every level of the problem hierarchy. This allows it to explore the combinatorial "core" of the problem much more efficiently than a top-level random restart ever could.
  • Simplification as Smoothing: The algorithm uses an approximation parameter ($\epsilon$). Interestingly, increasing $\epsilon$ (allowing more error) can actually improve results by smoothing out tiny, irrelevant local minima that would otherwise trap the optimizer.
Figure 5: RDIS-NRR’s minimum energy found and total time taken versus ϵ, on protein 3EEQ (ID 9). The x-axis is log scale.

Key Results

  • Exponential Efficiency: Analytically, the authors prove that RDIS is exponentially more efficient than gradient descent with random restarts for locally decomposable functions.
  • Superior Performance in Vision: In bundle adjustment tasks, RDIS found significantly lower error values than standard Levenberg-Marquardt (LM) and block-coordinate descent methods within the same time limit.
Figure 2: Minimum value found in one hour for increasing sizes of bundle adjustment problem (y-axis is log scale).
  • Dominance in Biology: On the protein folding benchmark, RDIS outperformed Conjugate Gradient Descent (CGD) on every single protein tested, often finding energy states that were orders of magnitude better.
Figure 4: Minimum value (energy) found on 21 different proteins.

Limitations and Future Work

While RDIS shows great promise, the authors note a few areas for growth:

  • Convergence Proofs: While the algorithm converges to stationary points when the approximation error $\epsilon = 0$, a formal proof for the approximate case ($\epsilon > 0$) remains elusive, despite its strong empirical performance.
  • Static vs. Dynamic Selection: Currently, variable selection is done once at each level based on graph structure. Future versions could dynamically re-select variables based on the specific values encountered during the search.
  • Broadening Scope: The authors suggest extending RDIS to handle hard constraints, discrete variables, and even high-dimensional integration problems.

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 Domingos},
  title = {{Recursive Decomposition for Nonconvex Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=S1-UkQfuZB},
}
Figure