Convex Optimization For Non-Convex Problems via Column Generation

Julian Yarkony, Kamalika ChaudhuriarXiv 2016 · arXiv

Abstract

This paper presents a novel framework for addressing notoriously difficult non-convex approximation problems, such as tensor decomposition and mixture modeling. By reframing these problems as convex optimization over an infinite set of "primitive" objects, the authors leverage column generation to iteratively identify and incorporate the most relevant components. This approach bypasses the local optima issues common in traditional methods like Expectation-Maximization (EM) and provides a principled way to encourage sparsity in complex models.

Introduction

In machine learning, a recurring challenge involves representing complex data—such as high-dimensional tensors or intricate probability distributions—as a weighted sum of simpler "primitives" (e.g., rank-1 tensors or Gaussian distributions). Traditionally, this task is treated as a non-convex optimization problem. Standard algorithms like gradient descent or Expectation-Maximization (EM) frequently become trapped in local optima, and the search space for potential primitives is often infinite or exponentially large, making exhaustive search impossible.

This research proposes a principled convex optimization framework designed to handle these massive variable spaces. By utilizing column generation, the method maintains a manageable "working set" of variables and iteratively expands it, ensuring that the model remains sparse while effectively approximating the target data.

Methodology

Convex Formulation and Column Generation

The core innovation lies in treating the approximation problem as a convex optimization over an infinite number of variables, where each variable corresponds to a potential primitive. To manage this infinite space, the authors adapt Column Generation, a classic technique from operations research.

The algorithm operates in a loop:

  1. Solve the Restricted Problem: The optimization is solved using only a small "working set" of primitives.
  2. Dual Analysis: The algorithm examines the Lagrangian dual of the current solution to identify the "most violated constraint."
  3. Primitive Identification: This step identifies which new primitive, if added to the working set, would most significantly improve the objective function.
  4. Update: The new primitive is added, and the process repeats until convergence.

Loss Families

The framework supports two primary loss families, each tailored to specific data types:

  • Family One (L2 Loss): Utilizes mean squared error with L1 regularization. This is particularly effective for tasks like tensor approximation and image compression.
  • Family Two (Cross-entropy Loss): Employs cross-entropy with L1 regularization, specifically designed for probability distributions such as Gaussian Mixture Models (GMMs).

Inference Sub-problems

Identifying the optimal new primitive to add is the most computationally intensive step. The authors employ specialized sub-routines for different tasks:

  • Tensors: Power iteration is used to find new rank-1 components.
  • GMMs: An approach based on Jensen’s inequality (analogous to the "M-step" in EM) is used to determine the best new Gaussian component.

Key Insights

The Power of the Dual

By shifting the "hard" non-convex part of the problem into the dual sub-problem, the framework gains robustness. While finding the absolute best primitive is often NP-hard, the authors demonstrate that finding a sufficiently good local optimum for a single primitive is enough to guarantee global progress in the convex master problem.

Sparsity and Noise Handling

The use of L1 regularization naturally encourages the model to use a minimal number of primitives. In probabilistic contexts (Family Two), noise is handled by allowing the model to assign weight to a high-entropy "uniform" primitive, effectively filtering out background noise from the structured signal.

Bypassing Local Optima

Unlike EM, which updates all components simultaneously and can stall in local optima, column generation keeps existing high-quality components fixed. It only introduces new components that are mathematically guaranteed to improve the global objective, providing a more stable path to the global optimum.

Experimental Results

The approach was evaluated using synthetic symmetric 3-way tensors across various sizes and noise levels.

  • Convergence and Speed: For L2 loss experiments, the algorithm converged to low-cost solutions rapidly, often within seconds for tensors up to size 45.
  • Ground Truth Recovery: In scenarios where the underlying basis was known, the generated primitives showed high alignment with the true components. The optimizer proved powerful enough to fit the injected noise, indicating a thorough exploration of the search space.
  • Scalability: While Family One (L2) scaled efficiently, Family Two (Cross-entropy) was found to be more computationally demanding, despite its theoretical advantages for probabilistic data.

Limitations and Future Work

As the working set of primitives grows, the underlying Linear Programming (LP) and Quadratic Programming (QP) solvers can experience performance degradation. Future work will focus on "warm-starting" these solvers to improve efficiency. Additionally, the authors suggest exploring branch-and-bound techniques to enforce strict L0 norm sparsity constraints. Finally, the research hints at a deeper connection between column generation and the success of large single-hidden-layer neural networks, suggesting that this framework may provide theoretical insights into why certain deep learning architectures perform so well.

Summary updated

BibTeX
@misc{yarkony2016convex,
  author = {Julian Yarkony and Kamalika Chaudhuri},
  title = {{Convex Optimization For Non-Convex Problems via Column Generation}},
  year = {2016},
  eprint = {1602.04409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.04409},
}
Figure