An official website of the United States government
Emerging research in computer graphics, inverse problems, and machine learning requires us to differentiate and optimize parametric discontinuities. These discontinuities appear in object boundaries, occlusion, contact, and sudden change over time. In many domains, such as rendering and physics simulation, we differentiate the parameters of models that are expressed as integrals over discontinuous functions. Ignoring the discontinuities during differentiation often has a significant impact on the optimization process. Previous approaches either apply specialized hand-derived solutions, smooth out the discontinuities, or rely on incorrect automatic differentiation. We propose a systematic approach to differentiating integrals with discontinuous integrands, by developing a new differentiable programming language. We introduce integration as a language primitive and account for the Dirac delta contribution from differentiating parametric discontinuities in the integrand. We formally define the language semantics and prove the correctness and closure under the differentiation, allowing the generation of gradients and higher-order derivatives. We also build a system, Teg, implementing these semantics. Our approach is widely applicable to a variety of tasks, including image stylization, fitting shader parameters, trajectory optimization, and optimizing physical designs.
more »
« less
Designing Discontinuities
Discontinuities can be fairly arbitrary but also cause a significant impact on outcomes in social systems. Indeed, their arbitrariness is why they have been used to infer causal relationships among variables in numerous settings. Regression discontinuity from econometrics assumes the existence of a discontinuous variable that splits the population into distinct partitions to estimate causal effects. Here we consider the design of partitions for a given discontinuous variable to optimize a certain effect. To do so, we propose a quantization-theoretic approach to optimize the effect of interest, first learning the causal effect size of a given discontinuous variable and then applying dynamic programming for optimal quantization design of discontinuities that balance the gain and loss in the effect size. We also develop a computationally-efficient reinforcement learning algorithm for the dynamic programming formulation of optimal quantization. We demonstrate our approach by designing optimal time zone borders for counterfactuals of social capital.
more »
« less
- Award ID(s):
- 2033900
- PAR ID:
- 10440937
- Date Published:
- Journal Name:
- Neural Compression Workshop (ICML 2023)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper is concerned with the quantization setting where the encoder and the decoder have misaligned objectives. We first motivate the problem via a toy example which demonstrates the intricacies of the strategic quantization problem, specifically shows that iterative optimization of the decoder and the encoder mappings may not converge to a local optimum. As a remedy, we propose a dynamic programming based optimal optimization method, inspired by the early works in the quantization theory. We then extend our approach to variable-rate (entropy-coded) quantization. We finally present numerical results obtained via the proposed algorithms.more » « less
-
Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators.more » « less
-
Computations in physical simulation, computer graphics, and probabilistic inference often require the differentiation of discontinuous processes due to contact, occlusion, and changes at a point in time. Popular differentiable programming languages, such as PyTorch and JAX, ignore discontinuities during differentiation. This is incorrect forparametric discontinuities—conditionals containing at least one real-valued parameter and at least one variable of integration. We introduce Potto, the first differentiable first-order programming language to soundly differentiate parametric discontinuities. We present a denotational semantics for programs and program derivatives and show the two accord. We describe the implementation of Potto, which enables separate compilation of programs. Our prototype implementation overcomes previous compile-time bottlenecks achieving an 88.1x and 441.2x speed up in compile time and a 2.5x and 7.9x speed up in runtime, respectively, on two increasingly large image stylization benchmarks. We showcase Potto by implementing a prototype differentiable renderer with separately compiled shaders.more » « less
-
An effective multi-element simulation methodology for quantum eigenvalue problems is investigated. The approach is derived from a reduced-order model based on a data-driven learning algorithm, together with the concept of domain decomposition. The approach partitions the simulation domain of a quantum eigenvalue problem into smaller subdomains that, referred to as elements, could be the building blocks for quantum structures of interest. In this quantum element method (QEM), each element is projected onto a functional space represented by a set of basis functions (or modes) that are generated from proper orthogonal decomposition (POD). To construct a POD model for a large domain, these projected elements can be combined together, and the interior penalty discontinuous Galerkin method is applied to achieve the interface continuity and stabilize the numerical solution. The POD is able to optimize the basis functions specifically tailored to the geometry and parametric variations of the problem and can therefore substantially reduce the degree of freedom (DoF) needed to solve the Schrödinger equation. To understand the fundamental issues of the QEM, demonstrations in this study focus on examining the accuracy and DoF of the QEM influenced by the training settings for generation of POD modes, selection of the penalty number, suppression of interface discontinuities, structure size and complexity, etc. It has been shown that the QEM is able to achieve a substantial reduction in the DoF with a high accuracy even beyond the training conditions for the POD modes if the penalty number is selected within an appropriate range.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
