Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies estimation of process and observation noise variance in a subclass of linear dynamical systems whose states evolve according to $X_{t+1} = X_t + h_t$ and observations follow $Y_{t} = \langle X_t, u_t \rangle + z_t$, in which $u_t$ are known observation vectors. The paper presents the first algorithm for the estimation of variance in this class of dynamical systems that enjoys finite-sample guarantees. The approach revolves around forming variance estimators that exploit data-dependent operators. 
strengths_and_weaknesses: **Strengths** 
- The paper presents the first variance estimation for the LDS subclass with finite-sample guarantees. The resulting algorithm is simple.
- As far as I know, techniques used in the derivation of the approach are original.
- The paper is reasonably well-written. The authors provide intuition regarding their choices and approach and compare them with alternatives.

**Weaknesses**
- The system considered in this work is a subclass of LDS with scalar observations, which can limit the applicability of the approach.
- The experiment section is a bit weak (although the paper is mainly theoretical). At least based on the experiment in Section 6.2, STVE does not perform better than MLE (followed by the Kalman filter). Additional empirical evaluation that highlights the benefits of STVE (e.g. in handling non-Gaussian noise) would strengthen the paper). 
questions: Additional related work suggestions that seem relevant:
- Rashidiejad, Paria, Jiantao Jiao, and Stuart Russell. "SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory." 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. 2020.
- Tsiamis, Anastasios, and George J. Pappas. "Linear systems can be hard to learn." In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2903-2910. IEEE, 2021.
limitations: Limitations are discussed. The work is mainly theoretical.
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: This paper provides novel finite-sample guarantees for parameter estimation in the dynamic linear regression setting, where the true linear model’s coefficients vary across time. By recharacterizing the dynamic regression problem into a linear dynamical system, the authors note that existing methods, such as the Kalman Filter, rely on knowing certain variance parameters. While one could estimate these variance parameters using maximum likelihood estimation, the accompanying Gaussian noise assumption is perhaps too strong and there are only asymptotic guarantees of the validity of the estimates. The authors of this paper have developed a procedure with finite sample guarantees for estimating the variance parameters with a less onerous sub-Gaussian noise assumption for the dynamical system. With a simulation, the authors demonstrate that the novel estimator’s error decays at a rate in line with the theoretical guarantees. In an empirical example of predicting electricity consumption over time, the authors show that their estimator, once inputted into a Kalman Filter algorithm, performs comparably to using maximum likelihood estimations as the inputs. 
strengths_and_weaknesses: Strengths

The paper provides novel finite-sample guarantees in a useful generalization of linear regression. The proofs seem innovative and non-trivial, providing bounds that may have previously seemed out-of-reach. In particular, the use of existing theory on the discrete Laplacian operator on the line seems like an especially novel approach that other theoreticians will find intriguing and useful.

The authors do a great job of showing how the problem set-up, which starts very general, can be recharacterized into a more specific problem that has been well-studied. No less, the authors home in on an aspect that has previously been untouched, providing bounds on estimating variance parameters in the dynamical system.

The clarity of the paper’s writing and the cogent overview of the literature were also appreciated. Via the problem set-up section, the authors provided very clear exposition on the links to previous literature and what the novel contributions of this paper is, aided by uniting the notation of their approach with others. The writing was clear throughout, and the authors provided ample details and justification for the proof sketches in the body of the paper.

Weaknesses

The two main ways to improve the paper are in enriching the experimental section and making more clear the importance of the novel finite sample guarantees.

In the empirical sections, it seems like MLE often does not differ much from the novel approach. While the authors briefly note this, it would be useful to have them discuss the implications of this more. For example, under what circumstances do they differ, and can we learn anything from those settings? In addition, for the performance comparisons on the real world data example, it would be helpful to list MSE or some other test metrics. While plotting the predictions versus the truth was certainly a step in the right direction, it could seem like obfuscation to not provide the metrics, especially since it seems like the novel estimator may have performed worse than the MLE. For the simulation study, the sensitivity analysis provided on the number of samples was certainly of utmost importance. However, the authors should also note why they chose some of the settings (e.g., why the number of covariates was five or the choices for the ground truth variance parameters). It was not clear whether these settings were chosen due to computational constraints, to enhance the signal-to-noise ratio, to adhere to some realistic empirical examples, or if they were just drawn out of a hat.

It may be useful to provide more color on the usefulness of better variance parameter estimates and these guarantees. Are the parameters only useful insofar as inputs to the Kalman Filter and related approaches to get better dynamic coefficient estimates? Or are these variance parameters intrinsically interesting?

questions: The field of data assimilation often deals with methods like the Kalman filter with unknown parameters; I was surprised not to see this mentioned and it would be helpful for the authors to explicitly address their contributions relative to work in that field. For instance, how does the submission compare with https://arxiv.org/abs/1903.09122, https://arxiv.org/abs/1912.12309, or https://arxiv.org/abs/2001.06270?
limitations: The paper discusses limitations naturally for the most part, given the extensive discussion of comparable methods and highlighting the new assumptions the novel approach relies on. The authors do note, briefly, at the end of the Experiments section that their novel approach performs “practically identical” to the maximum-likelihood estimation approach. While this is not at odds with the main claim of the authors of finally providing an estimator with finite sample guarantees, they are essentially acknowledging a limitation of the new estimator’s performance versus existing methods.

As far as the discussion on societal impact and the like, the paper eschews such discussion due to the theoretical nature of research.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers considers non-stationary linear regression with sub-Gaussian observation noise z (of variance \eta^2), where the regression vector X undergoes at each time t an additive modification by a process-noise vector h, also sub-Gaussian and zero mean with independent components of variance \sigma^2. 
Estimation of the true trajectory and forecasting can be done by Kalman-filtering, once the true noise-parameters are known, and the principal contribution of the paper is to provide and analyze an algorithm to estimate the variances \sigma^2 and  \eta^2. The approach is an alternative to maximum likelihood estimation (MLE).

A compressed form of the process equations leads to a linear equation in  \sigma^2 and  \eta^2 modulo a fluctuation term. Applications of the Hanson-Wright inequalitiy bound these fluctuations and show that they are of smaller order than the coefficients in the equation. A second equally structured equation is obtained from a truncated time-series, and the two equations are solved for \sigma^2 and  \eta^2. The paper is careful to demonstrate that this system of equations is in general well conditioned relative to the magnitude of fluctuations.

An experimental section compares the algorithm to competing methods and works about well as MLE. 
strengths_and_weaknesses: Strengths: 
1. In contrast to MLE the approach has performance guarantees for the more general sub-Gaussian noise model.
2. The paper contains a number of interesting mathematical tricks.

Weaknesses:
1. The presentation is a bit opaque. Section 4 could perhaps be a lot more readable if portioned into sub-sections: Obtaining the representation (7) - why using the pseudo-inverse and obtaining (11) - obtaining the second equation (12) - etc.
2. The role of Theorem 3 and Section G could be better explained. The most problematic part of the error bounds in Corollary 2 (inverse parenthesis) can already be observed when executing the algorithm, so from a practical point of view Theorem 3 and Section G are superfluous. Their interest lies in showing that generically the division in step 4 of the algorithm is unproblematic.

questions: Some typos:

l 146, square missing in expectation

l 185 and l 186, "the" missing before "sum" and "identity"

l 199, I believe it should be \gamma instead of \lambda

p 19, equation (78). u_max and u_min seem exchanged.
limitations: There is no section on limitations, but I am also not clear on what it should contain for this paper.
review_title: null

Meta-review: metareview: The paper considers the estimation of process and observation noise variances in a subclass of linear dynamical systems and provides algorithms with finite sample guarantees. The math is novel and the results are interesting. I am happy to recommend acceptance. 

confidence: Certain
Decision: Accept