Differentiable Approximations for Distance Queries

2025/01/01 by Ahmed Abdelkader, David M. Mount
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Optimization and Search Problems #acm:52C45 #cs.CG #msc:52C45

paper · pdf · doi:10.1137/1.9781611978322.172

published as ACM-SIAM Symposium on Discrete Algorithms (2025) 5065-5099 · Presented at SODA 2025

openalex publication_date 2025/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29 · arxiv created 2026/07/30 · arxiv updated 2026/08/03

Abstract

The widespread use of gradient-based optimization has motivated the adaptation of various classical algorithms into differentiable solvers compatible with learning pipelines. In this paper, we investigate the enhancement of traditional geometric query problems such that the result consists of both the geometric function as well as its gradient. Specifically, we study the fundamental problem of distance queries against a set of points P in ℝd, which also underlies various similarity measures for learning algorithms.

Citations

• A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
• Smooth Distance Approximation
• A Near-Linear Time Algorithm for the Chamfer Distance
• Economical Convex Coverings and Applications
• Transformer-Based Learned Optimization
• Lipschitz Continuous Algorithms for Graph Problems
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
• Theseus: A Library for Differentiable Nonlinear Optimization
• Plenoxels: Radiance Fields without Neural Networks
• Brax -- A Differentiable Physics Engine for Large Scale Rigid Body Simulation
• DeepMesh: Differentiable Iso-Surface Extraction
• Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarking
• A Survey of Algorithms for Geodesic Paths and Distances
• Differentiable Convex Optimization Layers
• DiffTaichi: Differentiable Programming for Physical Simulation
• SATNet: Bridging deep learning and logical reasoning using a\n differentiable satisfiability solver
• Topological Stability of Kinetic k-Centers
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Neural Ordinary Differential Equations
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Approximating Minimization Diagrams and Generalized Proximity Search
• Выпуклая оптимизация