# Searching for the underyling affine transformation in a ridge function

Quoting from Wikipedia:

A ridge function is any function $$f:\mathbb{R}^d\rightarrow\mathbb{R}$$ that can be written as the composition of a univariate function with an affine transformation, that is: $$f(\mathbf{x})=g(\mathbf{x}\cdot\mathbf{a})$$ for some $$g:\mathbb{R}\rightarrow\mathbb{R}$$ and $$\mathbf{a}\in \mathbb{R}^d$$.

This has the property that there are $$d-1$$ dimensions in which the ridge function is constant.

This led me to wonder the following questions:

What would be the most efficient algorithm to find $$\hat{\mathbf{a}}=\mathbf{a}/|\mathbf{a}|$$, the sole direction in which $$f$$ is not constant, when you can only query the function $$f$$; and what are the least restrictive conditions on $$g$$ to enable finding $$\hat{\mathbf{a}}$$? (The algorithm is also given a error bound $$\epsilon\in\mathbb{R_{>0}}$$, such that the algorithm is only required to find an $$\hat{\mathbf{a}}_{approx}$$ such that $$|\hat{\mathbf{a}}_{approx} - \hat{\mathbf{a}}|<\epsilon$$.)

I can imagine a gradient ascent on the magnitude of $$h(x)=\partial f(\mathbf{y} + x\hat{\mathbf{x}})/\partial x$$, as you vary $$\hat{\mathbf{x}}\in \mathbb{R}^d$$ (where $$|\hat{\mathbf{x}}|=1$$, $$\mathbf{y}\in \mathbb{R}^d$$ is fixed, and $$x\ll |\mathbf{y}|$$, $$x\in\mathbb{R}$$). In this case, the only requirement on $$g$$, then, is that its derivative is defined at $$\mathbf{y}\cdot\mathbf{a}$$.

But is there a more efficient algorithm, and how do the resources required for that algorithm scale with $$d$$ and error $$\epsilon$$?

(Side note: The problem is equivalent to determining the weights of a single-layer neural network whose single output neuron has a ridge activation function, solely by monitoring the single neuron's output.)

• With no conditions on $g$, it is hopeless. Are there any particular kinds of conditions you are particularly interested in? Your gradient method can't be implemented with the assumptions listed here: you said all we can do is query the function $f$, so we can't compute the gradient and thus can't use that method. Should we assume that we also have the ability to query the gradient $\nabla f$? The problem of finding the neural network is much easier, as in that case $g$ is known and has a "nice" form.
– D.W.
Apr 18 at 2:42
• @D.W. The condition that $g$ is continuous in the neighborhood of a known point is interesting. Doesn't that alone allow us to estimate $\nabla f$ near that point, and therefore perform gradient descent? (As I described in the question?) If I am mistaken, it would be helpful to hear your thoughts answer. Apr 18 at 6:16
• But I agree that the general case is hopeless, because $g$ can just e.g. multiply its input by zero. Hence, I was curious on the least restrictive condition on $g$, if such a thing can be reasoned about broadly. I'm willing to refine my question if it doesn't fall squarely in C.S. StackExchange's scope. Apr 18 at 6:19
• No, continuity is not enough. You can use the $(f(x+\epsilon)-f(x))/\epsilon$ trick to estimate the gradient, but there's no way to know how small to make $\epsilon$; for any fixed $\epsilon$ chosen by the algorithm, an adversary can choose an $f$ that changes more rapidly to make $\epsilon$ much too large. Lipschitz with known Lipschitz constant $K$ might suffice, I don't know.
– D.W.
Apr 18 at 15:35
• @D.W. Good to know. It's perhaps not surprising that the precise answer depends a lot on what we know about $g$! If I wanted to rephrase the question asking for the minimum requirements on $g$ to guarantee gradient ascent, should I ask a separate question or edit this one? Apr 18 at 23:02