Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Unraveling the iterative CHAD

Created by
  • Haebom

Author

Fernando Lucatelli Nunes, Gordon Plotkin, Matthijs V ak ar

Outline

This study extends Combinatorial Homomorphic Automatic Differentiation (CHAD) to programs that include partial functions, data-dependent conditionals, and iterative statements (while loops). While maintaining the structure-preserving semantics principle of the original CHAD, we introduce 'iteration-extensive indexed categories' as a theoretical basis for iterative statements. Through this, we extend the CHAD transformation with the only structure-preserving function (iterative Freyd category morphism) that maps the iterative framework of the source language to the container categories of the target language, and prove the correctness of the extended transformation using a categorical model. The key is to structurally preserve the iterative structure of the source language through the mapping to the container categories of the target language.

Takeaways, Limitations

Takeaways:
Enables backpropagation automatic differentiation for a wider range of functional programs, including partial functions, data-dependent conditionals, and loops.
Rigorous proof of the correctness of automatic differentiation transformations through a categorical framework.
The introduction of 'iteration-extensive indexed categories' presents a novel way to systematically integrate iteration structures in dependent-typed programming languages.
Limitations:
Accessibility difficulties due to the complexity of the concept of iteration-extensive indexed categories.
Lack of information on actual programming language implementation and performance evaluation.
Lack of discussion about extensibility to other types of loops or control flow structures.
👍