# Solving regularized least squares problem using black-box computation of $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T\mathbf{x}$

Let $$\mathbf{A} \in \mathbb{R}^{n \times n}$$. I'm working in a problem where I have a black-box algorithmic solution to compute the products $$\mathbf{A}\mathbf{x}$$ and $$\mathbf{A}^T \mathbf{x}$$ given an input $$\mathbf{x} \in \mathbb{R}^n$$. Given that I can't access the value of $$\mathbf{A}$$ directly, what are some examples of algorithms for solving the regularized linear least square problem

\begin{align} \min_{\mathbf{x}} \frac{1}{2} \| \mathbf{y} - \mathbf{A} \mathbf{x}\|^2 + \lambda \phi(\mathbf{x}) \end{align}

that only rely in the computation of $$\mathbf{A}\mathbf{x}$$ and $$\mathbf{A}^T\mathbf{x}$$? Here, $$\lambda >0$$ is a given regularization parameter. I'm more interested in the likelihood $$\frac12 \|\mathbf{y} - \mathbf{A} \mathbf{x}\|^2$$ updates so we can assume pretty much anything we want for $$\phi$$ for the sake of this question. If it makes the problem more concrete, you can assume that $$\phi$$ is convex lower semicontinuous, so that $$\text{prox}_{\lambda\phi}$$ exists and is single valued.

For instance, if $$\phi$$ is differentiable, given a stepsize $$\mu>0$$, the gradient descent update \begin{align} \mathbf{x}^{i+1} &= \mathbf{x^i} - \mu \mathbf{A}^T(\mathbf{A}\mathbf{x^i} - \mathbf{y}) - \mu \lambda \nabla \phi(\mathbf{x^i}) \end{align} can be implemented in my system. What are some other examples?

The conjugate gradient method works quite well on least square problems and is easy to implement. With a simple line search, it should be much better than a simple gradient descent.

There are many other iterative methods to solve linear least-square problems (a starting point). They usually consider $$A$$ a blackbox, but they assume a quadratic regularization. You may be able to apply the same tricks to your problem (presolving mostly), but those are a bit more involved.

• Thank you very much. I'll take a look at it.
– mlbj
Commented Apr 9, 2023 at 13:24

If, say, $$\phi()$$ is convex (so that a global min for the objective exists) but is not smooth, you could use the Nelder-Mead algorithm or one of the variations of it. It requires objective function evaluations only (no gradients). There are some other gradient-free optimization methods as well.

• Thank you very much!
– mlbj
Commented Apr 9, 2023 at 13:21