1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much. I'll take a look at it. $\endgroup$
    – mlbj
    Apr 9, 2023 at 13:24
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – mlbj
    Apr 9, 2023 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.