Timezone: »

 
Poster
Provably Correct Automatic Sub-Differentiation for Qualified Programs
Sham Kakade · Jason Lee

Tue Dec 04 02:00 PM -- 04:00 PM (PST) @ Room 210 #2
in Tue Poster Session B »
The \emph{Cheap Gradient Principle}~\citep{Griewank:2008:EDP:1455489} --- the computational cost of computing a $d$-dimensional vector of partial derivatives of a scalar function is nearly the same (often within a factor of $5$) as that of simply computing the scalar function itself --- is of central importance in optimization; it allows us to quickly obtain (high-dimensional) gradients of scalar loss functions which are subsequently used in black box gradient-based optimization procedures. The current state of affairs is markedly different with regards to computing sub-derivatives: widely used ML libraries, including TensorFlow and PyTorch, do \emph{not} correctly compute (generalized) sub-derivatives even on simple differentiable examples. This work considers the question: is there a \emph{Cheap Sub-gradient Principle}? Our main result shows that, under certain restrictions on our library of non-smooth functions (standard in non-linear programming), provably correct generalized sub-derivatives can be computed at a computational cost that is within a (dimension-free) factor of $6$ of the cost of computing the scalar function itself.
Keywords: Non-Convex Optimization · Optimization for Deep Networks · AutoML
[ Paper] 

Author Information

Sham Kakade (University of Washington)
Jason Lee (University of Southern California)

More from the Same Authors