{"id":502,"date":"2023-04-14T15:12:41","date_gmt":"2023-04-14T15:12:41","guid":{"rendered":"https:\/\/todaysainews.com\/index.php\/2023\/04\/14\/beyond-automatic-differentiation-google-ai-blog\/"},"modified":"2025-04-27T07:33:42","modified_gmt":"2025-04-27T07:33:42","slug":"beyond-automatic-differentiation-google-ai-blog","status":"publish","type":"post","link":"https:\/\/todaysainews.com\/index.php\/2023\/04\/14\/beyond-automatic-differentiation-google-ai-blog\/","title":{"rendered":"Beyond automatic differentiation \u2013 Google AI Blog"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\nPosted by Matthew Streeter, Software Engineer, Google Research<\/span><\/p>\n

<\/p>\n

\nDerivatives<\/a> play a central role in optimization and machine learning. By locally approximating a training loss<\/a>, derivatives guide an optimizer toward lower values of the loss. Automatic differentiation frameworks such as TensorFlow<\/a>, PyTorch<\/a>, and JAX<\/a> are an essential part of modern machine learning, making it feasible to use gradient-based optimizers to train very complex models.\n<\/p>\n

<\/p>\n

\nBut are derivatives all we need? By themselves, derivatives only tell us how a function behaves on an infinitesimal<\/a> scale. To use derivatives effectively, we often need to know more than that. For example, to choose a learning rate<\/a> for gradient descent<\/a>, we need to know something about how the loss function behaves over a small but finite<\/em> window. A finite-scale analogue of automatic differentiation, if it existed, could help us make such choices more effectively and thereby speed up training.\n<\/p>\n

\nIn our new paper “Automatically Bounding The Taylor Remainder Series: Tighter Bounds and New Applications<\/a>“, we present an algorithm called AutoBound that computes polynomial upper and lower bounds on a given function, which are valid over a user-specified interval<\/a>. We then begin to explore AutoBound’s applications. Notably, we present a meta-optimizer called SafeRate that uses the upper bounds computed by AutoBound to derive learning rates that are guaranteed to monotonically reduce a given loss function, without the need for time-consuming hyperparameter tuning.\u00a0We are also making AutoBound available as an open-source library<\/a>.<\/p>\n

<\/p>\n

The AutoBound algorithm<\/h2>\n

\nGiven a function f<\/em><\/code> and a reference point x0<\/sub><\/em><\/code>, AutoBound computes polynomial upper and lower bounds on f<\/em><\/code> that hold over a user-specified interval called a trust region<\/em>. Like Taylor polynomials<\/a>, the bounding polynomials are equal to f<\/em><\/code> at x0<\/sub><\/em><\/code>. The bounds become tighter as the trust region shrinks, and approach the corresponding Taylor polynomial as the trust region width approaches zero.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Automatically-derived quadratic upper and lower bounds on a one-dimensional function f, centered at x0<\/sub>=0.5. The upper and lower bounds are valid over a user-specified trust region, and become tighter as the trust region shrinks.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nLike automatic differentiation, AutoBound can be applied to any function that can be implemented using standard mathematical operations. In fact, AutoBound is a generalization of Taylor mode automatic differentiation<\/a>, and is equivalent to it in the special case where the trust region has a width of zero.\n<\/p>\n

\nTo derive the AutoBound algorithm, there were two main challenges we had to address:\n<\/p>\n

    \n
  1. We had to derive polynomial upper and lower bounds for various elementary functions, given an arbitrary reference point and arbitrary trust region.\n<\/li>\n
  2. We had to come up with an analogue of the chain rule<\/a> for combining these bounds.\n<\/li>\n<\/ol>\n

    <\/p>\n

    Bounds for elementary functions<\/h2>\n

    \nFor a variety of commonly-used functions, we derive optimal<\/em> polynomial upper and lower bounds in closed form. In this context, “optimal” means the bounds are as tight as possible, among all polynomials where only the maximum-degree coefficient<\/a> differs from the Taylor series. Our theory applies to elementary functions, such as exp<\/em><\/code> and log<\/em><\/code>, and common neural network activation functions, such as ReLU<\/a><\/code> and Swish<\/a><\/code>. It builds upon and generalizes earlier work<\/a> that applied only to quadratic bounds, and only for an unbounded trust region.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Optimal quadratic upper and lower bounds on the exponential function, centered at x0<\/sub>=0.5 and valid over the interval [0, 2].<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/p>\n

    A new chain rule<\/h2>\n

    \nTo compute upper and lower bounds for arbitrary functions, we derived a generalization of the chain rule that operates on polynomial bounds. To illustrate the idea, suppose we have a function that can be written as\n<\/p>\n

    \nand suppose we already have polynomial upper and lower bounds on g<\/em><\/code> and h<\/em><\/code>. How do we compute bounds on f<\/em><\/code>?<\/p>\n

    \nThe key turns out to be representing the upper and lower bounds for a given function as a single<\/em> polynomial whose highest-degree coefficient is an interval<\/a> rather than a scalar. We can then plug the bound for h<\/em><\/code> into the bound for g<\/em><\/code>, and convert the result back to a polynomial of the same form using interval arithmetic<\/a>. Under suitable assumptions about the trust region over which the bound on g<\/em><\/code> holds, it can be shown that this procedure yields the desired bound on f<\/em><\/code>.<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    The interval polynomial chain rule applied to the functions h(x) = sqrt(x) and g(y) = exp(y), with x0<\/sub>=0.25 and trust region [0, 0.5].<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nOur chain rule applies to one-dimensional functions, but also to multivariate functions, such as matrix multiplications and convolutions.\n<\/p>\n

    <\/p>\n

    Propagating bounds<\/h2>\n

    \nUsing our new chain rule, AutoBound propagates interval polynomial bounds through a computation graph from the inputs to the outputs, analogous to forward-mode automatic differentiation<\/a>.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Forward propagation of interval polynomial bounds for the function f(x) = exp(sqrt(x)). We first compute (trivial) bounds on x, then use the chain rule to compute bounds on sqrt(x) and exp(sqrt(x)).<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nTo compute bounds on a function f(x)<\/em><\/code>, AutoBound requires memory proportional to the dimension of x<\/em><\/code>. For this reason, practical applications apply AutoBound to functions with a small number of inputs. However, as we will see, this does not prevent us from using AutoBound for neural network optimization.<\/p>\n

    <\/p>\n

    Automatically deriving optimizers, and other applications<\/h2>\n

    \nWhat can we do with AutoBound that we couldn’t do with automatic differentiation alone?\n<\/p>\n

    \nAmong other things, AutoBound can be used to automatically derive problem-specific, hyperparameter-free optimizers that converge from any starting point. These optimizers iteratively reduce a loss by first using AutoBound to compute an upper bound on the loss that is tight at the current point, and then minimizing the upper bound to obtain the next point.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Minimizing a one-dimensional logistic regression loss using quadratic upper bounds derived automatically by AutoBound.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nOptimizers that use upper bounds in this way are called majorization-minimization<\/a> (MM) optimizers. Applied to one-dimensional logistic regression, AutoBound rederives an MM optimizer first published in 2009<\/a>. Applied to more complex problems, AutoBound derives novel MM optimizers that would be difficult to derive by hand.\n<\/p>\n

    \nWe can use a similar idea to take an existing optimizer such as Adam<\/a> and convert it to a hyperparameter-free optimizer that is guaranteed to monotonically reduce the loss (in the full-batch setting). The resulting optimizer uses the same update direction as the original optimizer, but modifies the learning rate by minimizing a one-dimensional quadratic upper bound derived by AutoBound. We refer to the resulting meta-optimizer as SafeRate.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Performance of SafeRate when used to train a single-hidden-layer neural network on a subset of the MNIST<\/a> dataset, in the full-batch setting.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nUsing SafeRate, we can create more robust variants of existing optimizers, at the cost of a single additional forward pass that increases the wall time<\/a> for each step by a small factor (about 2x in the example above).\n<\/p>\n

    \nIn addition to the applications just discussed, AutoBound can be used for verified numerical integration<\/a> and to automatically prove sharper versions of Jensen’s inequality<\/a>, a fundamental mathematical inequality used frequently in statistics and other fields.\n<\/p>\n

    <\/p>\n

    Improvement over classical bounds<\/h2>\n

    \nBounding the Taylor remainder term<\/a> automatically is not a new idea. A classical technique produces degree k<\/em><\/code> polynomial bounds on a function f<\/em><\/code> that are valid over a trust region [a<\/em>, b<\/em>]<\/code> by first computing an expression for the k<\/em><\/code>th derivative of f<\/em><\/code> (using automatic differentiation), then evaluating this expression over [a<\/em>,b<\/em>]<\/code> using interval arithmetic.<\/p>\n

    \nWhile elegant, this approach has some inherent limitations that can lead to very loose bounds, as illustrated by the dotted blue lines in the figure below.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Quadratic upper and lower bounds on the loss of a multi-layer perceptron<\/a> with two hidden layers, as a function of the initial learning rate. The bounds derived by AutoBound are much tighter than those obtained using interval arithmetic evaluation of the second derivative.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/p>\n

    Looking forward<\/h2>\n

    \nTaylor polynomials have been in use for over three hundred years, and are omnipresent in numerical optimization and scientific computing. Nevertheless, Taylor polynomials have significant limitations, which can limit the capabilities of algorithms built on top of them. Our work is part of a growing literature that recognizes these limitations and seeks to develop a new foundation upon which more robust algorithms can be built.\n<\/p>\n

    \nOur experiments so far have only scratched the surface of what is possible using AutoBound, and we believe it has many applications we have not discovered. To encourage the research community to explore such possibilities, we have made AutoBound available as an open-source library built on top of JAX<\/a>. To get started, visit our GitHub repo<\/a>.<\/p>\n

    <\/p>\n

    Acknowledgements<\/h2>\n

    \nThis post is based on joint work with Josh Dillon. We thank Alex Alemi and Sergey Ioffe for valuable feedback on an earlier draft of the post.<\/em>\n<\/p>\n<\/div>\n

    [ad_2]
    \n
    Source link <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

    [ad_1] Posted by Matthew Streeter, Software Engineer, Google Research Derivatives play a central role in optimization and machine<\/p>\n","protected":false},"author":2,"featured_media":503,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20],"tags":[],"class_list":["post-502","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-google-ai"],"_links":{"self":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/502","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/comments?post=502"}],"version-history":[{"count":1,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/502\/revisions"}],"predecessor-version":[{"id":2821,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/502\/revisions\/2821"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media\/503"}],"wp:attachment":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media?parent=502"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/categories?post=502"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/tags?post=502"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}