acceptodds
Under review as a conference paper at ICLR 2027

Fast Rates for Nonstationary Weighted Risk Minimization

Abstract

Weighted empirical risk minimization is a common approach to prediction under distribution drift. This article studies its out-of-sample prediction error under nonstationarity. We provide a general decomposition of the excess risk into a learning term and an error term associated with distribution drift, and prove oracle inequalities for the learning error under mixing conditions. The learning bound holds uniformly over arbitrary weight classes and accounts for the effective sample size induced by the weight vector, the complexity of the weight and hypothesis classes, and potential data dependence. We also analyze the drift error in the square loss setting and provide explicit bounds for structural-break and smoothly drifting processes. We then combine the learning and drift analysis in (auto-) regression problems with linear models, basis approximations, and neural networks. In all cases, the optimal weights are characterized by a bias–variance trade-off between learning and drift, while minimax-optimal rates (up to logarithmic factors) are recovered when specialized to unweighted and stationary settings.

Primary area:
learning theory
Keywords:
Statistical Learning, Fast Rates, Weighted Risk Minimization, Nonstationarity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_mDWcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  1. The paper provide a general decomposition of the excess risk into a learning term and an error term associated with distribution drift, and prove oracle inequalities for the learning error under mixing conditions.

  2. They analyze the drift error in the square loss setting and provide explicit bounds for structural-break and smoothly drifting processes.

Critical strengths

S1. Clear and meaningful learning–drift decomposition.
The paper decomposes the out-of-sample excess risk of nonstationary weighted ERM into a learning error and a drift error, making the key trade-off in weight selection particularly clear. Spreading the weights increases the effective sample size and reduces estimation error, but may increase the drift error due to the mismatch between historical and current distributions. This decomposition also provides a natural structure for the subsequent theoretical analysis.

S2. Strong uniformity of Theorem 3.2.
The main result is not restricted to a prespecified fixed weight vector, but holds simultaneously over w∈Ww\in\mathcal W, thereby accommodating data-dependent weight selection. Moreover, the hypothesis class Hw\mathcal H_w is allowed to depend on the weights. This is more general than a fixed-weight analysis and better reflects practical settings involving adaptive weighting.

S3. Relatively sharp fast rates for dependent data.
Through weight-dependent localization, the paper uses β\beta-mixing for coupling and ρ\rho-mixing for localized variance control. Under an appropriate local L2L_2-to-L∞L_\infty control condition, the analysis achieves an iid-order leading rate even under polynomial mixing.

Critical weaknesses

W1. The concrete drift analysis in Section 4 has a more limited scope than the general framework may suggest.
The detailed analysis of the drift term in Section 4 primarily focuses on the squared loss and further requires structural assumptions on the evolution of the regression function, density ratios, and related quantities. Therefore, while the title and the general framework suggest broad applicability, the complete learning-plus-drift excess-risk characterization applies to a somewhat narrower setting. The authors also acknowledge in the discussion that more explicit drift analyses require additional assumptions.

W2. The theory allows data-dependent weights, but no concrete data-driven weight-selection procedure is provided.
Although the uniform result accommodates weights selected based on the observed data, the paper does not develop a practical procedure for selecting such weights from data.

W3. The empirical validation is relatively limited.
The experiments mainly consider a scalar location model and serve primarily to illustrate the theoretical phenomena. They therefore provide limited evidence that the proposed framework or its implications lead to practical improvements on realistic nonstationary prediction tasks.

Questions for authors

Q1. Data-driven weight selection.
The uniformity over w∈Ww\in\mathcal W allows the selected weight vector to be data-dependent. However, the optimal learning–drift trade-off involves a drift term that is generally unknown. Is it possible to construct a fully data-driven weight-selection rule, based only on the observed sequence, that provably achieves or approximates the oracle trade-off developed in the paper?

Q2. Applicability of the local L2L_2-to-L∞L_\infty condition.
The iid-order leading rate under polynomial mixing appears to rely critically on the local L2L_2-to-L∞L_\infty control in Assumption A3. Could the authors clarify which commonly used hypothesis classes satisfy the favorable Cw,∞>0C_{w,\infty}>0 condition? Conversely, what rate should one expect when such local control is unavailable?

Q3. Practical relevance of the examples for Assumption A3.
The two examples in Example 3.1 used to illustrate Assumption A3 appear somewhat restrictive relative to hypothesis classes commonly used in practice. In particular: (1) the scalar class seems mainly illustrative and is rarely used as a practical prediction class; (2) for the linear feature class, how restrictive is the required eigenvalue condition in realistic settings, and is it generally straightforward to verify? For example, does the condition continue to hold when Φ\Phi is the feature map associated with a Gaussian kernel? (3) More broadly, can an analogous local L2L_2-to-L∞L_\infty condition be established for neural-network hypothesis classes, and if so, under what assumptions?

2 comments

We thank the reviewer for the positive evaluation and helpful suggestions. We clarified the scope of the drift analysis in the contributions (W1) and agree that our contribution is theoretical (W3). We expanded the explanation of Cw,∞C_{w, \infty} in the applications, added Gaussian features to Example 3.1, and extended the discussion on weight selection (W2). Changes in the manuscript are marked with orange font.

Q1. Data-driven weight selection.

Future-risk guarantees require assumptions relating past and future distributions. Our theorem already controls learning for any admissible data-dependent choice. However, constructing a selector that provably approximates the optimal learning–drift trade-off is a separate challenge, since the drift contribution is generally unobservable.

This question motivated dedicated research even under more restrictive settings. Mazzetto and Upfal (2023) establish adaptive window selection for independent observations, with an algorithm that involves a generally non-computable discrepancy quantity and knowledge of unknowable ground-truth parameters. Huang and Wang (2025) use stability-based comparisons of empirical losses, relying on independent repetitions at every time point and a quasi-stationarity condition. So even in these works solely dedicated to weight selection under independence, the oracle bounds require substantial additional assumptions. Developing such selection guarantees in our dependent setting would similarly require a substantial analysis in a restricted setting, which is beyond the general scope of our paper.

Q2. The role of Cw,∞C_{w, \infty} in the applications.

The favorable case Cw,∞>0C_{w, \infty}>0 in (A3), combined with finite KρK_\rho, enables the sharper polynomial-mixing rates (Section 3.3). Theorem 3.2 also covers Cw,∞=0C_{w, \infty}=0, although its bound can then be slower.

Section 5 and Appendix C.1–C.3 give concrete examples:

  • Linear models: Bounded features and a uniformly positive lower Gram eigenvalue give Cw,∞>0C_{w, \infty}>0. For a fixed feature dimension, this recovers the iid-order parametric rate under the stated polynomial-mixing conditions.

  • Basis expansions: Histogram bases on qq equal bins for uniformly distributed inputs satisfy Cw,∞=q−1/2>0C_{w, \infty}=q^{-1/2}>0. As the basis grows, Cw,∞C_{w, \infty} decreases, so recovering the iid-order rate n−2/3n^{-2/3} up to logarithms requires faster polynomial decay than for fixed-dimensional linear models.

  • ReLU networks: The condition Cw,∞>0C_{w, \infty}>0 does not generally hold for these classes. Our application therefore uses Cw,∞=0C_{w, \infty}=0 and recovers the usual smooth nonparametric rate only under exponential mixing, up to logarithms. For networks with fixed, bounded hidden features and a trainable linear output layer, uniformly positive definite feature Gram matrices give Cw,∞>0C_{w, \infty}>0.

Q3. Feature geometry and Gaussian kernels.

The Gram condition can be checked from assumptions on the input distribution. It is a standard well-conditioning assumption covering many common fixed-dimensional regression models, although it can fail when features become nearly collinear.

For finite Gaussian expansions, take mm fixed distinct centers and Φj(z)=m−1/2e−∥z−cj∥22/(2σ2)\Phi_j(z)=m^{-1/2}e^{-\lVert z-c_j\rVert_2^2/(2\sigma^2)}. The constant is Cw,∞=inf⁡P∈Pλmin⁡(EP[Φ(Z)Φ(Z)⊤])C_{w, \infty}= \inf_{P \in \mathcal P}\sqrt{\lambda_{\min}(\mathbb E_P[\Phi(Z)\Phi(Z)^\top])} and of order m−1/2m^{-1/2} for typical nondegenerate distributions. For the full infinite-dimensional Gaussian RKHS, however, we must take Cw,∞=0C_{w, \infty}=0.

Thank you for your helpful response. I will maintain my positive rating.

Reviewer_FaDrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies weighted ERM under nonstationary and dependent data. The work is primarily theoretical. The authors separate prediction error into learning and drift errors and establish error bounds that applies for arbitrary weight under mixing conditions. They further derive drift bounds for structural-break and smoothly drifting processes and apply the results to linear models, basis expansions, and neural networks.

Critical strengths

In my opinion, the main contribution of this paper is its theoretical insight into ERM under nonstationary and dependent data, beyond iid or stationary settings. The authors show that prediction error can be bounded by two terms, learning error and drift error, and establish theoretical bounds for both terms. These bounds characterize how factors such as the weights affect estimation error and bias caused by distribution changes. Moreover, the bounds applies uniformly over a class of weights.

Critical weaknesses

This paper is primarily theoretical. However, after reading the problem statement and assumptions, I kind of expect what results will be. The results are somehow as expected, and the proofs follow standard routines. It would be useful if the authors could clarify the difficulties beyond these existing routines. Also, the paper defines weighted ERM with the weights as a fixed input and then uses uniform bounds to control the weights. In my view, the weights are typically learned from the data. Therefore, the weights should be data-dependent, with randomness arising from the data. However, the current proof does not account for this. Also, the bounds describe how weights affect the error, but I am not sure how they could guide weight choice, particularly when the weights are learned from the data. Lastly, current results apply to arbitrary weights, but if the weights are designed to account for distribution drift, does the proposed decomposition still apply, for example, in transfer learning or distributionally robust optimization?

Questions for authors

If the weights are explicitly treated as data-dependent and the population risk is instead defined as E[∑tw^tL(Xt,h)]\mathbb{E}[\sum_t \widehat w_t L(X_t,h)], are current results still holds.

Weights are typically chosen using the observed data or prior knowledge. How can the assumptions A3 be verified for these choices?

1 comment

Thank you for the detailed review and the thoughtful questions. We clarified data-dependent weight selection and connections to related research in the discussion. Changes in the manuscript are marked with orange font.

1. Technical novelty and difficulties beyond existing routines.

While our proofs use some ingredients familiar to experts in the field, including coupling, peeling, and concentration, obtaining our results requires nonstandard adjustments to ensure uniformity over weight classes, preserve weight-specific effective-sample-size rates, and achieve sharp rates under slow mixing. The proof idea in Section 3.2 outlines two key adjustments:

  • Weight-dependent localization: The oracle, hypothesis class, excess-risk shells, and normalization all vary with ww. Jointly discretizing weights and their localized classes preserves weight-specific effective-sample-size rates on one event valid for every weight.

  • Sharp dependence control: β\beta-mixing controls coupling, while KρK_\rho controls localized variances. Combining this variance control with the shrinking envelope from (A3) makes the block-length contribution higher order, yielding sharper rates under slow mixing. We detail this mechanism in Section 3.3 and Proposition B.3.

2. How our theory and proof account for data-dependent weights.

Theorem 3.2 holds simultaneously over a weight class W\mathcal W and thus already includes any possibly data-dependent weight w^(X1,…,Xn)∈W\widehat w(X_1,\ldots,X_n)\in\mathcal W. Our proof explicitly allows this due to uniformity over W\mathcal{W} via the weight-dependent localization. This directly covers learned window lengths and smoothing parameters.

3. Alternative risk criterion.

Recall that our goal is to bound the out-of-sample excess risk in eq. (1). In particular, for data-dependent weights, we obtain with high probability:

\lesssim r(\\|\widehat w\\|_2)^2\log^2(1/\delta)+\\|h_{\widehat w}^{\ast}-h_{P_{n+1}}^{\ast}\\|_{L_2(P_{n+1})}^2.$$ The second term (the drift error) depends on the interplay between the weight-selection scheme and the nonstationarity mechanism. Analyzing the criterion $\mathbb E[\sum_{i = 1}^n \widehat w_iL(X_i,h)]$ is not required for this, and it is unclear to us why it would be interesting on its own. **4. How our bounds guide weight selection.** Our bound guides weight choice by making explicit the trade-off between learning error (which decreases with the effective sample size and increases with weight class complexity) and drift error (which favors weights on distributions similar to the target). **5. Clarifying Assumption (A3).** (A3) concerns the geometry of $\mathcal H_w$ and its weight-neighborhood classes, not the selection procedure. For a fixed hypothesis class, learning the weights does not change this condition. Appendix C verifies the assumptions for linear models, basis expansions, and ReLU networks; we clarified the constants $C_{w,\infty}$ in Section 5. **6. Applicability to transfer learning and DRO.** The decomposition applies to drift-adapted weights, including transfer learning when the weighted mixture represents the relevant source distribution and the target comparison satisfies our assumptions. Distributionally robust optimization (DRO) is also covered when its optimizer is a weighted ERM with admissible weights in $\mathcal W$.
Reviewer_YjnuOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the out-of-sample excess risk of weighted empirical risk minimization under nonstationary and dependent observations. The authors decompose the excess risk into a learning error and a drift error, and establish learning error bounds that hold uniformly over a class of weights. By combining localization and refined analysis, the paper obtains improved learning rates, including iid-order rates under polynomial mixing with additional regularity conditions. The authors further analyze the drift error under structural breaks and smooth distribution drift, derive excess-risk bounds for several model classes, and provide numerical simulations illustrating the theoretical results.

Critical strengths
  1. The paper provides a general theoretical framework for analyzing weighted ERM under nonstationarity and temporal dependence. The uniform guarantees over weight classes and the allowance for weight-dependent hypothesis classes are useful features of the analysis.
  2. The refined analysis provides improved learning rates under suitable mixing and regularity conditions. The theoretical results are further developed through a lower-bound construction and applications to linear models, basis expansions, and ReLU networks.
Critical weaknesses

The first inequality in line 277 appears not to follow directly from the stated assumptions. Assumption (A4) controls the learning error under PwP_w, while Assumption (A2) only provides norm comparability for pairs of functions in H\mathcal H. Since hw∗h_w^* is defined as the minimizer over all measurable functions, it need not belong to H\mathcal H. The current statement appears to require further justification or correction.

Questions for authors
  1. Could the authors clarify how the first inequality in line 277 is established? Assumption (A4) gives ∣h^w−hw∗∣L2(Pw)2≤Rw(h^w)−Rw(hw∗),\\|\hat {h}_w-h_w^*\\|_{L^2(P_w)}^2\le R^w(\hat h_w)-R^w(h_w^*), while applying (A2) to transfer this bound to L2(P)L^2(\mathcal P) appears to require hw∗∈Hh_w^*\in\mathcal H, which is not guaranteed by its definition.
  2. The faster rates appear to arise from a more refined theoretical analysis. Could the authors clarify whether these improvements require additional or stronger assumptions compared with existing results? A comparison with prior work under comparable assumptions would help better highlight the novelty of the paper and clarify the range of settings in which the faster rates apply.
2 comments

We thank the reviewer for the positive assessment and careful reading of our paper. Changes in the manuscript are marked with orange font.

Q1. The first inequality in line 277.

You are right that the first inequality does not hold in full generality when hw∗∉Hwh_w^{\ast}\notin\mathcal H_w. We now state the excess-risk and norm bounds separately, for all w∈Ww\in\mathcal W:

\lesssim r(\lVert w \rVert_2)^2\log^2(1/\delta), \qquad \lVert \hat h_w-h_w^{\ast} \rVert_{L_2(\mathcal P)}^2 \lesssim C_{\mathcal P}^2r(\lVert w \rVert_2)^2\log^2(1/\delta).$$ Our proof in Appendix B.1 derives the first inequality. The second then follows by the triangle inequality using an arbitrary in-class approximator $\bar h_w$, applying (A2) only to $\hat h_w-\bar h_w$ and (A4) under $P_w$, then taking the infimum: $$\lVert \hat h_w-h_w^{\ast} \rVert_{L_2(\mathcal P)}^2 \lesssim C_{\mathcal P}^2\left[R^w(\hat h_w)-R^w(h_w^{\ast}) +\inf_{h\in\mathcal H_w}\lVert h-h_w^{\ast} \rVert_\infty^2\right] \lesssim C_{\mathcal P}^2r(\lVert w \rVert_2)^2\log^2(1/\delta).$$ Here condition (3) gives $\inf_{h\in\mathcal H_w}\lVert h-h_w^{\ast}\rVert_\infty^2\le r(\lVert w\rVert_2)^2/(4C_L)$, so the rate remains unchanged up to constants. We adjusted the theorem and its proof accordingly. **Q2. Comparison with prior work.** We achieve iid-order leading rates under polynomial mixing by localizing empirical-risk fluctuations around the weighted oracle. Combining $\rho$-mixing variance control with the local envelope from (A3) makes the coupling-block contribution higher order, which we illustrate in Section 3.3. For comparison, [Hang and Steinwart (2014)](https://doi.org/10.1016/j.jmva.2014.02.012) study regularized ERM under stationary exponential $\alpha$-mixing, while [Farahmand and Szepesvári (2012)](https://www.sciencedirect.com/science/article/abs/pii/S0378375811003181?via%3Dihub) study regularized least squares under exponential $\beta$-mixing. Our results yield the same or better rates under exponential mixing and also allow polynomial mixing. In particular, for the important VC-type regimes $N(\epsilon) \sim \epsilon^{-D}$ that appear in our examples, their bounds include an additional factor $n^{\alpha}$, $\alpha > 0$, due to unnecessary simplifications in their complexity assumptions and analysis. [Deb and Mukherjee (2024)](https://arxiv.org/abs/2401.08978) develop localized bounds for stationary processes under polynomial $\beta/\rho$-mixing; these typically also carry additional polynomial factors in $n$. Our rates generally match those bounds and can be strictly faster when (A3) holds with $C_{w, \infty}>0$. We added this comparison to Section 3.3. However, the broader contribution is the fast oracle inequality that jointly handles nonstationarity, temporal dependence, and weighted risks, uniformly over a generic weight family, allowing the hypothesis class $\mathcal H_w$ to depend on the weights, and explicitly reflects effective sample size. The sharper dependence rate is only one component.

Thank you for the detailed response and revisions. The authors have addressed my concern regarding Theorem 3.2, and the additional discussion helps clarify the technical contributions. I will maintain my original rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.