# Algorithm Configuration for Structured Pfaffian Settings arXiv: https://arxiv.org/abs/2409.04367 ยท HTML: https://mlsanity.com/paper/2409.04367/ ## Key facts - Cited by 11 papers in the map (data through 14 Oct 2026). - Builds on 37 of its 83 references that are in the map. - First posted on arXiv 6 Sep 2024. ## Builds on (most cited first, 30 of 37) - [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018) - [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020) - [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018) - [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020) - [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015) - [Learning Algebraic Multigrid Using Graph Neural Networks](https://mlsanity.com/paper/2003.05744/) (2020) - [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019) - [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017) - [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021) - [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016) - [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019) - [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020) - [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022) - [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022) - [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020) - [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022) - [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018) - [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021) - [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021) - [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019) - [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019) - [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021) - [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022) - [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021) - [Learning Complexity of Simulated Annealing](https://mlsanity.com/paper/2003.02981/) (2020) - [Refined bounds for algorithm configuration: The knife-edge of dual class approximability](https://mlsanity.com/paper/2006.11827/) (2020) - [An Analysis of Robustness of Non-Lipschitz Networks](https://mlsanity.com/paper/2010.06154/) (2020) - [Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice](https://mlsanity.com/paper/2007.08864/) (2020) - [Online Page Migration with ML Advice](https://mlsanity.com/paper/2006.05028/) (2020) - [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022) ## Built on by (most cited first, 11 of 11) - [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025) - [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025) - [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025) - [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026) - [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026) - [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025) - [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025) - [Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming](https://mlsanity.com/paper/2606.08638/) (2026) - [Efficient Online Proportional Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2607.10963/) (2026) - [Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws](https://mlsanity.com/paper/2608.01670/) (2026) - [Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2608.17343/) (2026) ## Abstract (arXiv) Data-driven algorithm design automatically adapts algorithms to specific application domains, achieving better performance. In the context of parameterized algorithms, this approach involves tuning the algorithm's hyperparameters using problem instances drawn from the problem distribution of the target application domain. This can be achieved by maximizing empirical utilities that measure the algorithms' performance as a function of their hyperparameters, using problem instances. While empirical evidence supports the effectiveness of data-driven algorithm design, providing theoretical guarantees for several parameterized families remains challenging. This is due to the intricate behaviors of their corresponding utility functions, which typically admit piecewise discontinuous structures. In this work, we present refined frameworks for providing learning guarantees for parameterized data-driven algorithm design problems in both distributional and online learning settings. For the distributional learning setting, we introduce the textitPfaffian GJ framework, an extension of the classical textitGJ framework, that is capable of providing learning guarantees for function classes for which the computation involves Pfaffian functions. Unlike the GJ framework, which is limited to function classes with computation characterized by rational functions, our proposed framework can deal with function classes involving Pfaffian functions, which are much more general and widely applicable. We then show that for many parameterized algorithms of interest, their utility function possesses a textitrefined piecewise structure, which automatically translates to learning guarantees using our proposed framework.