Convex training of Lipschitz-regularized shallow neural networks

Technical Summary: Convex Training of Lipschitz-regularized Shallow Neural Networks

Problem Statement
Training shallow neural networks (SNNs) typically relies on stochastic gradient descent (SGD), which offers no guarantee of convergence to a global optimum and is sensitive to hyperparameter tuning. Furthermore, standard trained models are often vulnerable to adversarial attacks—small, worst-case perturbations to input data that alter predictions. While adversarial training and Lipschitz regularization can improve robustness, existing methods face significant challenges:

1. Non-convexity: Training programs incorporating Lipschitz constraints (e.g., via Semi-Definite Programming or ADMM) are non-convex, lacking convergence guarantees.
2. Activation Pattern Sensitivity: Previous convex reformulations for SNNs (e.g., Pilanci & Ergen, 2020) require sampling activation patterns. If these patterns are suboptimal, the resulting convex program may yield solutions worse than the initial SGD-trained network.
3. Model Expansion: Existing convex approaches often require doubling the number of hidden units to guarantee that an initial solution is feasible within the convex restriction, potentially leading to overfitting or making direct performance comparisons difficult.

Methodology
The authors propose a post-processing training procedure that transforms a non-convex, Lipschitz-regularized training problem into a sequence of convex restrictions. The core methodology involves:

1. Convex Restriction Construction:

   • The authors fix the signs of the outer layer weights and the activation patterns of the hidden units based on a pre-trained SNN.
   • By fixing these discrete variables, the original non-convex problem (which includes $\ell_2$ or Lipschitz regularization) is restricted to a convex sub-problem.
   • Crucially, this restriction is constructed such that the initial pre-trained solution remains feasible. Therefore, the global optimum of this convex restriction is mathematically guaranteed to be no worse than the initial solution.

2. Iterative Alternating Minimization (AM):

   • For Lipschitz-regularized problems, the authors propose an iterative algorithm (Algorithm 1).
   • Step 1: Given current weights, solve a Semi-Definite Program (SDP) to estimate the tightest Lipschitz upper bound (Lipschitz constant) and update the auxiliary matrix $T$.
   • Step 2: With $T$ fixed, solve the convex restriction (a Quadratic Program with Linear Matrix Inequality constraints) to update the hidden layer weights while maintaining the extracted activation patterns.
   • This process repeats, monotonically decreasing the objective value (loss + Lipschitz penalty) until convergence.

3. Pattern Multiset Handling:

   • Unlike prior works that sample patterns randomly or require unique patterns, this method utilizes the exact activation patterns (multisets) extracted from the pre-trained network.
   • The authors prove that if the extracted patterns correspond to the optimal solution's patterns, the convex program is equivalent to the original non-convex problem. Even with suboptimal patterns, the solution is guaranteed to improve upon the initial point.

Key Contributions

1. Convex Training Method: Development of a convex training method for Lipschitz-regularized SNNs with ReLU activations. The authors demonstrate that fixing outer layer weight signs and hidden unit activation patterns yields a convex restriction of the original non-convex problem.
2. Guaranteed Improvement: An iterative algorithm is proposed that solves a sequence of these convex restrictions to global optimality. The authors prove that the objective value decreases monotonically and that the final solution is guaranteed to be no worse than the initial pre-trained network.
3. Stronger Convex Restrictions: The paper introduces techniques for constructing these restrictions by extracting activation patterns and outer layer weights from any pre-trained SNN. This addresses the challenge of finding "good" activation patterns, as the method guarantees improvement regardless of the initial pattern quality.
4. Empirical Validation: Experiments on UCI and synthetic datasets (Rastrigin function) demonstrate that the proposed post-processing method yields networks with lower objective values and improved robustness against PGD (Projected Gradient Descent) adversarial attacks compared to existing methods like ADMM-based Lipschitz training and standard SGD.

Results

• Objective Value Reduction: On multiple datasets (Solar, Machine, Servo, Wine), the proposed convex solutions (denoted as $(\cdot)$-C-lip) achieved lower median Mean Squared Error (MSE) under adversarial conditions compared to baseline models trained via SGD, PGD, or ADMM.
• Robustness: The method produced models that were both more accurate and more robust to adversarial attacks of varying magnitudes ($\epsilon = 0, 0.1, 0.2$).
• Comparison to Baselines:
  • The convex restriction consistently outperformed the initial pre-trained models.
  • In contrast, methods that sampled only a fraction of activation patterns (e.g., 50 out of 100) failed to guarantee improvement and often produced worse solutions than the baselines, highlighting the importance of using the full set of extracted patterns.
  • The proposed method showed significant improvements over ADMM-based Lipschitz training, particularly on the "Servo" and "Machine" datasets.

Significance and Claims
The paper claims that its primary significance lies in providing a tractable, convex framework for training adversarially robust SNNs that overcomes the convergence issues of non-convex methods (like ADMM) and the solution quality uncertainty of existing convex approaches.

• Robustness Guarantee: By minimizing the Lipschitz constant via a convex restriction, the method promotes adversarial robustness without the convergence guarantees of standard non-convex training.
• Post-Processing Utility: The approach serves as a reliable post-processing step. It takes any feasible solution (e.g., from SGD or ADMM) and guarantees a solution of equal or higher quality, effectively refining existing models without the risk of degrading performance.
• Scalability and Practicality: The method utilizes off-the-shelf interior-point solvers (e.g., MOSEK) and avoids the need for heuristic pattern sampling that can lead to suboptimal results.

The authors modestly note that while the method guarantees improvement over the initial solution, it does not guarantee finding the global optimum of the original non-convex problem unless the extracted activation patterns happen to be optimal. Future work is suggested to extend this to deep neural networks and to develop methods for sequentially improving the pattern multiset selection.