Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples

1 Introduction

As a popular learning paradigm, pairwise learning has attracted much attention in the machine learning community, where the loss function is associated with two samples simultaneously [Lei et al., 2018; Huang et al., 2023]. Typical frameworks of pairwise learning include metric learning [Cao et al., 2016], gradient learning [Mukherjee and Zhou, 2006; Feng et al., 2015], AUC maximization [Cortes and Mohri, 2003; Gao and Zhou, 2015], and ranking [Rejchel, 2012; Huang et al., 2023]. In theory, the generalization performance of pairwise learning has been well investigated from various analysis routines, such as Rademacher complexity [Agarwal and Niyogi, 2009; Lei et al., 2021], algorithmic stability [Jin et al., 2009; Lei et al., 2021], integral operators [Mukherjee and Zhou, 2006; Ying and Zhou, 2016; Zhao et al., 2017], etc. However, all the existing results focus on the uniform convergence analysis independent of the real optimization algorithm, which often ignores the crucial impact of computing trajectory on the capacity of hypothesis space [S¸ ims¸ekli et al., 2021].

∗Corresponding author.

Recently, the computing trajectory of learning model has been addressed increasingly in learning theory studies due to its close relationship with generalization performance. For deep neural networks (DNNs), the existing generalization analysis often focuses on the final trained network [Neyshabur et al., 2017], where the computing trajectory is ignored usually. In view of this situation, S¸ ims¸ekli et al. [2021] have demonstrated that algorithmic trajectories can exhibit a fractal structure when a stochastic optimization algorithm is employed for implementing deep learning models. Moreover, fractal dimensions w.r.t optimization trajectories have been integrated into the generalization error analysis, where the generalization bounds rely on the intrinsic computing-dependent dimension rather than the hypothesis space dimension [Camuto et al., 2021; Birdal et al., 2021; Hodgkinson et al., 2022]. To illustrate the recent progress clearly, we summarize their main contributions in Table 1.

Indeed, these trajectory-dependent generalization guarantees provide some explanation for the phenomena: why overparameterized networks may not exhibit overfitting in practical scenarios [Dupuis et al., 2023]. When the loss function ℓ is L-Lipschitz and uniformly bounded by a constant B, the previous results in S¸ ims¸ekli et al. [2021], Camuto et al. [2021], Birdal et al. [2021] and Sachs et al. [2023] stated that the generalization error of learning models can be bounded by

LB√ Md (WZ,U ) log(n)+log(1/ζ) n with probability 1 - ζ, where n is the sample size and M d (WZ,U) is the fractal dimension with trajectory-dependent hypothesis space WZ,U (see Section 3 for detail definitions). Moreover, [Dupuis et al., 2023] got the refined generalization bounds based on data-depend fractal dimensions without Lipschitz assumption for loss function. Although these algorithm-dependent bounds have brought a new perspective on understanding generalization, they are limited to the pointwise learning with i.i.d. samples which often violated in real-world applications [Kohler and Krzyzak, 2020; Kurisu et al., 2022].

This paper focuses on the scenario where the observations are drawn from a stationary φ-mixing (or uniformly strong mixing) process, which is a commonly used assumption in learning theory [Yu, 1994; Meir, 2000; He et al., 2016]. Theoretically, we establish generalization bounds for pairwise learning with φ-mixing samples with the help of trajectorybased fractal dimensions, which assures the generalization error of our estimator can achieve the polynomial decay rate O(Ψ√log(n)/n). Here n is the sample size and Ψ is the sum of the φ-mixing coefficients (see Definition 1 in Section 3.1). To the best of our knowledge, there is no theoretical characterization of the generalization guarantees of pairwise learning with φ-mixing samples before. The main contributions of this paper are twofold:

• Optimization-dependent generalization bounds. We employ the fractal tool to bound the trajectory-dependent generalization error for pairwise learning, where the tight estimations can be derived benefit from much smaller hypothesis space. This change has enabled us to transform our focus from concerning the size of covering numbers (independently of optimization processes, e.g., Rejchel [2012] and Huang et al. [2023]) to fractal dimensions by topological data analysis tools S¸ ims¸ekli et al. [2021] and Dupuis et al. [2023]. Our results reduce the gap between the theoretical properties and algorithmic implementation of pairwise learning models, which improve the matching degree of generalization bounds to real applications.
• Improved analysis techniques. Without the requirement of independent observations, the previous analysis techniques in Lei et al. [2018] and Huang et al. [2023] can not be applied to the pairwise learning with φ-mixing samples directly. This obstacle is conquered through McDiarmid's inequality for φ-mixing processes [Mohri and Rostamizadeh, 2010] and extending Lemma A.1 in Cl´emenc¸on et al. [2008] to stationary processes. In particular, our analysis framework removes the Lipschitz condition of pairwise loss [Cao et al., 2016; Lei et al., 2018] by incorporating a data-dependent pseudo-metric for capacity estimation.

2 RelatedWork

Now we review the related work about generalization bounds for pairwise learning and learning theory with φ-mixing samples. To better evaluate our work, we compare it with the related results in Table 2 from the aspects of analysis tool, learning models, and learning rate.

2.1 Generalization Bounds for Pairwise Learning

Stability Analysis. Due to the intrinsic relationship between generalization and stability, there are some generalization guarantees of pairwise learning in terms of algorithmic stability tools, see e.g., Jin et al. [2009], Agarwal and Niyogi [2009] and Lei et al. [2021]. The derived results demonstrate that, under the strong convexity of the objective function, the related pairwise learning models enjoy the dimensional-independent generalization bounds with the decay rate at O(n- 1 2 ). All of the existing studies require that the learned pairwise model would change slightly if a single training example is replaced by another one, and include ranking algorithm [Agarwal and Niyogi, 2009], the iterative localized algorithm for pairwise learning [Lei et al., 2021] as special examples.

Uniform Convergence Analysis. The concentration estimation techniques in U-statistic were developed to tackle error analysis of regularized metric learning [Cao et al., 2016] and ranking [Rejchel, 2012; Huang et al., 2023]. The basic idea is to control the generalization bound via a Rademacher complexity [Lei et al., 2018] which uses the symmetry of the U-statistic [Cl´emenc¸on et al., 2008]. Moreover, there is also a classic method using Hoeffding decomposition [Hoeffding, 1992] to decompose the pairwise learning problem into i.i.d. terms and degenerate U-statistic terms [Huang et al., 2023]. Under proper capacity assumptions of hypothesis function space and independence of samples, convergence rate with O(n- 12 ) is obtained for the above pairwise learning models. However, it is often difficult to verify the independence assumptions directly in real applications, which limits the adaptivity of learning theory analysis. For online pairwise learning, [Wang et al., 2012] and [Kar et al., 2013] established regret bounds by developing analysis techniques associated with covering numbers and Rademacher complexity, respectively. Furthermore, the convergence rates for the final iteration of online pairwise learning algorithms have been examined through the lens of convex analysis [Ying and Zhou, 2016; Guo et al., 2016; Lin et al., 2017]. Despite rapid progress, all the uniform convergence analysis doesn't address the optimization trajectories and just states the computation-independent error bounds.

Operator Approximation Analysis. The operator approximation technique, from functional analysis, is introduced to characterize the generalization ability of least square regularized ranking [Chen, 2012] and gradient learning [Mukherjee and Zhou, 2006]. Compared with the uniform convergence depending heavily on the capacity assumption of hypothesis space, the learning theory analysis framework of operator approximation just requires that the minimizer of optimization objectives can be expressed by the empirical version of integral operator [Mukherjee and Zhou, 2006; Kriukova et al., 2016]. Explicitly, for the least square ranking, [Chen, 2012] gave the first operator approximation analysis on its convergence rate and Chen et al. [2013] stated the decay rate O(n- 14 ) for the excess risk of stochastic gradient descent ranking under mild parameter conditions. Moreover,

[Kriukova et al., 2016] obtained the improved estimations O(n- 12 ) under general source conditions, and [Zhao et al., 2017] got the same convergence rate by integrating Hoeffding's decomposition and regression estimation techniques.

2.2 Learning TheoryWith φ-Mixing Samples

Stationary Mixing Processes. The pioneering work of Yu et al. [1994] led to VC-dimension bounds under the assumption of stationary φ-mixing observations. Later, [Meir, 2000] derived the upper bounds of generalization error in terms of covering numbers and reached the convergence rate with O((log n/n) γ0 2(1+γ0) ), where γ0 is the parameter in φ-mixing coefficient. Moreover, [Mohri and Rostamizadeh, 2010] established the data-dependent learning bounds in terms of algorithmic stability, where the blocks of points for Hoeffding's decomposition are not necessarily of equal size and the generalized McDiarmid's inequality in Leo and Kavita [2008] plays a crucial role. [Ralaivola et al., 2010] and [Alquier and Wintenberger, 2012] provided PAC-Bayesian learning bounds under the φ-mixing assumptions. Additionally, Ralaivola et al. [2010] employed fractional covers to address the dependencies within the given set of random variables, and proposed a strategy to construct subsets of independent random variables, enabling the application of the standard i.i.d. PAC-Bayes bound. For the pairwise ranking, [He et al., 2016] provided the generalization bounds with φ-mixing samples by combining the independent block technique and the algorithmic stability analysis together. However, the information of computing trajectory isn't addressed sufficiently in the previous analysis for dependent observations.

Non-stationary Mixing Processes. For the the asymptotically stationary process, [Agarwal and Duchi, 2012] presented generalization bounds of stable online learning algorithms. Moreover, [Kuznetsov and Mohri, 2017] provided the first generalization bounds for time series prediction with a nonstationary φ-mixing stochastic process. For the Lasso estimator with φ-mixing samples, [Peng et al., 2023] employed the non-asymptotic concentration inequalities to the error estimations. As far as known, there is no generalization guarantee specifically addressing pairwise learning with φ-mixing samples based on algorithmic trajectory.

3 Preliminaries

This section introduces the framework of pairwise learning in φ-mixing process and recalls the definition of Minkowski dimension.

3.1 Pairwise Learning in φ-Mixing Process

Let the input space X ⊂ Rp be a compact space and the output set Y be a subset of R. The sample set

is drawn from an unknown distribution. Usually, the objective of a learning algorithm is to learn a prediction function fw based on Z. We consider parametric models where fw can be indexed by a vector element w ∈ W ⊂ Rd . Recognizing the limitations of the independent assumption in practical scenarios [Mohri and Rostamizadeh, 2010], we opt to discard it and instead investigate the set Z satisfying the exponentially φ-mixing condition.

Definition 1. [Yu, 1994] The process {zi}∞i=1 is said to be exponentially φ-mixing or uniformly strong mixing if there exist some constants b0 > 0, c0 ≥ 0, γ0 > 0 such that φmixing coefficient φ(k) satisfying

where σj i is the σ-algebra generated by zi, · · · , zj.

A classical φ-mixing example can be seen in Technical appendix A.1. In this paper, we focus on the pairwise learning problem on an example pair (zi, zj ), in which the effectiveness of the prediction function fw relies on a non-negative loss function ℓ (w, zi, zj). To evaluate the ability of w learned from set Z, we define the empirical risk

and its population version

Typically, the optimal parameter w⋆ can be found using a learning algorithm A to minimize the empirical risk Rn(w, Z). As mentioned in Molchanov [2005], the algorithm A can be thought as a measurable map that generates the trajectories WZ,U (hypothesis space) from set Z and an external random variable U ∈ U. In general, U is assumed to be independent of Z and accounting for the randomness of the learning algorithm (such as the batch indices in training).

Definition 2. The trajectories of the algorithm A after T iterations under the sample set Z can be defined as

where the parameter wt is returned by A at time t.

A common example of A is the stochastic gradient descent (SGD) algorithm, which can be viewed as a discretization of a stochastic differential equation [Mandt et al., 2016; Jastrzebski et al., 2017; Chaudhari and Soatto, 2018]:

where the second term accounts for randomness U coming from Brownian motion Bt and diffusion coefficient Σ : Rd → Rd×d . As considered in various studies [Mandt et al., 2016; S¸ ims¸ekli et al., 2021; Chaudhari and Soatto, 2018], the trajectories WZ,U of SGD algorithm is the set {wt}t≥0 with the parameter wt returned by A at time t.

On this basis, we define the worst-case generalization error which reflects the generalization ability

which is a trajectory-dependent definition of generalization and widely used in the literature [Bousquet and Elisseeff, 2002; Dupuis et al., 2023].

3.2 Minkowski Dimension

In this paper, we employ the Minkowski dimension to measure the capacity of the hypothesis space WZ,U and bound the worst-case generalization error (1). Before proceeding, we first propose a data-dependent pseudo-metric dZ(·, ·) on space WZ,U as follows:

where ⌊n/2⌋ rounds down n/2, ⌈n/2⌉ rounds up n/2 and Π is the set of all permutations of {1, · · · , n}. The fundamental requirements of pseudo-metric (2) which include the triangle inequality, symmetry, and non-negativity, have been verified and demonstrated in Technical appendix A.1. Based on this pseudo-metric, we present the definition of the covering number.

Definition 3. [S¸ims¸ekli et al., 2021] A set {wl}Nl=1 is the δcover of pseudo-metric space (WZ,U, dZ), if ∀w ∈ WZ,U, there exists wk ∈ {wl}Nl=1 such that

The covering number N(WZ,U , dZ, δ) is the minimum cardinal of all δ-covers.

As demonstrated in Dupuis et al. [2023], the δ-cover induced by pseudo-metric dZ(·, ·) is measurable which can induce the correct Minkowski dimension.

Definition 4. [Falconer, 2004] For a bounded pseudo-metric space (WZ,U , dZ), the Minkowski dimension is defined as:

Besides, the upper Minkowski dimension and the lower Minkowski dimension are respectively defined as :

and

which will be used in Section 4.2.

4 Main Results

This section presents our main theoretical results. The following assumptions are involved in our error analysis.

Assumption 1. The loss function ℓ : WZ,U ×Z ×Z →R is continuous and bounded by B.

Assumption 1 requires the continuity of loss function, which ensures that the quantities like (1) are well-defined random variables [Molchanov, 2005]. The bounded condition is standard in many generalization error estimations, see e.g., Dupuis et al. [1999] and Schmidt-Hieber [2017]. Different from S¸ ims¸ekli et al. [2021] and Camuto et al. [2021], we eliminate the necessity of the Lipschitz condition with respect to w for loss function ℓ due to the utilization of pseudo-metric (2).

Assumption 2. The strictly stationary process {zi}i≥1 satisfies the exponentially φ-mixing condition.

Assumption 2 imposes the dependence constraint among input variables. To handle this type of data, the generalized McDiarmid's inequality for φ-mixing observations is introduced in Leo and Kavita [2008] and Mohri and Rostamizadeh [2010].

Assumption 3. [Dupuis et al., 2023] Let C ⊂ Rd be any closed set, δ > 0,Z ∈ Z n and Z′ ∈ Z m. We can construct minimal δ-coverings N (C ∩ WZ,U , dZ, δ), which are random finite sets with respect to the product σ-algebra FZ ⊗ FZ′ ⊗ FU (measurability with respect to Z, Z′ , U).

Assumption 3 can be cast as a selection property. Indeed, there may be a wide range of possible minimal coverings for each realization of (Z, Z′ , U). This paper assumes that we can select one of them satisfying that the obtained random set is measurable. In addition, since the Minkowski dimension (3) can be expressed as a countable limit, Assumption 3 implies that M dZ (WZ,U) is a random variable [Dupuis et al., 2023]. Please see Dupuis et al. [2023] for more detailed discussions.

In our analysis, the capacity of searching space is measured by the Rademacher complexity and Gaussian complexity, which are defined as follows.

Definition 5. [Dupuis et al., 2023] Given the sample set Z = {zi}ni=1 , the parameter spaceW, and the function lw indexed by w ∈ W, the empirical Rademacher complexity over W on Z can be defined as

where the set ε = {εi}ni=1 is composed of Rademacher random variables satisfying P(εi = 1) = P(εi = -1) = 0.5. Similarly, the empirical Gaussian complexity over W on Z is defined as

where g1, · · · , gn are independent Gaussian random variables.

4.1 Upper Bound of Generalization Error

Now we introduce the following stepping-stone lemma, which is an extension of Lemma A.1. in Cl´emenc¸on et al. [2008] and plays a crucial role in our error estimations.

Lemma 1. Let qτ : Z × Z → R be real-valued functions indexed by τ belonging to a set T . If {zi}ni=1 is a stationary process, then

where Π is the set of all permutations of {1, · · · , n}.

The proof of Lemma 1 is shown in Technical appendix A.2. Then we establish the upper bound of generalization error for general pairwise learning with φ-mixing samples.

Theorem 1. Under Assumptions 1-3, for any ϵ, γ, ζ > 0 and n ∈ N+ there exists δn,γ,ϵ > 0 such that with probability at least 1 - 2ζ - γ, we have:

The proof of Theorem 1 is given in Technical appendix A.2, where essential improvement of analysis techniques [Dudley, 2014] are required due to the non-i.i.d. nature of the sequences.

Remark 1. We employ Rademacher complexity and McDiarmid's inequality to deal with the difficulties brought by U-statistic [Rejchel, 2012; Cao et al., 2016; Lei et al., 2018]. Generally, traditional methods require Lemma A.1 in Cl´emenc¸on et al. [2008] to transform the pairwise learning to the single index problem. However, it is not working for φ-mixing samples. To overcome this difficulty, we introduce Lemma 1 for rearranging the training samples and the generalized McDiarmid's inequality proved in Mohri and Rostamizadeh [2010] for handling the φ-mixing samples.

For learning models with complex hypothesis space (e.g., deep neural networks), it often leads to trivial bound when directly applying the uniform convergence analysis framework independently of computing algorithms [Zhang et al., 2021]. To address this issue, we integrate the fractal tools into error analysis of pairwise learning, where the refined bound benefits from trajectory-dependent capacity estimation of hypothesis space.

Remark 2. Our capacity estimation is similar to the classical bounds for pointwise learning based on topological tools [Camuto et al., 2021; Birdal et al., 2021; Hodgkinson et al., 2022; Dupuis et al., 2023]. To our knowledge, our results are the first endeavor on applying topological tools to pairwise learning. In particular, the Lipschitz condition for loss function is abrogated using a data-dependent pseudo-metric. The derived result in Theorem 1 illustrates the impact of mixing samples (via the coefficient Ψ) on the convergence rate. As the dependency among samples increases, the convergence rate will slow down.

Remark 3. It should be pointed out that M dZ (WZ,U) can be calculated by topological data analysis tools [P´erez et al., 2021]. And it always can be bounded by a positive constant in SGD algorithm (if {wt}t≥0 is a family of Feller processes) [S¸ims¸ekli et al., 2021].

It is well known that i.i.d. process can be viewed as a special case of φ-mixing process where the φ-mixing coefficients φ(k) = 0, k = 1, 2, · · · . As a byproduct, we also state the corresponding result of Theorem 1 for i.i.d. samples.

Corollary 1. Under Assumptions 1 and 3, for i.i.d. samples and any ϵ, γ, ζ > 0, there exists δn,γ,ϵ > 0 such that with probability at least 1 - 2ζ - γ, we have

Theorem 1 shows that the generalization error depends on the Minkowski dimension of algorithmic trajectories, which extends the previous results of pointwise learning with i.i.d samples [S¸ ims¸ekli et al., 2021; Camuto et al., 2021; Birdal et al., 2021; Sachs et al., 2023] to the pairwise setting with mixing observations. From Lemma A.15, we know that M dZ (WZ,U ) can be computed efficiently by tools of topological data analysis.

Remark 4. Typically, we can set δ = 1/√n. From Egoroff's Theorem in Technical appendix A.1, there exists a γ ≥ 0 such that with probability at 1-γ, N (WZ,U , dZ, 1/√n) uniformly converges to M dZ (WZ,U) with respect to 1/√n → 0. Thus, we have

for a sufficiently large n. Then under Assumptions 1-3, for any ζ > 0 and a sufficiently large n, there exists a γ ≥ 0 such that with probability at least 1 - 2ζ - γ, we have

Here, we recover a convergence rate √log(n)/n with i.i.d. setting (Ψ = 1) which is analogous to results relied on fractal tools in pointwise learning [S¸ ims¸ekli et al., 2021; Camuto et al., 2021; Dupuis et al., 2023]. To ensure a fair comparison with the works of S¸ ims¸ekli et al. [2021] and Camuto et al. [2021], we present the generalization bound under the assumption that the loss function satisfies the Lipschitz condition.

Corollary 2. Under Assumptions 1-3 and the L-Lipschitz assumption for the loss function ℓ, for any γ, ζ > 0 and a sufficiently large n such that with probability at least 1-2ζ-γ, we have:

where dw is the Euclidean metric.

The proof of Corollary 2 is shown in Technical appendix A.4. This result is similar to S¸ ims¸ekli et al. [2021]. Moreover, it can be observed that in the absence of the Lipschitz condition, we have shifted the analytical challenge to M dZ (WZ,U).

4.2 Lower Bound of Generalization Error

As an additional theoretical outcome, we endeavor to establish a lower bound by incorporating the introduced data-dependent fractal dimension. The next theorem is based on the classical arguments involving Sudakov's theorem [Vershynin, 2018] and Gaussian complexity. Here, we extend the technique for analyzing lower bound from the pointwise learning [Dupuis et al., 2023] to the pairwise learning with φ-mixing samples. The lower bound considered here requires a slightly different definition of the worst-case generalization error:

Furthermore, we define a new pseudo-metric

where {Gw,Z}w∈WZ,U is a Gaussian process related to Z (see Technical appendix A.1 for more details). In this Section, we replace dZ(·, ·) in Assumption 3 with dg,Z(·, ·). Now we can provide the lower bound of generalization error for pairwise learning with φ-mixing samples.

Theorem 2. Under Assumptions 1-3, for any ϵ, ζ > 0, there exist a constant c > 0 and δn,ϵ,ζ > 0 such that

holds true with probability at least 1 - ζ - ϵ.

Remark 5. Theorem 2 states a novel lower bound for pairwise learning through constructing a pseudo-metric dg,Z(·, ·), whose effectiveness is guaranteed by Assumption 3. The main differences between our proposed lower bound and the existing result [Dupuis et al., 2023] are the additional φ-mixing coefficient and the different fractal dimensions, which are induced by the mixing samples and the U-statistic associated with pairwise loss.

5 Experiment

In this section, we conduct several numerical experiments to investigate the relationship between the Minkowski dimension and generalization bound. Subsequently, we sought to validate our theoretical findings regarding the convergence properties through these experiments. More experiment details can be found in Technical appendix A.6.

5.1 Experimental Setup

Our experimental design is similar to Birdal et al. [2021] and Dupuis et al. [2023]. Given a fixed positive integer m0, we generate the random series {ei}i≥1 , which are i.i.d. drawn from Gaussian distribution N (0p, Ip×p). For any i ≥ 1, let

then the sequence {xi}i≥1 is an m0-dependent process and hence φ-mixing [Peng et al., 2023]. Consider the intrinsic relationship between the input and its response defined as Mukherjee and Zhou [2006],

During the experiment, we focus on the case of gradient learning model (more details for gradient learning model can be found in Technical appendix A.6). It is easy to verify that pairwise loss ℓ(w; zi, zj) satisfies the Assumption 1 for the aforementioned data generating process. Now we describe the implementation details of the empirical evaluation. Given the dataset Z = {z1, · · · , zn}, we employ the SGD algorithm to train three fully connected networks (FCN) with different layers under different parameter settings (batch size: 24, 48, 64, learning rate: 0.1, 0.01, 0.001, sample size n: 225, 900, 1406, 2025, 2756, 4556, 5625, 6806). During the training, the softmax activation function is employed. Subsequently, we consider the optimization trajectory near the local minimum discovered by SGD as the hypothesis set WZ,U . To be specific, we assume the SGD algorithm reaches a local minimum after k⋆ iterations. Then, we continue running this algorithm for 1000 iterations and set WZ,U to be {wk⋆+1, · · · ,wk⋆+1000}.

Indeed, the Minkowski dimension often can be calculated by the persistent homology (PH) dimension dimdZ PH0 WZ,U , which can be further approximated numerically in terms of the PH software provided by P´erez et al. [2021]. For more detailed information on PH, please refer to Technical appendix A.5.

5.2 Experimental Analysis

To ensure the fairness and impartiality, each experiment is repeated nine times for different scenarios. Figure 1 presents the PH dimension dimdZ PH0 WZ,U and the generalization gap of a seven-layer FCN (64, 32, 16, 8, 8, 8, 4) under various settings. Among them, different colors indicate different learning rates (green: 0.1; red: 0.01; blue: 0.001) and different markers indicate different batch sizes (plus: 24, triangle: 48, circle: 64). We observe a strong correlation between the PH dimension and the generalization gap in the case of a batch size 64. Besides, we find that the smaller batch size seems to show less correlation, which is consistent with the previous observation in Birdal et al. [2021] and Dupuis et al. [2023]. Intuitively, this phenomena maybe caused by the increased noise (such as the randomness associated with selecting k samples as the batch) in WZ,U which may lead to more complex fractal structures. As a result, more points are required for precise computation of the PH dimension in such cases.

Figure 2 shows the average generalization gaps of nine trials with different sample sizes under nine various scenarios (batch size, learning rate). As the sample size n increases, we observe a gradual decrease in the average generalization gaps. This observation aligns with our theoretical results and provides empirical evidence to support our findings.

The simulation experiments are also conducted on various settings using a five-layers FCN (64, 32, 16, 8, 4) and a nine-layers FCN (64, 32, 16, 8, 8, 8, 8, 8, 4). Please refer to Technical appendix A.6 for the experimental results.

6 Conclusions

This paper established the trajectory-dependent generalization analysis for pairwise learning with φ-mixing observations. For pairwise learning models, the derived theoretical results alleviate their sampling assumption on training data (i.e., i.i.d. observations) and match their real implementing algorithms tightly by employing the fractal theory to measure the computing trajectories in the hypothesis space. As far as we know, the current analysis is the first touch of optimization trajectory-dependent generalization characterization for general pairwise learning. In the future, it would be interesting to extend our analysis to much general dependent process, e.g., the τ-mixing process [Dedecker and Prieur, 2005; Liu et al., 2025].

Acknowledgments

This work is supported by the National Natural Science Foundation of China (NSFC) (Nos. 62376104, 12426512, 12301651) and the Open Research Fund of Engineering Research Center of Intelligent Technology for Agriculture, Ministry of Education (No. ERCITA-KF002).