Nonconvex proximal splitting: batch and incremental algorithms

Suvrit SraarXiv 2011 · DOI · arXiv

Abstract

Within the unmanageably large class of nonconvex optimization, we consider the rich subclass of nonsmooth problems that have composite objectives—this already includes the extensively studied convex, composite objective problems as a special case. For this subclass, we introduce a powerful, new framework that permits asymptotically non-vanishing perturbations. In particular, we develop perturbation-based batch and incremental (online like) nonconvex proximal splitting algorithms. To our knowledge, this is the first time that such perturbation-based nonconvex splitting algorithms are being proposed and analyzed. While the main contribution of the paper is the theoretical framework, we complement our results by presenting some empirical results on matrix factorization.

Introduction

In the fields of machine learning and signal processing, many optimization problems are formulated as "composite" objectives. These typically take the form $\min f(x) + h(x)$, where $f$ is a smooth function representing a loss or data-fidelity term, and $h$ is a nonsmooth regularizer, such as the $L_1$ norm used to induce sparsity. While these problems are well-understood in the convex regime, many modern applications—including matrix factorization, dictionary learning, and deep neural networks—are inherently nonconvex.

Existing optimization methods for nonconvex composite problems often rely on two restrictive assumptions. First, they typically assume "vanishing errors," meaning any computational inaccuracies must eventually shrink to zero. In large-scale systems, this is often impractical. Second, they often require "monotonic descent," where the objective value must decrease at every step. This requirement hinders the development of efficient incremental or stochastic algorithms, which are essential for processing massive datasets.

The NIPS Framework

To address these limitations, we introduce NIPS (Nonconvex Inexact Proximal Splitting). NIPS is a theoretical framework that "splits" the optimization task: it uses a gradient step for the smooth component ($f$) and a proximal operator for the nonsmooth component ($h$).

The NIPS framework introduces several key innovations:

  1. Robustness to Inexactness: Unlike previous theories, NIPS explicitly models computational errors $e(x^k)$. It provides convergence guarantees even when these errors are bounded but non-vanishing, ensuring the algorithm reaches a stable neighborhood of a solution.
  2. Incremental Scalability: By relaxing the strict descent requirement, NIPS enables an incremental variant for objectives that are sums of many functions ($\sum f_t(x) + g(x)$). This allows for online-style updates, making the framework suitable for very large datasets.
  3. Prox-Monotonicity: The theoretical backbone of NIPS relies on a new property called "prox-monotonicity," derived using Moreau envelopes. This property allows the algorithm to converge without needing a monotonic decrease in the objective function at every iteration.

Methods and Theoretical Contributions

The NIPS framework is designed as a versatile template that encompasses classic methods like Forward-Backward Splitting (FBS) and Gradient Projection, extending them into the nonconvex and inexact regime. It can handle various combinations of constraints and penalties.

Table 1: Summary of problem settings and proximity operator call frequencies within the NIPS framework.

As shown in the table above, the framework adapts to different domain spaces ($\mathcal{X}$) and regularizers ($g$), determining whether proximity operators are called during major or minor iterations. This flexibility allows NIPS to be tailored to specific computational constraints and problem structures, whether they are unconstrained or subject to convex constraints.

Empirical Evaluation

The framework's performance was evaluated on Nonnegative Matrix Factorization (NMF) tasks using several diverse datasets:

  • RAND: A $4000 \times 4000$ synthetic dense matrix.
  • CBCL: The MIT facial database ($361 \times 2429$).
  • YALE: The Yale B facial database ($32256 \times 2414$).
  • WEB: A massive, sparse Google web graph ($714,545 \times 739,454$).

Despite being implemented in Matlab, NIPS demonstrated efficiency comparable to SPAMS, a highly optimized C++ library. Projections suggest a C++ implementation of NIPS could be significantly faster than existing state-of-the-art tools. Furthermore, NIPS outperformed Stochastic Generalized Gradient Descent (SGGD) by producing solutions with lower objective values and superior sparsity, which is critical for feature selection.

Conclusion and Future Work

NIPS represents a significant step forward in nonconvex optimization by providing a robust framework that handles non-vanishing errors and enables incremental updates. While the current framework requires the nonsmooth part ($h$) to be convex, extending NIPS to handle fully nonconvex composite objectives remains an important area for future research. The ability to reach approximate stationary points in "dirty" computing environments makes NIPS particularly well-suited for modern, large-scale machine learning applications.

Summary updated

Abstract

Within the unmanageably large class of nonconvex optimization, we consider the rich subclass of nonsmooth problems that have composite objectives---this already includes the extensively studied convex, composite objective problems as a special case. For this subclass, we introduce a powerful, new framework that permits asymptotically non-vanishing perturbations. In particular, we develop perturbation-based batch and incremental (online like) nonconvex proximal splitting algorithms. To our knowledge, this is the first time that such perturbation-based nonconvex splitting algorithms are being proposed and analyzed. While the main contribution of the paper is the theoretical framework, we complement our results by presenting some empirical results on matrix factorization.
BibTeX
@misc{sra2011nonconvex,
  author = {Suvrit Sra},
  title = {{Nonconvex proximal splitting: batch and incremental algorithms}},
  year = {2011},
  eprint = {1109.0258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1109.0258},
}
Figure