A Transition Matrix-Based Extended Model for Label-Noise Learning

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:30:26

Abstract: The transition matrix methods have garnered sustained attention as a class of techniques for label-noise learning due to their simplicity and statistical consistency. However, existing methods primarily focus on class-dependent noise and lack applicability for instance-dependent noise, while some methods specifically designed for instance-dependent noise tend to be relatively complex. To address this issue, we propose an extended model based on transition matrix in this paper, which preserves simplicity while extending its applicability to handle a broader range of noisy data beyond class-dependent noise. The proposed model's consistency and generalization properties are theoretically analyzed under certain assumptions. Experimental evaluations conducted on various synthetic and real-world noisy datasets demonstrate significant improvements over existing transition matrix-based methods. Upon acceptance of our paper, the code will be open sourced.

Main paper: 
 introduction: 
 Deep neural networks have achieved remarkable success in various fields in recent years, especially in classification problems with labeled data [32, 2] . Compared to traditional methods, deep neural networks have greatly improved performance but their effects heavily depend on the accuracy of the provided labels. Bringing data with corrupted labels into the neural network model without special treatment can severely affect the prediction performance [8, 50] . However, acquiring accurately annotated data in reality can be very expensive, so a larger amount of data comes from the Internet or annotations by non-professional annotators. Therefore, it is currently worth studying and promoting how to alleviate the damage caused to the model when using noisy labels and make the model more robust, which is known as the problem of label-noise learning or called learning with noisy labels [29, 36, 10, 43, 41, 1, 35] .Various methods have been proposed for label-noise learning. Existing methods can be classified into several categories. One of them is to design novel loss functions or network structures [53, 39, 28] , which reduce the impact of noisy labels to make the model more robust. Another category is sample selection based on sample loss or feature extracted, dividing samples into the clean dataset and the noisy dataset [4, 10, 13, 19] . Then they relabel the noisy labels [33, 15] , or clear the noisy labels and use semi-supervised methods for learning [3, 19] . These methods are common recently and have achieved some good results. However, the process of sample selection is relatively subjective, and statistical consistency is lost after the selection, and most of them lack theoretical support.In contrast, transition matrix methods [9, 43, 22, 14, 59 ] have statistical consistency and usually have corresponding theoretical analysis as support, attracting continued attention and occupying an important position in various learning algorithms with label noise.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.The core idea of transition matrix methods is to use a matrix measuring the transition probability from the distribution of true label to the distribution of observed noisy label. If an accurate transition matrix can be estimated and combined with observable data to obtain the noisy class-posterior probability, the distribution of clean label can be inferred for network learning. Therefore, estimating the transition matrix is the key to this type of method. However, it is infeasible to estimate an individual transition matrix for each sample without additional conditions [26] . Previous methods mostly focus on classdependent and instance-independent label noise problems [43, 22, 51] , assuming that the transition matrix is fixed for all samples. Among these methods, some [31, 43] assume the existence of anchor points to estimate the transition matrix, while other methods obtain the optimal estimation by adding a regularization term for matrix structure to weaken the anchor points assumption [22, 51] . However, these methods are not suitable for instance-dependent label noise and complex real-world data because they estimate only one matrix for all samples. Moreover, when the estimation of noisy class-posterior distribution is inaccurate, the estimation of the transition matrix may be easily affected [47] , thereby affecting the estimation of the clean label distribution. Although some methods [42, 58, 52, 20] have recently been designed to use special networks or structures for instance-dependent noise situations, the estimation errors for them are still large, and the computational cost is too high to lose the concise characteristic of transition matrix methods.Addressing the limitations of current transition matrix-based methods, this paper introduces an extended model for transition matrix that extends their applicability from class-dependent noise to a broader range of label-noise data without requiring additional techniques such as clustering or self-supervised learning. Inspired by methods that handle noise using sparse structures [57, 25] , our model combines a global transition matrix with a sparse implicit regularization term [31, 25] for fitting the distribution of noisy labels across instances, replacing the need for estimating a separate transition matrix for each sample. This approach allows us to incorporate instance-level information into the model, expanding its capability beyond class-dependent noise scenarios while avoiding the unidentifiability and computational complexity of estimating instance-dependent matrices.The structure of the following sections is as follows. In Section 2, we give relevant definitions and propose our method. In section 3 we conduct a theoretical analysis of the proposed method on a simplified model. In Section 4, we conduct experiments on various synthetic and real-world noisy datasets, comparing with other transition matrix-based methods. We conclude the paper in Section 5.In addition, we provide a more specific review of related works in Appendix A, proofs of theorems in Appendix B, and experimental details in Appendix C.The main contributions of this paper are:• We propose a novel extended model for transition matrix, incorporating sparse implicit regularization, which enables the extension of transition matrix methods from class-dependent noise to a broader range of noisy label data while maintaining simplicity, without the need for excessive additional framework design or sophisticated techniques.• Under certain assumptions, we provide theoretical analysis on the convergence and generalization results of the algorithm on a simplified model. We prove the theorems proposed accordingly, giving support for the effectiveness of the proposed method.• Our proposed method achieves significant improvements compared to previous transition matrix methods on both synthetic and real-world noisy label datasets, and produces competitive results without the need for additional auxiliary techniques. 
methodology: 
 In this section, we give relevant definitions and propose a novel model that extends the transition matrix with implicit regularization (TMR) from class-dependent noise to more label-noise. It is a convenient and end-to-end model. We will formulate the method in detail and illustrate it theoretically.Let X ⊂ R d be the feature space, Y = {1, 2, • • • , C} be the label space, where C is the number of classes. Random variables (X, Y ), (X, Ỹ ) ∈ X × Y denote the underlying data distributions with true and noisy labels respectively. In general, we can not observe the latent true data samplesD (N ) = {(x i , y i )} N i=1 , but can only obtain the corrupted data D(N) = {(x i , ỹi )} N i=1, where ỹ ∈ Y is the noisy label corrupted from the true label y, while denote corresponding one-hot label as y and ỹ.Transition matrix methods use a matrix T (x) ∈ [0, 1] C×C to represent the probability from clean label to noisy label, where the ij-th entry of the transition matrix is the probability that the instance x with the clean label i corrupted to a noisy label j. The matrix satisfies the requirement that the sum of each row C j=1 T ij (x) is 1, and usually has the requirement for T ii (x) > T ij (x), ∀j ̸ = i. The set of possible values for T is denoted asT = T ∈ [0, 1] C×C | C j=1 T ij = 1, T ii > T ij , ∀j ̸ = i . Let P (Y |X = x) = [P (Y = 1|X = x), • • • , P (Y = C|X = x)] ⊤ be the clean class-posterior probability andP ( Ỹ |X = x) = [P ( Ỹ = 1|X = x), • • • , P ( Ỹ = C|X = x)] ⊤ be the noisy class-posterior probability, the formula can be write as:EQUATIONThough estimating the transition matrix and the noisy class-posterior probability, the clean classposterior probability can be inferred byP (Y |X = x) = T (x) -⊤ P ( Ỹ |X = x), where the symbol -⊤ denotes the transpose of the inverse matrix. Alternatively, the neural network can be utilized to fit the clean label distribution by the loss function:EQUATIONwheref θ (•) : X → ∆ C-1 (∆ C-1 ⊂ [0, 1] C is the C-dimensional simplex) is a differentiablefunction represented by a neural network with parameters θ and ℓ is a loss function usually using cross-entropy (CE) loss. Therefore, the key to addressing the problem in this class of methods lies in how to estimate the transition matrix.Since it is difficult to estimate the transition matrix T (x) individually for each sample, the majority of existing methods [31, 10, 22] focus on studying the class-dependent and instance-independent transition matrix, i.e., T (x) = T for ∀x. However, these methods are limited by the assumption of class-dependence and cannot be directly applied to instance-dependent label noise with good effectiveness. Our objective is to make improvement and extension based on this limitation.The main issue with directly applying class-dependent transition matrix methods to instancedependent noise lies in using a fixed matrix The core idea of our proposed model is to introduce a residual term r(X) to fit the distribution difference between P ( Ỹ |X) and T ⊤ P (Y |X), where r(X) is a C-dimensional vector for each X.It can be transformed into usingT ⊤ P (Y |X) + r(X) to fit P ( Ỹ |X).Intuitively, if an overall relatively suitable transition matrix T is applied to T ⊤ P (Y |X), then the difference between it and the probability P ( Ỹ |X) should be small. Inspired by methods that handle noise using sparse structures [57, 25] , we utilize a sparse structure to model the residual term r.Follow the works [30, 31, 25] , using implicit regularization to represent sparse structures is a method that facilitates updates and provides more stable learning performance. We exploit this technique to model the residual term as r i = u i ⊙ u i -v i ⊙ v i with respect to training sample x i , where u i , v i are all C-dimensional vectors and ⊙ denotes an entry-wise Hadamard product. As usual, we use a deep neural network f θ (•) to learn the true label probability y i w.r.t x i . So for the noisy label probability distribution ỹi given by the data, the model useT ⊤ f θ (x i ) + u i ⊙ u i -v i ⊙ v i to fit it.Bring it into the loss function as:EQUATIONDue to the potential existence of different T andP (Y |X = x) such that P ( Ỹ |X = x) = T ⊤ 1 P 1 (Y |X = x) = T ⊤ 2 P 2 (Y |X = x), we add a regularization term of the volume of the matrix Vol(T ) = log det(T ) to loss function as [22] to ensure the transition matrix is identifiable.The total loss function applied in our proposed method is:EQUATIONwhere we estimate parameters according to:EQUATIONWe use the gradient descent method to update the parameters to be learned above. This method constitutes our proposed extended Transition Matrix model with sparse implicit Regularization (TMR).The method steps are summarized in Algorithm 1 in Appendix B.1.Through our model, the estimation of individual transition matrices for each sample is replaced by the estimation of the global matrix and the sparse residual term. In this way, the number of parameters for the transition matrix is reduced from O(N C 2 ) to O(N C), which greatly reduces the difficulty of matrix estimation and computational consumption when C is large. In addition, the incorporation of sparse implicit regularization in combination with the transition matrix makes the learning optimization process concise and efficient.To further improve the effectiveness of our approach, we first utilize contrastive learning as a pretrained feature extractor, followed by label learning. In this work, we also examine the enhancement of the TMR method by incorporating the SimCLR method from contrastive learning as a feature learner as pre-trained encoder, then resulting in TMR+.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: In the theoretical analysis section and experimental section, we analyze the applicability and limitations of our method.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theoretical analysis: 
 In this section, we want to analyze the effectiveness of the proposed method theoretically under specific conditions related to label-noise generation. However, it is difficult to give a direct analysis of the deep neural network model. So we follow the theoretical analysis method of [25] to simplify the proposed model and study on an approximately linear structure to demonstrate the effectiveness of our proposed model.The first to solve is the construction of an approximate simplified model for theoretical analysis of our algorithm. Based on [12] , we use first-order Taylor expansion to approximate the deep neural network f θ (•), which is highly over-parameterized:EQUATIONwheref θ (x) is a C-dimensional vector, θ ∈ R p (p ≫ N ) denotes the parameters of the neural network, ∂f ⊤ θ (x) ∂θ θ=θ0is a p × C matrix, θ 0 is the initialization of θ, symbol • represents matrix multiplication. For simplicity, we drop the constant term in the derivation and abbreviate∂f ⊤ θ (x) ∂θ θ=θ0as ∇ θ0 f (x). The approximate formula becomes:EQUATIONThrough this processing, we simplify the deep neural network into an approximately linear structure, and we use f θ (x) = ∇ θ0 f (x) • θ in the following theoretical analysis. We use a N × C matrix F to represent the neural network predictions on the overall training dataset {(x i , y i )} N i=1 :EQUATIONIn order to be written in matrix form, we rewrite the formula (7) in vector expansion form:EQUATIONwhere vec(A) denotes matrix expansion of a m × n matrix A by column vectors:EQUATIONand Θ is a CP × C matrix, denoting the Kronecker product of C × C identity matrix I C with θ, i.e.,EQUATION)We use a Jacobian matrix G ∈ R N ×CP to denote the partial derivatives of the network for each sample:EQUATIONThen, an aggregate form of formula ( 7) is:EQUATIONNow we give a simplified model assumption that there exists an underlying ground truth parameter θ * such that corresponding F * generated by equation ( 13) fits the true label distribution for sample.Meanwhile, there exist potentially true transition matrix T * and sparse residual matrixR * = [r(x 1 ), • • • , r(x N )]⊤ made up of the residual terms r(x) for sample defined in Section 2.2. We assume that theN × C observed noisy label matrix Ỹ = [ ỹ1 , • • • , ỹN ]⊤ is generated by:EQUATIONExpanded form after bringing in G and θ * is:EQUATIONThe problem to be studied is transformed into given G and observed Ỹ generated by formula (15) , how to estimate the underlying θ * , T * and R * . At this time, our proposed loss function (4) to be optimized transforms into:EQUATIONwhereL is matrix form from ℓ in formula (4), U = [u 1 , • • • , u N ] ⊤ , V = [v 1 , • • • , v N ] ⊤ , R = U ⊙ U -V ⊙ V .Intuitively, the parameters θ, T , R are unidentifiable without other conditions due to the model ( 15)is over-parameterized. We need to add some conditional assumptions to ensure the convergence of parameters. The required conditions are summarized in the Appendix B.2, such as the low rank condition of G, sparsity of R * , special small initialization setting, sufficiently scattered assumption [22] of clean class-posterior probability distribution, etc. Under these conditions, we try to analyze the effectiveness of our algorithm. For the simplicity of proof, we use square loss in formula ( 16), which can be analogized to cross-entropy loss. The parameter optimization problem (5) becomes:EQUATION)Based on this, the convergence result of parameters estimation is as follows: The proof can be seen in Appendix B.3. Theorem 3.1 shows that under a simplified linear model and some conditions, one can use our proposed algorithm to obtain the consistent estimation of network parameters θ * applicable to learning with clean label data. At the same time, we can estimate the overall transition probability T * from the correct label to the noisy label that we observed. Theorem3.1 provides theoretical support for the effectiveness of our proposed method.In addition to convergence, the generalization of the proposed result is also worth exploring. It is finite to the amount of noisy label training data D(N) = {(x i , ỹi )} N i=1 we can observe, which is considered to be randomly sampled from the overall infinite noisy data D. We want to explore how well the parameters θ(N) , T(N) estimated by the proposed algorithm with finite data D(N) fit when applied to the overall data D.We define a function class about the data asEQUATIONwhere γ(•) is the true residual term for each sample. Each element in F is a function about data sample. It is worth mentioning that the term of log det(T ) can be incorporated into the loss function ℓ, without explicitly writing it separately for simplicity. Denote the ϵ-cover of Fas N F = N (ϵ, F, ∥ • ∥ ∞ ),EQUATIONwhere R * (N ) is the true residual terms for D(N) . If we know the ground truth R * , we have the following result:Theorem 3.2. Suppose the loss function is bounded by 0 ≤ ℓ(•, •) ≤ M . For any δ > 0, then with probability at least 1 -δ we haveEQUATIONThe proof can be found in Appendix B.4, using Theorem 2 in [48] as a reference. For any fixed ϵ > 0,as n continues to increase, the terms ln(2N F /δ) Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We provide partial code in the supplementary materials, and the complete code will be open-sourced upon acceptance of the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In this section, we present experimental findings to showcase the effectiveness of our proposed method compared to other methods. We evaluate our approach on both synthetic instance-dependent noisy datasets and real-world noisy datasets. More experimental details can be found in the Appendix C.We conduct experiments on following image classification datasets: CIFAR-10 and CIFAR-100 [16] ,CIFAR-10N and CIFAR-100N [40] , Clothing1M [44] , Webvision and ILSVRC12 [21] . Among them, CIFAR-10 and CIFAR-100 both have 32 × 32 × 3 color images including 50,000 training images and 10,000 test images. CIFAR-10 has 10 classes while CIFAR-100 has 100 classes. We generate instance-dependent noisy data on CIFAR-10 and CIFAR-100 with noise rates ranging from 10% to 50%, following the same generation method as in [42] . CIFAR-10N and CIFAR-100N are manually annotated by human annotators, existing noisy labels within them. Clothing1M is a realworld dataset consisting of 1 million training images, consisting of 14 categories. WebVision contains 2.4 million images crawled from the websites using the 1,000 concepts in ImageNet ILSVRC12, but only the first 50 classes of the Google image subset are used in our experiments. For the validation set selection in our TMR method, we randomly sampled 10 samples from each observed class for each dataset to form the validation set, while the remaining samples were used for the training set.We conduct the experiments using NVIDIA 3090Ti graphics cards. During the training process, we update the transition matrix using the Adam optimization method, the initialization is consistent with [22] . While the updates for other parameters are performed using the stochastic gradient descent (SGD) optimization method. More specifically, for CIFAR- In our experiments, we included the following commonly used baseline methods for instancedependent transition matrix estimation and comparison: (1) GCE [53] , (2) Forward [31] , (3) DMI [45] , (4) VolMinNet [22] , (5) PeerLoss [27] (6) BLTM [46] , (7) PartT [42] , (8) MEIDTM [6] , ( 9) SOP [25] as an implicit regularization method for comparison, as well as state-of-the-art methods for comparison purposes: (10) Co-teaching [10] , (11) ELR+ [24] , ( 12) DivideMix [19] , (13) SOP+ [25] , ( 14) CC [54] , (15) PGDF [5] , ( 16) DISC [23] . We primarily validated our TMR method against previous instance-based transition matrix methods on synthetic CIFAR-10/100 noise datasets. These methods mainly focus on estimating the transition matrix and do not leverage advanced self-supervised or semi-supervised techniques. We performed 5 independent runs for each experimental configuration, and the average values and standard deviations of each experiment are presented in Table 1 .The results demonstrate that our proposed TMR method outperforms other methods of the same category across various noise rates. It is evident that traditional transition matrix methods such as Forward and VolMinNet exhibit subpar performance when handling instance-dependent noise. On the other hand, specialized transition matrix methods designed for instance-dependent noise, such asParT and MEIDTM, still show significant gaps compared to our method.Furthermore, as the noise rates increase, the test accuracy of existing transition matrix methods significantly decline. This is particularly pronounced in the case of CIFAR-100 with 50% instancedependent noise (IDN) data, where all transition matrix methods achieve test accuracy below 60%.In contrast, our proposed TMR method achieves a remarkable test accuracy of 69.85%, showcasing its exceptional performance. That demonstrates relatively robust performance of TMR with only a slight decrease as the noise rate increases.It is worth mentioning that SOP [25] , as a method that also applies implicit regularization based on sparsity assumptions, achieves comparable performance to our method when the noise rates are low. However, it still falls short of our method's performance. As the noise rate increases, SOP is more adversely affected by the noise due to its reliance on the sparsity assumption. In contrast, our proposed TMR method effectively estimates the overall trend by utilizing the transition matrix and combines it with sparsity, thereby demonstrating robustness even in the presence of higher noise rates. For instance, on CIFAR-10/100 with a 10% noise rate, TMR outperforms SOP by 0.87 and 2.87 percentage points, respectively. When the noise rate increases to 50%, TMR surpasses SOP by 4.52 and 5.61 percentage points, respectively. This clearly demonstrates the general effectiveness of our method in handling label noise learning across various noise rates. In addition to comparing with transition matrix methods, we also enhanced our method, TMR, by incorporating SimCLR for feature learning, as TMR+. We compared TMR+ with other state-of-theart methods on multiple real-world noisy datasets, and the results are presented in Table 2 and Table 3 . The results demonstrate that regardless of the type of noise labels, whether it is aggregated, random, or the worst-case scenario in CIFAR-10N, as well as in CIFAR-100N with more label categories, our method consistently achieves the best results in handling real-world noise. When dealing with large datasets like Clothing1M and complex image datasets like Webvision, TMR+ also achieves excellent results compared to to other SOTA methods like CC, PGDF and DISC.Through extensive experiments on five real-world datasets, we demonstrate that our TMR method can significantly benefit from combining with self-supervised methods such as contrastive learning, indicating that high-quality features can greatly enhance our original TMR method. TMR is a plug-and-play model, where the feature extraction part can be unrelated to TMR itself and be replaced with other similar methods without requiring additional special handling. Besides the aforementioned experiments, we conducted ablation studies on proposed TMR method to assess the importance of each component. Table 4 presents the comparative results under 20% and 40% instance-dependent noise rates, where "w/o" denotes "without", "TM" represents the transition matrix, and "IR" the represents implicit regularization. From the results, it can be observed that the absence of either IR or TM significantly affects the performance of our TMR method. Removing IR has a greater impact, particularly in the case of instance-dependent noise, resulting in a substantial decrease compared to TMR. While removing TM yields similar results on CIFAR-10 with a 20% noise rate, the difference becomes apparent when the noise rate increases to 40% or when applied to more complex datasets like CIFAR-100. These results indicate that both the transition matrix and implicit regularization term are crucial components in our model, highlighting the innovation of combining these two aspects in our method. 
conclusion: 
 We propose an extended model for transition matrix that firstly combines it with sparse implicit regularization, enabling the extension of transition matrix methods from class-dependent noise to a broader range of noise scenarios while maintaining the simplicity of the model. The effectiveness of our method is theoretically analyzed under certain assumptions and validated through experiments on various noisy datasets. Additionally, our method can be enhanced by combining with pre-trained feature extractor such as contrastive learning, achieving state-of-the-art performance. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We provided a detailed description of the experimental setup in the experimental section, and specific settings for hyperparameters are provided in the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We conducted multiple repeated experiments to validate our approach and performed ablation experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We list the relevant details in the experimental section.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss the positive implications of our work and ensure it does not have any negative societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper currently does not include any new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. 
 
 Appendix: Most previous transition matrix methods focus on class-dependent label noise to simplify the estimation difficulty. Some of the early methods [31, 43, 47] usually assume the existence of anchor points and make the transition matrix identifiable by finding anchor points or approximate anchor points. To mitigate the anchor point assumption, VolMinNet [22] and TVD [51] add different forms of regularization for the transition matrix respectively to make it identifiable. While other methods [7, 17] try setting up unique network structure to estimate the transition matrix. Besides, [34, 48] utilize structures like meta-learning to estimate the transition matrix, but may require more clean data and computational consumption. Although the above methods are designed to handle class-dependent label noise, it is not suitable when encountering instance-dependent noise or real-world noisy data.However, it is not feasible to estimate a transition matrix individually for each sample without other assumptions or multiple noisy labels [26] . In order to achieve an approximate estimation of the instance-dependent transition matrix, [9] uses an adaptation layer to estimate the transition matrix based on each sample's output, but the error is large due to the influence of the initial value. While [46] uses a separate network to estimate the transition matrix based on the Bayesian label. Some methods [42, 38, 58, 59 ] learn a part-dependent or group-dependent matrix through clustering, which is a compromise estimation method lies between instance-dependent and class-dependent methods.Other methods [6, 14] utilize similarity in feature space to assist transition matrix learning. Although these instance-dependent transition matrix methods achieve identifiability through special treatments, they are usually relatively complex and have larger errors, which is contrary to the convenient and simple characteristics of transition matrix methods.Implicit regularization can be regarded as a statistical method for sparsity, playing the role of minimizing L 1 loss in sparse noise learning and being currently used in various models [55, 37, 49, 18, 56] . Among these methods, SOP [25] is the one worthy of special attention, which is related to our method. SOP also uses implicit regularization for noisy label learning, which gives a sparse representation of the residual term between prediction and observed noisy label. However, it does not take advantage of the overall transfer probability of noise and the noise sparsity assumption does not apply to high noise rates situation, so its performance on large noise rates data is relatively weak. We will compare it with our proposed method by experimental results specifically in Section 4.The steps of our TMR algorithm are shown in detail in Algorithm 1.Condition 1. For optimization problem (17) , initialize parameters in the algorithm 1 with u i = t1, v = t1, where 1 are vectors of all 1, t is a small value scalar. There exists a given α 0 > 0 such that the learning rates of gradient descent satisfy lr(u) = lr(v) = αlr(θ), α < α 0 .Condition 2. Denote the rank of G in formula (15) as r, the number of sparse nonzero entries of R * is k, P is the matrix of row vectors in SVD decomposition of G. Define s = N r max 1≤i≤N ∥P ⊤ e i ∥ 2 2 .Then k, r, s satisfy 4k 2 rs < N .Condition 3. The row vectors of matrix F in formula ( 14) are sufficiently scattered, which is a weakened requirement of the anchor points assumption can be found in Definition 2 of [22] .Proof. Denote Q = (I C ⊗ θ) • T , the optimization problem in ( 17) can be written as:EQUATION)Algorithm 1 Extended Transition Matrix Model with Sparse Implicit Regularization (TMR) Furthermore, it can be converted into the following optimization problem:Input: Training data {(x i , y i )} N i=1 , network f θ (•), coefficient λ, learning rate τ θ , τ u , τ v ,u i ← u i -τ u • ∂L/∂u i Update v i ← v i -τ v • ∂L/∂v i end for Update θ ← θ -τ θ • ∂L/∂θ if b/k is 0 then Update T ← T -τ T • ∂L/∂T end ifEQUATIONwhere β = -log t 2α as defined in 1. When Condition 2 is true, the solution to problem (22) are Q * and R * , where Ỹ is produced by G • Q * + R * . This conclusion can be deduced from the analogy of Proposition 3.5 in [25] . Combining formula (15) , we can get:EQUATION)Therefore, problem (21) transform into an optimization problem with parameter θ, T :EQUATIONThe above optimization problem has the same form as the optimization problem in [22] , similar with Theorem 1 in this paper, under Condition 3, the solution to problem ( 24) is:EQUATION)To sum up, when all conditions in Appendix B.2 are met, we can get the ground truth solution θ * , the estimators by our algorithm converge to T * , R * as mentioned in Theorem 3.1.Proof. We use the inequality we use Hoeffding inequality [11] to help us complete the proof. Since θ(N) , T(N) are not independent of the samples, we use ϵ-cover as mentioned in Section 3.2 to deal with the problem. In addition, the parameter R is omitted in the following proof for convenience and does not affect the understanding of the results.According to the definition of ϵ covering, We can find a pair of parameters θ k , T k in the covering set such that:EQUATION)Average the loss over samples, we have:EQUATION)To meet the requirement of probability 1 -δ in Theorem 3.2, we take the probability value as δ/2N F in Hoeffding inequality due to the randomness of k. Thus, with probability at least 1 -δ/2N F ,EQUATION)By the definition of formula (26) ,EQUATION)According to the property of θ(N) , T(N) in formula (19) , for any θ ∈ R p , T ∈ T,EQUATION)Using the Hoeffding inequality again with probability δ/2, with probability at least 1 -δ/2 we have:EQUATION)Combining inequalities ( 27), ( 28), ( 29), ( 30), (31) and adding the probability values, we get the conclusion that with probability at least 1 -δ,EQUATION)We conduct experiments on a single NVIDIA 3090Ti graphics card. For software, we use Python 3.11and PyTorch 1.10 to build the models. Throughout the training process, transition matrix updates are carried out using the Adam optimization method, while updates for other parameters are performed using the stochastic gradient descent (SGD) optimization method. The experimental setup involves a few training hyper-parameters, including the backbone network used, batch size, learning rate for parameters, and weight of the regularization term. For specific experimental configurations, please refer to Table 5 in Appendix C.2.The backbone network and hyper-parameters of the experiments on each dataset are listed in the table 5 . In addition to conducting experiments on instance-dependent noisy data, we further evaluated the general effectiveness of our method compared to other approaches by introducing class-dependent scenarios on CIFAR-10/100 datasets. Table 6 presents the comparative results on CIFAR-10/100 datasets with symmetric noise rates of 20% and 50%, as well as flip noise rates of 20% and 45%. It can be observed that for class-dependent noise, which serves as a simplified case of instance-dependent noise, our proposed method TMR outperforms other comparative methods, including transition matrix methods specifically designed for class-dependent noise, such as VolMinNet. Specifically, the transition matrix methods specifically designed for handling instance-dependent noise, such as BLTM, PartT and MEIDTM, do not show significant improvements when applied to class-dependent noise scenarios compared to the transition matrix methods designed only for class-dependent noise, such as VolMinNet. However, our proposed method, TMR, achieves significant improvements even when applied to class-dependent noise scenarios compared to VolMinNet. This indicates that our method has universal applicability and yields favorable results in both class-dependent and instance-dependent noise scenarios.NeurIPS Paper Checklist Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: We submitted the paper following the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There are no concerns in this regard regarding this work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The data and code used in our work are all publicly available and open-source.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 


Decision: This paper studies the problem of learning with instance-dependent noisy labels. the authors proposed to use a global confusion matrix shared by all instances and an additional residual term for each instance. For learning, an MLE loss combined with an implicit sparsity regularizer is optimized. The authors also provide a theoretical analysis of the proposed method. The strengths of the paper are theoretical analysis and simple and effective methods. However, weaknesses are a lack of novelty, insufficient motivation, missing baselines and less clarity in the mathematical formulation.  Three reviewers gave negative scores and one positive with lower confidence so the paper can not be accepted in this form. Therefore, it is suggested that the author carefully reorganize the entire paper following the suggestion provided by the review.

Reviews: review: paper_summary: paper_summary: This paper introduces a method that supplements the traditional estimate of a class-dependent transition matrix, which is popular in label-noise learning. Traditional transition matrix methods are less effective for instance-dependent noise. To overcome the limitation, the proposed method adds a residual term such that it can extend the projection of a class-dependent T on label predictions to fit the true one as if we have an instance-dependent T. Theoretical analyses of the algorithm confirm its convergence and generalization properties under specific assumptions. Experimental results on various synthetic and real-world noisy datasets such as CIFAR-N and Clothing1M show the performance.
strength_weakness: strength_weakness: 1. The intuition of the proposed residual is not clear. For example, why a sparse structure is preferable in this problem? Why do u and v enable a sparse structure? Why is a Hadamard product employed? Why not simply use a vector u?
2. The theoretical part of the main paper is heavy but the outcome is not convincing. Specifically, there is a huge gap between Eq. (17) and Theorem 3.1.
3. The assumption in Eq. (7) is too strong.
questions: questions: 1. Is Theorem 3.1 based on infinite data or finite data?
2. It is not clear how the convergence is guaranteed. The critical results refer to another paper.
3. How do you guarantee the uniqueness of $\mathbf \theta^*$, $\mathbf T^*$, and $\mathbf R^*$? I believe it is hard to prove and simply assuming the uniqueness is too strong.
limitations: limitations: NA
paper_summary: paper_summary: In noisy label learning problem, noise is often characterized by confusion matrix. In contrast to instance-independent noise, this work considers a setting where confusion matrices could be different for different samples. Under this setting, the authors proposed to use a global confusion matrix shared by all instances and a residual term for each instance to account for the different between instance-dependent confusion matrix and the global confusion matrix. For learning, an MLE loss combined with an implicit sparsity regularizer is optimized.
strength_weakness: strength_weakness: - Motivation for the use of sparsity regularizer is not clear. The authors does not discuss much on why the vector $\textbf{r}$, or matrix $\textbf{R}$ in their model should be sparse. They did point out in page 3, line 117 that the difference when using the global transition matrix and the instance-dependent transition matrix should be small. However, that is not sufficient to promote sparsity, as any other $l$-p ($l>1$) norm could have promoted that goal.
- The use of implicit regularizer is also not clear. And more importantly, since the output of $\textbf{T}^T P(\textbf{Y} | X) + \textbf{r}(X)$ is a probability vector, $\textbf{r}$(X) has to satisfy certain constraints. This is not discussed nor specified anywhere in the paper. And hence it is questionable how the parameterization of $\textbf{r}(X)$ could produce valid probability vector $\textbf{T}^T P(\textbf{Y} | X) + \textbf{r}(X)$.
- The analysis might contain flaw. Equation (14) is incorrect: $\widetilde{\textbf{Y}}$ is a matrix composing of one-hot vectors while the RHS is a matrix composing of probability vectors. The two are not equal in general. This equation seems to be the key step to motivate the objective to be analyzed in (17), and also the key step in the proof of Theorem 3.1 (page 15, line 534). 
- The analysis is based on linear model which is not very realistic.
questions: questions: - Should condition 1 be a design of the algorithm instead of a condition, since the learning rate should be in our control?
- In real-data experiments, should features extracted from self-supervised learning technique also be used for baselines, since it is applicable to most methods?
- How noisy is generated in synthetic setting?
- How does TMR combat a larger noise? Are there hyper-parameters we can tune in such situations? If yes, how were they selected in the experiment? If no, can you provide some intuition on how different noise level can be dealt with using the same algorithm configuration?
limitations: limitations: Yes
paper_summary: paper_summary: In learning from noisy labels, existing methods generally focus on class-dependent (but instance-independent) noise that can be modeled by a transition matrix $\mathbf{T}$. Some methods have also been proposed for instance-dependent noise (modeled by $\mathbf{T}(x)$). This work belongs to the latter. In particular, it proposes to implicitly model $\mathbf{T}(x)$ using an extended model based on the transition matrix $\mathbf{T}$ and a residual term $\mathbf{r}(x)$. Some theoretical properties (e.g. convergence and generalization) of the proposed algorithm (TMR) are analyzed under certain conditions. Experiments show that the proposed algorithm outperforms baselines.
strength_weakness: strength_weakness: **Originality**

- In Lines 120-125, the residual term $\mathbf{r}(x)$ is introduced. However, it is not clear to me how novel it is compared to the previous work [57,25,30,31]. The authors should elaborate on this point.
- I can see why residual term $\mathbf{r}(x)$ might be useful, but why is it modeled as in the form in Line 124? The motivation should be explained.

**Quality**

- The convergence analysis seems very restrictive to me because it requires too many assumptions (Lines 171-175, Lines 183-186, and Appendix B.2).
- The generalization analysis (Theorem 3.2) is w.r.t. the training loss (surrogate loss) under the noisy distribution $\tilde{\mathbb D}$, but the test accuracy under the clean distribution $\mathbb D$ is what people really care about. Is it possible to prove any consistency guarantees?
- Knowledge of the ground truth $R_*$ is required to derive Theorem 3.2, but we do not know $R_*$ in practice.
- Section 3 is not clearly written, and I found it hard to follow and assess its correctness (see below).

**Clarity**

Section 3 is not clearly written, and I found it hard to follow and assess its correctness. Specifically:

- In Lines 173-174, is $R_{\ast}$ assumed to be $U_{\ast} \odot U_{\ast} - V_{\ast} \odot V_{\ast}$?
- In Lines 203-205, $\mathcal F$ is a set of loss functions. What is the exact meaning of "about the data"? Why is $R$ not considered in $\mathcal F$? Is a fixed $R$ being used here?
- In Lines 206-207, what is the definition of $\epsilon$-cover?
- In Lines 207-208, what are the mathematical definitions of the "average losses"?
- In Lines 210-213, it seems that here $R_{\ast}$ is fixed. Yet, it does not make sense to me because $R$ should depend on the transition matrix $T$ and the distributions $\mathbb D$ and $\tilde{\mathbb D}$. What is "ground truth" w.r.t. here?

**Significance**

The significance of the proposed method could be further enhanced through a more rigorous theoretical analysis (see above).
questions: questions: Besides my questions listed above, here are my additional questions:

- For real-world noisy datasets, how did you get clean test labels?

- In Appendix C.3, what are symmetric noise and flip noise?

---

Minors:

- Eq. (20): $R^*$ ---> $R_*$.
limitations: limitations: I did not see where the authors discussed the limitations of the proposed method.
paper_summary: paper_summary: This paper studies the problem of learning with noisy labels. To handle the instance-dependent noise, the authors propose an extended model for transition matrix-based methods. Specifically, their model combines a class-dependent transition matrix with a sparse implicit regularization term. The authors provide a theoretical analysis of the proposed method. Experiments conducted on both synthetic and real-world noisy label datasets verify the effectiveness of their method.
strength_weakness: strength_weakness: 1. The method proposed in this paper appears to be a straightforward combination of VolMinNet and SOP.
2. The experimental results for TMR are missing for the CIFAR-N, Clothing1M, and WebVision datasets.
3. An important baseline, CCR [1], which is the state-of-the-art among transition matrix-based methods, is absent.
4. The paper lacks an analysis of the estimation error of the transition matrix. It would be beneficial to compare the estimation errors of the transition matrix for TMR against those of other baselines.

**Reference**

[1] Cheng, De, et al. "Class-dependent label-noise learning with cycle-consistency regularization." *Advances in Neural Information Processing Systems* 35 (2022): 11104-11116.
questions: questions: 1. Why is the residual term $r_i$ designed as $r_i = u_i \odot u_i - v_i \odot v_i$? If the residual term $r_i$ were designed as $r_i = u_i$, would there be any theoretical or empirical differences?
2. How does the residual term impact the estimation error of the transition matrix? Does it reduce or increase the error? An analysis or experimental results highlighting the effect of the residual term on the estimation error would strengthen the paper.
limitations: limitations: I did not find that the authors have discussed the limitations and potential negative societal impact of their work. To improve the paper, the authors can provide a thorough analysis of the limitations of their method in an independent section. For example, scenarios where the method might not perform well can be included.

Comments: title: Maintain my initial rating
comment: Since the authors did not post their responses, I maintain my initial rating.
Since the authors did not post their responses, I decide to maintain my initial rating.
Since the authors did not post their responses, I maintain my initial rating.