An efficient nonconvex reformulation of stagewise convex optimization problems

Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli, Krishnamurthy Dvijotham

Abstract: Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy. We establish theoretical properties of the nonconvex formulation, showing that it is (almost) free of spurious local minima and has the same global optimum as the convex problem. We modify PGD to avoid spurious local minimizers so it always converges to the global minimizer. For neural network verification, our approach obtains small duality gaps in only a few gradient steps. Consequently, it can quickly solve large-scale verification problems faster than both off-the-shelf and specialized solvers.

1. Introduction

Stagewise convex optimization problems, characterized by variables determined in a sequential manner, are fundamental to applications such as optimal control, isotonic regression, and the verification of deep neural networks. Despite their convex nature, these problems often pose significant scaling challenges for traditional solvers. First-order methods frequently suffer from slow convergence due to the sequential dependencies, while second-order methods are hampered by the computational intensity of large-scale matrix factorizations.

2. Nonconvex Reformulation and Methodology

The authors propose a novel nonconvex reformulation that exploits the inherent staged structure of these problems. The primary technique is a variable substitution where each activation variable $z$ is expressed as a convex combination of its known lower bound $\mu$ and upper bound $\eta$:

$$z = (1-\theta)\mu + \theta\eta, \quad \theta \in [0, 1]$$

This substitution effectively replaces complex nonlinear constraints with simple box constraints on the new variable $\theta$. This simplification enables the application of highly efficient Projected Gradient Descent (PGD) and its accelerated variants, such as FISTA.

Comparison of the original convex problem and its nonconvex reformulation, illustrating global minimizers and potential spurious local minima.

While the resulting formulation is nonconvex, the paper establishes a critical theoretical guarantee: under a nondegeneracy condition, all local minima are global minima. To handle rare degenerate cases where the gradient might vanish at a non-optimal point, the authors developed the FIX-DEGENERACY algorithm. This backward-pass procedure identifies and nudges the solver away from spurious local minima, ensuring convergence to the global optimum.

3. Experimental Evaluation and Results

The effectiveness of the reformulation was evaluated on neural network verification tasks using the CIFAR-10 dataset. The researchers tested three architectures—Tiny, Small, and Medium—trained via adversarial training and Interval Bound Propagation (IBP).

The results demonstrate significant performance gains:

  • Speed: On CIFAR-10 verification tasks, the proposed method was 3x to 50x faster than DeepVerify, a state-of-the-art specialized solver.
  • Superior Scalability: While general-purpose solvers like SCS and ECOS failed to scale beyond the smallest networks, the authors' method handled the "Medium" architecture (nearly 47,000 units) in roughly 200 milliseconds.
  • Tightness and Certification: The method consistently produced tighter bounds than IBP and automatically generated both primal and dual feasible solutions, allowing for the calculation of a duality gap to certify the quality of the solution.

4. Key Insights

The success of this approach stems from moving the problem's complexity from the constraints into a well-behaved nonconvex objective function. By simplifying the constraints to a box, the problem becomes significantly more amenable to first-order optimization. Furthermore, because the reformulation mirrors the structure of a neural network, gradients can be computed efficiently using standard backpropagation techniques.

5. Conclusion and Future Work

This work provides a powerful framework for solving stagewise convex problems at scale. While currently requiring smoothness for theoretical proofs, the authors have provided practical workarounds for non-smooth functions like ReLU. Future research will focus on a more rigorous treatment of non-smooth cases and extending the framework to more complex optimal control scenarios and generalized isotonic regression.

Summary updated

Abstract

Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy. We establish theoretical properties of the nonconvex formulation, showing that it is (almost) free of spurious local minima and has the same global optimum as the convex problem. We modify PGD to avoid spurious local minimizers so it always converges to the global minimizer. For neural network verification, our approach obtains small duality gaps in only a few gradient steps. Consequently, it can quickly solve large-scale verification problems faster than both off-the-shelf and specialized solvers.
BibTeX
@inproceedings{bunel2020efficient,
  author = {Rudy Bunel and Oliver Hinder and Srinadh Bhojanapalli and Krishnamurthy Dvijotham},
  title = {{An efficient nonconvex reformulation of stagewise convex optimization problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=mQVaL-ilgUW},
}
Figure