Paper Info

Title | ||
---|---|---|

Provably Correct Automatic Subdifferentiation for Qualified Programs. |

Abstract | ||
---|---|---|

The Cheap Gradient Principle [Griewank and Walther, 2008] - the computational cost of computing the gradient of a scalar-valued function is nearly the same (often within a factor of 5) as that of simply computing the 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 subderivatives: widely used ML libraries, including TensorFlow and PyTorch, do not correctly compute (generalized) subderivatives even on simple examples. This work considers the question: is there a Cheap Sub gradient Principle? Our main result shows that, under certain restrictions on our library of nonsmooth functions (standard in nonlinear programming), provably correct generalized subderivatives 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. |

Year | Venue | Keywords |
---|---|---|

2018 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018) | loss functions,computational cost,high dimensional,scalar function,nonlinear programming,scalar-valued function |

DocType | Volume | ISSN |

Conference | 31 | 1049-5258 |

Citations | PageRank | References |

0 | 0.34 | 0 |

Authors | ||

2 |

Authors (2 rows)

Cited by (0 rows)

References (0 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Sham Kakade | 1 | 4365 | 282.77 |

Lee, Jason D. | 2 | 711 | 48.29 |