Sample-Based Approximation of Ridge Functions

Definitions and mathematical statement

The supplied record denotes a class of ridge functions by $R_d^{\alpha,p}$, but does not define this class or specify the admissible values of $d$, $\alpha$, and $p$. In the usual real-variable terminology, a ridge function on a set $D\subseteq{\mathbb{R}}^d$ has the form \[ f(x)=g(\langle a,x\rangle),\qquad x\in D, \] where $a\in{\mathbb{R}}^d$ is a direction vector and $g$ is a univariate function defined on $\{\langle a,x\rangle:x\in D\}$. This terminology is explanatory only: the supplied record does not establish this as the exact definition of $R_d^{\alpha,p}$, nor specify restrictions on $a$, $g$, or $D$.

Source question. What algorithm can exploit the ridge structure of functions in $R_d^{\alpha,p}$ to approximate them efficiently from samples?

Here sample-based approximation means constructing an approximation using sampled function values. The supplied record does not specify the sampling domain, permitted sampling procedures, approximation norm, accuracy criterion, computational cost model, or target dependence on dimension and accuracy. It also does not state whether the direction is known, whether sampling may be adaptive or randomized, or whether guarantees are worst-case or probabilistic. Consequently, the question is retained as an algorithmic research request; a fully quantified performance requirement cannot be recovered from the supplied evidence.

Short English statement

Find an algorithm that uses the ridge structure of functions in $R_d^{\alpha,p}$ to approximate them efficiently from sampled values. The class definition and the meaning of efficiency are missing, so the precise algorithmic guarantee remains unresolved.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json; permanent ID $30002420$, source problem code catalogue entry, title: Sample-Based Approximation of Ridge Functions. No individual proposer is supplied; the proposed year is recorded as 2013.
• Supplied report citation: Uniform Distribution Theory and Applications (2014), Oberwolfach Reports, pp. 2837--2917, DOI 10.4171/owr/2013/49. Source URL and supplied literature source labeled "original OWR report": https://doi.org/10.4171/owr/2013/49. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature assessment, checked on 2026-08-21: the record labels the problem partially solved and states that sampling-number bounds and tractability regimes are established for the stated ridge-function classes, while no general optimal construction answering the request for an effective algorithm was found in the checked literature. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. The record requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that its mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. This verification claim is supplied metadata and has not been independently checked here.