An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs

Linbo Qiao, Wei Liu, Steven C. H. HoiarXiv 2018 · DOI · arXiv

TL;DR

This paper introduces a novel incremental path-following splitting algorithm (IPFS) to efficiently solve a challenging class of optimization problems common in machine learning. IPFS offers a theoretical guarantee of convergence and significantly reduces computational cost, outperforming existing methods on benchmark tasks.

What Problem Does This Paper Address?

Many machine learning problems, such as those in deep learning, matrix factorization, and phase retrieval, can be formulated as optimizing a highly nonconvex and nonsmooth objective function subject to linear constraints. These problems are notoriously difficult to solve due to the nonsmoothness (making gradient-based methods tricky) and the complexity of projecting onto the feasible region defined by linear inequalities. Existing methods often struggle with high dimensionality, leading to prohibitive per-iteration costs, or lack theoretical guarantees for these specific problem types. This paper aims to bridge this gap by developing an algorithm that is both theoretically sound and computationally efficient for these challenging problems.

Methods

The core of the proposed method, IPFS (Incremental Path-Following Splitting), is to transform the original problem into a sequence of "d-smoothed" problems. This is achieved by introducing slack variables to convert inequality constraints into equalities and then using a log-barrier function to handle the non-negativity constraints. This creates a sequence of problems that are easier to solve. The algorithm then incrementally follows a "path" of solutions from these smoothed problems, with the smoothing parameter decreasing towards zero, to converge to a solution of the original problem.

A key innovation is the use of a splitting method combined with either cyclic or randomized variable selection. This allows the algorithm to process only a subset of variables at each inner iteration, drastically reducing the computational cost, especially in high-dimensional settings. The theoretical analysis provides guarantees on the convergence rate and iteration complexity.

Datasets

The paper evaluates its method on two main tasks:

  • Constrained Concave Penalized Linear Regression (CCPLR): This is a synthetic dataset task where the authors generate data with varying dimensions and noise levels.
  • Nonconvex Support Vector Machine (NCSVM): This task uses real-world datasets, specifically mentioning the use of seven datasets with statistics provided in Table 1 (ohscal, w8a, a9a, 20news, SUSY).

Key Insights and Ideas

  • Path-Following for Nonconvexity: The paper demonstrates that a path-following approach, typically used for convex problems, can be effectively adapted to navigate the complex landscape of nonconvex nonsmooth optimization.
  • d-Smoothing as a Bridge: By gradually smoothing the objective function and constraints, the algorithm creates a sequence of tractable subproblems that guide the search towards a stationary point of the original, harder problem.
  • Splitting + Variable Selection = Efficiency: The combination of a splitting method with randomized or cyclic variable selection is crucial for achieving low per-iteration costs, making the algorithm practical for large-scale machine learning.
  • Theoretical Guarantees for a Difficult Class: This work provides the first incremental method with a theoretical guarantee for solving linearly constrained nonconvex nonsmooth programs, a significant step forward.

Key Results

The paper reports strong experimental results:

  • Consistent Outperformance: IPFS (both cyclic and randomized versions) consistently outperforms existing heuristic methods like InexactALM and proximal ADMM-m on both synthetic and real-world datasets.
  • Lower Objective Values: The proposed methods achieve lower objective values, indicating better solutions, particularly in the nonconvex optimization process.
  • High-Dimensional Advantage: The benefits of IPFS are especially pronounced when dealing with high-dimensional data, where its low per-iteration cost becomes a significant advantage.
  • Theoretical Guarantees: The algorithm is proven to converge to an $\epsilon$-approximate stationary solution within $O(1/\epsilon)$ iterations for the inner loop and $O(\log(1/\delta))$ iterations for the outer loop, where $\delta$ is the smoothing parameter.

Limitations and Future Work

  • Subproblem Solvability: While the paper assumes that the subproblems generated by the splitting method can be solved exactly (as shown in prior work for specific cases), it acknowledges that closed-form solutions are generally intractable. The authors suggest using iterative methods to approximate these solutions, but this could impact practical performance.
  • Parameter Tuning: The paper notes that parameter settings (like $\beta$) can vary between theoretical analysis and practical usage, suggesting that adaptive strategies for parameter tuning could further improve performance.
  • Future Work: The authors implicitly suggest exploring more advanced variable selection rules or further optimizing the subproblem solvers as potential avenues for future research. The abstract also mentions an error in the stationary point definition, which is being addressed.

Summary updated

Abstract

The stationary point of Problem 2 is NOT the stationary point of Problem 1. We are sorry and we are working on fixing this error.
BibTeX
@misc{qiao2018incremental,
  author = {Linbo Qiao and Wei Liu and Steven C. H. Hoi},
  title = {{An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs}},
  year = {2018},
  eprint = {1801.10119},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.10119},
}
Figure