Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a novel predictor-corrector algorithm for time-varying stochastic optimization. It exploits the continuity of the domain shift. This work demonstrates the superiority of the proposed algorithm over stochastic gradient descent both theoretically and empirically. Further, this works shows that a simple sample average estimation of the predictor-corrector term may lead to non-convergence. In applications shown, a moving average based method is instead applied to estimate the predictor-corrector term. The utility of the proposed method is shown in three concrete real applications. 
strength_and_weaknesses: Strengths:
1. This work focuses on an important and interesting question in ML community.
2. The proposed solution (adding an additional predictor-correct term to the gradient updating rule) is intuitive, general, and easy to implement.
3. Some theoretical insights are given to demonstrate the usefulness of the proposed algorithm, together with some concrete applications.

Weakness:
It seems to me this work does not provide a general way to estimate the predictor-correct term. Instead, only some specific forms for the applications in Section 4 are discussed. For the proposed algorithm to be truly useful, I wonder how easy it is for a practitioner to come-up with an estimation for the term, or what would be the general recommendation for them. Or maybe, another question whether the proposed moving average algorithm can be shown to be useful in for general applications.
clarity,_quality,_novelty_and_reproducibility: This is in general a high quality paper, with clear presentations, and some novel ideas. There are some important questions which this work does not address, though.
summary_of_the_review: I think this paper targets a very important question and provides direction for an intuitive solution. Yet, there are some important parts missing from its current form which somehow prevents it from being more useful and practical.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents a method to incorporate some knowledge about gradual distribution shifts during online gradient descent. The key idea is to add a predictor-corrector term to the gradient (i.e., adding an approximation of the time derivative), which tries to take into account the fact that the expected error changes over time with the current parameters. 

strength_and_weaknesses: The paper is somewhat interesting, and appears to be quite thorough, but relatively unconvincing to me, since it is mostly theoretical, and the only experiments are in toy synthetic tasks/settings. For me this is particularly surprising because so much of the text talks about very practical issues, like distribution shift, and object tracking. In fact the paper is not doing any normal kind of tracking, and instead considers a simple synthetic problem where "sensors" return estimates of the target's "distance", with some zero-mean variance. Maybe this paper will be convincing and helpful to some, but in my case I don't know what to do with it.  Since the paper is out of my domain I certainly won't fight to reject it, but I hope my suggestions on language will be somewhat helpful. 
clarity,_quality,_novelty_and_reproducibility: 
"The rest of the paper is organized as follows" -- and then only sections 2 and 4 are described. What about sections 3 and 5?

let \theta is -> let \theta be

"i.e. they are in general position" -> ? What does it mean for things to be in "general position"?

"it is immediate" -> ? (I don't know what is meant here.)

interchangeably to denote the same thing -> interchangeably

" on target function" -> on the target function

"it’s estimation" -> its estimation

"As statisticians, we query/intervene the model at discrete time steps" -> ? (this sounds like you are saying all statisticians do this) 

"As mentioned in the Introduction, we here compare performance of a time-adjusted gradient descent method to a time-unadjusted one"  -- The introduction did not mention this. The introduction mentioned comparing a predictor-corrector based algorithm versus gradient descent.

"demonstrated their efficacy in three applications" -- I am not sure about this. These are toy experiments in simulated data, not "applications" by my definition of the word.  

summary_of_the_review: This paper may be interesting to some, but given the language on handling distribution shift and offering improvements to object tracking, I expected something more practical, rather than assumptions/lemmas/theorems and toy experiments in simulated data.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of tracking the sequence of best parameters of quadratic functions, where the best parameters changes in a stochastic way. The paper proposes an algorithm called PC and proves its convergence guarantees in terms of ATE. Then, some application problems are introduced, and the PC algorithm is applied. Experimental results show the advantages of PC against the SGD.
strength_and_weaknesses: Strength
- simple update rule with a non-trivial theoretical guarantee
- promising experimental results


Weakness
- some technical issues are not clear (see below)

As summarized above, the claimed technical contributions are non-trivial and solid. However, I have several concerns on technical details, which could affect the evaluations of the theoretical results. 

* The sample complexity or success probability are not discussed. 
The problem setting is stochastic and the goal is to minimize ATE, i.e., the distance between the proposed and true parameters. To minimize this, the statistician has only access to finite samples from the distributions, which causes estimation errors. So, I am strongly wondering how the authors obtain the claimed results while avoiding these sampling/estimation issues. The paper needs some explanation on this matter to justify the results. Or some implicit assumptions exist.

So far, I do not have an intuition that the claimed results are correct. 
clarity,_quality,_novelty_and_reproducibility: The paper is well written in general, and the results seem novel. But I raised the concerns above and some explanation on the matter is desirable.
summary_of_the_review: The theoretical and empirical results seem non-trivial, but I have some concerns about details of theoretical results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of tracking a drifting optimization target under the assumption that the loss function is a smooth function of both the optimization parameter and time. The key insight is to compute the derivative of the minimizer with respect to time by differentiating the loss function with respect to time. Gradient descent is then augmented with an estimate of this derivative in order to more closely track the target.

High level calculations show that with sufficiently good estimates, this method will track the target with a better dependence on the time interval between updates ($h\rightarrow h^2$ where $h$ is the time interval).

In any given example, one then needs to build good estimates of the derivative of the target with respect to time. The authors explore several specific examples in which this can be obtained.

strength_and_weaknesses: The proposed approach makes a lot of sense and is presented clearly and intuitively. I agree with the authors that most approaches to tracking tend to ignore any possible temporal structure in the losses, and exploiting this seems a promising direction.

The requirement for strong convexity seems a bit limiting, however. This seems mostly needed for tracking the parameter vector distance, but one might expect that in many cases we are not interested in $$\|\theta -\theta^\star\|$$ but $$R(\theta)-R(\theta^\star)$$. Do the described techniques have any relevance for this metric?

Moreover, modern analysis of gradient descent methods typically focuses on non-asymptotic convergence bounds. Is there any way to obtain such a bound here? 

The paper could have been augmented with a discussion of lower bounds - is there any way in which the described techniques are optimal?

Finally, the authors may wish to compare with the literature on dynamic regret in online convex optimization, which may provide another alternative to gradient descent which has seen a lot of recent development. Since these techniques also ignore temporal structure in the losses, I would expect this method to still compare favorably.

clarity,_quality,_novelty_and_reproducibility: No concerns
summary_of_the_review: The paper initiates a study of drifting optimization utilizing temporal structure in the loss function. Results are presented that can improve over naive gradient descent, along with experimental validation on certain problems.

The theoretical development seems promising, although perhaps a little more limited than ideal, establishing some cases in which the techniques can improve over SGD in certain cases, but without many general convergence bounds.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This was a borderline paper, and there was a constructive and lively discussion among the reviewers.

Some of the weaknesses of this paper were the absence of non-asymptotic results (all are in the limit of infinitely many steps), and difficulties in estimating the predictor-correct term (even in simple experiments).

However, the reviewer lauded the creativity and novelty of the ideas exposed in the paper - as well as the quality of exposition and motivation.
justification_for_why_not_higher_score: see meta-review above - some weaknesses in this submission.
justification_for_why_not_lower_score: see meta-review above - the ideas were deemed interesting and valuable for the community to be exposed to.
Decision: Accept: poster