An efficient nonconvex reformulation of stagewise convex optimization problems

Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli, Krishnamurthy Dvijotham

Introduction

Many real-world optimization problems possess a "staged" structure, where variables are decided in a sequence and each stage's constraints depend heavily on the previous ones. Common applications include proving neural network robustness (finding worst-case inputs across sequential layers), optimal control (planning actions over time), and isotonic regression.

While these problems are technically convex—and thus theoretically solvable—standard off-the-shelf tools often struggle to scale. First-order methods, like standard gradient descent, are frequently "blind" to sequential dependencies, requiring many iterations to propagate information from the final stage back to the first. Conversely, second-order methods, such as interior-point solvers, are mathematically robust but encounter severe memory and speed bottlenecks when processing the large, dense matrices typical of modern deep learning.

To bridge this gap, this paper introduces a clever nonconvex reformulation for stagewise convex optimization problems. By re-parameterizing the problem to use simple box constraints, the authors enable the use of fast projected gradient methods that outperform specialized solvers by up to 50x while maintaining guarantees of global optimality.

The Nonconvex Reformulation Strategy

Instead of treating the stage variables ($z_i$) as direct optimization targets subject to complex nonlinear constraints, the authors propose introducing a new variable, $\theta_i$, restricted to the range $[0, 1]$.

  1. The "Theta" Trick: Each variable $z_i$ is expressed as a convex combination of its lower bound ($\mu_i$) and upper bound ($\eta_i$): $z_i = (1 - \theta_i)\mu_i + \theta_i\eta_i$.
  2. Box Constraints: This transformation converts difficult nonlinear constraints into simple "box constraints" (keeping $\theta$ strictly between 0 and 1). This allows the application of Projected Gradient Descent (PGD), which is computationally inexpensive per iteration.
  3. Backpropagation: Because the stages are sequential, the gradient of the objective with respect to $\theta$ can be calculated highly efficiently using standard backpropagation.
  4. Global Optimality: Nonconvex problems typically carry the risk of getting stuck in local minima. However, the authors prove that for this specific structural reformulation, "nondegenerate" local minima are actually global minima. They also provide a specialized "escape" algorithm to handle rare degenerate cases where the gradient might vanish.
Comparison of the original convex problem landscape and the nonconvex reformulation.

As illustrated above, while the reformulation introduces a nonconvex landscape with potential spurious local minima, the global minimum is preserved, and the modified PGD algorithm is designed to reliably converge to it.

Experimental Setup

The researchers evaluated their approach on the CIFAR-10 image classification dataset. They trained three different architectures using adversarial training to test neural network verification:

  • Tiny: Two fully connected layers (100 units).
  • Small: Two convolutional layers + two fully connected layers (~8k units).
  • Medium: Four convolutional layers + three fully connected layers (~47k units).

Key Results and Insights

The sequential nature of these problems, which usually impedes general solvers, actually provides a pathway to a much simpler parameterization. By choosing the right nonconvex form, it is possible to retain the global optimality guarantees of convex mathematics while unlocking the speed of gradient-based deep learning tools.

  • Massive Speedups: Compared to DeepVerify (a state-of-the-art specialized solver), the new method was 3x to 50x faster, depending on the network architecture.
  • Superior Scaling: Off-the-shelf convex solvers like SCS and ECOS failed to solve the "Medium" sized networks due to memory and time constraints. The nonconvex approach handled them easily.
  • Tight Bounds: The method consistently found tighter, more accurate bounds for neural network robustness than Interval Bound Propagation (IBP), which is fast but notoriously loose.
  • Early Convergence and Easy Certification: Because the method naturally generates both primal and dual feasible solutions, calculating a "duality gap"—a mathematical proof of how close the current solution is to the absolute best possible answer—is straightforward. In many cases, the algorithm reached a negligible duality gap in just a few gradient steps, allowing for early stopping.

Limitations and Future Directions

The theoretical proofs currently rely on the objective and constraint functions being "smooth" (differentiable). While neural networks often use non-smooth functions like ReLU, the authors suggest using smooth approximations; a rigorous treatment of purely non-smooth cases remains future work. Additionally, the theoretical convergence bound includes a constant that could potentially be large in certain adversarial edge cases, though this was not observed in practical experiments. Finally, the authors suggest this framework could be extended to even more complex "relaxations" of neural networks, such as those involving semidefinite programming, which are currently too slow for practical use.

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 projected gradient descent 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 provide tight duality gaps for many large-scale verification problems where both off-the-shelf and specialized solvers struggle.
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