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

Question

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?

Answer 1

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.

Answer 2

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.