Repository navigation
How GEAR Works
This page summarizes the method of the paper at a conceptual level. Section numbers refer to the paper.
GEAR solves bounded continuous nonlinear programs
minimize f_0(x) subject to f_i(x) <= 0, i = 1..m, x in [l, u]
Equalities and two-sided constraints are expressed with such rows. The objective and all constraints are the outputs of one computation graph over the vector x, so that a single pass evaluates all of them, for many boxes at once.
Neural network verifiers bound the output of a computation graph over an input box by propagating linear relaxations of each nonlinear operator backward through the graph. The result for each output f_i and box B is a linear function that lies below f_i on B. GEAR keeps these linear functions for every output instead of only their minimum over the box, and uses them for four purposes:
- a certified lower bound
Don the objective over the box, - a test whether the box contains no feasible point,
- clipping: using the constraints to shrink the box,
- a score for choosing the coordinate to split.
Because the bounds are computed for all boxes in a batch with tensor operations, the work runs on a GPU.
A box minimum of the objective's linear bound ignores the constraints. GEAR dualizes the constraints with multipliers and maximizes the resulting Lagrangian bound over the multipliers, which gives a lower bound that accounts for the linear bounds of the constraints. If the constraints' linear bounds contradict each other, the box is infeasible. Constraints are also used to shrink the box (clipping), after which the linear bounds are recomputed on the smaller box. Tighter relaxations for operators such as bilinear and quotient terms make the linear bounds themselves tighter.
Pruning boxes by their lower bound needs a feasible point, whose objective value P is an upper bound. GEAR runs a projected augmented Lagrangian method on the GPU: first-order steps on an objective-plus-penalty function, with projection onto the box, batched over many starting points and boxes. The multipliers from the dual computation provide starting information for this search. A point is accepted as an incumbent only after it is checked against the original constraints.
A box that cannot be pruned is split. GEAR scores each coordinate using the coefficients of the linear bounds weighted by the Lagrangian multipliers and by the box width, without bounding any child, and splits the coordinate with the highest score. Children inherit their parent's bounds, which stay valid on the smaller boxes.
Each iteration takes up to K open boxes with the lowest lower bounds and processes them as one batch: recompute linear bounds, test infeasibility, optimize the Lagrangian bound, discard boxes that are infeasible or whose lower bound reaches the best P, run the primal search on open boxes, and split the rest. The search stops when the relative gap (P - D) / max(1, |P|, |D|) is at most 1e-4, when the queue is empty, or at the time limit.
The lower bound D and the pruning decisions depend only on valid linear bounds. The heuristic parts (the choice of multipliers, the primal search, the branching score) affect speed, not the validity of D. Floating-point error in bound evaluation is accounted for in the direction that loosens the bound.
For the full description, the theory and the experiments, see the paper (Citing).