acceptodds
Under review as a conference paper at ICLR 2027

The Statistical Cost of Finding Smooth Coordinates

Abstract

Being smooth in the right coordinates is not the same as knowing them. We study which frame differences matter for approximation and how unknown coordinates affect function-estimation risk. Our geometric analysis shows that a positive-dimensional frame space can be covered by a single representation neighborhood at coarse resolution. For a fixed two-block matrix-dilation anisotropic Besov profile with rough dimension and inverse-smoothness gap , let . At resolution and a fixed distortion threshold , the representation entropy (log covering number) is zero when and equals when , with constants independent of and . We derive this transition from an exact finite-resolution metric formula; rotation transfer and explicit witnesses connect the metric to approximation and separation in function space. In a separate regression model with standard Gaussian design and independent Gaussian noise of fixed variance, consider with unknown and in the unit -ball, , . We prove matching local entropy bounds and the minimax rate for and , with constants uniform in the ambient dimension. The first term is the known-subspace estimation rate; the second is the representation cost, whose logarithm is unavoidable when that term dominates. Unknown coordinates can therefore be the leading contribution to function-estimation risk as grows.

Primary area:
learning theory
Keywords:
minimax rates, nonparametric regression, representation learning theory, anisotropic Besov spaces, Grassmann manifold

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_AyvYOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the approximation and statistical costs of unknown coordinates. For two-block Besov classes, it derives an exact resolution-dependent metric and characterizes the transition in representation entropy. In a separate Gaussian-design active-subspace model, it establishes matching local entropy bounds and the minimax rate $R_n^\star\asymp n^{-2s/(2s+k)} +\frac{m}{n}\log(1+n/m), \qquad m=k(d-k)=o(n),$ with constants independent of the ambient dimension. Numerical experiments check the geometric formulas and illustrate representation uncertainty in regression.

Critical strengths

The statistical rate distinguishes the known-subspace estimation term from the additional cost associated with an unknown subspace. It also identifies regimes where the latter becomes dominant as the ambient dimension grows, providing useful insight into the limitations of low-dimensional structure.

Critical weaknesses

The motivation for choosing Besov classes could be explained more intuitively. For readers unfamiliar with this framework, the connection between these regularity assumptions and the underlying problem of learning unknown smooth coordinates is difficult to assess.

Questions for authors

Why are Besov classes particularly suitable for studying this problem? Could the authors explain what properties of the target functions these assumptions represent, why they are reasonable, and which aspects of the analysis specifically rely on this choice? A brief comparison with more familiar smoothness assumptions would help clarify the modeling motivation.

3 comments

Thank you. We have expanded the Introduction to explain what the regularity assumption means before using it in the rate.

A familiar starting point. For q=2q=2, the statistical link space B2,2s(Rk)B^s_{2,2}(\mathbb R^k) is the Sobolev space Hs(Rk)H^s(\mathbb R^k), with equivalent norms. For example, when k=s=1k=s=1, the function and its first derivative are square-integrable. The unknown-coordinate question therefore already arises under a standard Sobolev assumption.

Why use the multiscale description? Besov regularity controls how much detail a function can have at successive resolutions: p=2p=2 measures its integrated energy, ss controls fine-scale decay, and qq combines contributions across scales. This is particularly useful here because a small overall signal can still contain a narrow feature that is sensitive to direction. Our localized witnesses make that precise: their width is of order R−1R^{-1} and their Gaussian L2L_2 norm is of order R−sR^{-s}, yet they distinguish subspaces at angular scale R−1R^{-1} (Proposition 4).

The condition s>k/2s>k/2 gives boundedness and Hölder control. Importantly, the threshold depends on the intrinsic dimension kk, rather than the ambient dimension dd. It lets us translate a change in subspace into a change in prediction.

Where does the proof use these properties? Link entropy gives the smoothness-dependent estimation term (Appendix E). Boundedness and Hölder continuity control comparisons across subspaces and support the upper bound (Appendix F). Shrinking witnesses supply the local packing behind the logarithmic representation term (Proposition 4; Appendix G). The separate geometric model uses multiscale comparisons to determine which frame differences become visible at a given accuracy (Theorem 1; Appendix B).

Thus Sobolev gives a familiar special case, Hölder describes the pointwise control we use, and Besov makes the relevant scale structure explicit. Appendix D fixes the norm convention. For fixed admissible parameters, equivalent norm choices affect constants rather than the stated rate exponents; likewise, qq affects constants rather than the displayed exponents.

Thank you for the reply. I will keep my score.

Thank you for taking the time to consider our response. We appreciate your constructive feedback on the motivation and presentation of the regularity assumptions, as well as your continued support for our work.

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

This paper studies the estimation of functions from anisotropic Besov spaces which are oriented in an unknown direction. In my understanding, the main contribution of the paper is to observe that the error in estimating the frame of orientation affects the estimation error by an amount which depends upon the differences in smoothness. This fact is used to obtain statistical estimation bounds.

The key to the argument seems to be to derive metric entropy estimates for the model class. These are then used to obtain statistical estimation bounds.

Critical strengths

Addressing the problem of unknown anisotropic smoothness is an important and interesting question. Some prior work exists such as

Cohen, A., Daubechies, I., DeVore, R., Kerkyacharian, G., & Picard, D. (2012). Capturing ridge functions in high dimensions from point queries. Constructive Approximation, 35(2), 225-243,

but I have not seen the statistical estimation addressed rigorously.

The observation that the frame estimation must be more accurate if the smoothness is more anisotropic is very nice and useful. This is the technical key to the argument.

Critical weaknesses

As far as I can tell, the authors don't give a practically implementable algorithm for performing the estimation. I think that this is a fairly serious issue, and I would like to see this component of the problem addressed.

Questions for authors

In equation (4) and Theorem 4, what exactly is Rn∗R_n^*? I don't see this defined anywhere.

Is there a specific implementable algorithm which obtains the minimax rates that you derive? If I understand correctly, the rates are derived abstractly from bounds on the metric entropy of the class of functions. It would be useful if a specific algorithm can be shown to attain these rates.

3 comments

Thank you. There are two parts to the algorithm question: a rule that attains the statistical rate, and a practical way to learn the directions. We now explain both explicitly.

Which estimator attains the rate? Appendix I gives least squares over a deterministic finite net of candidate prediction functions, fixed before observing the data. The finite-class inequality and entropy bound give the upper-bound order in Theorem 4 (Eqs. (22)–(24)). The remaining difficulty is computational: constructing and searching this net can be prohibitively expensive, and an efficient procedure with the same full-class guarantee remains open. Section 7 puts this in context: Damian et al. (COLT 2024; full version, Example 2.7, Section 3 and Theorem 5.2) give SQ/low-degree gap evidence for detection and direction recovery in related Gaussian single-index models, including a rescaled smooth link in our k=1k=1 class; Theorem 5.2 preserves its generative exponent under Gaussian noise. We cite this as context rather than as a lower bound for our prediction problem.

What can we run in practice? The submission already contained a practical estimator (Appendix J.2, now K.2): SIR/SAVE and random initializations, QR-constrained direction refinement, and kernel ridge fitting. We added a controlled paired evaluation in Section 6 and K.5, in which direction learning uses only the outer training split.

The study has two links, d∈{8,32}d\in\{8,32\}, n∈{512,2048,8192}n\in\{512,2048,8192\}, and ten paired replicates per configuration. Refinement reduces mean noiseless test error relative to initialization alone in all 12 configurations, with every pointwise 95% paired-bootstrap interval excluding zero and 116/120 paired replicates improving (Figure 8). It beats an ambient RBF kernel-ridge baseline in 120/120 replicates (Figure 7). At d=32d=32, its mean gap to the same learner given the true direction falls from about 0.21 at n=512n=512 to below 0.01 at n=8192n=8192 for both unit-variance targets. These results show the practical value of refinement on these targets; the finite-net theorem supplies the separate full-class statistical guarantee.

What is Rn⋆R_n^\star? In the revision, Eq. (2), before the introductory rate, defines

\mathbb E_{\mathcal D_n\sim P_{f^\star}^{\otimes n}} \left[\|\widehat f_{\mathcal D_n}-f^\star\|_{L_2(\gamma_d)}^2\right].$$ The infimum is over measurable estimators that may know $(k,s,q,\sigma,n,d)$, but not the link or subspace. The expectation covers the training design and noise; the loss is prediction against the noiseless regression function at an independent Gaussian input. Finally, on Cohen et al. (2012): they recover ridge functions from adaptive point queries, whereas our rate concerns passive, noisy Gaussian samples (Section 7).

I thank the authors for their response, which addresses the issues that I raised. With a clear definition of Rn∗R_n^* and a practically implementable algorithm, I have decided to raise my score to 4.

Thank you for taking the time to revisit our paper. We’re glad our response addressed your concerns, and we appreciate your support. You mentioned in your follow-up that you intended to raise your rating to 4, but the review still displays 3 on our end. When you have a chance, could you check whether the update was saved?

Reviewer_pKk4OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3(+2)
Read review
Paper summary

The paper presents a technical approximation-theoretic result in terms of the rate estimate in Theorem 4 which shows that, in high dimensions, the term corresponding to the so-called representation cost may dominate. The model for function approximation is a generalized ridgelet-like class of functions which exhibits invariance with respect to basis changes through the action of a subgroup of the orthogonal group. Accordingly, the authors consider a corresponding homogeneous space and the approximation property of a family of representatives for each equivalence class.

Critical strengths

None

Critical weaknesses

The paper has apparently been written by AI, as the authors document. It misses the standards of good paper writing and scientific communication. The introduction summarizes the technical findings without defining some of the important symbols (e.g. HβH_{\beta}). This is contrary to what an introduction should provide: explain the problem, the contribution and the (possible) impact to the field of representation learning in machine learning in a way that is more accessible to the interested and educated human reader, whose is familiar with machine learning but not an expert in a narrow niche of approximation theory.

Questions for authors
  • Can you provide a NON-AI based concise statement about the relevancy and the possible impact of your findings on representation learning in machine learning, for a broader educated human reader?

  • Can you provide a NON-AI based concise statement about the relevancy and the possible impact of your findings on representation learning in machine learning, for a broader educated human reader?

  • Can you provide or point to any concrete scenario in machine learning that might illustrate in a comprehensible way the significance of your contribution?

  • Can you comment on the rationale behind the organization of the paper. Why is a “separate Gaussian-design model”, which is essential for the main result, introduced not earlier than in Section 5?

3 comments

Thank you. We have rewritten the abstract and Introduction to put the learning question first, before the geometric notation.

Why does this matter? Suppose a response depends on a few weighted combinations of many measurements. If someone tells us those combinations, we can fit the response in a low-dimensional space. Without that information, the data must also tell us which combinations are useful. Our question is how much that extra task costs in prediction error. Theorem 4 gives matching upper and lower bounds in the stated regression model. Even when the intrinsic dimension stays fixed, the extra cost can become the main source of error as the ambient dimension grows sufficiently quickly relative to sample size. The lower bound applies to every estimator in this model, including methods that learn features and a predictor from the same sample: none can guarantee a faster worst-case rate over the whole class. Knowing that a low-dimensional representation exists is therefore not the same as being given it.

A concrete example. A simple feature-learning architecture first forms linear features W⊤xW^\top x and then applies a nonlinear predictor gg. Our regression model captures this setting. In a single-index experiment, we compare our learned-direction estimator with the same link learner supplied with the true direction. With 512 labelled observations, the gap in mean noiseless test error is about 3% of the target's variance at d=8d=8 and about 21% at d=32d=32, for both fixed, unit-variance targets (Section 6; K.5, Figure 7). The example illustrates the effect; the theorem establishes it in the worst case.

How do the two parts fit together? Sections 2–4 ask which coordinate differences matter at a chosen approximation accuracy. Section 5 asks how an unknown subspace affects prediction from noisy samples. We study these complementary questions in different function classes, and the revised Introduction explains their connection before the technical development.

The Gaussian model was stated in the submitted abstract and in Section 1 (Eq. (2) of the submitted version, p.2). Still, its role should have been easier to see. The new opening gives the motivation and a simple example, and then the model, the risk and the rate (Eqs. (1)–(3)). We also explain HβH_\beta when it first appears: basis changes within equal-smoothness blocks leave the regularity structure unchanged, and the quotient removes those redundant descriptions.

For the soundness concern, could you point us to the theorem, assumption, or proof step you have in mind? That would help us address it directly. We would also be happy to clarify any specific mathematical concern.

Reviewer_pKk4OpenReview ↗

final assessmnet

Thank you for the detailed response and the revisions. I appreciate the effort to clarify the motivation, improve the organization of the paper and give a concrete learning example. To clarify my soundness assessment, I did not identify a specific mathematical error in the proofs. My main concerns rare retaliated to the presentation, motivation and significance of the contribution for a broader machine learning audience and I will adjust the soundness rating accordingly. While the revisions address some of my concerns, they do not sufficiently change my overall assessment. I therefore maintain my recommendation.

Thank you for the clarification and for updating the soundness assessment. We would like to address the remaining concerns about motivation, significance, and presentation more directly.

1. The motivation is a concrete feature-learning problem.

Suppose a prediction task depends on a few linear combinations of many measurements. If these useful features are given, we only need to learn the response as a function of them. When they are unknown, we must learn to predict without being told which combinations matter. Our model captures a learned linear feature map followed by a nonlinear predictor, and asks how much this additional uncertainty costs in prediction error. This is the motivation now presented at the start of the paper.

2. The result identifies an unavoidable statistical cost of learning the representation.

Theorem 4 gives matching upper and lower bounds on worst-case prediction risk, separating learning within a known subspace from learning with an unknown representation. The additional cost can be the leading source of error even when the intrinsic dimension stays fixed. The lower bound shows that this extra term, including its logarithmic factor, is unavoidable in the regimes where it dominates.

This has a direct implication for representation learning: because the lower bound applies to every estimator in the stated model, it also applies to methods that learn features and a predictor jointly. The existence of a low-dimensional representation alone does not guarantee the rate available when that representation is supplied.

Appendix I provides an explicit estimator attaining the statistical upper-bound order. In a separate geometric model, we also characterize which coordinate differences matter for approximation at a given accuracy. Together, these results quantify the cost of unknown coordinates and explain how their effective complexity depends on the required accuracy.

3. The revised opening addresses the specific presentation issues raised.

The abstract and Introduction now lead with the learning question and a concrete example, introduce the model and prediction risk before the rate, explain HβH_\beta when it first appears, and explain the connection between the geometric and statistical questions. We would appreciate knowing which specific passage or missing explanation in the revised version still makes the problem or contribution difficult to understand.

The other reviews also identify concrete value in these contributions. Reviewer 3XFv described the underlying problem as an “important and interesting question,” while Reviewer AyvY highlighted “useful insight into the limitations of low-dimensional structure.” These assessments concern the learning question and the implications of the results.

Could you clarify whether your remaining concern about significance relates to the novelty of the results, the modeling assumptions, or their implications for representation learning? We would also welcome the other reviewers’ perspectives on the clarity and significance of this learning question. We respectfully ask you to reconsider the overall recommendation in light of these contributions and the revised presentation.

Comments on the paper

1 comment

Overview of the revision. Thank you for the reviews. We have rewritten the abstract and Introduction around the learning problem: what does it cost to learn a useful representation when only a few directions determine the response? The opening now gives an intuitive example, introduces the risk before the rate, and explains how the statistical and geometric questions are related.

One review also raises a concern about mathematical soundness, but does not identify a particular theorem, assumption, or proof step at issue. We have asked for clarification in our reply so that we can address it directly.

The revision also includes a finite-net least-squares construction attaining the statistical upper-bound order (Appendix I), a discussion of computation (Section 7), and a controlled paired evaluation of the practical estimator already in the submission (Section 6; K.5). We have also clarified several proof steps.

Updates to the earlier regression study. Appendix K.7 documents corrections to the earlier study's completed-run coverage, data use, target normalization, and compute and reproducibility reporting. In particular, no scheduled k=3k=3 regression run completed, and historical direction learning reused outer-validation labels later used for hyperparameter selection. The revised reporting makes these limitations explicit, while the new paired protocol confines direction learning to the training split. We also clarify the fixed-target scope of these regressions and remove the attribution of their subspace-recovery scaling to Theorem 4. Full job counts and the corrected timing and seed-accounting details are provided in K.7.

These corrections do not change the theorem statements or rates, or any of the new E1/E2 results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.