Tweeted twitter.com/StackCSTheory/status/1482095187606360065
fixed link
Source Link
wlad
  • 263
  • 1
  • 5

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation (as I've done here). The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation (as I've done here). The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

added 178 characters in body
Source Link
wlad
  • 263
  • 1
  • 5

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

deleted 3 characters in body
Source Link
wlad
  • 263
  • 1
  • 5

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of criticalmajor interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of critical interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

This is what I'm looking for. Take a recursive algorithm:

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:

def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.


My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

  • The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

  • Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers.

  • The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.

Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation. The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.

Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

added 18 characters in body
Source Link
wlad
  • 263
  • 1
  • 5
Loading
added 4 characters in body
Source Link
wlad
  • 263
  • 1
  • 5
Loading
added 88 characters in body
Source Link
wlad
  • 263
  • 1
  • 5
Loading
edited title
Link
wlad
  • 263
  • 1
  • 5
Loading
added 11 characters in body
Source Link
wlad
  • 263
  • 1
  • 5
Loading
deleted 1 character in body
Source Link
wlad
  • 263
  • 1
  • 5
Loading
Source Link
wlad
  • 263
  • 1
  • 5
Loading