The Cartesian reverse derivative is a categorical generalization of reverse-mode automatic differentiation. We use this operator to generalize several optimization algorithms, including a straightforward generalization of gradient descent and a novel generalization of Newton's method. We then explore which properties of these algorithms are preserved in this generalized setting. First, we show that the transformation invariances of these algorithms are preserved: while generalized Newton's method is invariant to all invertible linear transformations, generalized gradient descent is invariant only to orthogonal linear transformations. Next, we show that we can express the change in loss of generalized gradient descent with an inner product-like expression, thereby generalizing the non-increasing and convergence properties of the gradient descent optimization flow. Finally, we include several numerical experiments to illustrate the ideas in the paper and demonstrate how we can use them to optimize polynomial functions over an ordered ring.

Problem statement and motivation There has been a recent interest in studying systems of ODEs that solve an optimization problem -- also known as optimization flows -- with the understanding that their study can lead to the analysis and design of discrete-time solvers of optimization problems - also known as optimization algorithms. This interest is motivated by the fact that analyzing a system of ODEs can be much simpler than analyzing a discrete system. Indeed, the ambitious goal of this research area is to find a "general theory mapping properties of ODEs into corresponding properties for discrete updates" -- as quoted from the seminal work [20]. Our paper aims to provide a solution to this problem. Ideally, the desired pipeline is to first design an optimization flow -- using all the machinery of dynamical systems analysis -- with good stability and convergence properties, and then formulate a principled way of guaranteeing such good properties translate to its associated optimization algorithm through discretization. A first problem in the literature is that the analysis of the optimization algorithm is commonly done separately or independently from the analysis of its associated optimization flow (e.g., see [24, 25, 17, 26, 18, 12]), instead of the former analysis following directly as a consequence of the latter one. For example, separate Lyapunov analyses have been made for optimization flows and their associated algorithms. This problem diminishes one of the very first motivations of analyzing a system of ODEs, namely, that its analysis should directly establish properties of its associated discretization.

Abstract-- Logic synthesis requires extensive tuning of the synthesis optimization flow where the quality of results (QoR) depends on the sequence of optimizations used. Efficient design space exploration is challenging due to the exponential number of possible optimization permutations. Therefore, automating the optimization process is necessary. In this work, we propose a novel reinforcement learning-based methodology that navigates the optimization space without human intervention. We demonstrate the training of an Advantage Actor Critic (A2C) agent that seeks to minimize area subject to a timing constraint. Using the proposed methodology, designs can be optimized autonomously with no-humans in-loop. Evaluation on the comprehensive EPFL benchmark suite shows that the agent outperforms existing exploration methodologies and improves QoRs by an average of 13%. Logic synthesis transforms a high-level description of a design into an optimized gate-level representation. Modern logic synthesis tools represent a given design as an And-Inverter Graph (AIG), which encodes representative characteristics for optimizing Boolean functions.