Incorporating piecewise linear functions with constant regions in backpropagation

Date

2025-1

Author

Doğan, Adnan Harun

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

60
views

83
downloads

Cite This

Solving many fundamental problems, such as travelling salesman (TS), shortest path (SP), and graph matching (GM), requires the use of piecewise linear functions with constant regions (PFC). Although using such functions in deep neural networks (DNN) is promising, integrating a PFC into a DNN poses a significant challenge for gradient-based iterative optimizations. That is, traditional backpropagation methods struggle when encountering PFCs in DNN pipelines, leading to zero or undefined gradients that stall training. Although various heuristics-based gradient approximations exist, these approaches often remain task-specific and theoretically ungrounded. This thesis addresses the need for a unified and theoretically sound methodology for gradient approximation through PFC layers. First, it provides a comprehensive review and comparative analysis of existing techniques, highlighting that, despite their diversity, most methods share a common underlying principle. Building on these insights, the thesis introduces the Generalized Update (GU) as a unifying framework capable of representing known approximations as special cases and inspiring the development of new variants. The thesis also integrates Optimal Transport (OT) theory to replace non-differentiable label assignment in models like DEtection TRansformer (DETR), demonstrating how OT-based solutions can enhance tasks involving discrete decision-making. Overall, the thesis empirically validates the Generalized Update method’s effectiveness across multiple domains, including object detection, combinatorial optimization, and quantization. By closing the theoretical gap, offering a unified perspective, and validating the proposed approach in practice, this work provides a robust foundation for incorporating PFCs into DNN pipelines, ultimately broadening the scope and applicability of gradient-based optimization methods.

Subject Keywords

Gradients of Piecewise Linear Functions with Constant Regions, Combinatorial Optimization, Optimal Transport, Error-driven Update, Identity Update, Bipartite Matching in Object Detection

URI

https://hdl.handle.net/11511/113504

Collections

Graduate School of Natural and Applied Sciences, Thesis