Learnability of Discrete Dynamical Systems under High Classification Noise

Detailed comments

$\bullet$ The notation for $h^*$ on line 120 is not in accordance with how its employed in most of the rest of the article.

$\bullet$ PAC system is not described in needed detail.

$\bullet$ Line 170 can be phrased better. Possibly the authors want to empahsize that the learner does not know which transitioned state is wrong. The initial state prior to transitioning is known.

$\bullet$ In Remark 2, authors try and connect the original problem which is dynamic and the "stationary" problem being analyzed. The relationship of the dynamical updates of the original problem and the stationary problem that assumes a distribution of initial states being generated remains unclear and unconvincing; is it possible the dynamic setup cannot be described by a good distribution and thus data collected at diffferent phases of the dynamic evolution will lead to different results.

$\bullet$. In Remark 3, the authors provide rationale on why the measurment noise corruption leading to flipping the bit with probability less than $0.5$ leads no loss of generality. It seems like knowledge whether the probability of flipping the bit is greater than 1/2 or less than 1/2 is needed. The other part of the remark on the difficulty of unravelling the structure of the graph is difficult needs to be better qualified. There is a large literature on estimating topology of agents interacting with each other via quite general relationships. This part of the remark overeaches considerably.

$\bullet$ In line 225, the phrase number of labels is used. There is no explanaation of what labels mean. From later part, it seems like the number of labels is two, either zero or one. It is advisable to remove the use of labels and related development (for example in the Proof of Lemma 3.1) and set it to two.

$\bullet$ On element wise ERM, the authors use the emperical loss with respect to node $i$ of any hypothesis as

$\min\sum_{j=1}^q \mathbb{1} \left(h(W_j)[i]\not = \hat{W}_j[i]\right)$

where the tuples $(W_j,\hat{W}_j)$ are provided to the learner. The above optimization will lead to a solution say $h^{opt,i}$ for the $i^{th}$ node. The authors seem to make an assumption that $h^{opt,i}=h^{opt,j}.$ Though authors state as much, this assumption is very restrictive.

$\bullet$ Lemma 3.1 is quite confusing. The authors introduce partitions with respect to each node $i$ which are equivalence classes of hypothesis which result in the same empirical loss. Thus, the partition depends on the number $q$ of the available training data and thus are dictated by the probability distributions $D$ and $\eta_v.$ Thus the cardinality of the maximum element of the collection of partitions $t_max$ should be a random variable (dictated by the distribution on the training size, $q$, $D$ and $\eta_v.$) Now the order relation of $q$ involves $t_max$ which is itself dependent on $q$, $D$ and $\eta_v.$ This seems like a circular dependency. Authors needs to indicate clearly what the relationship implies.

$\bullet$ The V-ERM algorithm generates a hypothesis by first setting $\tau^{opt}_i$ the threshold for node $i$ that minimizes the empirical loss for node $i$ and then forming the hypothesis by using $\tau^{opt}_i$ for node $i$ for $i=1,\ldots,n.$ Theorem 3.2 statement does not suffer from the ambiguity of Lemma 3.1 pointed earlier; however, the proof relies on Lemma 3.1. There might be a way to derive Theorem 3.2 directly with the concrete construction of the partition.

$\bullet$ For VisScore and VisRange algorithms, the authors propose to use the training data of configurations and the transitioned measured configurations to evaluate the frequency of a score, of a node, which is number of neighbor states that possess the value $1$ over the $q$ number of training data. For each of these scores the frequency of the transitioned configuration of the node as measured is also tracked. The statitics of the score and the transitioned value is leveraged to obtain estimates on the threshold to be used for setting the state to one. The analysis tracks scores that have high frequency for a node and the associated frequency of transitioned state being $0$ or $1$. Here standard techniques are employed to arrive at the sample-complexity of etsimates on the probability of scores and the error introduced by the measurement (considered to have a probability less than $1/2$) to diminish with training size $q$ to arrive at the result.

$\bullet$ Simulation results are presented that show $VERM$ showing gradual improvement whereas VisScore and VisRange algorithms show phase transition like behavior. More analysis with respect to the nature of the graph would provide more insights. Authors can clarify how the simulations were carried out; whether the dynamic version was simulated or was distribution of configurations $D$ used in some manner. If the dynamic version was employed then it would be interesting to understand which kinds of distributions arise.

1. Refer to the Weaknesses section
2. The authors claim that the unknown graph case is hard. I don't see why there isn't a direct reduction to halfspace learning with random classification noise. There are many efficient algorithms for this problem. For the state of the art, see [DKT23]

[DKT23] Ilias Diakonikolas, Christos Tzamos, and Daniel Kane; A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning; STOC 2023

Please see the weaknesses above in addition to my questions below.

• Remark 2 is unclear in terms of how this dynamical system could be sampled over a trajectory. I think there could be some issues when the system updates are cyclic and the sampling only captures a single cyclic behavior. Let $\mathcal{D}$ be the trajectory of the system, and suppose the system is sampled every other time period. We can generate a system such that the score for a vertex $i$ is 0 during these time periods, but the threshold function could be arbitrarily large, say, the degree of $i$. Then, you will not be able to learn the threshold function of vertex $i$ despite the minimal training error. In other words, any positive threshold value minimizes the training error, but the test error would be high when we randomly sample from trajectory $\mathcal{D}$. Therefore, I believe there should be additional assumptions on the sampling behavior over a trajectory to avoid such ill cases and cyclic behavior. How can you address this?
• If you are sampling data from a trajectory of the dynamic system, the observed data would be correlated over time. How do you address the correlation over time in your proofs and results? Does it pose an additional challenge? How is it different from samples drawn from independent and identically distributed multiple trajectories of the system?
• If my understanding of Hamming distance ERM is correct, why do you claim ERM cannot be done efficiently unless P = NP on line 064? Do you mean ERM with the error loss function only?
• In Figure 3 (b), the sample complexity does not increase quadratically for the algorithm V-ERM. The sample complexity is $\mathcal{O}(n^2 \log(n))$ for this algorithm. Rather, it looks like a linear increase. How can you express this behavior?
• How do you explain the extension from VisScore to VisRange? What was the theoretical and empirical justification for focusing on this problem?
• How can you generalize these results to hypothesis classes of infinite size, e.g., $|\mathcal{H}| = \infty$? For example, you could have an interaction function with a parameter that can take infinitely many possible values.
• Similarly, how can these results be applicable to a system where vertex $v$ receives faulty observations from its neighbors? In other words, if we did not have random classification noise but had random observation noise from the neighbors due to partial information sharing or information asymmetry, can we use these algorithms for learning?
• How can the result be extended to non-stationary threshold functions (what happens when the threshold changes over time)?

How does the guarantees of VisRange vary with increased graph density? It is unclear how the performance scales with denser graphs, as higher connectivity could potentially increase noise propagation. Could the authors give more intuitions on that? Could the authors provide experimental results on how VisRange performs with varying graph densities?

Minor: Repeated ``there" in line 1103.