Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents an algorithm for learning switched linear dynamical systems. An algorithm is proposed which is linear in the size of the problem and the proposed algorithm is demonstrated on some benchmark systems.
strengths_and_weaknesses: Strengths:
1. the problem is well motivated, and still remains open in so many aspects.
2. The analysis of the proposed method is interesting.
Weaknesses:
1. the comparison of the proposed work is weak and makes evaluation of the proposed work difficult.
2. Switched systems can also be modeled using complementarity constraints. It would be good to compare or contrast against those techniques. 
3. The proposed method has been shown for autonomous systems only. Would it work for controlled systems, e.g. where x_k+1=Ax_k+Bu_k?

questions: Please try and answer these:
1.Switched systems can also be modeled using complementarity constraints. It would be good to compare or contrast against those techniques. Do you think that your method could be more efficient than the methods using complementarity constraints? For example, see Contactnets by Post et al. or https://arxiv.org/pdf/2203.10013.pdf.
2. The proposed method has been shown for autonomous systems only. Would it work for controlled systems, e.g. where x_k+1=Ax_k+Bu_k?
3. One the practical problems of estimating or learning in hybrid systems is dealing with imbalance in data between different modes? To make any of these algorithms useful for, say robotic systems, that is a problem that needs to be solved. How do you suggest your algorithm will work if there is an imbalance in data between different modes?
4. Have you tested you method when there are lots of possible modes in the system? A lot of practical systems like robotic systems usually have a lot of modes that can arise? How does your method scale with the number of modes? Please explain.

limitations: Some limitations have been described. I would like authors to think about the limitations I pointed out.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study learning switched linear dynamics from transition pairs of states. They exploit a gap in tolerance (over which performance is ill-defined) to guarantee that when a set of feasible matrices becomes too small, no solution is consistent with the constraints. This is used to prune the search tree of a mixed-integer program (MIP). The size of the tree is bounded using a cutting-plane argument when candidate solutions are picked as the centers of maximum volume ellipsoids (within constraint polytopes). The method is tested on synthetic data, author-curated handwriting data, and highway driving data.
strengths_and_weaknesses: # Strengths
- The paper is well-written, the proofs (in the appendix) are easy to follow and the proof summaries provide good baselines from which most of the details can be inferred.
- To my knowledge, the idea is novel and can be extended to several use cases beyond the proposed setting, such as control systems, state-based hybrid systems (with mode transitions at guards), and general mixed integer convex programming.

# Weaknesses
- It is unclear how to specifically prune leaves, as this involves computing the volumes of complex constraint polytopes.
- Some of the design decisions and experimental conclusions were questionable. Specifically:
  - Modern semidefinite programming (SDP) solvers can handle fairly large-scale problems, I would be interested to see how solving for maximum volume ellipsoid centers (as opposed to Chebyshev centers) would affect the performance of the overall approach.
  - The authors claim (in the checklist) that error bars are not informative, but the timing data for TS in Benchmark #2 is couterintuitive (time is not monotonically increasing); this makes me wonder if the behavior is due to a bug, third-party implementation details, randomness, etc., and standard deviations over more trials could help make this behavior more obvious. 
  - The decision to space data roughly equally (in Euclidean distance) for the handwriting data set isn't completely justified for me; sometimes real-world systems are affected by dynamics with very different transition behavior throughout the state space. I would be interested in experiments without this preprocessing step. 
  - While the predicted velocities for highway data seem good, the "behaviors" extracted from the trajectory modes (in Fig. 2 Right) are not clearly distinguished or obvious to me.

# Typos/Other Issues
- There is a period in the title
- Line 88 and 324, Markov should be capitalized
- The sentence on lines 101-102 is confusing
- Line 137 should read "and *an* absolute limit $\gamma$"
- For Lemma 1 to be necessary and sufficient as worded, the matrices should explain the data away with the mentioned error bound and tolerance, but also the absolute bound $\gamma$
- Line 160, data should be lowercase
- Page 6 was the first place I noticed nonstandard use of colons (to indicate setting a variable?)
- I believe the cited proposition on lines 260-261 should be Proposition 3.7.1
- Line 273, Cartesian should be capitalized
- Line 336-337 should read "which in *turn* can be useful"
- Line 348 should read "turning for changing *lanes*"
- Line 495 should read "*computing* convex sets"
- I believe the citation in Line 508 should be Section 8.4.2
- Should Line 553 (also 592) say that the path from the root to the leaf is of length *at least* $mK$? This seems to agree with the use of $T$ later (which is not introduced)
- Line 569 should read "as in *the* proof of Lemma 7"
- The proof of Lemma 10 is repetitive after the proof of Lemma 7, consider modifying this to highlight only the differences
- Line 617, "linear line" is redundant
- Line 619, I believe $i$ should take values from 0 to $T_{\mathrm{raw}} - 1$
- Page 17, the figure is hard to read. Moreover, the weights on each edge are all listed as 1.0
questions: - How are volumes of constraint polytopes computed? Are they computed, estimated, or are nodes simply pruned once the tree reaches depth $K_\min$? This is a minor concern but it should be addressed.
- Why exactly were handwriting data preprocessed to keep points roughly equidistant?
- Should Lemma 9 read $\mathsf{vol}(\widehat{P}_j) \leq (1 - \frac{1}{n})^n \cdot \mathsf{vol}(P_j)$? It seems like the multiplicative factor $(1 - \frac{1}{n})$ should be included for each row of the matrix $A_j$. Additionally, this would sharpen the $n^3$ in Lemma 10 to $n^2$.
limitations: I believe the authors have adequately captured the limitations of their work and have thought about potential negative societal impact. I think the submission could use a comment on how approaches for switched nonlinear systems may need to be developed (what kinds of approximations could be necessary, localized analysis, etc.), though this is clearly out of the current scope of the work.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This work deals with the problem of learning a switched linear system model from state-trajectory data, where the underlying mode switches are not observed. The goal is to learn state transition matrices and an assignment of each transition in a given data set to the corresponding mode, i.e., linear transition function, such that a certain error criterion is fulfilled.
Since the naive problem setting based on Mixed-Integer-Linear-Programming is computationally infeasible, the authors propose a relaxation of the problem. For the relaxed setting, a concrete algorithm is presented, its correctness is proven and its time complexity is investigated. Finally, the algorithm is applied to synthetic task, a handwriting prediction task and a traffic data set.
strengths_and_weaknesses: ## 1. Originality
The problem setting seems to be established, but the proposed relaxation approach is new. The algorithm and its analysis are also novel, but based on standard arguments. In particular, in the relaxed problem setting no technical complications appear and no novel techniques seem to be necessary. The algorithm uses a pruning approach based on a treshold of the volume of certain polyhedrons which seems to be new, but due to lack of familiarity with this area this evaluation is not certain.


## 2. Quality
The presentation needs to be improved. The article has language and grammar issues, as well as formatting problems (e.g., using a colon instead of an equality sign). Furthermore, some technical arguments could be explained better, e.g., in the Lemmas in Section 3 or Figure 2. Additionally, there should be more references. Finally, some relevant details on the experiments are missing. There seems to also some potential technical problems, cf. Questions section below. 

## 3. Clarity
As already mentioned, the presentation needs to be improved. For example, there is no pseudocode description of the whole algorithm (only some parts of it are presented in Algorithm 1). Some arguments and explanations are also difficult to follow.

## 4. Significance
The identification of switched linear systems is an established and relevant area. The proposed algorithm seems to be working and computationally efficient (in the number of data points, not the state dimension and number of modes). However, the comparison with prior work and state of the art (in particular, in the experimental section) needs to be more thorough, so its difficult to confidently assess the overall significance.
questions: ## Questions
* How exactly could the SARX model be used to deal with output measurements? Does the algorithm and its analysis need adaption to this case?
* Page 5, line 203: "then we create $m$ child nodes" This seems incorrect, since in Algorithm 1 a child node $\nu_j$ is only created if $\hat{P}_j$ is feasible
* Proof of Lemma 4, lines 531-532: Does such a leave node (with $\mu=\mu^\ast$) always exists?
* Proof of Lemma 5: According to the proof, the lower bound should be $\epsilon_\text{gap}^n2^{n^2}/(n!)^n$ How is the lower bound stated in the lemma then derived?
* Experiments:
  - Why the choice of $\epsilon_1=0$? Does it make the problem easier?
  - the MVE is replaced by Chebychev centers. What exactly is lost when using Chebychev centers, i.e., which guarantees cannot be given anymore?
  - What is the MILP approach? No details are given
* Page 7, line 303: Why $N=kT$? If the trajectories have $T$ time steps, then there are only $T-1$ transitions (and each data point correponds to a transition)

## Additional detailed remarks
* p1, l26: Why "explain away"? This is somewhat of a technical term in e.g. Bayesian networks
* p1, l28: Reference for NP-hard would be good here
* p1, l30: Reference for exponential complexity would be good here
* p2, l37: Unclear, what is $\epsilon_2$?
* p2, l39: The rest of the paragraph is very unclear. E.g., it is unclear what is meant by "tree" here.
* p2, 48: Which approach is used to generate the optimization problem solved by GUROBI? The latter is just a general-purpose MILP solver
* p2, l52: What does it mean to "predict the alphabet"?
* p2, l56: Is reference 28 the earliest one in this area?
* p2, l61: Wording unclear, "over a formulation"
* p2, l74: Unclear how minimizing the number of mode switches is a relaxation / simplification of the problem
* p2, l79-84: This paragraph needs to be improved. In particular, no references to existing works using the approach here are given. Are Deep Learning approaches used at all in this area? Furthermore, while at the start of the paragraph ReLUs are mentioned, at the end of the paragraph it is argued that Deep Learning approaches are problematic due to the use of smooth activation functions like sigmoids.
* p2, l87: The technical terms "traces" and "guards" haven't been defined
* p3, l91-92: Unclear, is variational inference used in the EM algorithm or is the EM algorithm regarded as a variational inference technique?
* p3, Definition 1: The formulation is rather unusual and a bit imprecise. For example, $A_1,\ldots,A_m$ are not $m$ different dynamical systems, but rather $m$ matrices inducing $m$ different linear dynamics. Furthermore, the last sentence "We can generalize this to have output maps that also depend on the mode" should be outside the definition.
* p3, l121: The term "observable" has a technical meaning in systems theory, better to use "not observed" here
* p3, l121-122: This sentence is unclear, more details on this approach are needed.
* p3, l135: Typo, "with" instead of "will" needed. Furthermore, the definition of $E_n$ should be moved to the notation section.
* p4, l136: Abbreviation SLS-ID not introduced
* p4, l136-137: Better not to used colons in the sentence
* p4, formula (2): Here $\leq$ seems to be mean entrywise order. Either define this or rewrite the formula in an elementary manner (e.g. $\forall j=1,\ldots,m$ we have $(A_j)_{k,l}\in[-\gamma,\gamma]$ for all $k,l=1,\ldots,n$)
* p4, l148: Is "big M method" a technical term in the field of switched linear systems?
* p4, l149: Abbreviation MILP not introduced
* p4, l150-151: There should be at least one reference for "a common approach"
* p5, l158: This is not really a definition, but rather an algorithm description and should be formatted and labelled accordingly
* p4, l159: Use $:=$ instead of $:$ 
* p4, l162-164: Are the outputs really the only two cases? This needs to be clarified
* p4, l166: "It is easy to show". At least some details should be provided, maybe in the supplementary material. Furthermore, this statement should be made more precise. For example, what about the case $x_i=0$ and $\|x_i'\|_\infty >> 0$?
* p4, l167: What does "ignoring the technicality related to the limit" mean?
* p5, Algorithm 1, l9: What does $\hat{P}_j$ feasible mean? That this polyhedron is non-empty?
    Furthermore, what happens if this condition is False for all $j=1,\ldots,m$? 
* p5, l186: In which space are the polyhedra?
* p7, l300: What is meant by traces? Trajectories?
* p7, l303: Why $N=kT$? If the trajectories have $T$ time steps, then there are only $T-1$ transitions (and each data point correponds to a transition)
* p7, l304: What are "predicted and actual states"? The setting introduced is identification, not prediction
* p8, l314-321: Why was this setting chosen? Is there related work on such tasks? What would be the state of the art?
* p8, l322-327: Details missing. For example, how are the JMM used?
* p9, Figure 2: Better labelling required. In particular, axis labels are missing in both subplots
* p9, l1360-361: It hasn't been explained how the approach can be extended using SARX models

## Supplementary material
* p13, l522-528: This paragraph could be made a bit easier to follow, e.g., to be more explicit.
* p15, Section D: Details on the MILP method and the implementation of the proposed method should be provided here
limitations: The authors addressed adequately any potential societal or ethical implications.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Summary: This paper studies the identification of switched linear dynamics where the underlying mode is hidden (but the total number of modes is known). The contribution is an approach whose computation complexity scales linearly in the number of samples, as opposed to the exponential scaling in the MILP approach. However, the complexity of the proposed approach still scales exponentially with the number of modes and the state dimension. The approach is a tree search algorithm, and the core innovation is a pruning-based technique on the volume. This limits the depth of the tree. The computation complexity of the approach is provided. 

strengths_and_weaknesses: Weakness: 

Still, exponential dependence on the number of nodes and state dimension is needed. The author needs to provide a discussion on why the exponential dependence is difficult to avoid. For example, I don’t really see why the exponential dependence on $n$ is needed. Based on the analysis, the exponential dependence comes from Lemma 6, but is there a way around it?  Also, the MILP algorithm only scales exponentially with $m,N$, not $n$, right? If so, this means the MILP algorithm could scale to high dimensions, while the proposed algorithm cannot. This should be acknowledged and discussed. 

Comparison: the majority of the paper focuses on comparison with the MILP approach, which is fine. However, in the related work session, a few other approaches are mentioned, e.g. the Ozay et al one and the clustering approach. How does the proposed approach compare with these related work, both theoretically and empirically? 

Presentation: the only pseudo-code is Algorithm 1, which is a subroutine on how to expand a node in the search tree. I suggest adding the pseudocode for the entire algorithm. 

questions: Line 4 of algorithm 1: 1: how are the $Q_1,\ldots,Q_m$ chosen. Arbitrarily from $P_j$? 

Line 6 of algorithm 1, I assume $(x_i,x_i’)$ is from line 2. However, what if Line 2 returns multiple pairs of $(x_i,x_i’)$? 

Line 232: should it be the mode $j = \mu^*(x_i,x_i’)\in [m]$? 

Line 224: where does the $2^{mN}$ compute from?  Based on my read of the algorithm, at each layer, each node splits into m nodes, and the maximum depth is N. So shouldn’t the complexity be $m^N$? 

Table 1, benchmark 2, tau = 0.00, for the TS run time, why the run time for N=10000 is smaller than N=1000. 

Line 236: a “stronger” assumption is introduced here - does the main result Theorem 1 relies on this assumption? If so, this stronger assumption should be introduced in or before Theorem 1. 

In both Lemma 4 and Lemma 5: there is a notion of “iteration”, which I think means each round of expansions of the current leaf nodes. Also, in Line 257, there is a redefinition of a step of the algorithm. Going back to my earlier comment on pseudo-code, I think the paper needs a formal presentation of the full algorithm so that the “iteration” is formally defined and the details of the algorithm are finalized. 

limitations: The authors have addressed the limitations and potential negative societal impact of their work
review_title: null

Meta-review: metareview: This was a borderline paper and after discussion with the reviewers, we have decided to accept the paper. The paper currently has many typos and the approach requires more comparison with other approaches for learning switched systems--- though these can be addressed in the final revision. Overall, the paper address a relatively open question from a machine learning viewpoint and the results are interesting and the approach is novel. 
confidence: Certain
Decision: Accept