Difference between minima of L1-regularized quadratics How can I find
$$F(A,b,x,c)=\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta+x^\top\theta+c||\theta||_1)-\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta-x^\top\theta+c||\theta||_1)?$$
(Note the sign in front of $x^\top\theta$.)
$x, b,\theta$ are vectors; $c>0$ is a scalar; $A$ is a positive definite matrix. $||\theta||_1=\sum_{r=1}^n |\theta_r|$. In order to solve the above one may require to use subdifferential since absolute values are not differentiable. 
An approximation with some guarantee is good enough for me.
Known case
By using Harville, 1997, Matrix Algebra From a Statistician's Perspective  Theorem 19.1.1:
$$F(A,b,x)=\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta+x^\top\theta)-\inf_{\theta\in\mathbb{R}^n}(\theta^{\top}A\theta+b^\top\theta-x^\top\theta)=-b^\top A^{-1}x.$$
Notes
My function is as follows:
$F(\sum_{t=1}^Tx_tx_t^{\top},-2\sum_{t=1}^{T-1}y_tx_t^{\top},2Yx_T^{\top},a)$
where $a>0$, $x,y,Y\in\mathbb{R}^n$. Maybe this coincides with the LASSO problem. I was hoping to get a closed form, which I don't think is possible, perhaps just to show that my problem is exactly like LASSO problem might be good. The issue is LASSO does not has a dual form. Maybe applying Online Gradient Descent Algorithm to this may work. I will work on that.
For the case when we have $a||\theta||_2^2$, we obtain:
$\frac{1}{4Y}{F(aI+\sum_{t=1}^Tx_tx_t^{\top},-2\sum_{t=1}^{T-1}y_tx_t^{\top},2Yx_T^{\top})}$
$=\frac{1}{4Y}F(aI+\sum_{t=1}^Tx_tx_t^{\top},-2\sum_{t=1}^{T-1}y_tx_t^{\top},2Yx_T^{\top})$
$=(\sum_{t=1}^{T-1}y_tx_t^{\top})(aI+\sum_{t=1}^Tx_tx_t^{\top})^{-1} x_T\;\;\;$
Which I guess is the dual form for ridge regression, maybe I can show similarly that my Problem is of LASSO. But for now the problem seems to be of difference of two LASSO.
What If
$F(A,b,x)=\inf_{\theta\in\mathbb{R}^n}(\frac{\theta^{\top}A\theta}{||\theta||_1}+b^\top\theta+x^\top\theta)-\inf_{\theta\in\mathbb{R}^n}(\frac{\theta^{\top}A\theta}{||\theta||_1}+b^\top\theta-x^\top\theta)=?$
 A: This is not a full answer yet, but it makes some progress.
Define$\newcommand\R{\mathbb R}\newcommand{\tp}{^\mathsf{T}}$
$$G(A, d, c) := \inf_{\theta \in \R^n} \theta\tp A \theta + d\tp \theta + c \lVert \theta \rVert_1,$$
so that
$$
F(A, b, x, c) = G(A, b + x, c) - G(A, b - x, c)
.$$
Note that the Lasso problem can be written as
$$
L(X, y, \lambda)
= \inf_{\beta \in \R^n} \tfrac12 \lVert y - X \beta \rVert^2 + \lambda \lVert \beta \rVert_1
= G(\tfrac12 X\tp X, X\tp y, \lambda)
.$$
Suppose that $A$ is full-rank, and define $L$ to be its Cholesky decomposition such that $R\tp R = A$; $R$ will be invertible. Then we can turn $G(A, d, c)$ into $L(X, y, \lambda)$ if:
\begin{gather}
\tfrac12 X\tp X = A \quad\text{i.e. } X = \sqrt{2} R \\
X\tp y = d \quad\text{i.e.} \sqrt{2} R\tp y = d \quad\text{i.e. } y = \frac{1}{\sqrt 2} R^{-\mathsf T} d \\
\lambda = c
.\end{gather}
So, as long as $A$ is full-rank, we have
$$
F(A, b, x, c) = L\left(\sqrt 2 R, \frac{1}{\sqrt 2} R^{-\mathsf T} ( b + x ), \lambda \right) - L\left(\sqrt 2 R, \frac{1}{\sqrt 2} R^{-\mathsf T} ( b - x ), \lambda \right)
.$$
Thus, since $R$ is full-rank, your problem is equivalent to considering
$$
L(X, y, \lambda) - L(X, z, \lambda)
.$$

By setting up the problem
$$
\inf_{\beta \in \R^n, z \in \R^n \text{ s.t. } z = A x} \tfrac12 \lVert y - z \rVert^2 + \lambda \lVert \beta \rVert_1
$$
and using strong duality, we can derive that (see e.g. page 2 of these notes)
\begin{gather}
L(X, y, \lambda) = \sup_{u \in C} \tfrac12 \lVert y \rVert^2 - \lVert y - u \rVert^2, \\ \text{where  }
C = \{ u \in \R^n : \lVert X\tp u \rVert_\infty \le \lambda \}
  = \bigcap_{i=1}^n \{ u : X_i\tp u \le \lambda \} \cap \{ u : X_i\tp u \ge -\lambda \} \tag{*}
\end{gather}
is a polyhedron depending on $X$ and $\lambda$ but (luckily) independent of $y$. Note also that $C = \lambda X^{-\mathsf T} \{ v : \lVert v \rVert_\infty \le 1 \}$, i.e. it is the image of the unit hypercube under the linear map $\lambda X^{-\mathsf T}$ (or the preimage of the unit hypercube under $\frac1\lambda X\tp$).
We can use this form to say that
\begin{align}
L(X, y, \lambda) - L(X, z, \lambda)
&= 
\sup_{u \in C}\left[ \tfrac12 \lVert y \rVert^2 - \lVert y - u \rVert^2 \right]
- \sup_{u \in C}\left[ \tfrac12 \lVert z \rVert^2 - \lVert z - u \rVert^2 \right]
\\&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2 - \inf_{u \in C} \lVert y - u \rVert^2 + \inf_{u \in C} \lVert z - u \rVert^2
\\&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2 - \lVert y - \Pi_C(y) \rVert^2 + \lVert z - \Pi_C(z) \rVert^2
,\end{align}
where $\Pi_C$ denotes projection onto $C$.
Polyhedra are convex, so we know that $\lVert \Pi_C(y) - \Pi_C(z) \rVert \le \lVert y - z \rVert$, but that doesn't quite get us there.
Note from (*) that $\Pi_C(y)$ will end up being the same as the projection of $y$ onto some hyperplane $X_i\tp u = \pm \lambda$, though we don't know which one. But then 
$$
\Pi_C(y) = y + \frac{\pm\lambda - X_i\tp y}{\lVert X_i \rVert^2} X_i
\qquad\text{so}\qquad
\lVert y - \Pi_C(y) \rVert^2 = \frac{(\pm\lambda - X_i\tp y)^2}{\lVert X_i \rVert^2}
.$$
Now, if $y$ and $z$ project onto the same face of $C$ – which is likely if $y$ and $z$ are "close" – then we get
\begin{align}
L(X, y, \lambda) - L(X, z, \lambda)
&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2
- \frac{(X_i\tp y \pm\lambda)^2}{\lVert X_i \rVert^2}
+ \frac{(X_i\tp z \pm\lambda)^2}{\lVert X_i \rVert^2}
\\&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2
- \frac{(X_i\tp y)^2 - (X_i\tp z)^2 \pm 2 \lambda X_i\tp (y - z)}{\lVert X_i \rVert^2}
\\&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2
- \frac{X_i\tp (y-z) \; X_i\tp (y + z)}{\lVert X_i \rVert^2}
\mp 2 \lambda \left( \frac{X_i}{\lVert X_i \rVert^2}\right)\tp (y - z)
\\&= \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2
- \tilde X_i\tp (y-z) \; \tilde X_i\tp (y + z)
\mp 2 \lambda \frac{1}{\lVert X_i \rVert} \tilde X_i \tp (y - z)
\end{align}
where $\tilde X_i = X_i / \lVert X_i \rVert$.
We can at least loosely bound this with Cauchy-Schwarz as
\begin{align}
\left\lvert L(X, y, \lambda) - L(X, z, \lambda) \right\rvert
&\le \left\lvert \tfrac12 \lVert y \rVert^2 - \tfrac12 \lVert z \rVert^2 \right\rvert
+ \lVert y - z \rVert \lVert y + z \rVert
+ \frac{2 \lambda \lVert y - z \rVert}{\min_i \lVert X_i \rVert}
\\&\le
\tfrac32 \lVert y - z \rVert \lVert y + z \rVert
+ \frac{2 \lambda \lVert y - z \rVert}{\min_i \lVert X_i \rVert}
.\end{align}
But remember that this bound only probably holds when $y$ and $z$ are "close," so that they probably hit the same facet – I'm not sure how to quantify that.
The dependence on $\min_i \lVert X_i \rVert$ can probably be improved, since probably constraints like $X_i\tp u \le \lambda$ are more likely to be active when $\lVert X_i \rVert$ is big.
Plugging into your original variables, we have $y - z = \sqrt 2 R^{-\mathsf T} x$, $y + z = \sqrt 2 R^{-\mathsf T} b$, $\min_i \lVert X_i \rVert = \min_i \sqrt{ 2 \sum_j R_{ij}^2 }$. Loosening the bound again we get that "probably", for "small" $x$: 
$$
\left\lvert L(X, y, \lambda) - L(X, z, \lambda) \right\rvert
\le
3 \lVert A^{-1} \rVert_2 \lVert x \rVert \lVert b \rVert
+ \frac{2 \lambda \sqrt{\lVert A^{-1} \rVert_2} \lVert x \rVert}{\min_i \lVert R_{i,\cdot} \rVert}
,$$
where $\lVert \cdot \rVert_2$ is the operator norm (the largest eigenvalue), and probably the row norms of $R$ have some meaning in terms of $A$ but I don't know what.
