Algorithm Configuration for Structured Pfaffian Settings
Authors: Maria Florina Balcan
Anh Tuan Nguyen
Dravyansh Sharma
Venue: Accepted by TMLR ()

Abstract: Data-driven algorithm design uses historical problem instances to automatically adjust and optimize algorithms to their application domain, typically by selecting algorithms from parameterized families. While the approach has been highly successful in practice, providing theoretical guarantees for several algorithmic families remains challenging. This is due to the intricate dependence of the algorithmic performance on the parameters, often exhibiting a piecewise discontinuous structure. In this work, we present new frameworks for providing learning guarantees for parameterized data-driven algorithm design problems in both statistical and online learning settings.
For the statistical learning setting, we introduce the Pfaffian GJ framework, an extension of the classical Goldberg-Jerrum (GJ) framework (Bartlett et al., 2022; Goldberg & Jerrum, 1993), 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 (quotients of two polynomials), 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 refined piecewise structure, which automatically translates to learning guarantees using our proposed framework.
For the online learning setting, we provide a new tool for verifying the dispersion property of a sequence of loss functions, a sufficient condition that allows no-regret learning for sequences of piecewise structured loss functions where the piecewise structure involves Pfaffian transition boundaries. We use our framework to provide novel learning guarantees for many challenging data-driven design problems of interest, including data-driven linkage-based clustering, graph-based semi-supervised learning, and regularized logistic regression.

Published in Transactions on Machine Learning Research (04/2025)
Algorithm Configuration for Structured Pfaffian Settings
Maria Florina Balcan
ninamffccs.co cmm.ess.ss.ccc..... edbu
School of Computer Science Carnegie Mellon University
Anh Tuan Nguyen
atnguyen@cs. wwtppyyee@csccm...coo cmnu. edu
Machine Learning Department
Carnegie Mellon University
Dravyansh Sharma"
dravy@ttic.co edu
Toyota Technological Institute at Chicago
Reviewed on OpenReview: https: // openreveew. net/ forum? id= Xmk1orbell6
Abstract
Data-driven algorithm design uses historical problem instances to automatically adjust and optimize algorithms to their application domain, typically by selecting algorithms from pa- rameterized families. While the approach has been highly successful practice, providing theoretical guarantees for several algorithmic families remains challenging. This is due to the intricate dependence of the algorithmie performance on the parameters, often exhibiting piecewise discontinuous structure. In this work, present new frameworks for provid- ing learning guarantees for parameterized data-driven algorithm design problems in both statistical and online learning settings.
For the statistical lcarning setting, we introduce the Pfoffian GJ framework, an extension of the classical GoldberyyJerrun (GJ) frumework (Bartlett et al. 2022 Goldberg & Jerrum, 1993), that capable of providing learning guarantees for function classes for which the com- putation involves Pfaffian functions. Unlike the GJ framework, which is limited function classes with computation characterized by rational functions (quolients of two polynomials), our proposed framework are much more general and widely applicable. We then show that for many parameterized algorithms of interest, their utility function possesses a refined piecewise structure, which automatically translates to learning guarantees using our proposed framework.
deal with function classes involving Pfaffian functions, which
For the online learning setting, we provide new tool for verifying the dispersion prop- crty of a sequence of loss functions, a sufficient condition that allows no-regret learning for sequences of piecewise structured loss functions where the piecewise structure involves Pfaffian transition boundaries. We use our framework to provide novel learning guarantees for many challenging data-driven design problems of interest, including data-driven linkage- based clustering, graph-based based semi-supervised learning, and regularized logistic regression.
1 Introduction
Data-driven algorithm design Ailon al. 2011 Gupta & Roughgarden, 2016 Balcan 2020 modern approach that develops and analyzes algorithms based on the assumption that problem instances come from underlying application domain. For example, news website might have its own patterns in how bots be leveraged to tune clustering
and humans interact with their content, and this distinctive information algorithms that distinguish automated crawls from human access patterns. Unlike traditional worst-case or average-case analyses, this approach leverages observed problem instances to design algorithus that achieve
"Most of the work done when DS was CMU.

---

Published in Transactions on Machine Learning Research (04/2025)
high performance for specific problem domains. For many applications, say combinatorial partitioning prob- lems (Balcan et al. 2017) mixed integer linear programming (Balcan et al. 2018a), algorithms are often parameterized, meaning they are equipped with tunable hyperparameters which significantly influence their performance. We develop general techniques for establishing learning guarantees for data-driven algorithm selection by learning the parameters from historical problem instances. Prior approaches for obtaining con- crete learning guarantees based on the classical Goldberg-Jrrum (GJ) (Goldberg & Jerrum 1993; Bartlett eet al., 2022) framework are limited to families where, roughly speaking, the algorithmic performance as a function of the hyperparameters has piecewise polynomial structure. Our techniques apply to larger variety of parameterized algorithm families characterized by piecewise Pfaffian functions, which is broader class of functions that also includes exponential and logarithmic functions.
Applications of data- driven algorithm design span varions fundamental areas. These include low-rank ap- proximation [Indyk et al., 2019 2021; Li et al. 2023), sparse linear systems solvers (Luz et al., 2020). dimensionality reduction (Ailon et al. 2021). and many more fundamental problems. This empirical success underscores the necessity for a theoret understanding of this approach. Intensive efforts have been made towards theoretical understanding for data-driven algorithm design, including learning guarantees for nu- merical linear algebra methods (Bartlett et al. 2022). tuning regularization hyperparameters for regression problems (Balcan et al.] 2022a, 2023b), , unsupervised and semi-supervised learning (Balcan et al. 2018c
2020a;
Balcan & Sharma 2021 1 applications to integer and mixed-integer programming (Balcan et al.
2018a
2021ep.
Prior theoretical work on data-driven algorithm design focuses on two main settings: statistical learning [Balcan et al.) 2021a; Bartlett et al., 2022) and online learning (Balcan et al.) 2018b). In the statistical learning setting, there is a learner trying to optimize hyperparameters for the algorithm within a specific domain. The learner has access to problem instances from that domain, which are assumed to be drawn from a fixed but unknown problem distribution. In this case, a key question is understanding the sample complexity, i.c. answering the following question: how many problem instances are required to learn hyperparamoters that yield good expected performance on future unseen problem instances? In the online learning setting, there is a sequence of problem instances chosen by an adversary arriving over time. The goal now to design no-regret learning algorithm: adjusting the algorithm's hyperparameters on the fly that the difference between the average utility of the learner and the utility corresponding to the best fixed hyperparameters in hindsight, that is, the learner's regret, diminishes over time. We develop tools to answer both these questions, applicable to a broad class of problems.
Technical formulation. Typically, the performance of an algorithm is evaluated by a specific utility function, measuring its run-time, memory, or solution quality, for example. More formally, for an algorithm with input instance space X and parameterized by a parameter class A, consider the utility function class u = dm(u,= : X + [0, H] A}, where un (x) gauges the performance of the algorithm with hyperparamoters when run on problem instance
X, and H is an upper- bound for the utility value. In the statistical learning data-driven algorithm design setting, we assume an unknown underlying distribution 'D over X. representing the application domain on which the algorithm operates. In this setting, designing parameterized algorithms tailored to a specific domain corresponds to the optimal selection of hyperparameters a for the given application- speciffi distribution D.
The main challenge in establishing learning guarantees for the utility function classes lies in the complex structure of the utility function. In other words, even minimal perturbation in can lead to drastic change in the performance of the algorithm, making the analysis of such classes of utility functions particularly challenging. In response to this challenge, prior work takes an alternative approach by analyzing the dual utility function class 41" = ( A + [0, H x E X). Each function in the dual function class often admits piecewise structured behavior (alccan et al., 202 2017 Bartlett et al. 2022).
Building upon this observation, in the statistical learning setting, Balcan et al. (2021a) propose a general approach that analyzes the learnability of the utility function class via the -heoorett complexity of the piece and boundary function classes induced by the piccewise structure of the dual. Approaching this from an alternative perspective, Bartlett et al. (2022) introduced new version of the GJ framework, where the piecewise structure of the dual function is expressed as a tree of computations involving fundamental
2

---

Published in Transactions on Machine Learning Research (04/2025)
arithmetic operations at the nodes and branches according to simple conditional statements. The complexity of the operations and the expressions that appear across the tree are shown to be related to the sample complexity of parameter tuning. Despite their broad applicability, these general frameworks have inherent limitations. In the statistical learning setting, the framework introduced by [Balcan et al. (2021a) reduces the problem of computing the learning-theoretic complexity of a piecewise structured ubility function to bounding the complexity of the corresponding piece and boundary functions, but this might be challenging to compute for certain function classes (see e.g., Bartlett et al. 2022). On the other hand, the GJ framework instantiated by Bartlett et al. (2022) is limited to the cases where the computation of utility functions only involves rational functions (i.e., ratios of polynomials) of the hyperparameters.
In the online learning setting, prior work has similar limitations. [alcan et al. (011 introduce disper- sion, which is a sufficient condition for no-regret learning of piecewise Lipschitz functions. Essentially, the dispersion property implics that if the discontinuities of utility function sequences do not densely concentrate any small region of the hyperparameter space, then no-regret learning possible. However, the dispersion property is generally challenging to verify (Balcan et. al.) 2018b; 2020b] Balcan & Sharma 2021), and requires further assumptions on the discontinuities of the utility function sequence. Moreover, when the form of the discontinuitics goes beyond affine and rational functions, prior techniques for verifying dispersion no longer apply.
Motivated by the limitations of prior research, part of this work aims to present theoretical frameworks for data-driven algorithm design when the utility function admits a specific structure. In the statistical learning setting, we introduce a powerful Pfaffian GJ framework that can be used to establish learning guarantees for function classes whose discontinuity involves Pfaffian functions (Definition f. Roughly speaking, the Pfaffian function class is very general class of functions that captures wide range of functions of interest, including rational, exponential, logarithmic, and combinations of these functions. Furthermore, we demonstrate that many data-driven algorithm design problems exhibit a specific Pfaffian piecewise structure, which, when combined with the Pfaffian GJ framework, can cstablish learning guarantecs for these problems. In the online learning setting, we introduce a novel tool to verify the dispersion property, where the discontinuilies of the utility function sequence involve Pfaffian functions, going beyond affine and rational functions.
Another aim of this work is to provide learning guarantoes for several under-investigated data-driven al- gorithm design problems, where the piecewise structure of the utility functions involves Pfaffian functions. The problems we consider have been investigated in simpler settings, including data-driven agglomerative hierarchical clustering (Balcan et al. 2017 2020a), data-driven semi-supervised learning (Balcan & Sharma 2021 and data-driven regularized logistic regression (Balcan et al. 2023b). However, previous investigations have limitations: they either have missing results for natural extensions of the settings under study (Balcan) et al., 2017 [alccan & Sharma 2021), require strong assumptions (Balcan et al., 2020a), or solely consider statistical learning settings (Balcan et al. 2023b). Moreover, we emphasize that the techmiques used in prior work are insufficient and connot be applied in our settings, which involve Pfatfian function analysis.
By carcfully analyzing the utility functions associated with these problems, we uncover their underlying Pfaffian structure and carefully control the corresponding Pfasfian complexity, which allows us to leverage our proposed framework to establish learning guarantees. It is important to note that analyzing the Pfaffian structure for specific problems poses a significant challenge. A loose estimation of the Pfaffian function complexity when combined with our proposed framework would still lead to weak learning guarantees.
Overview of the Pfaffian GJ framework. A Pfaffian GJ algorithm takes as input real-valued parame- ters a E A C Rd. Intuitively, the computation of the dual function w can be expressed via a tree using only certain kinds of operations (including Pfaffian functions). More precisely, for each input E X' and each real threshold r, one constructs fixed binary tree Tz, that can compute sign(u -r) for each e A. Each node v of the tree corresponds to fixed function evaluation fu, involving binary arithmetic operations (i.e. one of {+, -, +)) or a Pfalfian function, and the arguments include the parameters a a= (a),...,, .a)) and previously computed values on the path from the root to the node. The left and right children of v correspond to f. 2 0 and f. < 0 respectively. The tree can be used to compute sign (a) -r) for any a A by ovaluating a series of expressions along some root-to-leaf path (see Figure for a simple illustration). The Pfaffian GJ framework then corresponds to the following recipe for bounding the learning-theoree com-
3

---

Published in Transactions on Machine Learning Research (04/2025)
Problem instance x, threshold
Pfaffian GJ algorithm I x,
combination of following operators
Parameters
0?
1a(x)) 2 r?
then
else
R1 ag
U
① E |, x, +1
1: - R pfaffian operators
8, D; (i = 1, 2) E (a1, ... ... U Vipreviously computed values)
Figure 1: A simple illustration of the general idea of the Pfaffian GJ framework. Given problem instance a and real-valued threshold r, Pfaffian GJ algorithm Par takes as the inputs any possible parameters a = (01, .d) and outputs if ua (x) 2 by combining basic arithmetic operators, Pfaffian functions, and conditional statements. If we can bound the complexity of r aa,, our results imply that we can bound the pseudo dimension of the utility function class U.
plexity of U: Express the computation of the dual function u as a tree Ta. for any a, r and give bounds on the complexity of the tree (in terms of the number of distinct functional expressions across all nodes as well as the worst-case complexity of any functional expression). This automatically yields a bound on the sample complexity of tuning the parameters a using our results.
Contributions. In this work, we provide new framework for theoretical analysis of tatta-drive algorithm design problems. We then investigate many under-investigated data-driven algorithm design problems, analyzing their underlying problem structure, and then leveraging our newly proposed framework to provide learning guarantees for those problems. Concretely,
We present the Pfaffian GJ framework (Definition Theorem 4.2), pscudo-dimension of various function classes of interest in the data-driven setting. This framework draws inspiration from the refined version of the GJ framework introduced by BBartlttt et al. 2022 However, in contrast to the conventional GJ framework which is only capable of handling computation related to rational functions, the Pfaffian GJ framework can handle computations that involve Pfaffian functions (Definition 4 a much broader function class significantly increasing its applicability (see Figure [ for an illustration). We note that our proposed Pfaffian GJ framework of independent interest and can be applied to other research areas beyond data-driven algorithm design.
general approach for analyzing the
For the statistical learning setting, we introduce a refined notion of piecewise structure (Definition g see Figure for an example) for the dual utility function class, which applies whenever the piece and boundary functions are Pfaffian (see Figure 4 In contrast to the prior piecewise structure proposed by [Balcan et al. (2021a): Bartlett et al. (2022). our framework can be used to obtain concrete learning guarantees when the piece and boundary functions belong to the class of Pfaffian functions, which includes widely used utility functions, including the exponential and logarithmic functions. We then show how the refined piecewise structure can be combined with the newly proposed Pfaffian GJ framework to provide learning guarantees Theorem 5.2p for problems that satisfy this property.
For online data-driven algorithm design, we introduce general approach Theorem 7.2 Theorem 7.3) for verilying the dispersion property (Balcan et al. 2018b) a sufficient condition for online learning in data- driven algorithm design. Prior work (Balcan et al. 2020b Balcan Sharma 2021 provides techniques for verifying dispersion only when the piece boundarics are algebraic functions. We significantly expand the class of functions for which online learning guarantees may be obtained by establishing a novel tool which applies for Pfaffian boundary functions.
4

---

Published in Transactions on Machine Learning Research (04/2025)
Structure of the piecewise function u:
Figure 2: A simple illustration of Pfalfian piecewise structure. For each problem instance æ, there are Pfaffian boundaries that partition the space parameters a into regions. In each region, the value u, (a) is a Pfaffian function. See Figure 3 for more details.
We derive novel learning guarantees for variety of understudied data-driven algorithm design problems, including data-driven agglomerative clustering (Theorem 6.1], data-driven graph-based semi-supervised learning [Theorem 6.4/. We also recover the guarantee for data-driven regularized logistic regression in previous work by Balcan et al. (2023b). By carefully analyzing the underlying structure of the util- ity functions for these problems, we convert them inlo the form required our proposed framework, automatically yielding learning guarantees.
2 Related work
Data-driven algorithm design. Data-driven algorithm design (Ailon et al. 2011 Gupla & Roughgar- den 2016 Balcan 2020) is a modern approach for automatically configuring algorithms and making them adaptive to specific application domains. In contrast to conventional algorithm design and analysis, which predominantly focuses on worst-case or average-case scenarios, data-driven algorithm design assumes the existence of an (unknown) underlying problem distribution that determines the problem instances that the algorithm encounters. The main objective is identify the optimal configuration for the algorithm, lever- aging available problem instances at hand drawn from the consistently validated the effectiveness of data-driven algorithm approaches in various domains, including matrix low-rank approximation (Indyk et al.) 2019 2021), matrix sketching (Li et al. 2023), mixed-integer lincar programming (Cheng et al. 2024), among others. These findings underscore the significance of the data-driven algorithm design approach in real-world applications.
application domain. Empirical work has
Statistical learning guarantees for data-driven algorithm design. A growing body of work focuses on theoretically analyzing data-driven algorithm configuration by providing statistical generalization guar- antecs. This includes learning guarantoes for data-driven algorithm design of low-rank approximation and sketching algorithms (Bartlett al. 2022 Sakaue
Oki (002)) learning metries for clustering (Balcan) 2021 Balcan et. al. 2018c). integer and mixed-integer linear programming
et al. 2020a Balcan & Sharma

---

Published in Transactions on Machine Learning Research (04/2025)
Balcan et al. 2022b 2018a
Cheng & Basu 2024
simmlated annealing (Blum et al. 2021 hyperparameter
tuning for regularized regression (Balcan et al.
2022a; 2023b), decision tree learning (Balcan & Sharma
2024), robust nearest-neighbors (Balcan et al.
2023a), deep neural networks (Balcan et al. 2025 pricing
problems [Balcan & Beyhaghi 2024
Xic ct al.,
2024 among others.
Balcan et al. (2021a] introduced a general framework for establishing learning guarantees for problems that admit a specific piecewise structure. Despite its broad applicability, the framework has certain limitations: (1) it requires an intermediate task of analyzing the dual piece and boundary function classes, which can be non-trivial, and (2) naively applying the framework can lead to sub-optimal bounds (see e.g. [Blccan et al, 2020al, Lemma 7, and Bartlett et al. 2022 Appendix E.3). Recently, Bartlett et al. (2022) developed a new approach for establishing generalization guarantees when the computation of the data-driven algorithm's 's dual utility function can be described by basic arithmetic operators -,. (+,-,x,# +) and conditional statements,
by extending the classical GJ framework (Goldberg & Jerrum 1993
Online learning guarantees for data-driven algorithm design. Another line of work focuses on pro- viding no-regret learning guarantees for data-driven algorithm design problems in online learning settings. This includes online learning guarantces for greody knapsack, SDP-rounding for integer quadratic program- ming (Balcan et al.] 2018b), pricing problems (Balcan & Beyhaghi 2024), and data-driven linkage- based clustering [Blccan et al. 2020b).
Online learning for data-driven algorithm design is generally challenging task due to the discontinuity and piecewise structure of the utility functions. Most prior work provides learning guarantees in this setting by verifying the dispersion of the utility function sequence, a sufficient condition proposed by Balcan et al. (2018b), roughly stating that the discontinuity of the sequence is not highly concentrated in any small region of the hyperparameter domain. However, verifying the dispersion property is generally challenging. [Baccan let al. (2020b) provided a tool for verifying the dispersion property, targeting cases where the discontinuity is described by the roots of random polynomials for one-dimensional hyperparameters or algebraic curves in the two-dimensional case. [Balcan& & Sharma (2021) generalized this by providing tool for discontinuities described by algebraic varieties in higher-dimensions Balcan et al. (2020d) show no-regret online learning under dispersion with respect to more challenging dynamic basclines, and Sharma (2024) establishes how to oblain low internal regret in the data-driven setting. Our dispersion based results in this work imply online learning in these settings as well, using their results. (Sharma & Suggala (2025) show how to tune hyperparameters in online bandit learning algorithms using data-driven algorithm design. [alcaan et al.. (222bb) establish connections between this line of work and online meta-learning
Algorithms with predictions. Another modern approach for designing Maaming-based algorithms is algorithms with predictions (Mitzenmacher & Vassilvitskii 2022). in which predictions about certain aspects of the problem (provided either by machine learning models or human experts) are integrated at certain stages of algorithms to enhance their performance. The final performance of these algorithms is closely tied to the quality of predictions. A higher quality of predictions generally correlates with improved algorithmic performance. Hence, the algorithm, now integrated with predictive models, is analyzed based on its inherent algorithmic performance and the quality of predictions. Algorithms with predictions have proved their
efficacy in various classical problems, including support estimation (Eden et al.) 2021), ) page migration [Inyyk et al.] 2022). online matching, flows, and load balancing (Lvastida et al. 2020), among others
(Khodak et al. 2022 Lykouris & Vassilvitskii 2021: Wei & Zhang 2020).
While having many similarities and overlapping traits, there is a fundamental distinction between the two approaches. Data-driven algorithm design primarily seeks to optimize algorithmic hyperparameters directly for specific application domains. On the other hand, algorithms with predictions aim to incorporate predic- tion in some stages, with the hope that it will improve the performance of the algorithms if the quality of the prediction is good. However, one still needs to decide for what aspect of the problem should a prediction be used and what the prediction should be on an input problem instance, and these choices heavily affect the performance and propertics of the algorithms. It is worth noting that these two directions can complement each other and be integrated into the same system, as explored in recent work (Khodak et al. (022).. Most of the work in the literature has focused on how to incorporate good predictions, but there are no general
6

---

Published in Transactions on Machine Learning Research (04/2025)
results for end-to-end guarantees where the predictions are also being learned in addition to being used by the algorithm. Though there are some positive results for some very specific algorithmic problems e-g. online bipartite matching and the ski rental problem (Khodak et al. 2022).
3 Preliminaries
Parameterized algorithms, utility function class, and dual utility function class. In this work, our main focus is on parameterized algorithms, in which each algorithm has a set of hyperparameters a A C Rdd that have great influence the performance of the algorithm. Let X' represent the set of input problem instances on which the algorithm operates. For example, in the problem of agglomcrative hierarchical clustering (see Section 6.1 for details), a problem instance æ E X is given by (5,6), and consists of a set of points S that need to be clustered, and a set of candidate distance functions 8 = (81,..., 5L) used for measuring the distances between pairs of points (the set remains the same for every problem instance| ! For example, 8 might contain lp distances for difference values p E 00), or some other distance function that is suitable for the geometric structure of the points in S (ef. Balcan et al. 2020a).
The performance of the algorithm for any hyperparameter is measured by the utility function u X A [0, H), where u(x, a) represents the performance of the algorithm when operating on imput problem instance a and be parameterized by a. In the example above, could be in the I-probability simplex, served as the weights to combine distance functions in 6, i.e. 8a = >i a;d;, used in the clustering algorithm. The utility function class U of the algorithm is then defined as U/ = {ua X + [0, H] | a E A}. The utility function class U plays a central role in our analysis since the problem of tuning hyperparameter a for the algorithm can be formulated as the problem of analyzing the Icarnability of U in both statistical and online lcarning described below.
However, in data-driven algorithm design, the structure of the utility function class U can be very intricate in the sense that: (1) a very small variation of the hyperparameter a can lead to sharp, unpredictable changes in the utility function Va, and (2) the utility function uaa corresponding to a fixed a admits a very complicated structure as a function of æ. Hence, analyzing U is often conducted via analyzing the dual utility function class U", which often admits a certain degree of structure. The dual utility function class U of U can be defined as 21" = {u² A + [0, H] x E X), of which each dual utility function "t corresponding to a fixed problem instance is defined "n (a) == (ax), which consists of utility functions obtained by varying the hyperparameter a for fixed problem instances from X. In this work, will show that if Ut admits Pfaffian piecewise structure, we can recover the statistical and online learning guarantees for the utility function class U in several cases of interest.
Statistical learning. In contrast to traditional worst-case or average-case algorithm analysis, we assume the existence of an unknown problem distribution D over X, which encapsulates information about the rele- vanl application domain. Under such an assumption, our goal is to answer the sample complexity question, i.e. how many problem instances are sufficient to learn near-optimal hyperparameters of the algorithm for any application-specffic problem distribution. To this end, it suffices to bound the pseudo- dimensinn (Pollard 1984) of the corresponding utility function class U.
Definition 1 (Pseudo-dimension, Pollard 1984p. Consider a real-valued function class W1, of which each func- tion takes input in X. Given a set of inputs set of real-valued threshold .1..... ,N E F such that ((sign((((z:) - -r),,..,,iig... N The pseudo-dimension of U, denoted as Pdim(((), is the maximum size N of input set that U can shatter.
(#1...., we say that S is shattered by 24 if there exists a
- rx)) u E UH} =
If the function class 2/ is vinary-valued, this corresponds to the well-known VC-dimension (Vapnik & Cher- vonenkis 1974). Standard results in learning theory show that a bound on the pseudo-dimension implies a bound on the sample complexity (sce Appendix A for further background), which is formalized as follows.
Even though is the same across instances, we follow the convention from prior work Balcan et 2021a and include it. 8s a part the problem instance to define the dual utility functions more clearly.
7

---

Published in Transactions on Machine Learning Research (04/2025)
Consider a real-valued function class U, of which each function takes value in X. Assume that (u)im(U) is finäte and U is bounded by H. Then given > O and E (0, 1), for any m 2 m(6, s), where m((δ,) = o हτ (Pdim(F) + log(1/0)). with probability at teast 1 - ô over the draw of S = [1 (I1...., Im) ~ D", we have
Theorem 3.1 [Pollard 1984p
(anD((s(()))
2 sup EEED [ well
Here üg arg uau Ei=1 u(x)).
Online learning. In the online learning sctting, there is a sequence of utility functions u(z1, ").... ..... u(xr, :) corresponding to sequence of problem instances (Z1,..., ØT), coming over T rounds. The task is to design a for the algorithm so that the regret (w.r.t. the best hyperparameter
sequence of hyperparameters in hindsight) is small
T Σ at).
Regret,
max A
Σ u( a)
Our goal is to design a sequence of hyperparameters a1,..., ar that achieve sub-linear regret.
4 Pfaffian GJ framework for data-driven algorithm design
In a classical work, Goldberg & Jerrum (1933) introduced comprehensive framework for bounding the VC-dimension (or pseudo-dimension) of parameterized function classes cxhibiting a specific property. They proposed that any function within a given class can be computed via a specific type of computation, named a GJ algorithm, consisting of fundamental operators such as addition, subtraction, multiplication, division, and conditional statements, then the pscudo-dimension of such function class can be effectively upper bounded. The bound depends on the running time (number of operations) of the algorithm, offering convenient approach to reduce the task of bounding the complexity of a function class into the more manageable task of counting the number of operations.
However, bound based on running time can often be overly conservative. Recently, Bartlett et al. (2022) instantiated a refinement for the GJ framework. Noting that any intermediate values the GJ algorithm computes are rational functions of parameters, Bartlett et al. proposed the relevant complexity measures of the GJ framework, namely the predicate complerity and the degree of the GJ algorithm. Informally, the predicate complexity and the degree are the number of distinct rational functions in conditional statements and the highest order of those rational functions, respectively. Remarkably, based on the GJ framework's complexity measures, Bartlett et al. showed an improved bound, demonstrating its efficacy in various cases, including applications on data-driven algorithm design for numerical linear algebra.
It worth noting that the GJ algorithm has limitations it can only accommodate scenarios where inter- mediate values are rational functions. In other words, it does not capture more prevalent classes of functions, such the exponential function. Building upon the insights gained from the refined GJ framework, troduce an extended framework called the Pfaffian GJ Pramework. Our framework can be used to bound the of function classes that can be computed not only by fundamental operators and condi- tional statements but also by a broad class of functions called Pfaffian functions, which includes exponential and logarithmic functions. Technically, our result is a refinement of the analytical approach introduced by K Khovanski 1991];; Karpinski & Macintyre (1997): Milnor Weaver (1977). which is directly applicable to data-driven algorithm design. An important part of our contribution is a careful instantiation of our main result for several important algorithmic problems, as naive application could result in significantly looser bounds on the sample complexity.
in-
4.1 Pfaffian functions
We present the foundational concepts of Pfaffian chains, Pfaffian functions, and their associated complexity measures. Introduced by Khovanski (1991), Pfaffian function analysis tool for analyzing the properties
8

---

Published in Transactions on Machine Learning Research (04/2025)
of solution sets of Pfaffian equations. We note that these techniques have been previously used to derive upper bound on the VC-dimension of sigmoidal neural networks (Karpinski & Maciniyre 1997.
We first introduce the notion of a Pfaffian chain. Intuitively, a Pfaffian chain consists of an ordered sequence of functions, in which the derivative of each function can be represented as a polynomial of the variables and previous functions in the sequence.
Definition 2 (Pfaffian Chain, Khovanski 1991 A finite sequence of continuously differentiable functions m.....,% f4 Rdd + R and variables a = (a1...., ..) E R form a Pfaffian chain C(a, ....... .7)) if there are real polynomials Pi,(a, m..... n3) in a1...., ad ....., My for for all i E [d] and j E [g], such that
Onj da;
Pay( ......... mg)
(a(a) Here, we emphasize again that (a, .I....,. 11 is polynomial in a and the functions 7/1 (a)...... (()()....7;())))) of a. We now define two complexity notations for Pfaffian chains, termed the length and Pfaffian degree, that dictate the complexity of a Pfaffian chain. The length of a Pfaffian chain is the number of functions that appear on that chain, while the Pfaffian degree chain is the maximum degree of polynomials that can be used to express the partial derivative of functions on that chain. Formal definitions of Pfaffian chain length and Pfaffian degree are mentioned in Definition
Definition 3 (Complexity of Pfaffian chain). Given Pfaffian chain C(a. m..... :T)). as defined in Definition we say that the length of C is y, and Pfaffian degree of C is maxi,j deg(P:.))-
Given a Pfaffian chain, one can define the Pfaffian function, which simply a polynomial of variables and functions that chain.
Definition (Pfaffian functions, Khovanski 1991 Given a Pfaffian chain C(a, m..... Mg), as defined in Definition 2 a Pfaffian function over the chain C is a function the form g(a) = Q(a, 7h .....,, ,,)) where Q
is a polynomial variables a and functions ",,,.., My in the chain The degree A of the Pfaflian function g(a) is the degree of the polynomial Q(a, "l....
The concepts of the Pfaffian chain, functions, and complexities may be bit abstract to unfamiliar readers. To help readers better grasp the concepts of Pfaflian chains and Pfaffian functions, here are some simple examples.
Example 1. Consider the chain C(a, consisting of the variable and the function ea, where a R. Then C is Pfaffan chain since dea ea, which is polynomial of degree 1 in ea. Hence, the chain C has length g 1 and Pfaffian degree M 1. Now, consider the function f(a) (En)² a3. We observe that fa) is a polynomial in and e of degree 3. Therefore, [a) is Pfaffian function of degrec A = 3 of the Pfaffian chain C.
Example 2. The following example is useful when analyzing the learnability of clustering algorithms (we present only the variables and functions here, their interpretation is deferred to Section 6.1p. Let 9 = (S1,..., E RR and a E R be variables, and let d(B) = Σ d,3,, where d, E R4 are some fixed positive real cocfficients for i = 11...,k.. Consider the functions f(a, (3 = a(g)* g(a, (3) = In ( and h(a, B) := dB))a Then f. g, and h are Pfaffian functions, all of degree A 1, from the chain C(a, f.f.g..... of length 3 and Pfaffian degree 2, since
0ʃ = 0, da
0ʃ
d; p
03:
0g O,
Og
d, J,
da
03:
0h = h,
@h
d, f h.
da
03,
9

---

Published in Transactions on Machine Learning Research (04/2025)
4.2 Pfaffian GJ Algorithm
We now present formal definition of the Pfaffian GJ algorillo, which shares similarities with the GJ algorithm but extends its capabilities to compute Pfaffian functions as intermediate values, in addition to basic operators and conditional statements. This improvement makes the Pfaffian GJ algorithm significantly more versatile compared to the classical GJ framework.
Definition 5 (Pfaffian GJ algorithm). A Pfaffian GJ algorithm F operates on real-valued inputs a= (a1....,,ad) E C RR, and can perform three types of operations:
Arithmetic operators of the form v" = v 1 v', where O [+,-,x,;).
Pfaffian operators of the form v" = n1). where n : + R is Pfaffian function.
Conditional statements of the form "if v 2 O... else
Here e and o' are cither inputs (a1,..., or da) or (intermediate) values previously computed by the algorithm.
The main difference between the classical GJ algorithm (Goldberg & Jerrum 1993 Bartlett et al. 2022) and our Pfaffian GJ algorithm is that allow unary Pfaffian operators in the algorithmic computation. By leveraging the fundamental properties of Pfaffian chains and functions, intermediate functions computed by a specific Pfaffian GJ algorithm come from the same Pfaffian chain (see Appendix B.1 for details). Therefore, for a Pfaffian GJ algorithm r we can define a Pfaflian chain C corresponding to I, as formalized below.
easily show that all
Definition 6 (Pfaffian chain associated with Pfaffian GJ algorithm). Given Pfaffian GJ algorithm I operating on real-valued inputs a E A C Rd, we say that a Pfaffian chain C associated with if all the intermediate values computed by are Pfalfian functions from the chain
This remarkable property enables us to control the complexity of the Pfaffian GJ algorithm I by controlling the complexity of the correspouding Pfaffian chain C. We formalize this claim in the following lemma.
Lemma 4.1. For any Pfaffian GJ algorithm I involving a finile number of operations, there is a Pfaffian chain of finite length associated with r.
Proof Sketch. The Pfatfian chain C can be constructed recursively as follows. Initially, we create a Pfaffian chain of variables a with length 0. Using the basic propertics of Pfaffian functions discussed in Appendix B. each time computes a new value e, one of the following cases arises: (1) v is a Pfalfian function on the current chain C, or (2) we can extend the chain C by adding new functions, increasing its length (but still finite), such that becomes a Pfaffian function on the modified chain C.
Remark 1. We note that each Pfaffian GJ algorithm P can be associated with various Pfafian chains, with different complexities. For example, C(a, ..,...,, my) is a Pfatfian chain corresponding F, then Ca "i....., Tgy e is also Pfaffian chain corresponding to I, but with greater length compared to C. Therefore, in any specific application, designing the corresponding Pfaffian chain C for I with small complexity is a crucial task that requires careful analysis.
We now present our main technical tool, which can be used to bound the pseudo-dimension of function class by expressing the function computation as Pfaffian GJ algorithm and giving bound on the complexity of the associated Pfaffian chain. Technical background for the proof is located in Appendix B.2
Theorem 4.2. Consider real-valued function class U = (ua X + +
A} with domain X, of which each function Va E U is parameterized by a E A C Rd. Suppose that for every x E X and r E R, there is a Pfaffian GJ algorithum Ta.r, with associaled Pfaffian chain Ca. of length al most and Pfaffian degree al most M, that given ua E lt, outputs (x) Moreover, assume that values computed at intermediate steps of Ta.r are from the Pfaffian chain Ca.r, each of degree at most A; and the functions computed in the conditional statements are of at most K Pfaffian functions. Then Pdim(U) S q2 + 2dg log(A + +M) + Adg log d 2d log (AK) 16d.
10

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. To bound (4) the overall idea is that given any N imput problem instances 21,..., EN and N
thresholds ri....,Ph ,N, we bound (N), the number of distinct sign patterns
(sign(ua(<1) - ( (aa (mx) - TN)) (sign (" (a))--).....gg(((.. (a) rx))
obtained by varying a E A. Then we solve the inequality 2 < Ilc(N) to obtain an upper bound for Pdim(U().
From the assumption, for each x2 and threshold value Tt, the value of (ig -r;) = sign(ug (a) ri) can computed by a Pfaffian GJ algorithm T2n, that takes input as a and return if ua > r..
Again, from the assumption, the Pfaffian GJ algorithm Tæ,y, has at most K conditional statements, each determines if (a) 2 0 (j =,...., K), where Tw (a) Pfaffian function from the Pfaffian chain Ca.,r of length at most q and Pfaffian degree at most M corresponding T2...
Therefore, each binary value sign(" (a) r:) is determined by at most K other values in the form sign (ag(()).((a)) for j = 1,...,,, K, meaning that the number of patterns
(sign(" (a) - -......, -n).....suu...... (a) - TN))
is upper bounded by the number of sign patterns
(0gu(Ta.1(a)).... sign(Ta,, (igg) (a))........ sign (a)(()xx((())) x())))
obtained by varying a. Moreover, we can construct Pfaffian chain C' of length at most gN and Pfaffian degree at most A by merging all the Pfaffian chain Cz,, such that any function ( above is a Pfaffian function from the Pfaffian chain C', and of degree at most A.
Finally, the number of sign patterns (sign(Ta), (a)), ... sign.,,iiinnnn.nn..... (a))) can be upper bounded by the number of connected components of Rd U. U {a : T a 0}, where Ta..((a) is
Pfaffian hypersurface. Using results by KKovanski (1911) ) and Karpinski Macintyre (1977) (see Ap- pendix B.2 for background), can establish Lemma d² + 2dg log(A + .)) + 4dq log d + 2d AK + 16d.
B.6 which leads to the claimed bound Pdim S
Remark 2. For the case = 0, meaning that the functions computed in the conditional statements are merely rational functions in a, Theorem 4.2 gives an upper bound of Odd ((dlo)(A))) which matches the rate of GJ algorithm instantiated by Bartlett et al. (2022).
5 Pfaffian piecewise structure for data-driven statistical learning
In this section, we analyze function classes for which the duals have Pfaffian piecewise structure, a special case of the piecewise decomposable structure introduced by Balcan et al. (2221a). Compared to their piece- wise decomposable structure, our proposed Pfaffian piecewise structure incorporates additional information about the Pfaffian structures of piece and boundary functions of the dual function classes, as well as the maximum number of forms that the piece functions can take. We argue that the additional information can be derived as a by-product in many data-driven algorithm design problems, but would be ignored if naively using the framework by [Balcan et al. (2021a). We then show that if the dual utility function class 4 of parameterized algorithm admits the Pfaffian piecewise structure, then we can directly establish learning guarantecs for the utility function class U. We note that the advantage of our framework compared to the framework by Balcan al. (2021a) is two-fold: (1) our approach offers a concrete and alternative way of analyzing the pscudo-dimension for the utility function class 41 avoiding the non-trivial combinatorial tasks of analyzing the pseudo/ VC-dimenssion of the dual piece and boundary function classes if using the frame- work by Balcan et al. (2021a). and (2) directly and naively applying the framework by Balcan et al. (2021a) can potentially lead to loose or vacuous bounds (see c.g. [Blccan et al.) [2020a] Lemma. and Bartlett et al. 2022, Appendix E.3). Additionally, we propose further refined argument for the case where all dual utility functions share the same boundary structures, which leads to further improved learning guarantees.
11

---

Published in Transactions on Machine Learning Research (04/2025)
5.1 Prior generalization framework for piecewise structured utility functions in data-driven algorithm design and its limitations
In this section, we discuss a prior general framework for providing learning guarantees for data-driven al- gorithm design problems by Balcan et al.] (2021a). Many parameterized algorithms, such as combinatorial algorithms and integer/ming /mixed-inteeer programming (Balcan et al. 2018a 2017), exhibit volatile utility func- tions with respect to their parameters. In other words, even minor changes parameters can lead to significant alterations in the behavior of the utility function. Analyzing such volatile utility function classes poses significant technical challenge.
Fortunately, many data-driven algorithm design problems still possess certain degree of structure. Prior studies (Balcan et al.) 2017 2018a 2022a 2023b) have demonstrated that the dual utility functions asso- ciated with data-driven algorithm design problems often exhibit a piecewise structure. In other words, the parameter space of the dual utility function can be partitioned into regions, each separated by distinet bound- ary functions. Within cach region, the dual utility function corresponds to a piece function that exhibits well-behaved properties, such being linear, rational, or Pfaffaan in nature. Building upon this insight, prior work by Balcan et al. (2021a) proposed a formal definition of piecewise-structure dual utility func- tion class and established a generalization guarantee applicable to any data-driven algorithm design problem conforming to such structures.
Formally, let us recall the definition of the utility function class U = {ua : X' 10, H] a E A} for a parameterized algorithm, where A C Rd. This class represents functions that evaluate the performance of the algorithm, with Wa : X [0, H] denoting the utility function corresponding to parameter a. For a given input problem instance x X, (a())) yields the performance evaluation of the algorithm on Notably, for each input & E X, we can define the dual utility function corresponding to æ as 2 A- [0, If,, where ui (a) (x)) measures the performance for specific problem instance x function of the parameter a. Consequently, we can also define the dual utility function class ut" = : A x E X}. It was shown 2023b) that in many data-driven algorithm design problems, every function in the dual function class U adheres to a specific piecewise structure, which can be precisely
in prior work (Balcan et al. 2021a 2022a
defined as follows:
Definition 7 (Piccewise decomposable, Balcan et al. A to R is (F,G, -i-iccewess decomposable for class G C (0, and class F C R-A of piece functions if the following holds: for every h E H. there are & boundary function&DTG (T) (a) 2 0), () 2 0) E g and a piece function fb E F for each bit vector b E {0, 13 such that for all a E A, h(aa) = fo, (a) where E 10
2021a). A function class H R-A that maps a domain
ba =
An intuitive illustration of the piecewise structure can be found in Figure 3 Roughly speaking, if a function class satisfies the piecewise structure as defined in Definition 7 then for each function in such a class, the input domain is partitioned into multiple regions by & boundary functions. Within each region, which corresponds to a k-clement binary vector indicating its position relative to the k boundary functions, the utility function is well-behaved piece function. Based on this observation, Balcan al. (2021a) showed that for any algorithm, if the dual utility function class satisfies the piecewise structure defined in Definition then the pseudo-dimension of the utility function class is bounded.
X' Theorem 5.1 [Balcan et al. 2021a]. Consider the utilily function class U = ( (0, H] a E A}. Suppose that the dual function class U is (F,G, (, -ieeceewee decomposable with boundary functions G S {0, a and piece functions F R.A. Then the pseudo- dimension Uf U is bounded as follows
Pdim(U))= = (((Pdim(F)) + VCdim(g*)) log(Pdim(F") + VCdim(G*)) + VCdim((")log" where F and G is the dual class of F. and G, respecticely.
Intuitively, Theorem 5.1 allows us to bound the pseudo-dimension of the utility function class U, which is not behlebehaved, by alternatively analyzing the dual boundary and piece function classes F and g However,
2 At the risk of notation ahuse, we sometimes use the term boundary functions to refer to (a) rather than I(g (a) 2 0). We will ensure the context clear when employing this shorthand.
12

---

Published in Transactions on Machine Learning Research (04/2025)
Structure of the piecewise function
Structtre of the piecewise function
02
(0]
5)
(0s 5y
16
0 6
-0
(a) demonstration piecewise structure of uz in sheer view. This has been shown in Figure 2
(b) The corresponding plecewise structure of My in top view.
Figure 3: An example of the original piecewise structure (Definition 7 and our proposed Pfaffian piecewise structure (Definition [ Here, (a) demonstrates the sheer view of the piecewise structure of specific dual utility function u while (b) shows the corresponding top view for better illustration of regions and their boundaries. As can be seen, there
three boundary functions (x.1(a) (01 - 5) + (a2 5)2 - 16, and (a, = 01 - e partitioning the domain A into 7 regions. In each region, the function -n (a) takes the form of a Pfaffian function. What is not captured by the original piecewise structure Definition is that, in this example, there are only 4 forms that "²(aa can take, which either
2a a2 9a,2(a)
42 (blue region), e -..2(a)-a)) (red regions), log(az) + 2 (green region), and / + aî + exp(0.1 2
01 +
(yellow region). can verified that all the piece and boundary functions are Pfaffian function from the Pfaffian chain Cz (a, ex2 e -0.((af+a)) I 0.1vor
Var
Bartlett al. (2022) demonstrate that for certain problems in which the piecewise structure involves only rational functions, naively applying Theorem 5.1 can yield looser bounds compared to the approach based on the GJ framework (Goldberg & Jerrum 1993). Besides, applying Theorem 5.1 requires the non-trivial task of analyzing the dual classes F and G of piece and boundary functions. This might cause trouble, such as leading to loose bounds (see e.g. Balcan et al.) [020aa] Lemma 7) or vacuous bounds (e.g. [artlett et al.) [202]] Appendix E.3). This situation arises when the piece and boundary functions involve Pfaffian lunctions, motivaling the need to design refined approach.
5.2 A refined piecewise structure for data-driven algorithm design
In this section, we propose a more refined and concrete approach to derive learning guarantees for data- driven algorithm design problems where the utility functions exhibit a Pfaffian piecewise structure. The key difference between our proposed franeworks and the framework by Balcan al. (021a) is that we consider the following additional factors: (1) Both piece and boundary functions are Pfaffian functions from the same Pfaffian chain, and (2) the maximum number of the distinct forms that the piece function (a,;(a) admit.
13

---

Published in Transactions on Machine Learning Research (04/2025)
E C(a, Th. ... n7) such that V fxb &
fxb da,
Calculate (b1, ... b²) b, = 1g88((2) (a) 2 20)
= Po, n2 7g)
da, Q1,((a, Th1 ... 71a)
Calculate f fxb(a)
where Pb, Qi polynomials,
+) deg(Po. i), deg(Q:,) i) s
Calculate I()xx(a) 2 0)
*) f6 l (0, 11*) s ky
Figure 4: demoustration of how the computation of dual utility function satisfying Pfaffian piecewise structure can be described by the Pfaffian GJ algorithm. Given an input x E X' and a threshold E IR, the function ui is piecewise structured with boundary functions ga (for i = 1,... k), and piece functions fi,b (b E {0, }). Note that, the piece functions fh.b can take at most ky forms and all the piece and boundary functions are Pfaffian functions from the chain C.
Later, we will argue that by loveraging those extra structurcs, we can get a better pscndo-dimension upper bound by logarithmic factor, compared to using the framework by [alcan el al. (2021a). The Pfaffin piecewise structure is formalized as below.
Definition (Pfaffian piecewise structure). function class S RA that maps domain A C Rd to R is said to be (kz, kg, M,, A,d) d) piecewise structured if the following holds: for every h H, there are (8)
(1) (a) 2 0)...., I(gn (a) 2 0), where S kg, and a piece function fr.b for each binary vector b E {0, 1}ah such that for all a E A. h(a) = fa.ba where ba (T(o)
at most kg boundary functions of the forms I(g)
O)...., ([g. x (a) 0)) E 1 Morcover, the piece functions fu,b take of at most ky forms, i.e. Hf be E {0, } < kF, and all the piece and boundary functions fr,b.9, are Pfaffian functions of degree at most A over a Pfaffian chain Cn of length at most and Pfaffian degree at most M.
An intuitive illustration of Pfatfian piecewise structure and its comparison with the piecewise structure by [Balcan et al.) (2021a) can be found in Figure 3 For a data-driven algorithm design problem with A} where A Rd, we can see that if its dual
correspouding utility function class U {ua X [0, H] X} admits the Pfaffian piecewise structure as in Definition g
utility function class Zt = {uu :A - R then it can be computed using the Pfaffian GJ algorithm (see Figure 4 for visualization). Therefore, we can use the established results for the Pfaffian GJ algorithm (Theorem 4.2) to derive learning guarantees for such problems. We formalize this claim in the following theorem.
Theorem 5.2. Consider the utility function class U = {ua :x + (0, a a A} where A C Rd. Suppose that the dual function class u = {ur : A + [0, H x E X} is (ky, kg. M, d)- PPafffian piecewise structured, then the
of t is bounded as follows
Pdim(U) < d2g2 + log(o A + M) 4dg d 2d A(kF ko) + 16d.
Proof. An intuitive explanation of this theorem can be found in Figure 4 Since 4 admits (KF, kig. g. M, A, Pf-ffffn piecewise structure, then for any problem instance x E X' corresponding
the dual utility function ux, there are boundary functions T( (1) 2 O),... T( 2 0) where k S kg, and a piece function fa.b for each binary vector b E {0, 1 such that for all a E A, (a) = fa.b. (a), where ba (T(g (1) (a) O),..., [ (1) (a) 0)). Therefore, for any problem instance and real threshold RR
14

---

Published in Transactions on Machine Learning Research (04/2025)
the boolean value of (a(a) 2 0 for any A can be calculated by an algorithm Tæ,r described follow: first calculating the boolean vector ba: and then calculate the boolean value ba, (a) 2 0.
From assumption, note that ge and ja.b are Pfaffian functions of degree at most A from Pfaffian chain Co of length at most q and Pfaffian degree most M. This means that Far is a Pfaffian GJ algorithm. Therefore, combining with Theorem 4.2 we have the above claim.
J
Remark 3. The details of the differences between our refined Pfaffian piccewise structure and the piecewise structure by Balcan et al. (2221a) can be found in Appendix C.1 In short, compared to the framework by Balcan et al. (2021a), our framework offers: (1) an improved upper bound on the pemenondimension by logarithmic factor (Theorem C.I compared to naively applying (Balcan et al., (021a), and (2) a more concrete method for problems admitting a Pfaffian piecewise structure, without invoking dual piece and boundary function classes, which are non-trivial to analyze. This might lead to loose bounds (see e.g. Balcan et al. (020aa), Lemma 7, and Bartlett et al. (2022), Appendix E.3).
5.3 Special case:
function class
We now consider the case where all the dual utility functions v" E V share the same discontinuity structure, which can be used to establish improved bound for the utility function class V. We then argue that this analysis is particularly useful in some cases (e.g. Section 5.3.1
a A} where A S Rd, with the corresponding dual function class = {rr : A - [0, H] x E X). Different from Section 5.2 here all the dual utility function o shares the same discontinuity structure: that is, there is a partition of the parameter space A such that for any problem instance æ E X, the dual function 2i restricted any region A, is Pfaffian function. In this case, we have the following refined bound for the utility function class) V.
Concretely, consider a utility function class V = (va : X
........ A,
A} where A C CRd Assume there is a partition P = [AI,...,AA] of the parameter space A such that for any problem instance a E X, the dual function 2i is Pfaffian function of degree at most A in region A, from a Pfaffian chain Cz of length at most and Pfaffian degree M. Then the pseudo-dimension of V is upper bounded as follows
Corollary 5.3. Consider function class V = (va X - H]
Pdim(V)= = O + gd A + M) + qd d + logn).
Remark 4. The detailed proof is provided in Appendix by restricting the complexity of the Pfaffian chain to individual regions A, rather than across the entire partition P. The insight here is that, compared to the Pfalfian piecewise structure (Theorem 5.1,, Lemma 5.3 makes use the fact that all the dual functions of share the same discontimuity structure dictated by a fixed partition P of A. This shared structure significantly reduces the length of the Pfaffian chain, which is typically the dominant term in the upper bound.
Essentially, Lemma 5.3 simplifies the analysis
5.3.1
Use case: analyzing via surrogate function class
In many applications, we might want to analyze the utility function class U indirectly by studying a surrogate utility function class V. of which the dual function class V is "sufficiently close" to This indirect approach offers several advantages. First, even the dual utility function 4 may lack a clear structure or prove difficult to analyze, making impractical
establish learning guarantocs for 2 by examining 4I" (Balcan et al., 2023b). Second, when 4t* is excessively complex, deriving learning guarantees for U through its analysis may lead to sub-optimal bounds. In such cases, analyzing simpler surrogate function class V can yield tighter bounds (Balcan et al. 2020c
Formally, consider the utility function class U = (ua X' + [0, H] a E A} with the corresponding dual utility function class 2t" = {ur : A + [) | x E X} over instance space X' and parameter space
A C IRd. Assume that for any dual utility function " u²,, there a function on A + [0, H such that | "illoo S We then construct the surrogate dual function class y* fu A [0, H X),, and the surrogate utility function class V (va X [0, H] E A).
15

---

Published in Transactions on Machine Learning Research (04/2025)
In this section, we consider scenario where approximate the parameterized utility function over predefined partition , of the parameter space A. Formally, partition P of set A is a collection [AI..... An of non-empty subsets A, of A that are pairwise disjoint and whose union is the entire set A. For any problem instance I, the function (a) restricted to A; (for any i i= 1.....,, n) is a Pfaffian function from some Pfaflian chain Cz. This a special case, as for every problem instance æ. the dual function ve exhibits the same discontinuity structure, which can be leveraged for this property to recover the learning guarantee for the utility function class U. To do that, we proceed with the following steps: (1) derive learning guarantee for V using the property of V*, (2) using the relation between 4t and V", derive learning guarantee for U via V. Step (1) is resolved by Lemma 5.3 above, and to proceed step (2), we first recall the following useful results.
obtain a tighter bound. Our goal is
Lemma 5.4 (alcann et al. 2020c). Let F = {fa : X + [0, H] a A} and G = {ga : X + [0, H a E A} be two function classes parameterized by a E A and consist of functions mapping from X [0, H). For any set of problem instances S XN, we have
2s ( +
1 |S]
Ellaa -i
11
Here ls(F) is the empirical Rademacher complecity of F corresponding to the set of inputs $ ( [N); i.c.
1 sup fEF
(s(F) = EN s.6.d from wnif. {-1,1}
Σ
(
N
We also recall a standard result in learning theory, which draws a connection between empirical Rademacher complexity and the pscudo-dimension.
Lemma 5.5 WWinwright 2019).
Let. F be function class consisting of functions with bounded range [0, H).
Then (x(F) 0 H
Pdiml()
Here RN(F) supsExx (F).
N
We now ready to present the main result in this section, which allows to establish learning guarantees for the utility function class U via the surrogate function class V satisfying very specific piecewise Pfaffian structure.
Lemma 5.6. Consider the uhility function class U = {uaa : X [0, H] a E A} where A C Rd. Assume that there erists a function class = {Va X' + a E A} such that:
For any æ, we have - - oi E, and
2. There is a partition P == (AI....,
of A such that for any problem instance x E X, the dual function ui is a Pfaffian function of degree at most A when restricted to region As, from a Pfaffian chain Cr.A: of length most q and Pfaffian degree M.
Then, for any E (0, 1), w.p. at least 1-8 over the draw of m problem instances S (x1...., Fm, Dm where D is any problem distribution over X, we have
dd log A M) - qdlog logn
(1/8)
sup Ex-Dua(x)) Een = H aEA
+ + H
m
m
Here âg arg max m
Σm (z))..
Proof. From Lemma 5.3 we have Pdim dl + Log(4 M) + log + log n.), which implies
2m Rm 0 ( (HV ddd + qd log + M) + log d log
16

---

Published in Transactions on Machine Learning Research (04/2025)
From Lemma 5.4 we have
of qd log( + M) + qdlog + logo n + 5)
(m HH
m
A standard learning theory result implies the final claim.
A concrete application of the above general result to luning the regularization parameter in regularized logistic regression appears in Section 6.3
6 Applications of the Pfaffian piecewise structure framework
In this section, we demonstrate how to leverage our proposed framework to establish new statistical learning guarantecs for under-explored data-driven algorithm design problems. For convenience, the notation used in this section might be redefined for each application.
6.1 Data-driven agglomerative hierarchical clustering
Agglomerative hierarchical clustering (Murtagh & Contreras 2012), or AHC, is a versatile, two-stage cluster- ing approach widely employed across various domains. In the first stage, data is organized into a hierarchical clustering tree, determining the order in which data points second stage, the cluster tree is pruned according to specific objective function, for which some common choices are k-mean, k-median, or k-center [Looyd 1982 Xu & Wunnsch 2005), to oblain the final clusters.
merged into clusters. Subsequently, in the
The first stage of AHC involves carefully designing linkage functions, which measure the similarity between clusters and determine the pair of clusters to be merged at each step. These linkage functions require a pairwise distance function between data points and calculate the distance between clusters based on the distances of their constituent points in a specific manner. Common linkage functions include single-linkage, complete-lnnkage, and averago-linkage, and it is possible to generate infinite familics of linkage functions by interpolating them (Balean et al. 2017), which can lead to different merge sequences when building the hierarchical clustering tree. Note that if two linkage functions generate the same hierarchical cluster tree, they will yield the same final clusters, irrespective of the objective function used in the subsequent pruning stage.
Although linkage functions are a crucial component of AHC, they are generally chosen heuristically without any theoretical guarantees. Recently, [Balcan et al. (2017) proposed a principled data-driven approach for de- signing linkage functions. Similar to other data-driven settings, their analysis operates under the assumption that there exists an unknown, applicstion-speecffi distribution for clustering instances. They then provide learning guarantees for some simple families of linkage functions, paramcterized by a single parameter, that interpolates among single, complete, and average linkage. However, they assume that the pairwise distance function is fixed, whereas in practice, multiple distance functions, each with distinct properties and ben- efits, may be combined to achieve better performance. Subsequent work by Balcan et al. (2020a) proposes combining multiple pairwise distance functions by jointly learning their weights and the parameters of the linkage function. However, their analysis does not apply to all the families studied by Balcan al. (2017).
Contributions. In this section, we instantiate theoretical guarantees for novel data-driven AHC settings, where we near-optimally learn the parameter of the merge function family and the combination of multiple distance functions. Compared to prior work, the setting we consider is more general in prior work a combination of multiple distance metrics was only handled for simpler linear interpolations between single and complete linkage, while our techniques handle more sophisticated geometric interpolations as well that include average linkage.
6.1.1 Problem setting
Distance function, linkage function, and linkage family. Given a set of n points S X",, where X denotes the data domain, and distance function 8 X x X R2,, the overall goal of clustering is to
17

---

Published in Transactions on Machine Learning Research (04/2025)
partition S into clusters such that some notion of intra-cluster distance is minimized, and/or some notion of inter-cluster distance is maximizel. In the AHC approach, we first design linkage function ms based on 5, where ma(A, B3) specifies the distance between two clusters A and B. The cluster tree construction algorithm starts with n singleton clusters, each containing a single data point, and successively merges the pair of clusters A, B that minimizes the cluster-wise distance mA(A, B). This sequence of merges yields a hierarchical cluster tree, with the root corresponding to the entire set S, leaf nodes corresponding to individual points in S, and each internal node representing subset of points in S obtained by merging the point sets corresponding to its two child nodes. Subsequently, the cluster tree is pruned to obtain the final clusters via a dynamic programming procedure that optimizes chosen objective function. Common objective functions include k-means, k-medians, and k-centers. Importantly, given a fixed objective function, if two linkage functions generate the same cluster tree for a given datasel, they will yield the same final clusters.
As discussed previously, the point-wise wise distance function can be convex combination of several distance functions chosen from a given set of distance functions = fō1...... .5].. i.c., 5 = 63 Σ Bed; for some g ($I...., BL) E ALL). Here ALL) = { E - B, 2 0. -. 3 1} denotes the (L dimimennil probability simplex. The combined distance function 6g then used in the linkage function. In this work, we consider the following parameterized families of linkage functions:
1==
(d)(a, 1/a , .aERU(-O,,,)) 1011
M1
map
La (), +
min (ōs(a, 6)) + max (DEA
aEA.DEB
1/a
. .aERU(-00, 1 (00]
M2
m&&p
2.0 :A, B)
+
|
Σ
(a)(a,
aEA.BEB
E/ a Kea (o)
M3-
mg
3.0 B)
H
1
Σ aEA.BEB
.r E EUE oo) (0)
||||
The linkage function family M, interpolates between single and complete linkage. The linkage function family M2 is called the versatile linkage (Fernández & Gômez 2020). which interpolates among single, complete, and average linkage. The family M3 is another generalization of single, complete, and average linkages that incorporates multiple pairwise distance functions. Note that in .Ma. we do not combine all the given distance functions d = {ō1,..., 5r.) into one but treat them separately. Precisely, if we set a; 1, and aj = 0 for all: j * i, we have average linkage with respect to the distance function 8;; if we set a; = oo, and aj = 0 for all j + i, we have complete linkage with respect to the distance function 8;; and if we set 0r = 00, and aj = for j o i, we have the well-known single linkage with respect to 64-
Data-driven AHC. In the data-driven setting, we are given multiple problem instances Pi...., PN, where each problem instance P. (S,, 8) consists of set of points S, that need to be clustered and a fixed set of distance functions 8 that is shared across problem instances. Assuming that there exists an underlying problem distribution that represents a specific application domain, we aim to determine how many problem instances are sufficient to learn the parameters a of the linkage function families and the weights & of the distance functions (for the families MI and M2). These questions are equivalent to analyzing the pseudo- dimension of the following classes of utility functions.
For E (1, let A denote the algorithm that takes problem instance P (5, input and returns a cluster tree A8, 5) E T,, where T the set of all possible cluster trees, by using the interpolated merge function m&g 1,a Then given an objective function, for example, the k-means objective, the pruning function μk : T Sx takes input clustering tree, and returns a k-partition (PI...., Ph} of S that minimizes such objective function. Then, given a target cluster y = {CI...., Cx), the performance of the algorithm 1p- is measured by the Hamming distance between the produced clusters (A(AA
(S, 0)) (Pi....; Pk)
18

---

Published in Transactions on Machine Learning Research (04/2025)
and the target clusters y
k
(ON = min
C \ Pa.l-
dE
S
Here, the minimum is taken over the set of all permutations of 84 = [l,...,k), We can clearly see that takes value in {0, 1. ...... n-1 1}. However, note that given an objective function, the cluster tree is equivalent to the produced clusters. Thus, the performance of the algorithm is completely determined by the cluster tree it produces, and for simplicity, can express the performance of A. as u. (S,8) + ((4 8)). where e is function that maps cluster tree to a value in [0, 1].
Similarly, we denote Ag as the cluster tree building algorithm that takes P (S, 6) as the input and returns a cluster tree AS( 5) by using the linkage function 3. Again, we have that ug : (S, 6) + (S, 6)) represents the performance of the algorithm. We consider the following function classes that measure the performance of the above algorithm families:
H1 {ui a.. (8, - uSA
E ( A(L)),
H2 = {u2 (u (5
( A((4)),
H/. {uf (S.6) ((4g(())))))))) a, { (0)}.
In the next section, we analyze the pseudo-dimension of the function classes described above, which provides insights into the number of problem instances required to learn near-optimal AHC parameters for a specific application domain.
6.1.2 Generalization guarantees for data-driven hierarchical clustering
In this section, we will leverage our proposed Pfaffian piecewise structure Theorem 5.2p to establish the upper bounds for the pseudo-dimension of Hi, H2, and H3 described above. First, will instantiate pseudo-dimension upper bound for H1, which is formalized the following Theorem 6.1
Theorem 6.1. Let Hi be class of functions
H1 (u (5,8) + u(A (S (S,8)) BU( A((L))
mapping clustering instances (5, to [0, 1] by using merge functions from class Mi and an arbitrary objective function. Then Pdim ))) = On L
Proof. Overview. The high-level idea is to show that the dual utility function ui (a, B) + u(A9.0(S. (S. 8)) for any fixed problem instance P (S, 5) exhibits a piecewise structure: its parameter space is partitioned by multiple boundary functions, and within each region, the cluster tree remains unchanged, implying that the utility function is constant. We then characterize the number and complexity of the boundary funetions, which we show belong to Pfalfian system. Subsequently, can utilize our framework to obtain bound on the pseudo-dimension of Hi.
Proof details. Fix a problem instance P = (S, 8), and consider the dual utility function "i (a, (9) + u(A (S, 5)). Suppose A, C and A' S S are two candidate clusters at some merge step of the algorithm. Then A, is preferred for merging over A' B' iff
1/a
1/a
min (ōg(a, + max (Ba(a, b))a) AEE.
<
(5g(a, 8))a+ + max (6g(a, bEB
min
"EΛDEE
or equivalently,
(6p(an, b1)) b2)) < (()((),B))) (5 12))
19

---

Published in Transactions on Machine Learning Research (04/2025)
where (1)
b2) E arg a. (e (a), b4) E bEB: arg aed (eeeeeed..errrreree (o)(())( b))", and (d2, 122) E arg 'e (,g(a,
Each possible choice of the points an, b1, 0z, b2, a i/, o2 bg corresponds to a boundary function in the form
I((6g(a1, b,)) + (ōz(az, b2)) - (6g(a), 81)) + ((a((2,)2)) 0).
Among all possible choices of the points a, bi, a2 b2, a1, D/1 a2g b22 we get at most n distinct. boundary conditions across which the merge decision at any step of the algorithm may change
We next show that the boundary functions constitute a Pfaffian system in a, a........,8. BL and bound its complexity. For each pair of points a, b E S, define fa,(a, == 5g(a.d]: Ia,b (3) = In (nd b) and Na, 3) == (a 8)a. Recall óB(a,b) b) = Et=n Bidr(a, Consider the chain C(a, B. Ja.b. Ja,b, ha,s) of length = 3n², for a, S. We will show that these functions form a Pfaffian chain of Pfaffian degree M = Indeed, we have for each a.be S,
1
SSab 0, da
0fab = (((a,))fe,b>
08,
Dgo.b O,
Oga. 6,(a,b) b)fa.r
da
03,
Dha.b Do.bha,b
aha,b
0B; b),,bhaa,
da
which establishes the claim. The boundary conditions can clearly be all written in terms of the functions { meaning that the degree = Note that the piece functions are constant and can only take value in {0, 1 . 1}, meaning that ky n- Then we conclude that Hi admits (n 1, n², 3n 2, 1, L 1)- Pfalfian piecewise structure. Applying Theorem 5.2 now gives that Pdim(H.)) On ( L2 n log +
L log(( +n+ 1)) Ln)
]
Similarly, we also have the upper bound for the psoudo-dimension of H2, and Ha. Theorem 6.2. Let H2 be class of functions
H₂ {ug (5 ul u a +20 A((L))}
mapping clustering instances (S, 8) to [0, 1] by using merge functions from class M2 and arbitrary merge function. Then Pdim((H2) On L
Theorem 6.3. Let H3 be class of functions
H3 {ug: (S, 8) u(Ag(S,)) as (- {0}}
mapping clustering instances (8,8) to [0. by using merge functions from class Ms. Then Pdim(Hss) O(n
The detailed proofs of Theorem 6.2 6.3 for the function classes H2, and Ha can be found in Appendix D.I Although these function classes share the same ggeudo-dimension asymptotic upper bound, their structures differ, necessitating separate analyses and leading to distinct Pfaffian piecewise structures. To show that the dual function classes of Hi, H2, and H3 admit Pfaffian piecewise structure, we analyze the transition condition the hyperparameters when the preference for merging two candidate clusters A, B switches to merging different pair of clusters A', B' instead, at any merge step of the hierarchical clustering algorithm. The transition condition corresponds to an equality involving Pfaffian functions of the parameters and B. All of such equations corresponding to each tuple (A, B, A', B') C 5* will divide the parameter space into regions, in each which the AHC algorithm produces the same clustering tree, leading to the same performance. After this step, we construct the Pfaffian chains for cach function function classes Hi, H₂, and H3, where the difference naturally lies in the form of functions in those function classes. We then carefully analyze the complexities of the Pfaffian chain of those Pfaffian functions to obtain the above bounds.
20

---

Published in Transactions on Machine Learning Research (04/2025)
6.2 Data-driven graph- based supi-super learning
Semi-supervised learning (Chapelle et al. 2010) is a learning paradigm designed for settings where labeled data is scarce due to expensive labeling processes. This paradigm leverages unlabeled data in addition to a small set of labeled samples for effective learning. A common semi-supervised learning approach is the graph- based method (Zhu & Goldberg, 2009 Chapelle el al. 2010), which captures relationships between labeled and unlabeled data using a graph. In this approach, nodes represent data points, and edges are constructed based on the similarity between data point pairs, measured by a given distance function. Optimizing a labeling function on this graph helps propagate labels from the labeled data to the unlabeled data.
A large body of research focuses on how to learn such labeling functions given the graph, including using st-mincuts (Blum & Chawla 2001), optimizing harmonic objective with soft mincuts (Zhu et al. 2000).
label propagation (Zhu & Ghahramani 2002), among others. Recent work by Du et al. (2025) examines the problem of data-driven tuning of hyperparameters in label propagation based algorithms. However, it is crucial to design a good graph by setting the edge weights between the data point appropriatcly in order for these label oplimization algorithms to work well (Zhu & Goldberg 2009).
Despite its significance, the graph is usually considered given or constructed using heuristic methods without theoretical guarantees (Zhu 2005 Zemel & Carreira-Perptñánn 2004). Recently, Balcan & Sharma 20221) proposed novel data-driven approach for constructing the graph, by learning the parameters of the graph kernel underlying the graph construction, from the problem instances at hand. Each problem instance P consists of sets of labeled L and unlabeled data U and a distance metric d. Assuming that all problem instances are drawn from an underlying, potentially unknown distribution, they provide guarantees for learning near-optimal graph kernel parameters for such a distribution. Nonetheless, they consider only a single distance function, whereas in practical applications, combining multiple distance functions, each with its unique characteristies, can improve the graph quality and typically result in better outcomes compared to utilizing a single metric (Balcan et al. 2005
Contributions. In this section, we consider a generalized and more practical setting for data-driven graph- based semi-supervised learning, where we learn the parameters of the commonly-used Gaussian RBF kernel " v) = exp(-ô(u, (xp(-ō(u,e)/oo) and the weights 8 E (L) {B R 3 2 0, Σ 3r =1} of 5 E/=, which is a convex combination of multiple distance functions for constructing the graph.
6.2.1 Problem setting
Graph-based semi-supervised learning with Gaussian RBF Kernel. In the graph-based semi- supervised learning with Gaussian RBF kernel, we are given a few labeled samples C c X' x ), a large number of unlabeled points U C X, and a set of distance functions 8 = (ō....., 8r.), where 5, : X x X + R2 0 for == =,, I,....,.. Here, X' denotes the data space, and y = f0, 1} denotes the binary classification label space. To extrapolate labels from L to U, a graph B is constructed with the node set LUl and edges weighted by the Gaussian RBF graph kernel Wo, Wa,a(21, x22) = exp(-6(x1. 22))/²? for 02 E L LUU, where a is the bandwidth parameter, and ô = E 3:6; is a convex combination of the given distance functions. After constructing the graph G a popular graph labeling algorithm called the harmonic method (Zhu et al. 2003) is employed. It assigns soft labels by minimizing the following quadratic objective:
Σ M.0
f(
where / E [0, 1]" is the soft label vector that includes labels of labeled samples f(xxc) (x E L) and the prediction variables of unlabeled labels f(xu (zu E U) that we want to minimize over. Besides, n = [ + +|C| is the total number of samples, W denotes the graph adjacency matrix Wzzz2 (x,, and D is the diagonal matrix with entries D: = E, Wij. The final predictions are obtained by rounding Sau for zu E U, i.c. predicting (ff())) 2 }),, denoted by (C, Let u (C, + [0, 1] denote the utility of the algorithm corresponding to a and B, which is given by u = 1 1n88, where 1 is the average 0-1 binary classification loss of the predictions of the above algorithm when the graph is built with parameters a.
21

---

Published in Transactions on Machine Learning Research (04/2025)
Data-driven graph-based semi-supervised learning. In the data-driven setting, problem instances Pi...., ......... P., each P; is represented as tuple (Li, 6) of set of labeled samples Li, a set of a unlabeled samples U4 and a set of distance functions 8 that is shared across problem instances. Assuming that there is an underlying (unknown) problem distribution that represents a specific application domain, we want to know how many problem instances are sufficient to learn the best parameters a, 8 that are near-optimal for such problem distribution. To do that, we want analyze the psoudo-dimension of the following function class:
given multiple
g f (C, + (C.,))) (0) ELL)).
6.2.2 Generalization guarantees for data-driven semi-supervised learning with Gaussian RBF kernel and multiple distance functions
We now instantiate the main result in this section, which establishes an upper bound for the pseudo-dimension of the function class G described above.
Theorem 6.4. Let G be class of functions mapping semi-supervised leorning instances (C,U, 8) to [0, 1]. Then Pg) = On" L2), where n = [C]+ [4] is the total number of samples in each problem instance, and L= 6) is the number of distance functions.
Proof. Technical overview. Fix a problem instance P = (C, we will show that the dual utility function function 37, u (C, U, 8) is piecewise constant and characterize the number and complexity of the boundary functions which we will show belong a Pfaffian system. This implics bound on the pseudo-dimension of following our Pfaffian piecewise structure Theorem 5.2
Proof details. First, the quadratic objective minimization has a closed-form solution (Zhu et al. 2003 given by
fu = (Dru - Wuueee.
where W denotes the graph adjacency matrix, D is the diagonal matrix with entries Dac.;; Ej=1 (o, 2y), and subscripts u, C refer to the unlabeled and labeled points, respectively. Here
Sc E (0, 13141 is the ground truth label of samples the labeled set L.
The key challenge now is to analyze the formula (Dru Wuu) 1 of which the clement will be shown to be Pfaffian functions of o, B. Recall that (Z,, recall the identity A- adi(a) for any invertible matrix A, where adj(A) and det A are the adjoint and can see that any element of (Dru Wuu) is
for 24,2 E LUU. First, we
det(a))
determinant of matrix A, respectively. Therefore, rational function of wo,a(z;,x,) of degree at most [2[] (i.e. a ratio of polynomial functions where both the mumerator and the denominator have degrees at most [
Now, consider the Pfaffian chain C(a, B, wi1...., Wnn) with L+ variables a, A, and of length = n² +1. To see the Pfaffian degree of C, note that for any pair of nodes T,, 2, E E U C, we have
(w,, 03k
)6()),2;) o²
exp (-
)0(x),2)) o²
for k 1, I.....L.
Dw a 20g(z;; 2z) exp )g(0)12;))
(;)) (x1,
do
o²
Thus, the Pfaffian chain C has Pfaffian degree M 55 Now, consider the dual utility function s(a, 19). Note that
ucuusao,8) 8) I(L(f(au) 2 1/2) = g(zu)),
1
Σ
22

---

Published in Transactions on Machine Learning Research (04/2025)
where g(zu) is the ground-truth label of unlabeled node zu E U, using for evaluation purpose. We can
see that, for each sample zu E U, T(((u)) 2 1/2) = (10) boundary function. Both functions In cach region determined by the sign vector bu = (b(xu))avEu where b(zu) = ((((u)) 2 1/2) for zu E U the dual utility function "C,u1,0 is a constant functions. We can see that there are at most [M 1 such constant functions that VC (O, B) can take. Therefore, by Definition the dual function class G is (MI) + 1, [M] 1, + (1),,fa)) piccewise structured. We can apply Theorem 5.2 get
(mn) (0))))) 2 1/2) = ( 2 (12 is a
((m)
(xu) are Pfaffian functions from chain C and of degree [2]]
(g) O 4 T,2 n² ((()) + n² log I. + I. [4])
Noting [4] I n and simplifying yields the claimed bound.
6.3 Data-driven regularized logistic regression
Logistic regression (James et al. 2013) is a fundamental statistical technique and widely used classification model with numerous applications across diverse domains, including healthcare screening (Armitage et al. 2008), market forecasting (Linoff & Berry 2011), and engineering safcty control (Palei & Das 2009). To miligate overfitting and enhance robustness, regularization for sparsity (41) and shrinkage (l2) is commonly employed in logistic regression (Mohri et al. regularized linear models in general, the regularize eegularization parameters, which control the magnitude of regu- larization, play a crucial role (Mohri et al. 2018 Murphy 2012 James et al. 2013) and must be carefully chosen. Setting regularization parameters too high may lead to underfitting, while setting them too low may nullify the effectiveness of regularization. In practice, a common strategy for selecting regularization param- eters valisaaali,,,,on, which is known to lack theoretical guarantees, in general (Zhang 2009: Chichignoud
2018 Murphy 2012). In regularized logistic regression and
et al. 2016).
Recently, Balcan et al. (023b)) proposed data-driven approach for selecting regularization parameters in regularized logistic regression. Their methodology considers each regression problem, comprising training and validation sets, as a problem instance drawn from an underlying problem distribution. The objective is to leverage the available problem instances to determine regularization paramcters that minimize the validation loss for any future problem instance sampled from the same distribution.
Contribution. In this section, we will demonstrate the applicability of Lemma 5.3 by recovering result by Balcan et al. (002bb).
6.3.1 Problem setting
Regularized logistic regression. We closely follow the data-driven regularized logistic regression setting by Balcan et al. (003b)). A problem instance P = (X, y, X Bval) E Rm.p.mm = Rm=x x {+1}m x Rm' xp x (+1]"², where m' m, consists of training set (X, y) of samples and validation set (X yval) of m' samples. Given a regularization parameter À [Aminy Amax], where 0 < Amin Amax, the regularized logistic regression solves for the coelficients B(x.v) that is the best fit for the training set (X, y), i.e.
(A) = arg min 1(3 (X,v)) b)) + AR(3).
BERP
where 1(B, (X, v)) = 1 Em log(1 +
B)) denotes the logistic loss, and R(B) is either sparsity
(I131)) or shrinkage (11 regularizer.
Data-driven regularized logistic regression. In the data-driven setting, we assume that there is an unknown, application specific problem distribution D over Rm, We then can define the optimal hyperparameter X for such problem distribution D as
X E arg min (pnD(hx(P)), AE XE Me(Amin::nmm Awox)
23

---

Published in Transactions on Machine Learning Research (04/2025)
where,
hx(P) 11 111x x) (2), (Kaal, yval)) =11
log(1 exp(-y;:0 B (xxx))()))
m
m expl exp(-viar) B(xx)((1)))
=H
log
m
which is the validation utility function for the problem instance P corresponding to the regularization hyperparameter A. Since the problem distribution D is unknown, we assume that we are given a set S = {PI...., .P.....,PPI PN of problem instances drawn iid. from D, and we set the regularization hyperparameter Ảs via ERM, i.c.,
Ås E
arg max XE(Amin:Amaci
hx(P.).
Our goal determine how many problem instances N do we need such that with high probability, the performance of the optimal hyperparameter X and the hyperparameter Äs tuned using the set of problem
instances S {PI.... Pv) are sufficiently close. Define H. = {hx Rm.p.m' + [0, H] X E [Amiuy Xmax]] The goal above is equivalent to analyzing the learning-theoretic complexity of the function class H.
6.3.2 Generalization guarantee for data-driven regularized logistic regression
As discussed previously, the challenge for analyzing the learnability of is the unknown structure of hx(P) as function of problem instance Even if we consider the dual function class H1 {hpp [Amin Amax [0, H] P E Rm.p..n }, it also hard to analyze the structure of H we do not have the explicit form of (X). Hence, the approach here is to construct surrogate function class V. that is sufficiently "close" to H" and is more well-behaved, and then we will use the idea proposed in Section 5.3. to recover the learning guarantee for H.
Using this approach, we recover the following result by Balcan et al. (023bb which establishes learning guarantees for hyperparameter luning for regularized logistic regression.
Theorem 6.5. Consider the problem of luning regularization parameter for regularized logistic regression with E (or l2) regularizer under data-driven selting. Consider the function class H = (hx Rum. -> TK. E [Amino )max]), where (x)P) is the volidation utility for the problem instance P and with regularization hyperparameter Then for any E (0, 1), with prodability least 1-8 over the draw of m problem instances S = (PI..... PN] D.N where 'D is some problem distribution over Run.p.m', have.
m² + log(1/c) o (V
1og(1/5) N ) + +EpwDlhis (P)]
+
sup xe Xe(Nmin.Aamaal
EgwD h2 (P)),
N
where 0 is some sufficiently small value (salisfying Theorem D.1
Proof. Technical overview. The idea is to construct surrogate dual function class V = {up, Dainn Amax] + [0, H}} that is sufficiently close to H. In other words, given any sufficiently small e (sce Theo- rem D.1), we want to construct V. such that for any problem instance Rm,p.m' we have
< c. This can be done using Theorem D.1 Moreover, we can partition the space [Aminy Amax] into 4(Amaax - Amin) intervals, over each of which the function v'e. is a Pfaffian function from a Pfalfian chain with bounded Pfaf- fian complexity. We then use our results from Section 5.3 (Theorem 5.3 to bound the statistical complexity of the surrogate primal function class Ve, which then can convert to the statistical complexity of H.
Proof details. We now go to the details of the proof, which consists of the following steps.
24

---

Published in Transactions on Machine Learning Research (04/2025)
Constructing the surrogate dual and primal function classes V and V.. To construct such
surrogate dual function class V for H", for any problem instance P = (X, y, X Mval), Balcan et al. (2023b)
first approximate the regularizod logistic regression estimator (A) by ( ((.,) (A), using Algorithm (sce
Appendix 6.3 if R(8)= = ||8|| (or Algorithm 2 if R(B) () Intuitively, for sufficiently small 6, the search space Ammin Amax] can be divided into (Amax - Amin) intervals. Within each interval, ((x.x) (A) is linear function of X, and there exists uniform error bound of O(e2) for the approximation error || (1 (x. - (A)lla (formalized in Theorem D.1 The surrogate dual validation utility function class
y can now be defined as V.r (1/p:e [Amiu: Amax] IR P E Rm.p.))) Here
(A) = 118((2 m) (2), val yral)) =H1
log(L + exx((-xxpp- B ((x,1)) (A)))
m
m
.H
log
II + exp(- -y,, Bix x)
m'
and ((x,y)()) (A) defined as in Theorem D.1 An important property of (X.y) (A) its piecewise linear
structure: we can partition [Aming Amax] into (Amax Amin) intervals, and in each interval [Amin + te, Amin + (t + 1)e), (x (A) = Aap + bp,eds where ap,,,t bp.e.. is defined as in Theorem D.1 This leads to the piecewise structure of V2, and we have successfully construct a surrogate function class for H- that is: (1) admits piecewise structure, and (2) sufficiently close to H.
We can then the define V. (ux,e Rmm.. + R X E Dmmnn )max]} where (P. = up;
Analyzing the pseudo-dimension of V. We can now proceed to analyze the pseudo-dimension of V. using our proposed results from Scction 5.3 First, notice that f(z) = m log 2 is a monotonic function. Hence, we can simplify the analysis by analyzing the pseudo dimension of Ge = {gr, Rm.p.mm + R X E Ammnn {max]] where
m
gx.e (P) = II + exp(- ((x (A))).
i=1
Again, we can define the dual function class G f,p. x - R P Rm...me of Ge, where gh.( == (P).
Fixing problem instance and a threshold 7 E R. by the property of ((x2,, (x) we know that the domain Dmins Amax] can be partitioned in to [ Aminl intervals. In each interval DAmin + tc, Amin (t + 1)c]. gh. (X) takes the form
m Ir. (A) II (1 expl (Aa: + b,))).
Notice that from the problem assumption we have m' < m. Therefore, in each interval [Amia + te, Amin + (t + 1)e), (A) is a Pfaffian function of degree at most m from a Pfaffian chain of length at most m and of Pfaffian degree at most m. From Lemma 5.3 we conclude that Pdim((.) = O(m² [og(1/e)), which implies Pdim(V.) = O(m + log(1/e)).
Recovering the guarantee for H. Note that we just establish the upper bound for the learning-thcorett complexity of the surrogale primal function class V., To recover the learning guarantee for H, need to leverage the approximation error guarantee between H and H(t), Using Theorem 5.4 we then conclude that
(x) (000000
-0
m² (1/) + 2 )
N
Finally, classical learning theory results imply the claim.
25

---

Published in Transactions on Machine Learning Research (04/2025)
Remark 5. Balcan et al. (2023b) introduced the result presented above (Theorem 6.5 For this specific
application, the loundation of their approach and our framework (Section 5.3) are similar. Concretely, our proof makes use of Corollary 5.3
which is similar to the proof in prior work. One can think of the novelty
of results presented in Section 5.3 is in obtaining a generalization that is applicable to other problems.
7
Online learning
In this section, we introduce new general techniques for establishing no-regret learning guarantees for data- driven algorithms in the online learning setting with full-information feedback when discontinuity of the piecewise Lipschitz dual loss or utility functions admit Pfaffian structure. Prior work (Balcan et al., 2020b) provided tool for online learning when non-Lipschitznnss (or discontinuity) occurs along roots of polynomials in one and two dimensions, and Balcan & Sharma (2021) extended the result to algebraic varieties in higher dimensions. Here, we generalize the results cases where ton-Lipschizzness occurs along Pfaffian hypersurfaces. For convenience and matching the frequently used notations in the online learning literalure, we will present our results using utility functions instead of loss functions.
We note that although the online learning sctting is more general than the statistical learning scttings (in the sense that guaranlees for online learning seltings can be automatically translated into guarantees for statistical learning settings via online-to-batch conversion), the results in online learning settings typically require extra smoothness assumption compared to the statistical learning setting, as noted in prior work [Balcan et al.) 2024a). Here, we consider the dispersion property online learning in this setting and develop tools to verify whether the dispersion property holds when the discontinuities of the loss sequences involve Pfaffian functions. Roughly speaking, dispersion means that the discontinuities of the dual function do not concentrate in any small region of the parameter space. So, by online-to- tothttchhhhhhhh conversion arguments, our online learning results imply sample complexity guarantees, but only if the distribution satisfics dispersion. In contrast, our sample complexity results the statistical setting do not make such an assumption, and hold even if the discontinuities concentrate.
sufficient condition for no-regret
7.1 Overview of the dispersion property
We first start by giving a high-level overview of the dispersion property, which serves as a sufficient condition for online learning where the sequence of loss (or utility) functions is not continuous but is piecewise Lipschitz. While it is not always possible to obtain sub-linear regret for online learning with piecewise Lipschitz loss functions, Balcan et al. (2018b) introduce the dispersion condition under which online learning is possible. Informally, dispersion measures the number of discontinuities of the loss function that can occur in ball of given radius. A sufficient bound on the dispersion can lead to a no-regret learning guarantee. Concretely, we will use the /-point-dispersion (Balcan et al.] 2020b) which is a slightly more generalized notion.
Definition 9 (f- Lf-point-dispersed, Balcan et al. 2020b). The sequence of loss functions E,, l2. is f-point- dispersed for the Lipschitz constant L and dispersion function f N x (e) + R if for all T and for all 0, we have
E mmax (tt = 1...,,...,77 P.p"
- ((0')) (e((())))))))))) Lllp - 1'112311 s S(T,)),
where the max is taken over all p, E C: 11p 0ll1a s.
The expectation here is over both the randomization of the algorithm (e.g. Theorem 7.6 for logistic regres- sion) for which the performance is measured by the loss functions & and the "smoothed" adversary that generates the sequence of input instances on which the losses are measured (e.g. Theorem 7.4 for hierarchical clustering). In more detail, there are examples where randomization of the underlying algorithm sufficient to ensure that Definition is satisfied (Balcan et al. 2018b] Theorem 7.6). However, in other cases, one can establish f-point-dispersion by assuming that the input instances in the adversarial sequence are perturbed
Thhe loss function for the entire parameter domain is revealed to the learner in each round, after the learuer has chosen the parameter for that round.
4 'Algorithm here refers an algorithm from our parameterized family of algorithms under study, as opposed to the online learning algorithm used learn its parameters.
26

---

Published in Transactions on Machine Learning Research (04/2025)
slightly using smoothed analysis (introduced by Spielman & Teng 2003 see Balcan et al. 2018b 2022a
2023a for some examples). Intuitively, the adversary can choose an adversarial problem instance, which is then slightly modified to avoid the concentration of a large number of loss functions in the sequence that have Lipschitzness violations (or discontinuitics) in arbitrarily small regions of the parameter space. The exact nature of perturbation to the input instance needed to ensure Definition M is satisfied depends on the problem instance, e.g. for hicrarchical clustering, it is sufficient to assume that pairwise distances between points in the clustering instance follow bounded-density distribution (Theorem 7.4). In contrast to the statistical setting above, this smoothing does not need to be ii.d., although in this work will assume that the perturbations are independent (e.g. Theorem 7.3
A continuous version of the classical multiplicative weights algorithm achieves the following no-regret guar- antee provided the loss functions are dispersed.
Theorem 7.1 (Balcan et al. 2020b). Let C C Rd contained in a ball of radius R and E l2,....: : C [0, 1] be piecewise L- L-pipschitz functions that are --point-disperse learning under hull-information feedback, i.e. (p(p) is revealed for all p C after the learner has picked Pt. for round t, there ewists an algorithm that satisfies the regret bound
with an To intteeiior mindmizer. Then, for online
Σ ((.) e1(0") <O(viTlog(R/)) ((T
E
for any r E r0.
Though the dispersion property provides sufficient condition for no-regret learning piece- wise Lipschitz loss functions, it is verifying the dispersion property that poses challenge for Pfaffian struc- tured functions. In this section, we provide general tool for verifying dispersion property for the sequence of loss functions of which the discontinuities involve in Pfaffian hypersurfaces (Section 7.2 h. We then demon- strate the applicability of our tool by providing no-regret learning guarantees for under-explored data-driven algorithm design problems in the online learning setting (Soction 7.3
Contributions.
7.2 A general tool for verifying dispersion property involving Pfaffian discontinuity
We first introduce a useful notion of shattering which we use to establish a constant upper bound on the VC-dimension of class of Pfaffian functions with bounded chain length and Pfaffian degree when labeled
by axis-aligned segments (i.c., line segments parallel to some coordinate axis). This bound is crucial in
exlending the framework for establishing dispersion developed in prior work (Balcan et al. 2020b d Balcan
& Sharma 2021b. We use tools from the theory of Pfaffian functions (included in Appendix E
Definition 10 (Hitting and shattering). Consider Pfaffian chain C(x, fi.... fa). Let P (P...... Pk denote a set of hypersurface, each defined by Pfaffian function P(æ, fi( chain C. We say that a subset P' C P is hit by a line segment v if, for any P E P, v intersects with P iff P'P line T hits a subset p' C P, there is a line segment v T such that v hit P', collection V of line segments shatters P for each subset P' S R. there exists line segment V such that v hits P'.
= 0 from the Pfaffian
We have the following key structural result which intuitively establishes bound on the complexity of intersection of Pfaffian hypersurfaces.
Theorem 7.2. There is a constant KM.dd depending only on M, 9, d, and p such that azis-aligned line segments in IP cannot shalter any collection of Ka.dd Pfaffian hypersurfaces consisting of functions from a Pfaffion& C chain of length 9, degree at most d and Pfaffian degree at most M.
Proof. Let C(x, Jt)....)))))) Sq), where x E RP, is a Pfaffian chain of length and of Pfaffian degree at most M. Let p = (PI...., P denote a collection of K Pfaffian hypersurfaces fi fi))...........).......)))) fq = 0 for i= 1..,..., K, where cach P. is a Pfaffain function of degree at most d from the Pfaffian chain C. We sock to upper bound the number of subsets of P which may be hit by axis-aligned line segments. We will first consider shattering by line segments in fixed axial direction x my for (p)-
27

---

Published in Transactions on Machine Learning Research (04/2025)
Let Y be line along the axial direction T... The subsets of P which may be hit by segments along Y, are determined by the pattern of intersections of Yr with the hypersurfaces in P. We can now use Theorem F.1 to bound the number of intersections between Y, and any hypersurface P. = 0 for P. E P as
R 2 1/22 d(M min(g. p) + d)",
using the fact that the straight line T is given by p p- 1 equations 21 for k # which form a Pfaffian system with P. of chain length 9; Pfaffian degree M, and degrees dcg(P:) = d, deg(rx)
1 for k * j. Therefore Y, intersects hypersurfaces in P at most KR points, resulting in at most K R + segments of T,, Thus, I may hit at most (KR+1)= = O(K22)(o=)) (M min p} + 2) subsets of P. We remark that these upper bounds correspond to an assumption that the Pfaffian hypersurfaces are in general position, i.e. a small perturbation to the hypersurfaces does not change the number of intersections. Note that there can only be fewer subsets otherwise, so the upper bound still holds.
We will now bound the number of distinct subsets that may be hit as the axis-alignod T2 is varied (while it is still along the direction ιy). Define the equivalence relation by ~ Lon if the same sequence of hypersurfaces in P intersect lxz and Taz (in the same order, including with multiplicities). To obtaín these equivalence classes, we will project the hypersurfaces in P onto a hyperplane orthogonal to the xy-direction. By the generalization of the Tarski-Seidenbery theorem to Pfaffian manifolds, we get collection of semi-Pfaffiat (2p(2x+-)))" (M + dy ) sets (van den Dries 1986), and these sets form cell complex with at most ([K())))((((2)++)))
cells Gabrielov & Vorobjov 2001 This is also a bound on the number of equivalence classes for the relation ~..
Putting together, for each axis-paralle direction zy, the number of distinct subsets of P hit by any line segment along the direction 2y is at most O(K22v(e-1) df (M min p} + (1)) (M + d))0 Thus, for all axis-parallel directions, we get that the total number of subsets of P that may be hit is at most
CK = =0 (p2ato--i) (M min(q. p} + d)2a ((0) ( +2 + dypo")).
For fixed M, d, p, this grows sub-exponentially in K, and therefore there is an absolute constant Ka such that Cx < 2 provided K > Ka..dd.p- This implies that a collection of KM.qd Pfaffian hy hypersurfaces cannot be shattered by axis-aligned line segments and establishes the desired claim.
We can now use the above theorem to establish the following general tool for verifying dispersion of piecewise- Lipschitz functions where the piece boundaries are given by Pfaffian hypersurfaces.
Theorem 7.3. Let li....,T: : IRP + R be independent piecewise L-Lipschitz functions, each having discon- tinuities specified by collection of at most K Pfaffian hypersurfaces of bounded degree d, Pfaffian degree M and length of common Pfaffian chain q. Let L. denote the set of usis-aligned paths between pairs of points in Re, and for each s E L define D(T, s) = {[1 tts that Elsup.ec D)T S sup.ec EID(T, 8)] + (OVTlogTT where the soft-O nolation suppresses constants in d. p. M.q.
T | le has a discontinuity along s}|. Then we have
Proof. Technical overview. We relate the number of ways line segments can label vectors of K Pfaffian hypersurfaces of degree d, Pfaffian degree M and common chain length g, to the VC-dimension of line segments (when labeling Pfaffian hypersurfaces), which from Theorem 7.2 is constant. To verify dispersion, we need a uniform--convergence bound on the number of Lipschitzness violations between the worst pair of points p, pf at distance < E, but the definition allows us to bound the worst rate of discontinuities along any path between p.p' of our choice. We can bound the VC-dimension of axis aligned segments against. Pfaffian hypersurfaces of bounded complexity, which will allow us to establish dispersion by considering piecewise axis-aligned paths between points p and p'.
Proof details. The proof is similar to the analogous results in (Balcan et al. 2020b Balcan & Sharma 2021). The main difference is that instead of relating the number of ways intervals can label vectors of discontinuity points to the VC-dimension of intervals, we instead relate the number of ways line segments
28

---

Published in Transactions on Machine Learning Research (04/2025)
can label vectors of K Pfaffian hypersurfaces of bounded complexity to the VC-dimension of line segments (when labeling Plaffian hypersurfaces), which from Theorem 7.2 is constant. To verify dispersion, we need a
bound on the number of Lipschitz failures between the worst pair of points a, a' at distance I e, but the definition allows us to bound the worst rate of discontinuitics along any path between ax a' of our choice. We can bound the VC dimension of axis aligned segments against bounded complexity Pfaffian hypersurfaces, which will allow us to establish dispersion by considering piecewise axis-aligned paths between points a and a'.
Let P denote the set of all Pfaffian hypersurfaces of degree d, from Pfaffian chain of length at most q and Pfaffian degree at most M. For simplicity, we assume that every function has its discontinuities specified by a collection of exactly K Pfaffian hypersurfaces (K could be an upper bound, and we could simply duplicate hypersurfaces as needed which does not affect our argument below). For each function 4, let T(*) e pk denote the ordered tuple of Pfaffian hypersurfaces
P whose entries are the discontinuity locations of l.- That is, 4 has discontinuities along (TT ........... KK/ ), but is otherwise L-Lipschitz.
(9))
For any axis aligned path s, define the function fe pk + {0, 1] by
if for some i E [K], Tr intersects 8, otherwise, (o {
fa(t))
fa(T)) =
where π = (MI....., Tx) E PK, The sum (((()))) counts the number of vectors (m ,.....=k) (11) that in- tersect 8 or, oquivalently, the number of functions fi...., by that are not L-Lipschitz on s. We will apply VC- dimension uniform convergence arguments to the class F {Ss PK {0, 1} s is an axis-aligned path]. (0) In particular, we will show that for an independent set of vectors (=1 7 K with high probability we have that Σ f (T))) is close to E[ Ei= fs(r(())] for all paths
Now, Theorem 7.2 implics that the VC dimension of F is at most K.g.d..- A standard VC-dimension uniform convergence argument for the class Ff imply that with probability at least 1 1 8, for all Sa E F
1 ())
Σ
E
1
16(
00 %
K KM + log(1/8) or
T
T
T
T
Σ (T( - E
Σ
(1(
s 0 (VTlog(1/6).
1=1
Now since () = Ei= (0)) we have for all and 6, with probability at least 1 1- 6, supsec D(T, s) S suPsEc ([)(TT,)] (og/loo Taking expectation and setting ō 1/VT implies
E(sup D(T, $)] S (1 - 8) sEC
sup O((Tlo((1/))) + --
SEC
s)] OlVTToo(VTT) + VT,
.EC
which implies the desired bound. Here we have upper bounded the expected regret by T in the low probability failure event where the uniform convergence does not hold.
The above result reduces the problem of verifying dispersion to showing that the expected number of discon- tinuities ETD(T, s)] along any axis-aligned path s is Ö(TT), which together with Theorem 7.3 implics that the sequence of functions is f-point-dispersed with f(T,c) = Ö(TT + VT), which in turn implies no-regret online learning (Theorem 7.1
7.3 Applications
We will now instantiate our general online learning results for concrete applications, including linkage clus- tering and regularized logistic regression. The koy new challenge for establishing online learning guarantocs is that we need to analyze the relative position of the Pfaffian structured discontimutiiss (in contrast, in the statistical learning setting, we only cared about the number of induced sign patterns).
29

---

Published in Transactions on Machine Learning Research (04/2025)
7.3.1 Online learning for data-driven agglomerative hierarchical clustering
We first show how to analyze the dispersion property of Pfaffian structured loss functions in agglomerative hierarchical clustering. Technical lemmas needed for the proof are deferred to Appendix E
Theorem 7.4. Consider on adversary choosing sequence of clustering instances where the t-th instance has symmetric distance matrie D(t) [0, R| and for all j.d follows distribution of which the probability densily function is bounded by some constant k. For the sub-family of M1 with o Omin for Omin < 0C, we have that the corresponding sequence of utility functions uit are f sooint-disperse with ((T,e) Ö(ET VT).
Proof. Technical overview. By using a generalization of the Descartes' rule of signs, we first show that there is at most one positive real solution for the equation
bi)) + (d(a), b2)) = U() + (d(ag,b2))
We then use 6 boundedness of the distances di to show that the probability of having a zero ot E I in any interval of width / is at most Ö(e). Using that we have at most n such boundary functions, we can conclude that E[D(T, s)] (n and use Thcorem 7.3.
Proof details. As noted in the proof of Theorem 6.1 the boundaries of the piecewise-constant dual utility functions are given by
(((a1,b))) + (d(a,,b2)) (d(d), K1) + (d(a)z b,))"
(1)
for some (not necessarily distinct) points a1, b1, 02 b2, d1 8/, a22. b/2 S.
We use the generalized Descartes' rule of signs (Jameson 2006 Haukkanen & Tossavainen 2011 which implies that the number of real zeros in a (for which boundary condition is satisfied) is at most the number of sign changes when the base of the exponents are arranged in an ascending order (since, the family {a" a E [4} is Descartes admissible on R), to conclude that the boundary of the loss function occurs for at most one point a* apart from a We consider the following distinct cases (up symmotry):
Case ds(01, b1) 2 do(a2, be) 2 do(d), b() 2 dg(al, bb). The number of sign changes is one, and the conclusion is immediate.
Case ds(a1, 61) do(a', b1) 2 da(az, b2) 2 da b2). The only possibility is dæ(a1, b1) do ( bi) and d2 b2) = d b2). But then, the condition holds for all a and we do not get critical point. This corresponds to the special case lie-breaking when merging clusters, and we assume ties are broken following some arbitrary but fixed ordering of the pair of points.
Case da(al, b)) 2 ds(ai,,)) 2 dæ b2) 2 dz(ah.bb) The number of sign changes two. Since solution, there is most one a" E ((0) corresponding to critical point.
Now, let 0. Consider an interval 1 [2)) with on Omin such that the width 02 on S If equation [ has solution a I (guaranteed to be unique if it exists), we have that
d(ai, b1) ((d( + (2), - (d(az, (d(az,b2))) b2)) 1/a"
Let Pı denote the density of d(aj, b1) which is at most by assumption, and let f(a") (d(a),b))))" + (d(ah,b,) b)))a' b2))" and (a") == (f(a"))l/a' We seek to upper bound Prp, (di(a)) a e Taf(a*) 2 0} to get bound on the probability that there is critical point in I.
30

---

Published in Transactions on Machine Learning Research (04/2025)
Now consider two cases. If f(a) S c" for all we have that di(a) f(a) e for all a e I. Thus, the probability of having critical point in is (sse) in this case.
Else, we have that f(a") > ex > 0 for some a" E I. Using Taylor series expansion for di (a) around a", we have
di di(a" d()==
Thus, the set {a)) a E I. f(a))) 2 0} is contained in an interval of width most [d{(a))O(()) implying upper bound of s|d, (a*) (()(( the probability of having a critical point in T.
Thus it is sufficient to give bound on (a))), We have
( (-1 In f(a")) + g(a")
dí(a') = di(a") ((aa))
a+2
f(a*)
di(a") -d(aa)lnd(aa))) (f(at)
a
where
g(a) In d(d(d), (Q(((d), b() +In ()dlb, In dn ba) (d)a2, b2))a"
Thus,
1 g(a")
di (a*) ((("))nn((aa))) Indi(a"))
(d"())
[aa)
g(aa)
+ +dd((a") (Inaa')nn(aaa))
[(at)
g((0))
+ +RInR)
f(a*)
Omin
Now using Lemma E.3
we get that
g(a")
S 1
+ In R,
f(a*)
a"
and thus,
Rn R O
1d (a*)) 50
Using that have at most n² boundary functions of the form Rln R knn and using Theorem 7.3 conclude that the sequence of utility functions are f-point- Ō a
conclude that E s)]
dispersed with ([T,))=(C Ö VT).
We also show how to tools above to establish the dispersion property for the M3 linkage clustcring algorithm family.
Theorem 7.5. Consider an adversary choosing sequence of clustering instances where the t-th instance has symmetric distance matriz D(t) R] and for all j.d follows distribution of which the probability density function is bounded by some constant (t) For the family of clustering algorithems M3,
have that the corresponding sequence of utility functions ug as function of the parameter (a)....,au) az) are d-poind-dispersed with f(T,c) (( VT).
31

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. Technical overview. It is sufficient to show dispersion for each ag keeping the remaining parameters fixed. This is because the definition of dispersion allows us to consider intersections of discontinuities with axis-aligned paths. WLOG, assume 02...., az are fixed. The boundary functions are given by solutions of exponential equations in 01 of the form
1
Σ BEA,bEB
(a) = B"
Σ
||
d'EA'VED'
for A, B,, C S. We can now use Theorem conclude that the discontinuities of ug are f d-ponttddisperse with f(T, c) = Ö VT).
7.3 together with Theorem 25 of Balcan & Sharma (2021)
Proof details. We will show dispersion for cach a; koeping the remaining parameters fixed. This is sufficient because, the definition of dispersion (Balcan et. al. 2020bb allows us to consider discontinuities along axis- aligned paths between pairs of points a, a' in the parameter space. WLOG, assume that ....... az are fixed. The boundary functions are given by solutions of exponential equations in an the form
Σ BE
Σ
(ddd)d(()
|
BA
d'EA'EER
for A,B,N, B' C S. We rewrite this equation in the form Σj=1 aee42 0 where, 01, bj In(d1( b)) for a, e Ax or a E A' x B' and aj = Al
b) for a. E A x or 0j BB (2 b for a', A' B'. The coefficients a are real with magnitude most R By Lemma E.4 we have that (a, 6) is n'-bounded for r¹ S max R R "), and therefore xR1//min
the coefficients aj have x--bounded density for x" S n2 = o n²
4-1 )
(using Lemma 8
Cmman
from Balcan al. (0118))) ). Using Theorem E.5 the probability there is a discontinuity along any segment along the direction 01 of width is = Ö(c). Thus, for any axis-aligned path between points a, a' e R the expected number of discontimuities for any utility function ug² (t E [T]) at most Lpı = Ô(c). We can
now apply Theorem to get
E[sup D(T, E s]] + Ö( /Tlo sEC
sEL Ö(ET) + Ö(VTlooT))
where L denotes the set of axis-aligned paths between pairs of points a' E IR,, It then follows that Elsupsec D(T, s)] = Ö(VT) for e 2 7-122, establishing that the sequence of utility functions uz (1) (T) is /-point-dispersed with ʃ(T, c) = ÔGT + VT).
7.3.2 Online learning for data-driven regularized logistic regression
We consider an online learning selting for regularized logistic regression from Section 6.3 The problem instances P. = (x (9, x()) online learner predicts the regularization coefficient x in each round. The regret of the learner is given by
v v are now presented online sequence of rounds l,.... T, and the
(ho, (P.) -Mx))
Ry E
where X arg min TT (P())). Our main result is to show the existence of a no-regret
learner in this setting.
32

---

Published in Transactions on Machine Learning Research (04/2025)
Theorem 7.6. Consider the online learning problem for tuning the logistic regression regulariza- lãon coefficient X stated above. There erists on online learner with expected regrel. bounded by OlVTloog (Amaz - Amsn)
Proof. Technical overview. The key idea is to use an appropriate surrogate loss function which well approximates the true loss function, but is dispersed and therefore can be learned online. We then connect the regret of the learner with respect the surrogate loss with its regret w.r.t. the true loss.
We consider an e-grid of À values. For each round t, to construct the surrogate loss function, sample uniformly random point from each interval [Amin + +e, Amin + (k++ + and compute the surrogate loss h 1 at that point, and use a linear interpolation between successive points. By Theorem [D.]] this has an error of at most O(e"), which implics the regret gap with the true loss is at most O(e"T) when using the surrogate function.
We show that the surrogate function is /-point-dispersst (Definition 4, Balcan et al. (2020b) with (TT,r) = r2. Using Theorem of Balcan et al. (2020b), we get that there is an online learner with regret Ol ((VTlog((AAm))))
Amin)/r)+ (TTr))+++++e = PlV/Tlog((Anaa -Amin//r) + Tr + Setting 1/4 and r == T we get the claimed regret upper bound.
Proof details. We consider an e-grid of X values given by intervals [Amin + kc, Amin (k + 1)c] for h 0 O...... Amare Ammin J. For each round L, to construct the surrogate loss function, we sample uniformly random
point 1 from each interval [Amin + ke, Amin + (A: + 1)e] and compute the surrogate model ((x. (A) at that point using Algorithm 2 for & (l2), and use a linear interpolation between successive points 2, , (k+1) which at most 2E apart. By Theorem D.1 we have that [|5(x....) (A) (x....) (A)ll2 = O(e2) for any A E [Amiu Amax], where ( (A) is the true model (that exactly optimizes the logistic loss) for (X,,3)). By Lemina 4.2 of Balcan et al. 2023b) we can conclude that the corresponding surrogate loss h (P;) also satisfics ( (P:) hx))))ll s (c2) for any [Amins Amaaz]
This implies the regret with respect to the true loss is at most O(e2T) more than the regret when using the surrogate function. Suppose X = arg min.eeAmmmdeeaee ΣT [P))) We have,
T RT
((x) hx (P.)
T
T
Eiha, (Pt) - hx- (P.)) >
Elhxx(PP) hx- (Po)
1=1
Σ E[h,, (Pt) +
T
$ Σ E(ha, h2(P))) + (0(T)
where â = arg min Pamin Ammul Σx (P.)).
We next show that the surrogate function is f-point- f-point-dispersed (Definition 4, Balcan et al. (2020b) with ((T,r) 2T. c. Indeed, let 0 < < c. Let I = (A1, A2) C [Aminy Amax] be an interval of length Then the probability (P.) has a critical point in 7 is at most r/c.
Using Theorem of Balcan et al. (2020b) combined with the above argument, we now get that there an online learner with regret O ((vT T log (ogg((Ama (Amax Amin)/r) + fTT,)) +Trr))+++++r = (ooooo(((Ama) Amin)/r) + Tr + +T). Setting é = -1/4 and 73/1 we get the claimed upper bound.
7
33

---

Published in Transactions on Machine Learning Research (04/2025)
8 Conclusion and future directions
In this work, we introduce the Pfaffian GJ framework for the data-driven statistical learning setting, provid- ing learning guarantees for function classes whose computations involve the broad class of Pfalfian functions. Additionally, we propose the Pfafian piecewise structure for data-driven algorithm design problems and es- tablish improved learning guarantees for problems admitting such a refined piecewise structure. We apply our framework to three different previously studied data-driven algorithm design problems (including hierarchical clustering, graph-based semi-supervised learning and regularized logistic regression), where known techniques do not yield concrete learning guarantees. By carefully analyzing the underlying Pfaffian structure for these problems, we leverage our proposed framework to establish novel statistical learning guarantees. We further study the data-driven online learning setting, where we introduce a new tool for verifying the dispersion property, applicable when the transition boundaries of the utility functions involve Pfaffian functions.
Our work opens many interesting directions for future rescarch. First, in the statistical learning setting, our work only focuses on providing an upper bound for the learning- theoretic complexity of function classes for which the dual admits the Pfaffian piecewise structure, and establishing lower-bounds remains an important question prior work (Balcan et al. 2017 Balcan & Sharma, 2021 Balcan et al. 2023b) establishes near- tight lower bounds for simpler algorithm families of clustering, semi-supervised learning and regression, that do not involve Pfaffian functions.
Tt is an interesting question to apply our techniques to other scenarios such as data-driven techniques for solving mixed-integer programs for example learning to cut and learning to branch (Balcan et al., 2018aa 2022c Cheng & Basu 2024).. Another concrete question is establishing online learning results for clustering families beyond M1 and for tuning the graph kernel in semi-supervised learning. We expect general tools here (e.g. Theorem 7.3 to be helpful, but a careful analysis is neoded to bound the expected nunber of discontinuities in any parameter interval. Finally, our framework focuses on establishing statistical sample complexity and no-regret learning guarantees for algorithm configuration for structured Pfaffian settings. Techniques have been developed in prior work for computationally efficient configuration of algorithms for clustering and semi-supervised learning (Balcan et al.) 2024b Sharma &
Jones )023), but only for algorithm families with simpler piecewise structure than those studied here.
9 Acknowledgment
This work was supported in part by NSF grants CCF-1910321 and 11S-1901403, the Defense Advanced Research Projects Agency under cooperative agreement HR00112020000 1202003,, and Simons Investigator Award MPS-SICSS-0626333..
References
Nir Ailon, Bernard Chazelle, Kenneth L Clarkson, Ding Liu, Wolfgang Mulzer, and C Seshadhri. Self- improving algorithms. SIAM Journal on Computing, 40(2):350-33) 375, 2011.
Nir Ailon, Omer Leibovich, and Vineet Nair. Sparse linear networks with fixed butterfly structure: Theory and practice, 2021.
Martin Authony and Peter L. Bartlett. Newral Network Learning: Theoretical Foundations. Cambridge University Press, USA, 1st edition, 2009. ISBN 052111862X.
Peter Armitage, Geoffrey Berry, and John Nigel Scott Matthews. Statistical methods in medical research. John Wiley & Sons, 2008.
Maria-Florina Balcan. Book chapter Data-Driven Algorithm Design. In Beyond Worst Case Analysis of Algorithms, T. Roughgarden (Ed). Cambridge University Press, 2020.
Maria Florina Balcan and Hedyeh Beyhaghi. New guarantees for learning revenue maximizing menus of lotteries and two-part tariffs. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Maria-Florina Balcan and Dravyansh Sharma. Data driven semi-supervised learning. Advances in Neural Information. Processing Systems, 34:14782-14799 2021.
34

---

Published in Transactions on Machine Learning Research (04/2025)
Maria-Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. Conference on Uncerlainly in Artificial Intelligence, 2024.
Maria-Florina Balcan, Avrim Blum, Patrick Pakyan Choi, John Lafferty, Brian Pantano, Mugizi Robert Rwebangira, and Xiaojin Zhu. Person identification in webcam images: An application of semi-supervised learning. In ICML 2005 Workshop Learning with Partially Classified Training Data, volume 2, 2005.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoretic foun- dations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pp. 213-274. PMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Interna- tional Conference on Machine Learning, pp. 344 353. PMLR, 2018a.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 614. IEEE, 2018b.
Maria-Florina Balcan, Travis Dick, and Colin White, Data-driven clustering via parameterized Lloyd's familics. Advances in Neural Information Processing Systems, 31, 2018c.
Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. In International Conference Learning Representation, 2020a.
Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting, In Conference Uncertainty in Artificial Intelligence, pp. 908- PMLR, 2020b.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm configuration: The knie of dual class approximability. In International Conference on Machine Learning, pp. 580- 590. PMI.R, 2020c.
Maria-Floo Florina Balcan, Dravyansh Sharma, and Travis Dick. Learning piecewise Lipschitz functions in chang- ing environments. In International Conference on Artificial Intelligence and Statistics, pp. 3567-3577. PMLR, 2020d.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 919 932, 2021a.
Maria-Florine Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to- to-learn non- convex lipsehis- functions. In Newral Information Processing Systems, 2021b.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015-4027, 2021c.
Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the ElasticNet across instances. Advances in Neural Information Processing Systems, 0-27769-27782 2022a.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved sample complex- ity bounds for branch-and-cut. In 28th International Conference on Principles and Practice of Constraint Programming, 2022b.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnability of Gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35:33890- 10:33890-33903, 2022c.
Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang, An analysis of robustness of non-Tipschitz networks. Journal of Machine Learning Research, 24(98):1-43 2023a.
35

---

Published in Transactions on Machine Learning Research (04/2025)
Maria-Florina Balcan, Anh Nguyen, and Dravyansh Sharma. New bounds for hyperparameter tuning of regression problems across instances. Advances in Newral Information Processing Systems, 36, 2023b.
Maria-Florina Balcan, Dan Deblasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? Journal of the ACM, (1(5)11-58, 2024a.
Maria-Florina Balcan, Christopher Seiler, and Dravyansh Sharma. Accelerating erm for data-driven algo- rithm design using output-sensitin techniques. Advances in Neural Information Processing Systems, 37: 72648-72687, 2024b.
Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Sample complexity of data-driven tuning of model hyperparameters in neural networks with struct parameter-deeendeen dual function. arXiv preprint arXiv:2501.1978, 2025.
Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural 2002.
results. Journal of Machine Learning Research,
Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference Learning Theory, pp. 2013-2044 PMLR, 2022.
Avrim Blum and Shuchi Chawla. Learning from labeled and unlabeled data using graph mincuts. Interna- tional Conference on Machine Learning, 2001.
Avrim Blum, Chen Dan, and Saced Seddighin. Learning complexity of simulated anncaling. In International conference on artificial intelligence and statistics, pp. 1540-1548. PMLR, 2021.
Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien. Semi- Supersiue Learning. The MIT Press, 1st edition, 2010. ISBN 0262514125.
Hongyu Cheng and Amitabh Basu. Learning cut generating functions for integer programming. Advances Neural Information Processing Systems, 37:61455-61488, 2024.
Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (ods.), Advances in Neural Information Processing Systems, volume 37, pp. 25036 25060. Curran Associates, Inc., 2024.
Michael Chichignoud, Johannes Lederer, and Martin J Wainwright. A practical scheme and fast algorithm to tune the lasso with optimality guarantees. Journal of Machine Learning Research, 17(229):1122 20, 2016.
Ally Yalei Du, Eric Huang, and Dravyansh Sharma. Tuning algorithmic and architectural hyperparameters in graph-based sumi-super learning with provable guarantees. Conference on Uncertointy in Artificial Intelligence, 2025.
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandcop Silwal, and Tal Wagner. Learning- based support estimation in sublinear time. In International Conference on Learning Represenlations, 2021.
Alberto Fernández and Sergio Gómez. Versatile linkage: a family of space-conserving strategies for agglom- erative hierarchical clustering. Journal of Classification, 37(3))584-8)) 597, 2020.
Andrei Gabrielov. Multiplicities of Pfaffian intersections, and the lojasiewicz inequality. Selecta Mathematica, 1:113-127, 1995.
Andrei Gabrielov and Nicolai Vorobjov. Complexity of cylindrical decompasitions of sub-pfaffian sets. Journal of Pure and Applied Algebra, 164((-2):179 197, 2001.
Paul Goldberg and Mark Jerrum. Bounding the Vapnik- Chervonenkis dimension of concept classes parame- terized by real numbers. In Proceedings of the sixth annual conference on Computational learning theory, pp. 361-369, 1993.
36

---

Published in Transactions on Machine Learning Research (04/2025)
Rishi Gupta and Tim Roughgarden. A PAC approach to application-speelfe algorithm selection. In Proceed- ings of the 2016 ACM Conference. on Inmovalions in Theoretical Computer Science, pp- 123-134, 2016.
Pentti Hankkanen and Timo Tossavainen. A generalization of Descartes' rule of signs and fundamental theorem of algebra. Applied Mathematics and Computation, 218(4):1203-12277 2011.
Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. Advances in Neural
Information Processing Systems, 32, 2019.
Piotr Indyk, Tal Wagner, and David Woodruff. Few-shot data-driven algorithms for low rank approximation. Advances in Newral Information Processing Systems, 34:10678-10690, 2021.
Piotr Indyk, Frederik Mallmann-Trean Slobodan Mitrovic, and Ronitt Rubinfeld. Online page migration with ml advice. In International Conference Artificial Intelligence and Statistics, pp. 1655-1670. PMLR, 2022.
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction statistionl learning, volume 112. Springer, 2013.
Graham JO Jameson.
Counting zeros of generalised polynomials: Descartes? rule of signs and Laguerre's extensions. The Mathematical Gazette, 20(518):223-22) 234, 2006.
Marek Karpinski and Angus Macintyre. Polynomial bounds for VO dimension of sigmoidal and general Pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169-176, 1997.
Mikhail Khodak, Maria-Florina Balcan, Amoct Talwalkar, and Sergei Vassilvitskii. Learning prodictions for algorithms with predictions. Advances in Neural Information Processing Systems, 35:3542 3555, 2022.
Askold G Khovanski. Fewnomials, volume 88. American Mathematical Soc., 1991.
Thomas Lavastida, Benjamin Moscley, R Ravi, and Chenyang Xu. Learnable and instanco-robust predictions for online matching, flows and load balancing. arXiv preprint ar 0rxi::2011.11770 2020.
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David Woodruff. Learning the positions in countsketch. In The Eleventh International Conference on Leorning Representations, 2023.
Gordon S Linoff and Michael JA Berry. Dala mining techniques: for marketing, sales, and customer rela- tionship management. John Wiley & Sons, 2011.
Stuart Lloyd. Least squares quantization in PCM. IEEE transactions on information theory, 28(2):129-15) 137, 1982.
Daay Luz, Meirav Galun, Haggai Maron, Ronen Basri, and Irad Yavneh. Learning algebraic multigrid using graph neural networks, 2020.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1 25, 2021.
John Willard Milnor and David W Weaver. Topology from the differentiable viewpoint, volume 21. Princcton university press, 1997.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-33 35, 2022.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
Fiomn Murtagh and Pedro Contreras. Algorithms for hicrarchical clustering: an overview, Wiley Interdisci- plinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-97, 2012.
37

---

Published in Transactions on Machine Learning Research (04/2025)
Sanjay Kumar Palei and Samir Kumar Das. Logistic regression model for prediction of roof fall risks in bord and pillar workings in coal mines: An approach. Safely science, 47(1):88 96, 2009.
David Pollard. Convergence of stochastic processes. Springer Series in Statistics, 1984.
Saharon Rosset. Following curved regularized oplimization solution paths. Advances in Neural Information Processing Systems, 17, 2004.
Shinsaku Sakaue and Taihei Oki. Improved generalization bound and learning of sparsity patterns for data- driven low-rank approximation. In International Conference on Artificial Intelligence and Statistics, pp. 1 10. PMLR, 2023.
Dravyansh Sharma. No internal regret with non-convex loss functions. In AAAI Conference on Artificial Intelligence, 2024.
Dravyansh Sharma and Maxwell Jones. Efficiently learning the graph for semi-supervised learning. PMLR, 2023.
Uncertuinly in Artificial Intelligence, pp.
Dravyansh Sharma and Arun Suggala. Offlin-to-online hyperparameter transfer for stochastic bandits. In
Proceedings of the AAAT Conference on Artificial Intelligence, volume 39, pp- 20362-2011 20370, 2025.
Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algo-
rithms. Mathematical Programming, 97:375-404 2003.
Lou van den Dries. generalization of the Terski-Seidenberg theorem, and some nondefinability results. Bulletin of the American Mothematical Society, 15(2):189 193, 1986.
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974.
Martin J Wainwright. High-dimensional statistics: A non-asymplolic viewpoond, volume 48. Cambridge university press, 2019.
Hugh F. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167-178, 1968.
Alexander Wei and Fred Zhang. Optimal consstres trade-offs for learning-augmente online
algorithms. Advances in Neural Information Processing Systems, 33:8042-8053, 2020.
Yaqi Xie, Will Ma, and Linwei Xin. VC theory for inventory policies. arXiv preprint orXiv:2444.11000 2024.
Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions on neural networks, (3):645 678, 2005.
Richard Zemel and Miguel Carreira-Perpinán. Proximily graphs for clustering and manifold learning. Ad- vances in neural information processing systems, 17, 2004.
Tong Zhang, Some sharp performance bounds for least squares regression with L1 regularization. Annals of Statistics, 2009.
Xiaojin Zhu. Semi- superviee learning with graphs. Doctoral thesis, Carnegie Mellon University, 2005.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. ProQuest number: information to all users, 2002.
Xisojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Synthesis lectures artificial intelligence and machine learning, 3(1):1-130, 2009.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International conference Machine learning (ICML-03). pp. 2003.
38

---

Published in Transactions on Machine Learning Research (04/2025)
Appendix
A Preliminaries
In this section, we first recall some additional classical notions and results on learning theory, which also helpful in our analysis. For completeness, along with the definition of pseudo-dimension (Definition [ we now give formal definition of the VC-dimension, which counterpart of pseudo-dimension when the function class is binary-valued.
Definition 11 (Shattering and VC-dimension, Vapnik & Chervonenkis 1974p. Let 2 is class of binary- valued functions that take input from X. Let = Dmn C X' be the set of m. input instances, we say that is shattered by if
((.()))......ud
a E E = 2m
The VC-dimension of u, denoted VCdim(U4), the largest size of the set S that can be shattered by U.
Rademacher complexity (Bartlett & Mendelson 2002 is another classical learning-theorett complexity measure for obtaining data-dependent learning guarantees.
Definition 12 (Rademacher complexity, Bartlett & Mendelson 2002 Let U be a real-valued function class be set of m input instances drawn from
which takes input from domain U. Tet S = ( Fm some problem distribution D over X. Then the empirical Rademacher complexity Is(Uf) of U with respect to U is defined as
ss( Eg
sup well
The Rademacher complexity u for n samples is then defined as
1 m
lm( = ES-Dm Es-DDm(m(()) ES-D.
sup
o,u(
We now recall the classical notion of uniform convergence.
Definition 13 (Uniform convergence). Let U be real-valued function class which takes input from X, and D is distribution over X. If for any 0, and any 8 [0, 1], there exists [c, 8) s.t. with probability least 1 - 8 over the draw of m 2 N(c, 8) samples æI, ~ D, we have
Am sup
u ((x;)) - E (u)=)(())) Sc.
well
1=1
then we say that FF uniformly converges.
B Omitted proofs from Section 4
In this section, we will present basic properties of Pfaffian chain/functions and proof for Theorem 4.2
B.1 Some facts about Pfaffian functions with elementary operators
In this section, formalize some basic properties of Pfaffian functions. Essentially, the following results say that if end up with function that is also the Pfaffian function from that Pfaffian chain. Moreover, even if the two Pfaffian functions are not from the same Pfaffian chain, we can still construct a new Pfaffian chain that contains both the functions and the newly computed function as well (by simply combining the two chains).
http:///bwcccnni/iiliiiggg////// hultiplying/diiidiiii two Pfaffian functions from the same Pfaffian chain, we
Fact 1 Adddition/Subrractionn Let g, h be Pfaffian functions from the Pfaffian chain C(a, m..... ng) (a e Rd).. Then have g(a) + h((a) also Pfaffian functions from the chain C.
39

---

is a Published in Transactions on Machine Learning Research (04/2025)
are polynomial of a and Thi do, (g h)) are also polynomial of a and T/: which concludes the proof.
Proof. For any 0s: have Bag (g = h)(a) du; 9(a) = Ba, h(a). Since agia) a
da; and 8h(a) de;
]
Fact 2 (Multiplication). Let 9, h be Pfaffian functions from the Pfalfian chain C(a, C(a, ma) (a R4) of length q and Pfaffain degree M. Then have s(a)k(a) is a Pfaffian function from the chain Ca ......
Proof. For any as we have 8u, (a(a))(()) = ah(a) + h ag(a) which is polynomial of a, m. Mg. 9, h. J
Fact 3 (Division). Let g. be Pfaffain functions from the Pfaffian chain C(a, :g..... ) (a E (Rd) of length
and Pfaffian degree M. Assume that h(a) + O, then we have g(a) is Pfalfian function from the Pfalfian chain (" Ta 1 h R)
k(a
Proof. For any ai we have 8 g(aa)
Og(a) g(a) Oh(a)²
Dag h(a) Ma Da. is polynomial of a, Ti..... . Ta: 1 R.
Bac A(a)
Fact 4 (Composition). Let h be Pfaffian function from the Plaffian chain C(a, ",,... mg) (a Rd), and g be Pfaffian function from the Pfaffain chain (b Th...., n(p) (b R). Then g(h(a)) Pfaffian function from the Pfaffian chain C" (" (...,, e Mg. h, (h), (1))))))).()()))))
Proof. For any oi, we have Og(h(a)) ah(a) (g(h(a))
da Ja, ai(aa Note that Og(h(a)
ah(aa P(h(a), o/ (h(a))...... (h(a)),
where P is some polynomial. Therefore, g(h(a)) is a Pfaffian function from the Pfalfian chain C" (a, m..... Tg h, 1/2 (()())........((()))
B.2 Background for proof of Theorem 4.2
In this section, we will present the proof of the Pfaffian GJ algorithm guarantee (Theorem 4.2 To begin with, we first recall some preliminary results about standard technique for establishing pseudo-dinension upper-bound by analyzing the solution set connected components bound.
B.2.1 Preliminaries on the connection between pseudo-dimension and solution set connected components bound
We first introduce the notion of regular value. Roughly speaking, given a smooth map F Rd R where r S d, regular value IR' is the point in the image space such that the solution of F(a) is well-behaved.
Definition 14 (Regular value, Milnor & Weaver 1997p. Consider C' functions fi...., fr R - R where Then
S d, A C Rd, and the (smooth) mapping F A + I' given by F(a) = (a........ (G....., ) E R" is a regular value if either: (1) F ("I((( = 0, or (2) F (d-r) ddmmeedmmnnso sub-manifold of Rdd
It is widely known that by Sard's Lemma (Milnor & Weaver 1997), ; the set of non-regular values of the smooth map F' has Lebesgue measure Based on this definition, we now present the definition of the solution set connected components bound.
Consider func- tions T....., TK X x A + E, where A C Rd. Given Ti...., NN assume that (Z, Rd R is C² function for i E [K] and j E [N]. For any F IR + R", where F(a) (0) (a), ..., (a)) with θ chosen from the NK functions Ti (xx)), if the number of connected components of (e), where e is a regular value, is upper bounded by independently on Fi, r, and c, then we say that is the solution set connected components bound.
Definition 15 (Solution set connected components bound, Karpinski & Macintyre 1997..
The solution set connected components bound offers an alternative way of analyzing VC-dimension (or pseudo-dimension) of related parameterized function classes, which is formalized in the following lemma Karpinski & Macintyre 1997 We include high-level proof sketch for comprehensiveness.
40

---

Published in Transactions on Machine Learning Research (04/2025)
Consider the binary-valued function ((x, a), for E X and a E IRd constructed using the boolean operators AND and OR, and boolean predicates in one of the two forms "r(x, a) > 0" or "T(x, a) = 0". Assume that the function (ax a) can be one of at most K forms (Ti,.... TK), where (2) (i [K]) is a C function of a for any fixed x. Let '6 = { X - {0, 10,1] a E Rd) where &a = (.. Then
Lemma B.1 Karpiiski & Macintyre, 1997
VCdim( S 2 B + (16 + 2og K)d,
where B is the solution set connected components bound.
Proof Sketch. The key idea involved in proving the lemma is combinatorial argument due to Warren 19688) which bounds the number of connected components induced by collection of boundary functions by 2j=0 bj- where by is the number of connected components induced by intersections of any j functions. This can be combined with the solution set connected components bound B, to get bound Σ 2 (2) B S B (2Nke) the total number of connected components. The result follows from noting 2 < B (2 if the N instances 21,...;Wy By to be shattered.
We now recall a result which is especially useful for bounding the solution set connected components bound B for equations related to Pfaffian functions.
Lemma B.2 (Khovanski 1991 page 91). Let C be a Pfaffian chain of length q and Pfaffian degree M, consists of functions fi....,fa in Rd. Consider non-singular system of equations (1(a) where r I d, in which (:(a) (i E [r]) is polynomial of degree at most A in the variable and in the Pfaffian functions J1....,Jy: Sq- Then the manifold of dimension k d delermined by this system has al most 2dl 1)5 - (r (r- dd) connected components, where S = r(A - 1) + dM +1.
O, = 0
The following corollary the direct consequence of Lemma B.2
Corollary B.3. Consider the setting in Lemma B.1 Assume that for any fixed æ, TI E [K] is Pfaffian function of degree at most A from Pfaffian chain C with length and Pfaffian degree M. Then
B < 2dg(d4 1)/2 1/2
The following lemma gives connection between the number of sign patterns and number of connected components.
Given N real-valued functions hi...., hN, the number of dis- tinct sign patterns h (a)....,. (()))) a Rd] is upper-boundee by the number of connected components Rd (a E Rdd (a) =). 0).
Lemma B.4 (Section 1.8, Warren 1968
The following result is about the relation between the connected components and the solution set connected components.
Lemma B.5 (Lemma 7.9, Anthony & Bartlett 2009 Let (fi...., fx be set of differentiable functions that map from R& + R, with regular zero-set intersections. For each i, define 7, the zero-sct of fe: 7 {a E gd fi(a) = 0}. Then
CC
Rd_
U Z, VEINI
S Σ CC
n Zi
SCIM
iES
Combining with Definition 15. the RHS becomes B BE (N) < B
((NN)
(NN
for N 2 d.
41

---

Published in Transactions on Machine Learning Research (04/2025)
B.2.2 Pfaffian formulae
We now introduce the building block of the Pfaffian GJ framework, named Pfoffian formula. Roughly speaking, a Pfaffian formula boolean formula that incorporates Pfaffian functions.
Definition 16 (Pfaffian formulae). Pfaffian formulae f =: + {True, False} is disjunctive normal form (DNF) formula over boolean predicates of the form g(a, .,,...... mh) 2 O, where g is a Pfaffian function of Pfaffian chain C(a, 7.....,7..). myy.
The following lemma essentially claims that for any function class, its computation can be described by a Pfaffian formula and the corresponding Pfaffian chain exhibits bounded complexities, then the function class also possesses bounded pseudo-dimension.
Lemma B.6. Suppose that each algorithm. I. E L is parameterized by a E Rdd Suppose that for every X and E IR, there is a Pfaffian formala far of Pfaffian chain C with length q and Pfaffian degree M, that given L E L, check whether L(x) > Suppose that far has at most K distinct Pfaffian functions in its predicates, each of degree at most A. Then,
Pdim (C) S d² + 2dq log( A + M) + 4dq log d + 2d AK + 16d.
Proof. This lemma is direct consequence of Lemma B.1 and Corollary B.3
C Additional details and omitted proofs for Section
In this section, we will present an additional comparison between our proposed framework and the general piecewise structure framework by Balcan et al. (2021a), as well as detailed proof for Lemma 5.3
C.1 A detailed comparison between the piece-wise structure by |Balcan et al. (2021a) and our refined Pfaffian piece-wise structure
In this section, we will do a detailed comparison between our refined Pfaffian picco- bice-wise structure, and the piece-wise structure proposed by [Balcan et al. (2021a). First,, we derive concrete pseudo-dimension bounds implied by Balcan al. (2021a) when the refined Pfaffian piece-wise structure is present. We note that this implication is not immediate and needs careful argument to bound the seariingthheoreie complexity of Pfaffian piece and boundary functions which appear in their bounds.
Thcorem C.1. Consider the utility function class U {ua X - R aaac a A), where A C Rd. Suppose Uhat U admils (k5,kg, q, dM) d)PPafffan piece-wise wise structure. Then using Theorem 5.1 by Balown el al. 2021d), we have
Pdim(U)) = Old + dq log( (A + M) + dg d + d) logl(d dg (og(AA + M) + log d + d)kgl).
Proof. Consider utility function class u {ua X + IR E A}, where A C Rd. we assume that ' admits (ky, kg..gg q. M, A, Pf-fffin piece-wise structure. Then, 2t also admits (F, G. kg) piece-wise structure following Definition 7 Here, H. is the set of Pfaffian functions of degree A from Pfaffian chain of length q and Pfaffian degree M, and G is the set of threshold functions which are also Pfaffian functions of degree A from the same Pfaffian chain of length q and Pfaffian degree M.
The first challenge in using the framework of Balcan et al. is that it only reduces the problem bounding the learning-theoretin complexity of the diecewise-structure utility function to that of bounding the complexity of the piece and boundary functions involved, which is non-trivial in the case of Plafian functions. That is, we still need to bound Pdimm(F*) and VCdim(G*), where F and G are dual function classes of J and
G, respectively. To bound VCdim(G"), we first consider the set of N input instances S [01, 101,....90 gN C g, and bound the nunber of distinct sign patterns,
ss(N)= (())(.)))....). a E A) (x((
| E AHL.
42

---

Published in Transactions on Machine Learning Research (04/2025)
From Lemma B.5 and
B.4 and B.2
can bound (N) as
CeN (eN) [s(N) -022 +M)) (eN)
Solving the inequality 2N 0120166-11122 + M)jd (=t) have VCdim S dg(dg-1)
d log A + dg log(d M)).
We now bound Pdim(FF). By definition, we have F = : a A}. Again, to bound Pdim(F)) we first consider the set S = (fi...., fN] C F and a set of thresholds (ri,.... TN and we want to bound the number distinct sign patterns
- -1), (N) ( -xn)) E
rN)) (((sin((f((a) -r. (igl - rx)) ) a = AHH.
Using similar argument as for 9", we have Pdimm(F)= (dF dg log( A + M) + dy log d + d). Combining
with Theorem 3.3 by Balcan et al. 2021a we conclude that
Pdim(4)) ((dpqp dg log(( A + M) do d + d) logi(d dq log( M) + dg d + d)kkl).
Remark 6. Compared our bounds in Theorem 5.2 Theorem C.1 (implied by Balcan al. (2021a) has two notable differences. First, our bound is sharper by logarithmic factor Ologg(d'q dy log( ( M) dg log d + d)), which is consequence of using sharper form of the Sauer-Shelah lemma. Second, we have dependence on logarithmic term ky which is asymptotically dominated by the other terms, and corresponds to better multiplicative constants than Theorem C.1
C.2 Omitted proofs for Section 5.3.1
a E A} where A C Id. Assume there is a partition p= {Ai..... An of the parameter space A such that for any problem instance x E X, the dual utility function uz is a Pfaffian function of degree at most A in region A, from a Pfaffian chain CA. of length at most q and Pfaffian degree M. Then the psoudo-dimension of V is upper-bounded as follows
Lemma 5.3 (restated). Consider a function class V = [Va :
X' + :''
Pdim(V) = dl gd + M) qd log d log n).
Proof. Consider N problem instances TI...., EN with N corresponding thresholds TI, ....... TN, we first want to bound the number of distinct sign patterns (N) = (siinn(va (x1) -T1), sign(va (xN) TN)) a e AH)
Denote II (N) = ((sign(va(x)) - TI), (ig (æx) - TN)) a E ArH,, we have [l S Σ 11 (N). For any E [n], from the assumptions, Lemma 5.2 and using Sauer's Lemma, we have
cNN S TT(NN) <
S
where S C + lo M) + ldl d) for some constant C. Therefore Iy S n (=N) (
Solving
the inequality N (N),,, we conclude that Pdim(V) O(g² dd + gdlog(A M) gd d + log n) expected.
D Additional background and omitted proofs for Section 6
In this section, will present the deferred proofs well additional for various applications in Section
43

---

Published in Transactions on Machine Learning Research (04/2025)
D.1 Omitted proofs for Section 6.1
Theorem
6.2
Let H2 be class of functions
H2 [ug 0: (S, 0) (S, R e A([L))
mapping clustering instances 6) to [0, 1] by using merge functions from class M2 and an arbitrary merge function. Then Pdim(H2) O
Proof. Fix the clustering instance (5, 6). Suppose A, _ S and A', B' S S are two candidate clusters at some merge step of the algorithm. Then A, B is preferred for merging over A', B' iff
1/a
1/a
Σ AEA,RER
(og(a.b))
S |
Σ ,EA'
(G((a.b))
|A|BI]
equivalently,
Σ &EADEB
b))( <
1
Σ
(ōg(a, b))*
A|
dEA',bEB'
For distinct choices of the point sets A, B, A', B', we get at most (²)² 24n distinct boundary conditions across which the merge decision at any step of the algorithm may change.
We next show that the boundary functions constitute a Pfaffian system in a, a,,....., 31 and bound its complexity. For each pair of points a, E S, define fa,la, 3) = Tp(ā.]] (a, = d b) and ha.(aa 3) = Es(a,b)". Similar to the proof of Theorem 6.1 these functions form a Pfaffian chain C(a, 3. fa.b: Io,b, ho,b) for a, b E S. We can see that C is of length q == =32 and Pfaffian degree M 2. The boundary conditions
all be written in terms of the functions ( meaning kg n² and de- gree A 1. Again, note that k n+1. Therefore, H. admits (n 1,, 3n 1, P)-Pfaffian piece-wise structure. Applying Theorem 5.2 now gives that Pdim(H2) = On + log L+ log 2 = O(n' ]
Theorem 6.3
Let H3 be class of functions
H3s {ug (8,6) - m(Ag(S,))) as E R [0)}
mapping clustering instances (8 to [0.1] by using merge functions from class Ma. Then Pdim(Hs)) O(n
Proof. Fix the clustering instance (S, 8). Suppose A. S S and A', C S are two candidate clusters at some merge step of the algorithm. Then A, B is preferred for merging over A', B' iff
E.a. a
1/ a
Σ AEA
-
1
II Megn (6((a,))))
B|||B|
A'||Ba
or equivalently,
Σ
(o,a <
Σ
Ie
A
A'
dEA.B
GEA'.EER
For distinct choices of the point sets A, B, A', B', we get at most (2")² < 24n distinct boundary conditions across which the merge decision at any step of the algorithm may change.
We next show that the boundary functions constitute a Pfaffian system a1,...,0y and bound its complexity. For each pair of points a S, define ha ... az) := [1 b)) Note that Bo. == In (a, b)ha (al.,,.a...........
and thus these functions form Pfaffian chain of chain length n² and Pfaffian degree The boundary conditions can be all written in terms of the functions (ha.b) ha,ess moaning that kg 2th and A Again, note that ky n n+1 Therefore H2 admits (n+1,2** 14t n² 1, Pfafffan piece-wist wise structure. Applying Theorem B.6 now gives that Pdim(H2) O
44

---

Published in Transactions on Machine Learning Research (04/2025)
D.2 Additional background and omitted proofs for Section 6.3
Theorem D.1 (Rosset 2004. Given problem instance P = (X, y, X vals yoat) Tm.pp for sufficienlly small
E> 0, if we use Algorithm
to approzimate the solution B(x.s) (2) of RLR under E (tz) constraint by
((xx)) (A) then there is a uniform bound ((c²) on the error |1 (2) ((x,)) (2)ll2 for any X E [Amias Amax].
For any x E (de,de-1l, where d Amin kc, the approzimate solution BL0 (2) is calculated by
(2) = 36( - ( (x.)) 1 [VI (1 (x.0)) + Asgn
[ = aid + bt:
if we use Algorithm 1 for RLR under l constroint, or
0 (2) (2) 0..0) - [ (x.) 22
VI (8 (x.1) + +288(00 =d,A + by.
if we use Algorithm 2 for RLR under lg constraint.
A Algorithm Approximate incremental quadratic algorithun for RLR with & penalty, Rossel, 2004
Set 1862 = ((x,,) (Amin), = 0, small constant 8 E Rso, and A = {i I [8xx (w * 0}.
while d < Amax do
de+1 d +
( = (8) A -
1 [ (xx))) + Aet1 sgn (8(-) {
1
P411 -
A= AU # Al
VI( (X,3)) >
d+11}
A= A /j EA ++t+11
| <)}
Algorithm 2 Approximate incremental quadratic algorithm for RLR with l penalty, Rosset 2004
Set ( (x(x,)) (Amin),
while X1 Amax do
A+t1 = d +
((0)()) (A) 8/0 - [ (x.1)) + 2 [V] (8(22 + 2
1=
E
Additional background and omitted proofs for Section 7
We record here some fundamental results from the theory of Pfaffian functions (also known as Fewnomial theory) which will be needed in establishing our online learning results. The following result is a Pfaffian analogue of Bezout's theorem from algebraic geometry, useful in bounding the multiplicity of intersections of Pfaffian hypersurfaces.
Theorem E.1 [hovanski
1991 Gabriclov 1995). Consider system of equations =.. (x) 0
where g:(x)) = P((x, fi(x)..... fo (x)) is polynomial of degree at most d, in x E R and f1.... fg are sequence of functions that constitute a Pfaffian chain of length and Pfaffian degree at most M. Then the number of non-degenerate solutions of this system does not exceed
1 ... dr (min (g. (. + d1 + d, n + 1)9.
45

---

Published in Transactions on Machine Learning Research (04/2025)
E.1 Online learning for data-driven agglomerative hierarchical clustering
We will now present some useful lemmas for establishing Theorem 7.4 The following lemma generalizes Lemma 25 of Balcan et al. (2020b).
Lemma E.2. Let X Xn be a finile collection of independent random variables each having densilies upper bounded by K. The random variable Y =i= BiX, for some fixed scalars Bi...., , Bn with E 3: has density fy satisfying frly)= S R for all y-
Proof. We proceed by induction on n. First consider n = 1. Clearly Y X1 and the conclusion follows from the assumption that X1 has density upper bounded by K.
Now suppose n > We have Y 31X1 + 32X2 ...... BnX, 81Xi (1 Bi)X', where X' 1-8 Ei= B,X, By the inductive hypothesis, X' has density fx which is upper bounded by k. Let fx, denote the densily of X1. Noting X" = I-9:
X and using the independence of X' and X1, gel.
fv f fxr
y --
31
fx, (x)(d)d $ J Rfx, (z)dz n.
1- $1
This completes the induction step.
We will now present a useful algebraic lemma for establishing Theorem 7.4
Lemma E.3. If a >> O, a, b.b. O, and a ba c. > 0, then
a Ina + 6a In ca
Inc
I + max
a + 1a ca
Proof. We consider two cases. First suppose that c > a and c e> b. We have that
a In ba Inb cd Inc
a on 6at Inc ca Inc
ca < a tb - $ chn
a + ba
in this case.
Now suppose e S a (the case e S b is symmetric). Observe that for a > 0, the function f(x) = x² K is monotomically increasing for < Ke 1/0 when K, a, >> O. This implies for K = max(a, b)e//a.
K < a
K
K 5
ca In
In
< + 1 In
c
a
equivalently,
a Iaa+bmmb c Inc < In k(a" + - cc)).
Since, a + b --- <a> >0>0, 0, we further gel
Ima+bbi bat Inb Inc a + ba ca
1 + max (a, b}. Ink
a
To establish Theorem 7.5
we first present a useful lemma, and restate useful result from Balcan & Sharmal
2021
46

---

Published in Transactions on Machine Learning Research (04/2025)
Lemma E.4. Suppose X is real-calued random variable taking values in [0 for some M RR and suppose its probability densily is upper-bounded by K. Then, Y = Xa for E [Omin: 1] for some Omin >> 0 lakes values in [0, M] with a k'-bounded density with k¹ S - max M mmm 3..
amain
Proof. The cumulative density function for Y is given by
Fy Pr(y =0)= S s///
pii = 1o fx(x)dr,
=
where (x(x) the probability density function for X. Using Leibniz's rule, we can obtain the density function for
d (r(4)
Pr(
dy
d 1//a
fx(x)dz
dy Jo
y 1/a
dy
y
a
1-1- < y S 1 and therefore JY (1) < Now for y 1, y -
x
Else, S M, and [r S
M
Pman
We will also need the following result due to Balcan & Sharma when the discontimuities of the loss function are given by roots an exponential equation in the parameter with random coefficients. We refer the readers the original paper for a proof.
2021 which is useful to establish dispersion
Theorem E.5 (Balcan & Sharma, 2021). Let db(x) = Ei= aee be random function, such that coefficients ag real and of magnitude at most R, and distributed with joint density at most k. Then for any interval I of width at most e, Pr(Ø has zero in 1) < Ō(e) (dependence on bi, n, R. suppressed).
47


Reviews:
[{"review_id": "WZOYK355o4", "reviewer": "Reviewer_BX7E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- Extends GJ framework to Pfaffian GJ framework (rational functions --> Pfaffian functions)\n  * inspired by [Bartlett-Indyk-Wagner, COLT 2022]\n  * builds on [Goldberg-Jerrum, COLT 1993]\n- Introduces a general approach (Theorem 7.2, Theorem 7.3) for verifying the\n  dispersion property [Balcan-Dick-Vitercik, FOCS 2018]\n- The two examples in Section 4.1 are very helpful.\n- Excellent applications: hierarchical clustering, graph-based SSL, regularized logistic regression\n- Section 6 is a good tutorial for how to use the GJ Pfaffian framework (**highlight of the paper**)\n- Section 7.3 shows how to apply the online learning ideas to agglomerative hierarchical clustering and regularized logistic regression\n\n**Weaknesses**\n- The online case assumes a large number of samples and compute to find good hyperparams,\n  but it may be better in practice to run a portfolio solver with the same compute budget\n  (i.e., trying lots of different hyperparameter combinations) to get a good solution for the\n  sample at time $t$. This doesn't have the same provable gauarantees, but it's more practical.\n- These are interesting theoretical results, but it's unclear how useful they are in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work provides learning guarantees for parameterized data-driven algorithm\nproblems in distributional and online settings (i.e., how to learn good\nhyperparameters for general algorithms based on a historical sequence of\nproblem instances).\nIt generalizes many prior works of Balcan (10+ citations) to _Pfaffian functions_ (i.e., an extension of the class of rational functions that includes exponential and logarithmic function calls).\nSpecifically, it shows that if dual utility function class $\\mathcal{U}^*$ admits Pfaffian piecewise structure,\nthen we can recover distributional and learning gaurantees for the given utility function $\\mathcal{U}$.\n\nThere are three main contributions:\n\n**Distributional learning** (Section 5)\n\n  - Extends the Goldberg-Jerrum (GJ) framework [Goldberg-Jerrum, COLT 1993] from rational functions to Pfaffian functions\n  - The main learning guarantee result is Lemma 5.6\n  - The main technical building block is Lemma 5.3 (Appendix C), which is a refined analysis of [Balcan-DeBlasio-Dick-Kingsford-Sandholm-Vitercik, STOC 2021]\n\n**Online learning** (Section 7)\n\n  - Provides a new method for verifying the _dispersion property_ of a sequence of loss functions with Pfaffian hypersurfaces, which is a sufficient condition for obtaining regret bounds\n  - Studies the same set of applications in the distributional learning section\n\n**Applications** (Section 6 and 7.3)\n\n- The authors present several practical applications and show how these problems fit into their framework to inherit its guarantees:\n  * Agglomerative hierarchical clustering\n  * Graph-based semi-supervised learning with Gaussian radius basis function kernel\n  * Regularized logistic regression (i.e., learning the best regularization strength to use)", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "No required changes, but see the following questions, typos, and suggestions for v2 of the manuscript.\n\n**Questions**\n\n- [page 02] It seems that online learning is more general than the\n  distributional learning setting (since we could each draw in the distributional\n  setting as a problem instance chosen by the adversary). Can you comment on the\n  difference in the paper, and whether or not you give stronger gaurantees in the\n  distributional setting? It may be good to also compare to more practical _learning with predictions_ settings, e.g., [Mitzenmacher-Vassilvitskii, Communications of the ACM, 2022]\n- [page 05] What are the fixed set of distance functions $\\mathbf{\\delta}$ in\n  an instance of hierarchical clustering? I think this example in its current\n  form creates more confusion than in clears up.\n- [page 44] Is the proof of Theorem E.5 intentionally missing?\n\n**Typos and suggestions**\n\n- [page 05] $\\alpha$ in the definition of utility class function should be bold.\n- [page 05] Disregard if \"dual utility function class\" is a standard term in the literature, but something like \"transpose utility function class\" better describes the behavior\n- [page 06] \"(See Appendix A.1 ...)\" --> \"(see Appendix A.1 ...)\"\n- [page 06] Given that Theorem 3.1 has $\\text{PDim}(\\mathcal{U})$ in the hypothesis\n  and is from 1974, it would be good to find the original source for pseudo-dimension,\n  as the one given is from 2012.\n- [page 07] In definition of Pfaffian chain: some of the $\\eta_j$ should be $\\eta_q$.\n- [page 09] Add `\\qedhere` after the last line in the proof of Theorem 4.2.\n- [page 15] Consider using $= O(\\cdots)$ instead of $\\le O(\\cdots)$ when the\n  RHS uses big-O notation\n- [page 16] In $d = \\delta_\\beta$, the $\\beta$ should be boldfaced.\n- [page 31] Typo: \"... providing an upper-bound bound for ...\" --> \"...\n  providing an upper bound for ...\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h1SpfBHnyx", "reviewer": "Reviewer_EpQD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses:\n\nI have the following comments/questions: \n\nDefinition 5: I don’t understand Definition 5. The first sentence says the inputs of algorithm is a \\in R^d, which is a vector, but in the operation discerption, v seems to be a real value (e.g., the Pfaffian operators). Is v supposed to be a? If it is not a, please give the definition of v and also its domain.\n\n\n“Therefore, we can use the established results for the Pfaffian GJ algorithm (Theorem 5) to derive learning guarantees for such problems.”is it supposed to be Theorem 4.2 (I don’t see Theorem 5 in the paper)? \n\nLemma 5.4: \n1)\tR shoule be \\mathbb{R}. \n2)\tShould it be S\\subseteq X^{N} not S\\subseteq X? \n3)\tFinally, in the last equation, xi_i should be xi_N. \n\nLemma 5.6: We are talking about utility here not loss in this section, so I think hat{a} is defined as argmin, not argmax?\n\nMismatch of the notations: before Section 6, the authors talk about maximizing utility, while after section 6 it is switched to minimizing the loss, which is confusing. I suggest the authors unity the notation.\n\nFigure 2: mathbb{1} should be mathbb{I}; Moreover, how is P_{b,j} defined? Note that be is a vector, not a real value.\n\nI don’t fully understand Remark 5. I wonder if the authors could discuss more about: what is the benefit of applying the proposed framework for this problem, compared to Balcan et al. (2023b)? I think it is an important question since it is the major application of the results given in Section 5.3.\n\nDefinition 9: Why there is an expectation, and which element is stochastic? If ell_ts are drawn from some distribution in this online learning setting, please add more discussion about this. Since the stochastic setting is already discussed before, I thought here the losses should be adversarial. I understand that there might be an expectation in Theorem 7.1 as the algorithm might be stochastic, but I don’t understand Definition 9. Similarly, I am not sure about the proof of Theorem 7.2. Is there an implicit assumption that all loss are iid? \n\nWhat is M in Theorem 7.1? \n\nTheorem 7.3: l should be ell.\n\nTheorem 7.3: Here L has two definitions: one the Lipschitz constant, and the other is the set of axis-aligned paths between pairs of points. The second one should use a different notation. \n\nTheorem 7.6: there are missing [ ] and ( ).\n\n\nStrengths: \n\nSignificance and Novelty: \n\n1. A more generalized analysis framework. The proposed Pfaffian GJ framework generalizes the GJ framework studied by previous work (Bartlett et al. (2022)). , which can involve more complicated functions, such as exponential and logarithmic functions. However, note that it seems that logarithmic functions (logarithmic regression) has been considered by previous work (Balcan et al. (2023b)). The proposed framework can recover pervious case as a special case. \n\nThe authors also provide several new applications of there framework. For example, in data-driven agglomerative hierarchical clustering, the proposed methods is applible under much more general conditions. It broadens the application domain of  data-driven algorithms and analysis. \n\n\n2. For the online learning setting, the proposed efficient ways to verify the dispersion property of a border class of loss functions (i.e.,  Pfaffian functions). The authors also show that it is applicable to many real world problems. \n\n3. Presentation: Except from the comments in the beginning, I think the authors did a good job on introducing the Pfaffian function related ideas. I also appreciate it that the authors clearly written down the connection to previous work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies data-driven algorithm design in both stochastic and online learning setting. For the stochastic setting, the authors proposed the Pfaffian GJ framework, which can provide Pseudo dimension bounds for a broad class of utility functions (i.e., Pfaffian functions). It include important functions such as the exponential function. The proposed framework is more general compared to the  previous GJ framework as it includes Pfaffian functions. The authors also provide several applications for their proposed framework, some of them show that the proposed framework can lead to similar guarantees as previous work under milder conditions. For the online learning setting, the authors propose a novel way of varifying the dispersion property of Pfaffian functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses part of the section above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5wVVX7iuCP", "reviewer": "Reviewer_XaQa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is in applying a strong and appropriate technique to substantially advance the line of work of generalization bounds for data-driven algorithm design. The conceptual and technical content, and the results it yields, are sufficiently strong to merit acceptance for publication.\n\nThe main weakness of this manuscript is that it seems quite careless and haphazard in the technical details. Many seem glossed over, not properly written formally, and possibly imprecise. I stress that I don't doubt that the overall approach is sound, given its history in the related literature and its presentation in this paper. I do have doubts about the level of formality in some parts, which in turn lead to doubts about some of the precise bounds stated, especially those stated with explicit rather than hidden constants. These are fixable issues and I wouldn't want to see a significant paper rejected because of them, but since this is an archival submission in a journal that emphasizes methodological soundness, I feel the authors should thoroughly clean up the manuscript of such formal issues and gaps. I detail some of these issues below under requested changes, though inevitably I was unable to list all of them.\n\nApart from the technical content, the writing itself evidently had not undergone proper proofreading prior to submission, in terms of linguistic errors and misuse of citation tags (citep/citet), and these would need to be cleaned up as well to make the paper more readable. There are too many instances of this for me to list, so I give up trying altogether.\n\nPerhaps the main weakness at the technical level is the somewhat notorious $q^2$ dependence incurred by the technique of (Khovanskii 1991) in the Pfaffian chain length $q$. In the application to data-driven algorithms given in this paper, this leads to VC dimension bounds with quadratic dependence on the number of parameters, which is likely loose as one typically expects it to be near-linear (there is no discussion of lower bounds in the paper). But since this dependence is a long-standing issue, and that no prior bounds were known for the problems considered in this paper, this is far from an argument against the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper belongs to the line of work on learning theory for data-driven algorithms. Gupta and Roughgarden (2016) initiated the study of proving VC dimension bounds for parameterized families of algorithms, or more precisely, for the classes of loss functions corresponding to those algorithms. These bounds yield generalization bounds for selecting approximately optimal parameters from a bounded number of samples drawn from an application-specific distribution. Balcan et al. (2018) extended this to the online learning setting, where the goal is to select parameters with vanishing regret compared to the optimal parameters in hindsight.\n\nSo far, there have been two general approaches for proving VC dimension bounds for data-driven algorithms. One by Balcan et al. (2021) relies on piecewise decomposition of the dual function classes of losses. It is very general, albeit it requires the non-trivial step of bounding the VC dimension of the classes arising in the piecewise decomposition of the specific task in question. Furthermore, due to its generality, it falls short of fully exploiting the problem structure in some cases, leading to suboptimal or vacuous bounds. The other approach by Bartlett et al. (2022) relies on a refinement of the GJ algorithm framework of Goldbert and Jerrum (1993). It leads to sharper bounds in some cases, albeit it is limited in applicability to cases where the class of losses can be expressed or approximated by rational functions of the parameters. \n\nThis paper extends these approaches to the case of Pfaffian functions (Khovanskii 1991). Pfaffian functions are a much more general class of functions than rational functions handled in Bartlett et al. (2022), and yet usefully more specific than the generic piecewise decomposition from Balcan et al. (2021). Thus this approach addresses cases not handled by previous approaches, and substantially expands the scope of algorithms for which VC dimension bounds are achievable. Much like Karpinski and Macintyre (1997) extended the GJ framework to Pfaffian functions in order to prove VC dimensions for a broader class of neural network activations, this paper takes the natural step of carrying out this extension for data-driven algorithms. It extends the GJ algorithms framework from Bartlett et al. (2022) to Pfaffian GJ algorithms, and the piecewise decomposition framework from Balcan et al. (2021) to Pfaffian piecewise functions. It then uses these general results to prove generalization bounds for families of parameterized algorithms that were either suboptimally handled or not handled by previous approaches. It also shows how to apply these techniques in the online learning setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Possible technical issues -- please explain and/or correct. \n\nThis is inevitably a partial list, so as written above, please make a thorough technical correction pass over the manuscript. \n\nTheorem 4.2: Clarification needed about the degrees. \n1. Could you specify the precise definition of \"degree\" $\\Delta$ of an intermediate value? Is it the polynomial for a Pfaffian operator step or the rational degree for an arithmetic operator step or what exactly?\n2. In the statement of the theorem, $M$ is the Pfaffian degree of the chain and $\\Delta$ is the degree of intermediate values. But in the proof, $\\Delta$ is the Pfaffian degree of the chain. Shouldn't this be $M$? Does this change the claimed bound on the pseudo-dimension in the theorem?\n3. In Lemma B.2, could you please point to the specific result within (Khovanskii 1991) that you cite? This is a monograph-length work. Also, little $m$ in the $\\Delta^m$ term is undefined -- presumably a typo. \n4. In Corollary B.3, $\\Delta$ appears in the final bound but nowhere before. What is it here? Is it the polynomial degree of the $\\tau_i$'s?\n\nAll these issues make it  very hard to properly read and verify the theorem. \n\nLemma 5.4:\n1. What is \"messy $G$\" in the RHS? Presumably a typo \"messy $R$\"?\n2. Did you write \"$\\mathbf{x}i_i$\" instead of $\\xi_i$? This is quite confusing.\n\nLemma 5.6: \n\nIs $H$ (the upper bound on the utility range) missing from the lemma's conclusion?\n\nTheorem 6.5:\n1. What is going on with $m$? Did you use the same letter in the same theorem statement for both the matrix dimension and the number of samples?\n2. $\\epsilon$ appears in the final bound but nowhere before in the theorem statement, what is it here? Is it any $\\epsilon>0$, according to the proof?\n\nTheorem A.1: \n\nIt looks you mistakenly switched between then $N(\\epsilon,\\delta)$ and the $N(\\epsilon/2,\\delta)$\n\nNo future directions mentioned under \"future directions\"", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: First of all, I would like to apologize to the authors for taking unusually long to complete the review procedure for this paper. Two factors have played into this: 1) the relative underrepresentation of the topic of the paper at TMLR and within the reviewer pool and 2) the length of the paper which was beyond the limits for regular papers at TMLR. Thanks to these challenges, it took quite long to find suitable reviewers for this paper.

Eventually, I have managed to find three expert reviewers who all wrote detailed and informative reviews about the paper. All of them have appreciated the contributions of the paper, especially after the meticulous updates made by the authors in response to the reviews. Given this strong support and my own reading of the paper, I am happy to concur with the reviewers and recommend this paper for acceptance at TMLR.
Decision: Accept (poster)