Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper under review is devoted to the analysis of the stochastic approximation algorithm with the presence of the drift term. The main result is to derive finite-time bounds on the expected mean square error. 
main_review: The authors consider the problem of form
$
min f(x) + r_t(x)
$, where $r_t$ is a drift term. The author assumes that the stochastic gradient used for solving the problem is unbiased. Under that assumptions, the author proves finite-time bounds. The results seem to be correct but I have serious doubts about novelty.  The assumptions about bias and assumptions on drift term in my opinion make that such a bound are well known in the community. In my opinion, this kind of result can be straightforwardly obtained from Athchade et al 2016 or Rossaco et al 2014. Due to that, I do not believe that the paper meets the standards of NIPS conference.

####UPDATE
After reading the author response and other reviews, I agree that  I underestimate the novelty of the paper. 

limitations_and_societal_impact: The work has no potential negative impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work considers the problem of stochastic gradient descent for time varying optimization. Based on the analysis of SGD in this setting, the problem actually contains two qualitatively different regimes: one with high drift-to-noise ratio, and one with low drift-to-noise ratio. The paper further provides tight convergence analysis (both in expectation and in high probability) for the two regimes.
main_review: The paper gives a new way of looking at time varting optimization. The proof techniques are not new, but the discovery of the two regimes is very interesting and this implication can be useful for real world applications. 

This paper is clearly written and well-organized.
limitations_and_societal_impact: The potential negative societal impact is addressed properly.

I don't have any major problem for this paper. There are only some minor problems (the numbering of the lines is for the supplementary material):

The checklist is unfinished. The authors should do a double-check.

The figures do not show the "95% CI" indicated in the legend.

Line 323, one of the "Theorem 4.2" should be "Theorem 3.2".
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: the paper deals with tracking the minimum of a convex function which is evolving in time according to an unknown stochastic dynamic. The racking problem is classical in signal processing and automatic control (identification of linear or non-linear systems which are changing over time). It is less familiar in ML despite the fact that the problem of concept drift is very important in current practice. 
The paper presents finite-time bound both in expectation and in high-probability for the tracjking of a a proximal stochastic gradient algorithm. The proposed result displays the relations between the learning rate, the excess risk and tracking error. 

The paper uses rather stringent technical assumptions. In particular, the average loss $f_t$ are $\mu$-strongly convex, and the gradient  $\nabla f_{t}$  is  $L$-Lipschitz continuous.  The noise $z_{t}:=\nabla f_{t}\left(x_{t}\right)-g_{t}$ is a martingale increment with uniformly bounded variance.

The paper first provides finite time bounds for $\mathbb{E}\left\|x_{t}-x_{t}^{\star}\right\|^{2}$ under the assumption that $\mathbb{E}\left\|x_{t}^{\star}-x_{t+1}^{\star}\right\|^{2} \leq \Delta^{2}$. The bound in Theorem 3.2. has a transient term, a fluctuation term and a tracking error. The fluctuation term is proportional to the gradient noise variance and the stepsize. The tracking error is inversely proportional to the square of the stepsize.  This result coincides to the classical tracking error for linear system identification (under the considered stochastic model for the parameter).
The authors identify two regimes depending on the ratio  $\Delta / \sigma$.  The high drift-to-noise is not interesting (the stepsize should then be set like in the stationary case), but the low drift-to-noise  necessitates a  learning which is typicallt smaller that $1/2L$. A finite time bound is obtained in Theorem 3.2 (for constant learning rate) and Theorem 3.8 (for a step-decay schedule). In Section 3.3, the authors develop high-probability guarantees under the assumption that the tracking error is (conditionally to the past) sub-exponential and the gradient noise is sub-gaussian. The HP bound (for fixed stepsize) is given in Theorem 3.10. 


main_review: Originality: To my knowledge, this is the first paper that deals with tracking in machine learning. The study of tracking is very classical in system theory, but not in ML. Most of the work in pursuit is devoted to the identification of linear systems. The work on bounds in HP is also new.

Quality:  The paper is well written and the main arguments are easy to follow. The proofs are  adapted from the classical arguments in the stationary case, so there are no really major surprises.  I would have liked a more detailed discussion of the assumptions. The assumption of sub-Gaussianity of the gradient seems to me to be costly. If the $f_t(x)= \mathbb{E}[ (y - \varphi^x)^2]$ where $\varphi \sim N(0,\sigma^2 Id) $ (the "easy" gaussian linear regression), and if $\tilde{\nabla} f_t(x)= \varphi_t ( y_t - \varphi_t x)$ (assuming for simplicty $\{(y_t,\varphi_t)\}$ i.i.d. then this assumption is not satisfied. Even if the regression vector is  bounded, then the assumption is not satisfied (unless $x_t$ is bounded). Therefore the assumption on the noise term seems strong. It would be good to check the assumption whether the condition is satisfied for the $\ell_2^2$-regularized logisitc regression (under which condition on the regressors ?). When reading the example, it is not clear to understand what you mean by "using a noisy gradient $g_t$ satisfying $\left\|g_{t}-\nabla f_{t}\left(x_{t}\right)\right\| \leq \sigma$ for each step  $t$



Significance: This is a essentially theoretical paper, a  first step in analyzing the tracking ability of stochastic gradient algorithms. Of course, this work opens many research directions and questions. It is clear that all the results remain very theoretical, one would like to have algorithms able to adapt to different constants (lipschitz, strong convexity, non-stationarity). The assumptions are very strong (in particular, it is very restrictive to assume a priori that the gradient noise is sub-gaussian, this precludes the use of this result even in very simple examples).
limitations_and_societal_impact: none
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies stochastic optimization under non-stationary drift. Losses are assumed
strongly convex with Lipschitz gradients and unbounded domain. Finite-sample
bounds are derived for the tracking errors
$||x_t - x_t^*||$ and $\ell_t(x_t)-\min_{x^*}\ell_t(x^*)$ of SGD, both in-expectation and with high-probability.

main_review: Overall I thought the paper was excellent. The analysis is useful and interesting, and the writing
was clear and precise throughout. I could
see it becoming a go-to reference for myself, and I can think of several colleagues who would be
equally enthusiastic. 
My questions and concerns are mostly minor, revolving around
adaptive filtering and presentation.

**Adaptive Filtering**
First, I'm generally a bit suspicious about how much the results presented here actually
relate to adaptive filtering, as is claimed. It seems to me that the results relate only
to filtering --- the optimal choice of $\eta$ depends on knowledge of $\Delta$, which would
amount to knowing the variance of the process noise driving the hidden state. Concretely, in the classic
least-squares setting, we'd have $x_{t}^*=F_{t} x_{t-1}^* +u_t$, $y_t = H_t x_t^* + v_t$ , where $u_t\sim\mathcal{N}(0, Q)$ and $v_t\sim N(0, R)$, and
we want to track $x_t^*$ through observations of $y_t$. The results presented here seem to suggest we'd need to
know both $R$ and $Q$ in order to set $\eta=\eta^*$, but given this information there's really nothing adaptive about the problem ---
not knowing these variances is precisely the difficulty of adaptive filtering!
However, I think a lot of the discussion surrounding Adaptive Filtering would be just as effective rephrased in terms
of regular filtering. I would also be curious to see exactly how the iterates chosen when using the optimal fixed $\eta^*$
relate to the steady-state solution of the Kalman filter, which *also* requires knowledge of the noise variances to
set its step-size/gain matrix.

Previous point aside, it seems like the connection to filtering could only hold
in the 1d and/or time-invariant case without additional information? In higher dimensions, even the
squared loss $\frac{1}{2}(y_t - F_tx_t)^2$ will only satisfy the strong-convexity assumption in a rather small subset 
of filtering problems.
In my (quite limited) experience with filtering, it seemed like additional
assumptions on the transition/measurement matrices (e.g. the observability matrix is invertable, etc)
to say much of anything in higher dimensions.

**Presentation**
I am quite irritated with the supplementary materials. Rather than an appendix containing
technical details, the supplementary materials are an extended version of the paper,
also with its own appendix. This feels like a rather dishonest way to get around the
page limit requirements. It was also just generally annoying to navigate, and find what
I was looking for, with some results now being mixed in along side the things I already read
in the main paper, some being in the appendix of the supplementary, no real indication of
where I should look to find something mentioned in the main text. For now I've adopted the
optimistic view that this was a product of time restrictions and a properly structured
appendix is in the works.

The experiments were the weakest part of the paper to me; in my opinion these
could be moved entirely to the appendix to make room for some of the other
results. Further, there's actually a 9 page limit this year, so there's
potentially two full pages that could be used to avoid deferring so many of the results to the appendix.

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: All the reviewers were positive about this paper and felt that it presented a good analysis of less-well-studied problem.

Decision: Accept (Poster)