acceptodds
Under review as a conference paper at ICLR 2027

Asymptotic Analysis of Empirical Risk Minimization on Entrywise i.i.d. Heavy-Tailed Data

Abstract

Many real-world datasets exhibit unusually large values far more frequently than predicted by Gaussian models. Heavy-tailed distributions capture this behavior, yet evaluating learning performance under them remains challenging because rare, large feature entries retain non-vanishing effects even in high dimensions. Even in the canonical setting of empirical risk minimization for linear regression with entry-wise i.i.d. symmetric -stable data, a precise asymptotic characterization of prediction has been lacking. In this work, we introduce a functional order parameter that describes the random effective problem associated with each coefficient. Using the replica method, we fully characterize the generalization error in the proportional high-dimensional limit where the sample size and feature dimension diverge at a fixed ratio. Additionally, this analysis establishes a heavy-tail universality law, scaling laws relating typical errors to prediction reliability, and the Bayes-optimal prediction error. In addition to characterizing the effects of extreme entries on the learning process, our method applies broadly to other systems with persistent local heterogeneity.

Primary area:
learning theory
Keywords:
replica method, statistics, heavy tail, high-dimensional statistics

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_S8BoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the asymptotic behavior of regularized empirical risk minimization for linear regression with independent, identically distributed heavy-tailed feature entries. The authors consider the proportional high-dimensional limit, where the sample size NN and feature dimension DD tend to infinity with N/D→κ∈(0,∞)N/D\to\kappa\in(0,\infty). review1 The main contribution is a replica-based derivation of functional fixed-point equations that describe a random one-dimensional optimization problem associated with an individual coefficient. Rather than retaining the entire training dataset, this characterization represents its effect through a random response function whose distribution satisfies the fixed-point equations. The authors use this description to predict the limiting coefficient-error distribution and the resulting test prediction error. review1 I am not sufficiently familiar with the replica method to assess the derivation in detail, so I have not independently verified it. Nevertheless, the close agreement between the theoretical predictions and the simulations provides encouraging empirical support for the proposed characterization in the tested settings. review1 The analysis also offers interesting insights into universality across heavy-tailed feature distributions and the scaling of typical and extreme prediction errors. In addition, the authors characterize a Bayes-optimal benchmark for Gaussian teacher coefficients and Gaussian label noise, and compare independent-entry and elliptical heavy-tailed feature models.

Critical strengths
  • The paper provides a novel asymptotic characterization of empirical risk minimization with independent heavy-tailed features, reducing the problem to a one-dimensional random optimization described by functional fixed-point equations. This extends previous results beyond quadratic losses and elliptical models.
  • The theoretical predictions agree closely with numerical simulations and lead to interesting insights into heavy-tail universality and the different scaling behaviors of typical and extreme prediction errors.
  • The paper also derives an explicit characterization of Bayes-optimal estimation error and establishes an interesting comparison between independent and elliptical heavy-tailed feature models.
Critical weaknesses
  • The results are restricted to data with independent and identically distributed feature entries.

  • A large part of the theoretical framework is presented only in the appendix, including the definitions of the main quantities QQ, ζ\zeta, and RR in Appendix B.3. This makes the paper difficult to follow for readers who are not familiar with this literature. I understand that this is an editorial choice, but I think the main text would benefit from more mathematical details. As it stands, readers may find it difficult to identify the precise mathematical contributions without going through the appendix.

  • Most numerical experiments use Huber loss, ridge regularization, Gaussian teacher coefficients, and Gaussian noise. These experiments provide useful validation, but one of the main contributions of the paper is its ability to handle more general losses and penalties. An additional experiment with a nonsmooth loss or a nonquadratic strongly convex penalty would help demonstrate this broader scope.

Questions for authors

Could you state clearly which conclusions depend on the replica assumptions and which are proved independently of them? In particular, are any additional assumptions needed to identify the functional fixed point with the limiting coefficient distribution? Did you state the existence and uniqueness of the solution somewhere? Which precise result of Montanari and Saeed establishes Proposition 4 under your assumptions? Could you also distinguish universality of the coefficient-error moment from Gaussianity of the test prediction score? Could you include a small experiment with another loss or a nonquadratic strongly convex penalty? This would help demonstrate the scope of the functional characterization beyond the Huber–ridge setting used in the experiments. Could you extend your results to non iid data and more general models?

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

The authors introduce a high-dimensional model of entry wise iid heavy-tailed data in a convex regression setting. Using the replica method, the paper derives predictions for the generalization errors as a function of the sample complexity κ\kappa, proposes a heavy-tail universality result within this setting, derives large- $ \kappa $ scaling laws, and studies Bayes-optimal performance. Most of these new results for $ \alpha<2 $ rely on the replica symmetric prediction, without an independent rigorous validation in any case, for example using random-matrix or other asymptotic tools.

Critical strengths

For me, the main strength of the paper is that the authors address heavy-tailed data. I believe that these settings have been underexplored in the current literature on replica methods for statistical learning, and understanding how entry-wise heavy tails differ from Gaussian and elliptical models could be potentially relevant; nevertheless, I believe that this should have been addressed in a different way.

Critical weaknesses

I am not convinced that the paper establishes sufficient technical novelty in the replica methodology. The authors should be much more explicit about what is technically new, since the main results of the manuscript rely on this construction. In particular, they should clarify the connection with previous functional saddle-point functional order parameters. Appendix A acknowledges that functional order parameters were already developed for heterogeneous systems in statistical physics and related optimization problems, but the discussion still gives me the impression that the manuscript overstates the novelty and potential generality of the framework introduced here. At the moment, I see the methodological contribution as incremental rather than as a fundamentally new replica construction.

Relatedly, the authors do not sufficiently emphasize that the Bayes-optimal results also depend on the replica assumptions used earlier in the paper. I would have appreciated at least one independently established non-Gaussian case that could validate the heuristic replica prediction.

The numerical protocol is also poorly explained in the manuscript. Appendix B states the self-consistent equations, but I cannot find a sufficiently explicit description of which equations are solved numerically, how the functional order parameters are represented or approximated, or how convergence of the numerical procedure is assessed. Similarly, the manuscript does not explain which optimization algorithm is used to obtain the finite-dimensional ERM markers in the figures. In Figure 1, even the regularizer $ \gamma $ is not explicitly stated; from the supplementary code, I infer that ridge regularization, $ \gamma(w)=w^2/2 $, is used. Since Figure 1 is the main empirical validation of a non-rigorous replica calculation, I believe these details should be stated in the manuscript rather than left to the reader to reconstruct from code.

There is also a visible discrepancy around $ \alpha=1.4 $, $ \kappa = 1 $, and $ \lambda=0.01 $ between the theoretical curve and the finite-dimensional ERM result, which is not discussed. More generally, the authors do not show convergence toward the asymptotic prediction as a function of $ D $ in any controlled setting. Such an experiment would be particularly useful here, since it would help distinguish finite-dimensional effects from the replica prediction.

Finally, the paper motivates entry-wise heavy-tailed data through real applications and argues that this structure can be more realistic than an elliptical model in some sensing and measurement systems. However, all experiments in the paper are synthetic. There is no semi-synthetic experiment with real heavy-tailed covariates, nor a concrete application showing that the theory explains an observation seen in practice. This leaves me unsure about the extent to which the paper advances our understanding of machine-learning problems beyond the synthetic model considered here.

Questions for authors

I first list questions that I believe the authors could reasonably address during the rebuttal:

  1. Which steps or constructions in the replica derivation are genuinely new relative to existing functional replica method? I would appreciate a more explicit comparison with the closest prior constructions throughout the derivation, rather than only isolated references in Appendix A. This question is important because I currently see this as the central potential technical contribution of the manuscript.

  2. Could the authors state explicitly which saddle-point equations are solved numerically and how the functional distributions are represented and approximated? How are the finite-dimensional ERM markers obtained? What optimizer, initialization, and convergence criteria are used?

  3. Could the authors comment on the visible discrepancy in Figure 1 around $ \alpha=1.4,\kappa = 1,\lambda=0.01 $? Is this attributed to finite-dimensional effects, numerical approximation of the saddle equations, or something else?

The following questions are more central to my recommendation, but I do not believe they can be adequately addressed during the rebuttal without substantially changing the paper:

  1. Which modeling choices justify the particular entry-wise i.i.d. data model considered here? Is there a real or semi-synthetic setting in which this model captures the observed structure and where the replica prediction explains something that can actually be seen in practice?

  2. Can at least one of the new heuristic replica predictions for $\alpha<2 $ be established independently and rigorously? In particular, the Bayes-optimal quadratic case appears to offer a natural opportunity for validation through heavy-tailed random-matrix/local-resolvent methods.

Overall, I currently lean toward rejection. Answers to the first set of questions would improve my understanding of the paper and could clarify the technical novelty and numerical evidence. However, they would not resolve my main concerns regarding the lack of independent mathematical validation of the replica predictions and the absence of a demonstrated connection to real or semi-synthetic data.

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

The paper considers estimation and prediction in a high-dimensional linear model where the covariates are independent and have a heavy tailed distribution. The paper establishes asymptotic results, characterizing the generalization error, heavy-tail universality law and Bayes-optimal prediction error.

Critical strengths

This is a theoretical paper. The mathematical writing is good. The main paper is readable. The problem studied is an interesting problem. I like the universality result.

Critical weaknesses

The paper only have asymptotic theory results. The assumptions on the model in Sec 3.2 are very strong and not practical. Numerical studies under misspecification of the asymptotic model is needed for any practical utility of the paper. These results will also help us understand the impact & limitations of the theory done in the paper. So, it would complement the current theory. I did not find any justification in the paper of the following statement made in abstract: "In addition to characterizing the effects of extreme entries on the learning process, our method applies broadly to other systems with persistent local heterogeneity."

Questions for authors

When do the asymptotic regimes kick in? Can some simulations be done to show finite sample performance/guarantees? Why does the paper only consider replica methods? How do these methods compare with other robust statistics methods? Can (is it currently being done?) the huber loss be tuned based on the error distribution? I think Figure 1 considers different Huber losses. I got confused if the loss is currently tuned. Some clarification will help. The model (1) assumes independent covariates and the model (2) is a linear additive model. On top of that the error distribution is assumed to have a bounded density. The original coefficients are also considered to be sub-gaussian. These are very strong assumptions which would seldom hold in practice for any application. For a scientific contribution and not just an asymptotic mathematical result, we need to know more about the performance of the method beyond the asymptotic regime considered in the paper. What happens under misspecification? Numerical studies under misspecification as well as discussion on the necessity & limitation of these assumptions are needed. Can the authors discuss if the current results can be extended to non-linear methods?

Comments on the paper

2 comments
Area_Chair_VykmOpenReview ↗

Reminder to engage in the discussion with Authors

Dear Reviewers,

Thank you for your effort in reviewing this submission. The authors’ responses to your comments have been available since November 10. Please take the time to read them and engage in the discussion. In particular, please indicate whether your main concerns have been adequately addressed and raise any remaining questions as soon as possible, so that the authors have an opportunity to reply before the rebuttal period ends on November 18.

Best regards

AC of Submission 20800

Dear Reviewers,

The rebuttal period ends in less than two days. If you have not already done so, I kindly ask you to acknowledge the authors’ responses, and indicate whether your main concerns have been adequately addressed or further clarification is needed.

Thank you.

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.