Generalization Gradient Descent

Authors: Rueicyuan Su, Tzuen Su, Jia-Ching Wang, Minghsiang Su
Primary area: learning theory
Keywords: out-of-distribution, generalization problem, gradient descent

Abstract:
We propose a new framework for evaluating the relationship between features
and generalization via a theoretical analysis of the out-of-distribution (OOD)
generalization problem, in which we simultaneously use two mathematical methods:
a generalization ratio that quantitatively characterizes the degree of generalization,
and a generalization decision process (GDP) that formalizes the relationship of loss
between seen and unseen domains. By combining the concepts of informativeness
and variation in the generalization ratio, we intuitively associate them with OOD
problems to derive the generalization inequality. We then introduce it to the GDP to
select the best loss from seen domains to gradient descent for backpropagation. In
the case where the classifier is defined by fully connected neural network, the entire
system is trained with backpropagation. There is no need for any model selection
criterion or operating on gradients during training. Experiments demonstrate the
potential of the framework through qualitative and quantitative evaluation of the
generalization ability.

Decision: reject
Reviewer scores: 6, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1729084979966

thread_type:
official_review

<thread_object>
creator: reviewer_kcqj

<content>
summary:
This paper introduces a new way of performing gradient descent.  Firstly, this paper defines a certain kind of generalization capability. Then, this paper proposes a method  which selects training sample of each step in a reinforcement learning (RL) manner, thereby improving the gradient descent process.

strengths:
This paper presents a novel approach to gradient descent. It proposes an innovative method that selects the training samples for each step using a RLstrategy, which enhances the overall gradient descent process. This approach demonstrates a creative combination of RL and optimization techniques, potentially leading to improvements in training efficiency and model performance. The integration of RL for sample selection is a unique aspect that sets this work apart from traditional gradient descent methods, which is quite interesting.

weaknesses:
Line 149: eature -> feature

Line 176: The definition of $W^*$ is a little confusing. Do you mean $\forall W^* \in \mathcal{W}^*$ or $\exists W^* \in \mathcal{W}^*$?

Line 505: The font in the image is too small to be readable.

  

In Definition 3.1, this paper introduced the definition of the Ideal feature matrix function. However, I still don’t have an intuitive sense of it, and it feels like it’s missing some explanation here. I think it would be better if the reasoning behind this definition or references to relevant literature could be provided.

questions:
Theorem 4.2 provides an upper bound of the generalization error. Is the generalization upper bound tight? Additionally, I noticed that the upper bound of the generalization error is composed of both the generalization ratio (GR) and the training error. The optimization in the RL section is performed with respect to GR. However, as the sample size n increases, which part—GR or training error—will dominate the generalization error? If there are some theoretical results regarding this, I believe the results could be more complete.

In the RL section, the paper uses Q-learning to adjust the training set. The state space is the set of G, and the action space is the selection of training samples. However, I’m a bit confused: for a highly complex model, can its state really be represented by a one-dimensional scalar G (Generalization Ratio)? The theory here seems a bit not solid enough.

Overall, I think the idea of this paper is interesting, but I still have these concerns. I would be happy if the authors could address my questions. Thank you.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730145938099

thread_type:
official_review

<thread_object>
creator: reviewer_t6dp

<content>
summary:
The paper proposes a variation of the framework of (Ye et al., Neurips 2021) to analyze out-of-distribution generalization, then propose a training algorithm that uses these concepts to offer cross-domain generalization performance.

Ye et al. (2021) studies how to use a small set of domains Eavail to construct a classifier that works across a larger set of domains Eall that we obviously are not expected to know in advance. They provide bounds that depends on an essentially unknowable "expansion function" that measures how features qualities expand from Eavail to Eall.  This paper instead assumes that all domains are available in a set Eavail that is partitioned into training domains Etrain and validation domains Eval. There is no Eall anymore, and one wonder why one should not train using all the known domains of Eavail (which are all the domains that matter) rather than a subset.  Other differences relative to (Ye et al. 2021) include an attempt to talk about features in all network layers (instead of just the penultimate one).

strengths:
This is an ambitious paper.

weaknesses:
* This paper instead assumes that all domains are available in a set Eavail that is partitioned into training domains Etrain and validation domains Eval. There is no Eall anymore, and one wonder why one should not train using all the known domains of Eavail (which are all the domains that matter) rather than a subset. 

* There is something disturbing in equation (3) [Thm 2.1].   Remember that W(X) is a dxN matrix.  An expression of the form P(W(X^{e_i})|...) should be normalized over the values taken by this matrix, not over the i indice representing the domains.  Either the notation is inadequate (meaning that the authors mean something else) or the theorem is wrong.

* Through definition 3.8, algorithm GGD depends on all the domain distributions in Eavail and not just the domain distributions in Etra.  Since one wishes to be robust in Eavail  (unlike Ye et al. (2021), there is no Eall here], why not use Eavail directly.  The only justification that comes to my mind would be when Etra is small and Eval is much larger.  But evaluating GR_{KL}(W, Eavail) does not seem cheap. 

* I must recognize that I find all this very unclear.

questions:
Please see the weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730469918672

thread_type:
official_review

<thread_object>
creator: reviewer_fd14

<content>
summary:
The paper tackles the out-of-distribution (OOD) generalization problem. The main ideas are to consider the distribution of features invariant to domain shifts and to formulate them as the ideal feature matrix function, generalized model, and non-generalized model.  The paper also introduces the variation, the informativeness, and the generalization decision process (GDP) to propose a new algorithm called the generalization gradient descent (GGD) based on the framework of reinforcement learning. The GGD performs better than the traditional gradient descent in their experiment.

strengths:
The paper discusses the generalization problem mathematically rigorously. The ideas of generalization ratio and generalization decision process are novel and the introduction of reinforcement learning framework is unique.

weaknesses:
It is not clear whether the framework is practical or not since the definition of the ideal feature matrix function that the posterior distributions of y are the same seems too strong to exist in real problems. The reviewer recommends showing some examples. The experiment is rather small and specific, that is, it compares only GGD and TGD. The effectiveness of the proposed algorithm should have been confirmed with a larger number of problems. In addition, this work strongly depends on the previous work (Ye+ 2021) and its difference seems not large since many of the concepts were introduced there.

questions:
None.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730542788365

thread_type:
official_review

<thread_object>
creator: reviewer_eyvk

<content>
summary:
This paper proposes a novel framework for analyzing out-of-distribution (OOD) generalization, integrating a generalization ratio to quantify generalization capacity and a generalization decision process (GDP) to link losses across seen and unseen domains. This framework enables backpropagation-based training without model selection, using a combination of informativeness and variation in generalization to derive a generalization inequality, with experiments showcasing its effectiveness in improving generalization ability.

strengths:
1. They designed an algorithm focused on enhancing the generalization ability of gradient descent, leveraging the concept of a generalization ratio and insights from reinforcement learning.
2. They experimentally demonstrate that the algorithm outperforms traditional gradient descent.

weaknesses:
1. The title is intriguing. Would it be clearer to use 'Gradient Descent with the Generalization Ratio: Enhancing.......' instead?
2. In my view, GGD is proposed based on reinforcement learning and the generalization ratio. However, the motivation behind the algorithm design could be clarified further.
3. There is considerable overlap with the paper by Ye et al. (2021). It might help to elaborate more on the ideas behind the algorithm's design.
4. The writing could be improved, as there are several grammatical errors throughout.

questions:
1. You introduced the concept of the generalization ratio (GR) in this paper. Could you clarify the functional difference between V_KL for different e_i sets and GR?
2. As a novel and important criterion, could you elaborate on the properties of GR and why it serves as a strong evaluation metric?
3. Could you design some experiments that demonstrate the advantages of using GR instead of V_KL as Ye et al. (2021) also provided a model selection criterion?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732641846424

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We have submitted the revised version of our paper with corrections to the typos. We would like to extend our sincere gratitude to all the reviewers for their valuable feedback. We remain confident in the strengths of this submission, which are primarily grounded in the OOD mathematical framework proposed by Ye et al. (2021). In our work, we demonstrate innovative, simple, meaningful, and scalable algorithms that perform comparably or even surpass traditional gradient descent methods. These conventional approaches are often more prone to overfitting, unable to handle OOD scenarios effectively, and lack groundbreaking advancements. We believe that we have addressed all of the questions posed by the reviewers. We would appreciate if the reviewers could update their evaluations and scores, clearly articulating any aspect they still don't like about the paper so that we can continue improving it for the future.
</content>
</thread_object>

</thread>


Metareview: