Optimization in

Neural Networks

Chris Choy

Ph.D. at CVGL

http://chrischoy.org

Optimization of a Neural Network

Examples

Optimization in a Neural Network

Table of Contents

• Papers
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Fast Bilateral Solver
• Conditional Random Fields as Recurrent Neural Networks
• Summary
• Conclusion

Amos & Kolter,

OptNet: Differentiable Optimization as a Layer in Neural Networks, ICLR’17

OptNet: Introduction

• Neural Networks
• A linear transformation (conv, fc) followed by a simple nonlinear operation (ReLU)
• Individual layer with richer behavior
• Can reduce the overall depth of the network (Not verified in the paper)
• To this end
• Propose a layer that can solve small quadratic programs
• Advantages
• Developed custom primal dual interior point QP (batch) solver
• 100x times faster in the custom batch solver

OptNet

Amos et al., OptNet: Differentiable Optimization as a Layer in Neural Networks

• Parameters Q, q, A, b, G, and h are also differentiable and can be optimized
• Gradient of the eq at its solution.
• by taking the matrix differential of the KKT cond.
• https://github.com/locuslab/qpth/blob/master/qpth/qp.py#L124

KKT Condition

Then, the Lagrangian is

​

​

​

Stationarity, primal feasibility, complementary slackness

Matrix Differential

Diagonal matrix

Properties

• Efficient batch solver: faster than non-batch solver Gurubi and CPLEX
• Thm.1
• Subdifferentiable
• Thm.2
• n-dim element-wise piecewise linear f with k linear region → an OptNet with O(nk) params.
• Thm.3
• Exists a function that can be specified by an OptNet layer that can be approximated using exponentiallly many units.
• Caveats:
• Cubic complexity (num vars. & constraints)
• Dim less than 1k
• Structure in data
• Sparsity, Teoplitz …
• More tuning

Experiment 2: Total Variation Denoising

​

​

• y: observations
• encourages differences to be sparse
• piecewise constant function.
• FC Net: Regress y
• TV: vary lambda, choose best
• OptNet: Random init D
• OptNet TV: init to prev D

Experiment 3: MNIST

• Show it is possible to include an OptNet layer into a nnet
• Potentially learn constraints and dependencies over the latent space
• FC600-FC10-FC10-Softmax
• FC600-FC10-Optnet10-Softmax
• No marginal improvement
• No analysis

Experiment 4: Sudoku

• One-hot encoding
• CNN, OptNet do not know the rule
• Caveat
• Unstable
• No analysis on the learned constraints

Barron & Poole,

Fast Bilateral Solver, ECCV’16

Optimization in a Neural Network: Bilateral Solver

Gaussian Blur vs. Bilateral Filter

Bilateral Filtering

• Spatial coorindates: x, y
• Color coordinates: YUV
• Bilateral Space: spatial + color spaces

Evidence (Unary)

Smoothness (Pairwise)

Differentiation at the solution

Depth Superresolution

Stereo: Middlebury V3

Depth Superresolution

​

Filtering & Colorization

Semantic Segmentation

Zheng et al.,

Conditional Random Fields as Recurrent Neural Networks, ICCV‘15

Optimization in a Neural Network: Bilateral Solver

Fully Connected CRF with Gaussian Edge Potential

Fully Connected CRF

Meanfield Approximation and Iterative Update Eq.

CRF as RNN

• Unary potential
• CNN prediction
• Meanfield Iteration
• RNN

Experiments

Conclusion

Neural Network:

OptNet:

Fast Bilateral Solver:

CRF as RNN:

Conclusion

​

• Complex operation beyond linear multiplications
• Optimization
• Iterative methods
• Fixed point, Newton, Cutting Plane, Conjugate Gradient, ...
• Backprop through the solver
• Backprop through iterative methods
• CRF as RNN
• Gradient at the solution
• Given the solution, compute gradient for the rest of the vars.
• OptNet
• Fast Bilateral Solver