ii) $(\theta, v) \mapsto G(\theta; v) - G(T(v); v)$ is continuous on $T \times U$.

Proof. (i) Let $v^* \in U$ and $\{v^t, t \ge 0\}$ be a $U$-valued sequence such that $\lim_t v^t = v^*$. Then, by A 3-b, for all, $\theta \in T$

$$G(T(v^t); v^t) \le G(\theta; v^t).$$

By A3-a, $G$ is continuous on $T \times U$ (see Proposition 12) and thus $\lim_t G(\theta; v^t) = G(\theta; v^*)$. The sequence $\{T(v^t), t \ge 0\}$ is a $T$-valued sequence and there exists a subsequence $\{v^{\rho(t)}, t \ge 0\}$ such that $\lim_t T(v^{\rho(t)})$ exists and is in $T$. Note that, as a subsequence of $\{v^t, t \ge 0\}$, we have $\lim_t v^{\rho(t)} = v^*$. Using again that $G$ is continuous, we have for all $\theta \in T$

$$G(\lim_t T(v^{\rho(t)}); v^*) \le G(\theta; v^*).$$

This inequality implies that $\lim_t T(v^{\rho(t)})$ is a minimizer of $\theta \mapsto G(\theta; v^*)$. Since this minimizer is unique by A3-b, we have $\lim_t T(v^{\rho(t)}) = T(v^*)$. This holds true for any subsequence $\{v^{\rho(t)}, t \ge 0\}$ and concludes the proof.

(ii) It follows from the continuity of $T$ and of $G$ (see Proposition 12). $\square$

## 6.2 Proof of Theorem 4

For all $v \in U$, $\text{Argmin}_T G(\cdot; v)$ is not empty by Proposition 12-i and $\text{Argmin}_T F$ is not empty by Proposition 12-ii.

(Item ii) Let $\theta \in \text{Argmin}_T F$. From (7), we have for any $v \in U[\theta]$, $\min_T F = F(\theta) \ge F(\tau)$ for any $\tau \in \text{Argmin}_T G(\cdot; v)$. This yields $\tau \in \text{Argmin}_T F$ and $F(\theta) = F(\tau)$, hence $\theta \in \mathcal{L}$. Let $\theta^* \in \mathcal{L}$, $v \in U[\theta^*]$ and $\tau \in \text{Argmin}_T G(\cdot; v)$. Since $\theta^* \in \mathcal{L}$, we have $F(\tau) = F(\theta^*)$. Combined with (7), this yields $G(\theta^*; v) = G(\tau; v)$. Therefore, $G(\theta^*; v) = \min_T G(\cdot; v)$ and $\theta^* \in \text{Argmin}_T G(\cdot; v)$.

(Item iii) By definition, we have $\mathcal{L} = \{\theta \in T : F(T(v)) = F(\theta) \text{ for all } v \in U[\theta]\}$. From (7), it is easily seen that $\mathcal{L}$ is equal to the first set in (8). Let us prove the second equality in (8). If $T(v) = \theta$, then $F(T(v)) = F(\theta)$, and together with (7), this yields $F(T(v)) = F(\theta) = \min_T G(\cdot; v)$. Conversely, if $F(T(v)) = F(\theta) = \min_T G(\cdot; v)$, then by (7), we have $\theta \in \text{Argmin}_T G(\cdot; v)$ which implies, under the stated assumptions, that $\theta = T(v)$.

## 6.3 Proof of Theorem 5

Since $F$ is continuous and $\mathcal{L} \cap T$ is compact, the set $\mathcal{D} := F(\mathcal{L} \cap T)$ is a compact subset of $\mathbb{R}$. Denote by $\mathcal{D}_\beta$ the $\beta$-neighborhood of the closed set $\mathcal{D}$: $\mathcal{D}_\beta := \{w \in \mathbb{R} : d(w, \mathcal{D}) < \beta\}$; $d$ is the Euclidean distance from a point to a closed set. Since $\mathcal{D}$ is compact, we have

$$\mathcal{D} = \bigcap_{\beta>0} \mathcal{D}_\beta. \qquad (24)$$
Since $G(\theta^{t+1}; v^t) - G(T(v^t); v^t) \ge 0$ by definition of $T(v^t)$, then

$$ \left| G(\theta^{t+1}; v^t) - G(T(v^t); v^t) \right| \le 2 \sup_{(\theta, v) \in \mathbb{T} \times \mathbb{U}} \left| \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(\theta, X^{t+1,i}; v) - G(\theta; v) \right| $$

The proof is concluded by application of Theorem 13 with $u \leftarrow (\theta, v)$, $V \leftarrow \mathbb{T} \times \mathbb{U}$ and $h(u, X) \leftarrow g(\theta, X; v)$. Note indeed that A3-a implies B1-ii and B1-iii; A4 implies B1-iv; and A2-Item b implies B1-v.

### 6.6.2 Proof of Item ii and Item iii.

**Lemma 16.** Let $\mathcal{K}$ be a compact subset of $\mathbb{T}$. The set $V := \{(\theta, v) : \theta \in \mathcal{K}, v \in \mathbb{U}[\theta]\}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$.

*Proof.* $V$ is bounded as a subset of the compact set $\mathbb{T} \times \mathbb{U}$. Let us prove it is closed. Let $\{\theta^t, t \ge 0\}$ be a $\mathcal{K}$-valued sequence converging to $\theta^* \in \mathcal{K}$, and let $\{v^t, t \ge 0\}$ be a sequence converging to $v^* \in \mathbb{U}$ and such that $v^t \in \mathbb{U}[\theta^t]$; we prove that $v^* \in \mathbb{U}[\theta^*]$. Since $\mathbf{F}$ and $\mathbf{G}$ are continuous functions (see A3-c and Proposition 11), we have

$$ \mathbf{F}(\theta^*) = \lim_t \mathbf{F}(\theta^t) = \lim_t \mathbf{G}(\theta^t; v^t) = \mathbf{G}(\theta^*; v^*) $$

thus showing that $v^* \in \mathbb{U}[\theta^*]$. This concludes the proof. $\square$

We apply Theorem 5 with $\mathcal{L} \leftarrow \mathcal{L}^+$.

**Step 1.** We first prove that $\mathcal{L}^+$ is closed. Let $\{\theta^t, t \ge 0\}$ be a $\mathcal{L}^+$-valued sequence, converging to $\theta^*$; let us show that $\theta^* \in \mathcal{L}^+$.

There exists a sequence $\{v^t, t \ge 0\}$ such that $v^t \in \mathbb{U}[\theta^t]$ and $T(v^t) = \theta^t$ for all $t \ge 0$. Since $\{v^t, t \ge 0\}$ is a $\mathbb{U}$-valued sequence, there exists $v^* \in \mathbb{U}$ and a subsequence $\{v^{\rho(t)}, t \ge 0\}$ such that $\lim_t v^{\rho(t)} = v^*$. It holds

$$ \mathbf{F}(\theta^*) = \lim_t \mathbf{F}(\theta^{\rho(t)}) = \lim_t \mathbf{G}(\theta^{\rho(t)}; v^{\rho(t)}) = \mathbf{G}(\lim_t \theta^{\rho(t)}; \lim_t v^{\rho(t)}) = \mathbf{G}(\theta^*; v^*) $$

where we used that $\mathbf{F}$ and $\mathbf{G}$ are continuous on $\mathbb{T}$ and $\mathbb{T} \times \mathbb{U}$ respectively (see A3-c and Proposition 11). In addition,

$$ \theta^* = \lim_t \theta^{\rho(t)} = \lim_t T(v^{\rho(t)}) = T(\lim_t v^{\rho(t)}) = T(v^*), $$

where we used that $\mathbb{T}$ is continuous on $\mathbb{U}$ (see Proposition 12). Hence, there exists $v^* \in \mathbb{U}[\theta^*]$ such that $T(v^*) = \theta^*: \theta^* \in \mathcal{L}^+$.

**Step 2.** By A3-b and A3-c, $\mathbb{T}$ is a point-to-point map and $\mathbf{F}$ is continuous.

**Step 3.** The condition H-i follows from A1 (see (7)).
**Step 1.** Let $\alpha > 0$. Since $\mathcal{D}_\alpha$ is a finite union of disjoint bounded intervals, there exist a positive integer $n_\alpha$ and two increasing real-valued sequences $\{a_\alpha(k), 1 \le k \le n_\alpha\}$ and $\{b_\alpha(k), 1 \le k \le n_\alpha\}$ such that

$$ \mathcal{D}_\alpha = \bigcup_{k=1}^{n_\alpha} (a_\alpha(k), b_\alpha(k)). \qquad (25) $$

**Step 2.** Since $\mathbb{F}$ is continuous and $\mathcal{D}_{\alpha/2}$ is open, $\mathbb{F}^{-1}(\mathcal{D}_{\alpha/2})$ is an open covering of $\mathcal{L} \cap \mathbb{T}$. Define

$$ \epsilon_{\alpha} := \inf_{\theta \in \mathbb{T} \setminus \mathbb{F}^{-1}(\mathcal{D}_{\alpha/2}), \nu \in \mathbb{U}[\theta]} (\mathbb{F}(\theta) - \mathbb{F}(\mathbb{T}(\nu))); \quad \rho_{\alpha} := \epsilon_{\alpha} \wedge \alpha. \qquad (26) $$

Observe that since $\mathbb{T} \setminus \mathbb{F}^{-1}(\mathcal{D}_{\alpha/2})$ is a compact subset of $\mathbb{T} \setminus \mathcal{L}$, then $\epsilon_\alpha > 0$ (and therefore $\rho_\alpha > 0$) by H-ii.

**Step 3.** We write

$$ \mathbb{F}(\theta^t) - \mathbb{F}(\theta^{t+1}) = \mathbb{F}(\theta^t) - \mathbb{F}(\mathbb{T}(\nu^t)) + \mathbb{F}(\mathbb{T}(\nu^t)) - \mathbb{F}(\theta^{t+1}). \qquad (27) $$

By H-iii, there exists $T_\alpha$ such that

$$ \forall t \ge T_\alpha, \quad |\mathbb{F}(\mathbb{T}(\nu^t)) - \mathbb{F}(\theta^{t+1})| \le \rho_\alpha/2. \qquad (28) $$

Hence, if $t \ge T_\alpha$ and $\theta^t \in \mathbb{T} \setminus \mathbb{F}^{-1}(\mathcal{D}_{\alpha/2})$ then (26)-(28) imply that $\mathbb{F}(\theta^t) - \mathbb{F}(\theta^{t+1}) \ge \epsilon_\alpha - \rho_\alpha/2 \ge \rho_\alpha/2$. Consequently, upon noting that $\inf_{\mathbb{T}} \mathbb{F} > -\infty$, the sequence $\{\mathbb{F}(\theta^t), t \ge 0\}$ is infinitely often in $\mathcal{D}_{\alpha/2}$ and therefore in $\mathcal{D}_\alpha$. This implies that the sequence $\{\mathbb{F}(\theta^t), t \ge 0\}$ is infinitely often in an interval of (25): i.e., $I_\alpha := (a_\alpha(k_\star), b_\alpha(k_\star))$, where $k_\star := \max\{k \in [n_\alpha] : \liminf_t \mathbb{F}(\theta^t) > a_\alpha(k)\}$.

**Step 4.** Let $t \ge T_\alpha$, such that $\mathbb{F}(\theta^t) \in I_\alpha$. We prove by induction that for any $s \ge 0$, $\mathbb{F}(\theta^{t+s}) < b_\alpha(k_\star)$. The property holds true for $s = 0$; assume it holds for $s > 0$. Using again (27), we distinguish two cases:

* if $\mathbb{F}(\theta^{t+s}) \in \mathcal{D}_\alpha \setminus \mathcal{D}_{\alpha/2}$, then (26)-(28) imply that $\mathbb{F}(\theta^{t+s}) - \mathbb{F}(\theta^{t+s+1}) \ge \epsilon_\alpha - \rho_\alpha/2 \ge \rho_\alpha/2$. Hence $\mathbb{F}(\theta^{t+s+1}) \le \mathbb{F}(\theta^{t+s}) - \rho_\alpha/2 < b_\alpha(k_\star) - \rho_\alpha/2 < b_\alpha(k_\star)$.

* if $\mathbb{F}(\theta^{t+s}) \in \mathcal{D}_{\alpha/2}$, then (27)-(28) and H-i imply that $\mathbb{F}(\theta^{t+s}) - \mathbb{F}(\theta^{t+s+1}) \ge 0 - \rho_\alpha/2$. Since $\mathbb{F}(\theta^{t+s}) < b_\alpha(k_\star) - \alpha/2$ and $\rho_\alpha \le \alpha$, then $\mathbb{F}(\theta^{t+s+1}) < b_\alpha(k_\star)$.

This concludes the induction.

**Step 5.** We have $\liminf_t \mathbb{F}(\theta^t) > a_\alpha(k_\star)$ and there exists $t$ such that for all $\tau \ge 0$, $\mathbb{F}(\theta^{t+\tau}) < b_\alpha(k_\star)$. Hence, $\mathbb{F}(\theta^t) \in I_\alpha$ for any $t$ large enough; i.e., the set $\mathcal{F}$ of the limiting points of $\{\mathbb{F}(\theta^t), t \ge 0\}$ is not empty and is included in the interval $I_\alpha$.

Let $0 < \alpha_1 < \alpha_2$: $I_{\alpha_1} \subseteq I_{\alpha_2}$ so that for any positive sequence $\{\alpha_n, n \ge 0\}$ decreasing to zero, $\mathcal{F} \subset \bigcap_n I_{\alpha_n}$ and $\bigcap_n I_{\alpha_n}$ is an interval. Note also that $\bigcap_n I_{\alpha_n} \subset \mathbb{F}(\mathcal{L} \cap \mathbb{T})$ by (24). Therefore, the sequence $\{\mathbb{F}(\theta^t), t \ge 0\}$ converges to an interval in $\mathbb{F}(\mathcal{L} \cap \mathbb{T})$; this concludes the proof of the first claim.
**Step 4.** Let $\mathcal{K}$ be a compact subset of $\mathbb{T} \setminus \mathcal{L}^+$ and set $\mathbb{V} := \{(\theta, v) : \theta \in \mathcal{K}, v \in \mathbb{U}[\theta]\}$. By Lemma 16, $\mathbb{V}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$. For $(\theta, v) \in \mathbb{V}$, $F(\theta) - F(\mathbb{T}(v)) > 0$ since $\theta \notin \mathcal{L}^+$ (see (7) and A3-b). In addition, the function $(\theta, v) \mapsto F(\theta) - F(\mathbb{T}(v))$ is continuous on $\mathbb{V}$. Hence, $\inf_{(\theta,v) \in \mathbb{V}} F(\theta) - F(\mathbb{T}(v)) > 0$ and this concludes the proof of H-ii.

**Step 5.** By Proposition 7, H-iii holds as soon as $\lim_t G(\theta^{t+1}; v^t) - G(\mathbb{T}(v^t); v^t) = 0$ and the condition (9) holds. The first limit holds true by Item i. Let us prove (9). Applying Lemma 16 with $\mathcal{K} := \mathbb{T}$ shows that $\{(\theta, v) : \theta \in \mathbb{T}, v \in \mathbb{U}[\theta]\}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$. Therefore, since $\mathbb{T}$ is continuous on $\mathbb{U}$, the set $\mathcal{K}_\delta := \{(\theta, \theta') \in \mathbb{T} \times \mathbb{T}, v \in \mathbb{U}[\theta] : \|\theta' - \mathbb{T}(v)\| \ge \delta\}$ is compact. On $\mathcal{K}_\delta$, A3-b implies that $G(\theta'; v) - G(\mathbb{T}(v); v) > 0$. Since $G$ and $\mathbb{T}$ are continuous, then the condition (9) is verified.

## 6.7 Technical results of Section 5

**Lemma 17.** Let $q \in (0, 1)$. For all $y, u \in \mathbb{R}$, $|\rho_q(y+u) - \rho_q(y)| \le |u|$.

*Proof.* Set $\Delta := \rho_q(y+u) - \rho_q(y)$. Assume that $y+u \ge 0$ and $y \ge 0$. Then $\Delta = q(y+u) - qy = qu$ and $|\Delta| \le |u|$.

Assume that $y+u < 0$ and $y < 0$. Then $\Delta = (q-1)(y+u-y) = (q-1)u$ and $|\Delta| \le |u|$.

Assume that $y+u \ge 0$ and $y < 0$. This implies that $u > 0$ and $y \ge -u$. Then $\Delta = q(y+u) - (q-1)y = y+qu \in [(q-1)u, qu]$, and $|\Delta| \le |u|$.

Assume that $y+u < 0$ and $y \ge 0$. This implies that $u < 0$ and $y < -u$. Then $\Delta = (q-1)(y+u) - qy = -y + (q-1)u \in [qu, (q-1)u]$, and $|\Delta| \le |u|$. $\square$

**Proof of Proposition 10** We write for any $\tau \in \mathbb{R}^\ell$

$$ \langle \theta, \overline{W} \rangle = \langle \tau, \overline{W} \rangle + \frac{1}{\ell} \sum_{j=1}^{\ell} (\ell(\theta_j - \tau_j) \overline{W}_j), $$

and since the function $u \mapsto \rho_q(u)$ is convex, this yields

$$ \rho_q(Y - \langle \theta, \overline{W} \rangle) \le \frac{1}{\ell} \sum_{j=1}^{\ell} \rho_q(Y - \langle \tau, \overline{W} \rangle - (\ell(\theta_j - \tau_j) \overline{W}_j)). $$

Set

$$ f_{\eta}(\theta, X) := \rho_{q}(Y - \langle \theta, \overline{W} \rangle) - \rho_{q}(Y) + \eta \|\theta\|_{1}, $$

We obtain $f_\eta(\theta, \cdot) \le g_\eta(\theta, \cdot; \tau)$ for any $\theta, \tau \in \mathbb{R}^\ell$. When $\tau = \theta$, it is easily checked that $g_\eta(\theta, x; \theta) = f_\eta(\theta, x)$. Since $\rho_q$ is strictly convex, then $\mathbb{U}[\theta] = \{\theta\}$. This concludes the proof of A1. It is easily seen that $|\rho_q(Y+u) - \rho_q(Y)| \le |u|$ (see e.g. Lemma 17) so that

$$ |g_{\eta}(\theta, X; \tau)| \le (2\|\tau\| + \|\theta\|) \|\overline{W}\| + \eta\|\theta\|_{1}. $$
**Step 6.** Let us prove the last statement. If $F(\mathcal{L} \cap \mathbb{T})$ has an empty interior, there exists $F^*$ such that $\lim_t F(\theta^t) = F^*$. Since $\{\theta^t, t \ge 0\}$ is a compact sequence and $F$ is continuous, then $\{\theta^t, t \ge 0\}$ converges to the set $\{\theta \in \mathbb{T} : F(\theta) = F^*\}$.

Let a converging subsequence $\{\theta^{\rho(t)}, t \ge 0\}$, with limiting value $\theta^* \in \mathbb{T}$; such a sequence exists since $\mathbb{T}$ is compact. The proof is by contradiction: assume that $\theta^* \notin \mathcal{L}$. Since $\mathcal{L} \cap \mathbb{T}$ is closed, there exists $\delta > 0$ such that the compact ball $\mathcal{K}_\delta := \{\theta \in \mathbb{T} : \|\theta - \theta^*\| \le \delta\}$ is in $\mathbb{T} \setminus \mathcal{L}$. The assumption H-ii implies that there exists $\epsilon_\delta > 0$ such that for all $\theta \in \mathcal{K}_\delta$ and for all $v \in \mathbb{U}[\theta]$, $F(\theta) > \epsilon_\delta + F(\mathbb{T}(v))$. Since $\lim_t \theta^{\rho(t)} = \theta^*$, there exists $T_\delta$ such for all $t \ge T_\delta$, $\theta^{\rho(t)} \in \mathcal{K}_\delta$. Therefore for all $t \ge T_\delta$, $F(\theta^{\rho(t)}) > \epsilon_\delta + F(\mathbb{T}(v^{\rho(t)}))$ which yields

$$ \lim_t F(\theta^{\rho(t)}) \ge \epsilon_\delta + \lim_t F(\mathbb{T}(v^{\rho(t)})). \qquad (29) $$

On the other hand, the assumption H-iii and the result $\lim_t F(\theta^t) = F^*$ imply that

$$ \lim_t F(\mathbb{T}(v^{\rho(t)})) = \lim_t F(\theta^{\rho(t)+1}), \quad F^* = \lim_t F(\theta^t) = \lim_t F(\theta^{\rho(t)}) = \lim_t F(\theta^{\rho(t)+1}). \quad (30) $$

The results (29) and (30) imply that $F^* \ge \epsilon_\delta + F^*$, which is a contradiction.

## 6.4 Proof of Proposition 7

Let $\epsilon > 0$. Since $F$ is continuous (see A3-c) and $\mathbb{T}$ is compact: there exists $\eta_\epsilon > 0$ such that

$$ \|\tau - \theta'\| \le \eta_\epsilon \implies |F(\tau) - F(\theta')| \le \epsilon/2; $$

and $\sup_{\mathbb{T}} |F| < \infty$. It holds

$$ \begin{aligned} |F(\mathbb{T}(v)) - F(\theta')| &= |F(\mathbb{T}(v)) - F(\theta')| (1_{\|\mathbb{T}(v)-\theta'\| \le \eta_\epsilon} + 1_{\|\mathbb{T}(v)-\theta'\| > \eta_\epsilon}) \\ &\le \frac{\epsilon}{2} + \frac{2}{\eta_\epsilon} \sup_{\mathbb{T}} |F| \|\mathbb{T}(v) - \theta'\|. \end{aligned} $$

Set $\delta_\epsilon := \epsilon\eta_\epsilon/(4\sup_{\mathbb{T}}|F|)$. Then we write by using (9),

$$ \begin{aligned} \|\mathbb{T}(v) - \theta'\| &\le \|\mathbb{T}(v) - \theta'\| 1_{\|\mathbb{T}(v)-\theta'\| < \delta_\epsilon} + \|\mathbb{T}(v) - \theta'\| 1_{\|\mathbb{T}(v)-\theta'\| \ge \delta_\epsilon} \\ &\le \delta_\epsilon + \|\mathbb{T}(v) - \theta'\| 1_{\|\mathbb{T}(v)-\theta'\| \ge \delta_\epsilon} \\ &\le \delta_\epsilon + 2 \operatorname{Diam}(\mathbb{T}) 1_{\mathcal{G}(\theta';v) - \mathcal{G}(\mathbb{T}(v);v) \ge \tilde{\eta}\delta_\epsilon} \\ &\le \delta_\epsilon + \frac{2}{\tilde{\eta}\delta_\epsilon} \operatorname{Diam}(\mathbb{T}) (\mathcal{G}(\theta';v) - \mathcal{G}(\mathbb{T}(v);v)). \end{aligned} $$
Hence, since $\mathbb{T}$ is a compact set, A3-a is satisfied with $p = p_\star$; remember that $\overline{W} := (1, W) \in \mathbb{R}^l$. A3-b holds since $\rho_q$ is strictly convex. Finally, since $u \mapsto \rho_q(u)$ is continuous, the functions $\theta \mapsto f_\eta(\theta, x)$ and $(\theta, \tau) \mapsto g_\eta(\theta, x; \tau)$ are continuous on $\mathbb{T}$ and $\mathbb{T} \times \mathbb{T}$ respectively, for all $x \in \mathbb{R} \times \mathbb{R}^l$. The proof of A3 is concluded by the dominated convergence Theorem.

**The optimization step** Let $q \in (0, 1)$ and $\eta > 0$. The SAM2 update (5) in Algorithm 2, boils down to solving $\ell$ independent optimizations in 1D (see Proposition 10)

$$ \operatorname{argmin}_{u \in \mathbb{R}} \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} \left\{ \rho_q \left( Y^{t+1,i} - \langle \tau, \overline{W}^{t+1,i} \rangle + \ell \overline{W}_j^{t+1,i} \tau_j - \ell \overline{W}_j^{t+1,i} u \right) - \rho_q(Y^{t+1,i}) + \ell \eta |u| \right\}. $$

Using notation $a_{N+1} := 0$, $b_{N+1} := 2\ell\eta N$ and $q_{N+1} = \frac{1}{2}$ to account for the penalty term, the 1D optimizations are all of the form

$$ \arg \min_{u \in \mathbb{R}} g_{N,\eta}(u) \quad \text{with} \quad g_{N,\eta}(u) := \frac{1}{N} \sum_{i=1}^{N+1} \rho_{q_i}(a_i - b_i u); \qquad (25) $$

where for all $i \in [N]$, $q_i = q$ and $(a_i, b_i) \in \mathbb{R}^2$ with $b_i$ assumed different from 0 without loss of generality. For all $i \in [N+1]$, set $\mu_i := a_i/b_i$ with $\mu_{N+1} = 0$ and denote by $\mu_{(i,N+1)}$ the order numbers $\mu_{(1,N+1)} \le \mu_{(2,N+1)} \le \dots \le \mu_{(N+1,N+1)}$. By definition of $\rho_{q_i}$, it holds

$$ \begin{aligned} u \le \mu_i &\implies \rho_{q_i}(a_i - b_i u) = |b_i|(\mu_i - u)(q_i 1_{b_i>0} + (1-q_i)1_{b_i<0}) \\ u \ge \mu_i &\implies \rho_{q_i}(a_i - b_i u) = |b_i|(u - \mu_i)((1-q_i)1_{b_i>0} + q_i 1_{b_i<0}). \end{aligned} $$

This implies that the function $u \mapsto g_{N,\eta}(u)$ tends to $+\infty$ when $|u| \to +\infty$, is continuous on $\mathbb{R}$, and is linear on the intervals $(\mu_{(i,N+1)}, \mu_{(i+1,N+1)})$ for all $i \in [N]$; a minimizer of $u \mapsto g_{N,\eta}(u)$ is $\operatorname{argmin}_{i \in [N+1]} g_{N,\eta}(\mu_i)$. If $\eta = 0$, the same conclusion holds straightforwardly.

# 7 Conclusion

We have proposed a new SAM2 algorithm that extends the applicability of MM algorithms in a stochastic optimization context where the objective majorizers cannot be observed or computed exactly but can be estimated through stochastic simulations. When compared to gradient approaches, MM algorithms are interesting because their progress toward the target does not critically depend on the tuning of hyperparameters such as step-sizes. In a stochastic context, combining MM with sample averaging, SAM2 uses Monte-Carlo approximations of the majorizers constructed from samples of data. The setting of step-sizes is then replaced by successive samples of increasing sizes, whose exact values are not critical as illustrated numerically in our experiments. Another advantage of SAM2 is that no smoothness assumptions are made on the objective and majorizers,
As a conclusion, by the definition of $\delta_\epsilon$, we have

$$|F(T(\nu)) - F(\theta')| \le \epsilon + \frac{4}{\eta_\epsilon \tilde{\eta}_{\delta_\epsilon}} \sup_{\mathbb{T}} |F| \mathrm{Diam}(\mathbb{T}) (G(\theta'; \nu) - G(T(\nu); \nu)).$$

## 6.5 Uniform strong Law of Large Numbers for double arrays

Theorem 14 establishes a uniform strong Law of Large Numbers for double arrays, with the proof following the same lines of argument as that of Andrews (1992, Thm. 3), for example.

**Theorem 14.** Make the following assumptions.

B1. i) $\mathbb{V}$ is a compact subset of $\mathbb{R}^v$ and $(\mathbb{X}, \mathcal{X})$ is a measure space.

ii) $h: \mathbb{V} \times \mathbb{X} \to \mathbb{R}$ is measurable and there exists $p > 1$ such that $\mathbb{E}[\sup_{u \in \mathbb{V}} |h(u, X)|^p] < \infty$, where $X$ is a $\mathbb{X}$-valued random variable defined on $(\Omega, \mathcal{A}, \mathbb{P})$.

iii) For all $x \in \mathbb{X}$, $u \mapsto h(u, x)$ is continuous on $\mathbb{V}$.

iv) The deterministic $\mathbb{Z}_{>0}$-valued sequence $\{N_t, t \ge 1\}$ satisfies $\sum_{t \ge 1} N_t^{-(p-1)\wedge(p/2))} < \infty$.

v) The random variables $\{X^{t,i}, t \ge 1, 1 \le i \le N_t\}$, defined on $(\Omega, \mathcal{A}, \mathbb{P})$, are i.i.d. with the same distribution as $X$.

Then, with probability one,

$$\lim_{t \to \infty} \sup_{u \in \mathbb{V}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - \mathbb{E}[h(u, X)] \right| = 0.$$

Set $H(u) := \mathbb{E}[h(u, X)]$ and observe that under B1-ii and B1-iii, the dominated convergence theorem implies that $H$ is continuous on $\mathbb{V}$.

The proof of Theorem 14 is based on Proposition 15: statement i) establishes a strong Law of Large numbers for a fixed $u \in \mathbb{V}$, and statement ii) establishes a strong Law of Large numbers for the modulus of continuity defined for any $\delta > 0$, by

$$\omega_{\delta}(x) := \sup_{u \in \mathbb{V}, u' \in \mathbb{V}, \|u-u'\| \le \delta} |h(u, x) - h(u', x)|.$$

In the terminology of Davidson (2021, Sec. 22.4), statement i) is referred to as almost sure pointwise convergence of the quantity $N_t^{-1} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u)$ to zero, and statement ii) implies its strong asymptotic uniform stochastic equicontinuity (often shorted to strong stochastic equicontinuity, for brevity), via the Markov's inequality. By Davidson (2021, Thm. 22.8), when $\mathbb{V}$ is compact (and thus totally bounded and separable), taken together, almost sure pointwise convergence and strong stochastic equicontinuity are equivalent to almost sure uniform convergence to zero of
which covers a much larger number of situations than gradient-based approaches. Nevertheless, when compared to gradient update, the sample averaging update links successive estimates only through a warm-start-like relationship that may result in a more variable sequence of estimations. One standard way to reduce this variability is to use Polyak averaging. With our framework, another possibility is to add a Bregman term between two successive estimates. Such addition leads to a minor change in the majorizers definition while penalizing departure from the previous parameter value and producing much smoother sequences. Similarly sparsity constraints though a $L_1$ norm could easily be added without changing the applicability of SAM2. In practice, this could be of great practical interest to handle datasets both large in size and dimension.

## References

Amemiya, T. (1985). *Advanced Econometrics*. Cambridge: Harvard University Press.

Andrews, D. W. K. (1992). Generic uniform convergence. *Econometric Theory*, 8, 241–257.

Atchadé, Y. F., Fort, G., & Moulines, E. (2017). On perturbed proximal gradient algorithms. *Journal of Machine Learning Research*, 18(10), 1–33.

Audet, C. & Hare, W. (2017). Derivative-free and blackbox optimization. Springer Series in Operations Research and Financial Engineering.

Bauschke, H. & Combettes, P. (2011). *Convex Analysis and Monotone Operator Theory in Hilbert Spaces*. CMS Books in Mathematics. Springer New York.

Beck, A. & Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. *Oper. Res. Lett.*, 31(3), 167–175.

Beck, A. & Teboulle, M. (2009). *Gradient-based algorithms with applications to signal-recovery problems*, (pp. 42–88). Cambridge University Press.

Bickel, P. J. & Doksum, K. A. (2015). *Mathematical statistics: basic ideas and selected topics*, volume 1. CRC Press.

Bohning, D. & Lindsay, B. R. (1988). Monotonicity of quadratic-approximation algorithms. *Annals of the Institute of Mathematical Statistics*, 40, 641–663.

Bonnans, J. F. (2019). *Convex and stochastic optimization*. Springer.

Bubeck, S. (2015). Convex optimization: Algorithms and complexity. *Found. Trends Mach. Learn.*, 8(3–4), 231–357.
$N_t^{-1} \sum_{i=1}^{N_t} h(\cdot, X^{t,i}) - H$. Thus, under A6, the conclusions of Theorem 14 and Proposition 15 are almost equivalent.

**Proposition 15.** Assume B1.

i) For any $u \in \mathbb{V}$, there exists $\Omega_u \in \mathcal{A}$ such that $\mathbb{P}(\Omega_u) = 1$ and on $\Omega_u$,

$$ \lim_{t \to \infty} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right| = 0. $$

ii) For any $\delta > 0$, $\mathbb{E}[(\omega_\delta(X))^p] < \infty$ and there exists $\bar{\Omega}_\delta \in \mathcal{A}$ such that $\mathbb{P}(\bar{\Omega}_\delta) = 1$ and on $\bar{\Omega}_\delta$,

$$ \lim_{t \to \infty} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} \omega_\delta(X^{t,i}) - \mathbb{E}[\omega_\delta(X)] \right| = 0. $$

$$ \text{Finally, } \lim_{\delta \to 0} \mathbb{E}[\omega_\delta(X)] = 0. $$

*Proof.* (Item i) Let $u \in \mathbb{V}$. Set $Y^{t,i} := h(u, X^{t,i}) - H(u)$. We prove that for any $\varepsilon > 0$, $\mathbb{P}(\limsup_t A_\varepsilon^t) = 0$ where $A_\varepsilon^t := \{N_t^{-1} \left| \sum_{i=1}^{N_t} Y^{t,i} \right| \ge \varepsilon\}$. This will imply that with probability one, $\lim_{t \to \infty} N_t^{-1} \sum_{i=1}^{N_t} Y^{t,i} = 0$ and conclude the proof.

We write, by using the Markov inequality,

$$ \sum_{t \ge 1} \mathbb{P}(A_{\varepsilon}^{t}) = \sum_{t \ge 1} \mathbb{P} \left( \left| N_t^{-1} \sum_{i=1}^{N_t} Y^{t,i} \right| \ge \varepsilon \right) \le \varepsilon^{-p} \sum_{t \ge 1} N_t^{-p} \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} Y^{t,i} \right|^p \right] $$

where $p > 1$ is given by B1-ii. The random variables $\{Y^{t,i}, t \ge 1, 1 \le i \le N_t\}$ are i.i.d. and centered under B1-ii and B1-v. Hence

$$ \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} Y^{t,i} \right|^p \right] = \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} Y^{\star,i} \right|^p \right], $$

where $\{Y^{\star,i}, i \ge 1\}$ are i.i.d. random variables with the same distribution as $Y^{1,1}$. $n \mapsto \sum_{i=1}^n Y^{\star,i}$ is a martingale sequence with $L^p$-moment (see B1-ii). By Hall & Heyde (1980, Sec. 2.4, Thm. 2.10), there exists a constant $C_p$ such that for any $t \ge 1$,

$$ \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} Y^{\star,i} \right|^p \right] \le C_p \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} |Y^{\star,i}|^2 \right|^{p/2} \right]. $$

From standard calculations (see e.g. Lemma 16), this yields

$$ \mathbb{E} \left[ \left| \sum_{i=1}^{N_t} Y^{\star,i} \right|^p \right] \le C_p N_t^{(p/2)\vee 1} \mathbb{E} \left[ |Y^{\star,1}|^p \right]. $$
Byrd, R. H., Hansen, S. L., Nocedal, J., & Singer, Y. (2016). A stochastic quasi-newton method for large-scale optimization. *SIAM Journal on Optimization*, 26(2), 1008–1031.

Byrne, C. L. (2014). *Iterative optimization in inverse problems*. CRC Press.

Cadoni, S., Chouzenoux, E., Pesquet, J.-C., & Chaux, C. (2016). A block parallel majorize-minimize memory gradient algorithm. In *2016 IEEE International Conference on Image Processing (ICIP) (pp. 3194–3198).: IEEE*.

Cappé, O. & Moulines, E. (2009). On-line expectation-maximization algorithm for latent data models. *Journal of the Royal Statistical Society B*, 71, 593–613.

Celeux, G. & Diebolt, J. (1992). A stochastic approximation type EM algorithm for the mixture problem. *Stochastics and Stochastic Reports*, 41, 119–134.

Chalvidal, M., Chouzenoux, E., Fest, J.-B., & Lefort, C. (2023). Block delayed majorize-minimize subspace algorithm for large scale image restoration. *Inverse Problems*, 39(4), 044002.

Chen, G. & Teboulle, M. (1993). Convergence analysis of a proximal-like minimization algorithm using Bregman functions. *SIAM Journal on Optimization*, 3(3), 538–543.

Chen, X., Liu, W., Mao, X., & Yang, Z. (2020). Distributed high-dimensional regression under a quantile loss function. *Journal of Machine Learning Research*, 21, 1–43.

Chen, X., Liu, W., & Zhang, Y. (2019). Quantile regression under memory constraint. *Annals of Statistics*, 47, 3244–3273.

Chouzenoux, E. & Fest, J.-B. (2022). Sabrina: A stochastic subspace majorization-minimization algorithm. *Journal of Optimization Theory and Applications*, 195(3), 919–952.

Chouzenoux, E. & Pesquet, J.-C. (2016). Convergence rate analysis of the majorize-minimize subspace algorithm. *IEEE Signal Processing Letters*, 23(9), 1284–1288.

Combettes, P. L. & Pesquet, J.-C. (2015). Stochastic quasi-fejér block-coordinate fixed point iterations with random sweeping. *SIAM Journal on Optimization*, 25(2), 1221–1248.

Combettes, P. L. & Wajs, V. R. (2005). Signal recovery by proximal forward-backward splitting. *Multiscale Modeling & Simulation*, 4(4), 1168–1200.

Cui, Y. & Pang, J. (2022). *Modern Nonconvex Nondifferentiable Optimization*. Philadelphia: SIAM.

Dacunha-Castelle, D. & Duflo, M. (1986). *Probability and Statistics: Volume II*. Springer.
Under B1-iv, the Borel–Cantelli lemma implies that $\mathbb{P}(\limsup_t A_\epsilon^t) = 0$.

(Item ii) Let $\delta > 0$. We write $\omega_\delta(x) \le 2 \sup_{u \in \mathbb{V}} |h(u, x)|$, and from B1-ii, we have $\mathbb{E}[(\omega_\delta(X))^p] < \infty$. Set $Y^{t,i} := \omega_\delta(X^{t,i}) - \mathbb{E}[\omega_\delta(X)]$. Following the same line of argument as in the proof of Item i, it can be shown that under B1-ii, B1-iv and B1-v, $\lim_t N_t^{-1} \sum_{i=1}^{N_t} Y^{t,i} = 0$ with probability one (details are omitted).

Let us apply the dominated convergence theorem. Let $x \in \mathbb{X}$. By B1-i and B1-iii, for any $\epsilon > 0$, there exists $\eta_{\epsilon,x} > 0$ such that $\|u-u'\| \le \eta_{\epsilon,x}$ implies $|h(u, x)-h(u', x)| \le \epsilon$. Therefore, for any $\epsilon > 0$, there exists $\eta_{\epsilon,x} > 0$ such that for any $\delta \in [0, \eta_{\epsilon,x}]$, $\omega_\delta(x) \le \epsilon$. This implies that $\lim_{\delta \to 0} \omega_\delta(x) = 0$. In addition, $\omega_\delta(X) \le 2 \sup_{u \in \mathbb{V}} |h(u, X)|$ and the RHS is integrable by B1-ii. Therefore, the assumptions of the dominated convergence Theorem are satisfied and $\lim_{\delta \to 0} \mathbb{E}[\omega_\delta(X)] = 0$. $\square$

**Proof of Theorem 14.** Define $\mathbb{I}_Q := \{1/q, q \in \mathbb{Z}_{>0}\}$. Since $\mathbb{V}$ is compact (see B1-i), for any $\delta \in \mathbb{I}_Q$, there exists a finite covering of $\mathbb{V}$ by closed balls $\{B_{\delta,1}, \dots, B_{\delta,L_\delta}\}$ of radius $\delta$; let us denote by $v_{\delta,1}, \dots, v_{\delta,L_\delta}$ the centers of these balls. Set

$$ \Omega^* := \left( \bigcap_{\delta \in \mathbb{I}_Q, \ell \in \{1, \dots, L_\delta\}} \Omega_{v_{\delta, \ell}} \right) \cap \left( \bigcap_{\delta \in \mathbb{I}_Q} \bar{\Omega}_\delta \right), $$

where $\Omega_\nu$ and $\bar{\Omega}_\delta$ are given respectively by Proposition 15-i and Proposition 15-ii. Since $\Omega^*$ is a countable intersection of sets of probability one, then $\mathbb{P}(\Omega^*) = 1$. We prove that on $\Omega^*$,

$$ \limsup_{t \to \infty} \sup_{u \in \mathbb{V}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right| = 0. $$

Let $\epsilon > 0$. By Item ii, there exists $\delta_\epsilon > 0$ such that $|\mathbb{E}[\omega_{\delta_\epsilon}(X)]| \le \epsilon/6$; without loss of generality we can assume that $\delta_\epsilon \in \mathbb{I}_Q$ and we do so. We write

$$ \sup_{u \in \mathbb{V}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right| \le \sup_{\ell \in \{1, \dots, L_{\delta_\epsilon}\}} \sup_{u \in B_{\delta_\epsilon, \ell}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right|. $$

We now prove that on $\Omega^*$, there exists $T_\epsilon$ such that for all $t \ge T_\epsilon$, each of the $L_{\delta_\epsilon}$ terms on the RHS is upper bounded by $\epsilon$. This will conclude the proof.

Fix $\ell \in [L_{\delta_\epsilon}]$. We write $\sup_{u \in B_{\delta_\epsilon, \ell}} \left| N_t^{-1} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right| \le \sum_{j=1}^2 \mathcal{T}_{j,\epsilon,\ell}(t) + \mathcal{T}_{3,\epsilon,\ell}$ where

$$ \mathcal{T}_{1,\epsilon,\ell}(t) := \sup_{u \in B_{\delta_\epsilon,\ell}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - \frac{1}{N_t} \sum_{i=1}^{N_t} h(u_{\delta_\epsilon,\ell}, X^{t,i}) \right|, $$

$$ \mathcal{T}_{2,\epsilon,\ell}(t) := \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u_{\delta_\epsilon,\ell}, X^{t,i}) - H(u_{\delta_\epsilon,\ell}) \right|, $$

$$ \mathcal{T}_{3,\epsilon,\ell} := \sup_{u \in B_{\delta_\epsilon,\ell}} |H(u_{\delta_\epsilon,\ell}) - H(u)|. $$
Davidson, J. (2021). *Stochastic Limit Theory: An Introduction for Econometricians*. Oxford University Press.

Delyon, B., Lavielle, M., & Moulines, E. (1999). Convergence of a stochastic approximation version of the EM algorithm. *Annals of Statistics*, 27, 94–128.

Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. *Journal of the Royal Statistical Society Series B*, 39, 1–38.

Dieuleveut, A., Fort, G., Moulines, E., & Robin, G. (2021). Federated-em with heterogeneity mitigation and variance reduction. *Advances in Neural Information Processing Systems*, 34, 29553–29566.

D'Orazio, R., Loizou, N., Laradji, I. H., & Mitliagkas, I. (2023). Stochastic mirror descent: Convergence analysis and adaptive variants via the mirror stochastic polyak stepsize. *Transactions on Machine Learning Research*.

Dragomir, R. A., Even, M., & Hendrikx, H. (2021). Fast stochastic Bregman gradient methods: Sharp analysis and variance reduction. In M. Meila & T. Zhang (Eds.), *Proceedings of the 38th International Conference on Machine Learning*, volume 139 of *Proceedings of Machine Learning Research* (pp. 2815–2825).: PMLR.

Fort, G., Gach, P., & Moulines, E. (2021a). Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence. *Statistics and Computing*, 31, 1–24.

Fort, G. & Moulines, E. (2003). Convergence of the Monte Carlo expectation maximization for curved exponential families. *The Annals of Statistics*, 31(4), 1220–1259.

Fort, G. & Moulines, E. (2023). Stochastic variable metric proximal gradient with variance reduction for non-convex composite optimization. *Statistics and Computing*, 33.

Fort, G., Moulines, E., & Wai, H.-T. (2021b). Geom-spider-em: Faster variance reduced stochastic expectation maximization for nonconvex finite-sum optimization. In *ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)* (pp. 3135–3139).: IEEE.

Gourieroux, C. & Monfort, A. (1995). *Statistics And Econometrics Volume 2: Testing, Confidence Regions, Model Selection, And Asymptotic Theory*. Cambridge: Cambridge University Press.

Hall, P. & Heyde, C. (1980). *Martingale Limit Theory and Its Application*. Elsevier Science.

Hong, M., Wang, X., Razaviyayn, M., & Luo, Z.-Q. (2017). Iteration complexity analysis of block coordinate descent methods. *Mathematical Programming*, 163(1), 85–114.
It holds by definitions of $\omega_\delta$ and $\delta_\epsilon$, that

$$ \mathcal{T}_{1,\epsilon,\ell}(t) \le \frac{1}{N_t} \sum_{i=1}^{N_t} \omega_{\delta_\epsilon}(X^{t,i}) \le \frac{\epsilon}{6} + \left| \frac{1}{N_t} \sum_{i=1}^{N_t} \omega_{\delta_\epsilon}(X^{t,i}) - \mathbb{E}[\omega_{\delta_\epsilon}(X)] \right| $$

By Item ii, since $\delta_\epsilon \in \mathbb{I}_Q$, on $\Omega^*$ there exists $T_{1,\epsilon}$ such that for any $t \ge T_{1,\epsilon}$, we have $\mathcal{T}_{1,\epsilon,\ell} \le \epsilon/3$ and by Item i, on $\Omega^*$ there exists $T_{2,\epsilon}$ such that for any $t \ge T_{2,\epsilon}$, $\mathcal{T}_{2,\epsilon,\ell}(t) \le \epsilon/3$. Finally, $\mathcal{T}_{3,\epsilon,\ell} \le \mathbb{E}[\omega_{\delta_\epsilon}(X)] \le \epsilon/6$ by definition of $\delta_\epsilon$. Set $T_\epsilon := T_{1,\epsilon} \lor T_{2,\epsilon}$. On $\Omega^*$, for any $t \ge T_\epsilon$ and for any $\ell \in [L_{\delta_\epsilon}]$,

$$ \sup_{u \in B_{\delta_\epsilon, \ell}} \left| \frac{1}{N_t} \sum_{i=1}^{N_t} h(u, X^{t,i}) - H(u) \right| \le \frac{2\epsilon}{3} + \frac{\epsilon}{6} \le \epsilon. $$

**Lemma 16.** Let $\{Y^i, i \ge 1\}$ be i.i.d. variables such that $\mathbb{E}[|Y^i|^p] < \infty$ for some $p > 1$. Then,

$$ \mathbb{E}\left[\left|\sum_{i=1}^{N}(Y^i)^2\right|^{p/2}\right] \le N^{(p/2)\vee 1} \mathbb{E}[|Y^1|^p]. $$

*Proof.* In the case where $p/2 \le 1$, we write

$$ \mathbb{E}\left[\left|\sum_{i=1}^{N}(Y^i)^2\right|^{p/2}\right] \le \mathbb{E}\left[\sum_{i=1}^{N}|(Y^i)^2|^{p/2}\right] = \mathbb{E}\left[\sum_{i=1}^{N}|Y^i|^p\right] = N \mathbb{E}[|Y^1|^p]. $$

In the case where $p/2 \ge 1$, by the Minkowski inequality, we write

$$ \mathbb{E}\left[\left|\sum_{i=1}^{N}(Y^i)^2\right|^{p/2}\right] = \left(\left\|\sum_{i=1}^{N}(Y^i)^2\right\|_{p/2}\right)^{p/2} \le \left(\sum_{i=1}^{N}\|(Y^i)^2\|_{p/2}\right)^{p/2}. $$

The RHS is equal to

$$ \left(\sum_{i=1}^{N} \mathbb{E}[|Y^i|^p]^{2/p}\right)^{p/2} = \left(\sum_{i=1}^{N} \mathbb{E}[|Y^1|^p]^{2/p}\right)^{p/2} = \left(N \mathbb{E}[|Y^1|^p]^{2/p}\right)^{p/2} = N^{p/2} \mathbb{E}[|Y^1|^p], $$

concluding the proof. $\square$
Hunter, D. R. & Lange, K. (2000). Quantile regression via an MM algorithm. *Journal of Computational and Graphical Statistics*, 9, 60–77.

Hunter, D. R. & Lange, K. (2004). A tutorial on MM algorithms. *The American Statistician*, 58, 30–37.

Ichinose, T., Yukawa, M., & Cavalcante, R. L. G. (2023). Online kernel-based quantile regression using Huberized pinball loss. In *2023 31st European Signal Processing Conference (EUSIPCO)* (pp. 1803–1807).

Jiang, R. & Yu, K. (2022). Renewable quantile regression for streaming data sets. *Neurocomput.*, 508(C), 208–224.

Karimi, B. & Li, P. (2021). Two-timescale stochastic em algorithms. In *2021 IEEE International Symposium on Information Theory (ISIT)* (pp. 890–895).: IEEE.

Karimi, B., Miasojedow, B., Moulines, E., & Wai, H.-T. (2019a). Non-asymptotic analysis of biased stochastic approximation scheme. *Proceedings of Machine Learning Research*, 99, 1–31.

Karimi, B., Wai, H.-T., Moulines, E., & Li, P. (2022). Minimization by incremental stochastic surrogate optimization for large scale nonconvex problems. In *International Conference on Algorithmic Learning Theory* (pp. 606–637).: PMLR.

Karimi, B., Wai, H.-T., Moulines, R., & Lavielle, M. (2019b). On the global convergence of (fast) incremental expectation maximization methods. In *Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS)*.

Khanh Hien, L. T., Phan, D. N., Gillis, N., Ahookhosh, M., & Patrinos, P. (2022). Block Bregman majorization minimization with extrapolation. *SIAM Journal on Mathematics of Data Science*, 4(1), 1–25.

Lai, T. (1989). Extended stochastic liapounov functions and recursive algorithms in linear stochastic systems. In K. H. N. Christopeit & N. Kohlmann (Eds.), *Stochastic Differential Systems: Proceedings of the 4th Bad Honnef Conference, June, 20–24, 1988* (pp. 206–220).: Springer New-York.

Lan, G. (2020). *First-Order and Stochastic Optimization Methods for Machine Learning*. Springer Nature Switzerland AG.

Lan, G., Nemirovski, A., & Shapiro, A. (2012). Validation analysis of mirror descent stochastic approximation method. *Mathematical Programming*, 134, 425–458.

Lange, K. (2013). *Optimization*. New York: Springer.
## 6.6 Proof of Theorem 9

### 6.6.1 Proof of Item i

We write

$$ 
\begin{aligned}
& G(\theta^{t+1}; v^t) - G(T(v^t); v^t) \\
& \leq G(\theta^{t+1}; v^t) - \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(\theta^{t+1}, X^{t+1,i}; v^t) + \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(T(v^t), X^{t+1,i}; v^t) - G(T(v^t); v^t)
\end{aligned}
$$

where we used that, by definition of $\theta^{t+1}$,

$$ \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(\theta^{t+1}, X^{t+1,i}; v^t) - \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(T(v^t), X^{t+1,i}; v^t) \leq 0. $$

Since $G(\theta^{t+1}; v^t) - G(T(v^t); v^t) \geq 0$ by definition of $T(v^t)$, it then holds that

$$ \left| G(\theta^{t+1}; v^t) - G(T(v^t); v^t) \right| \leq 2 \sup_{(\theta, v) \in \mathbb{T} \times \mathbb{U}} \left| \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} g(\theta, X^{t+1,i}; v) - G(\theta; v) \right|. $$

The proof is concluded by application of Theorem 14 with $u \leftarrow (\theta, v)$, $V \leftarrow \mathbb{T} \times \mathbb{U}$ and $h(u, X) \leftarrow g(\theta, X; v)$. Note indeed that A3-a implies B1-ii and B1-iii; A4 implies B1-iv; and A2-Item b implies B1-v.

### 6.6.2 Proof of Item ii and Item iii.

**Lemma 17.** Let $\mathcal{K}$ be a compact subset of $\mathbb{T}$. The set $V := \{(\theta, v) : \theta \in \mathcal{K}, v \in \mathbb{U}[\theta]\}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$.

*Proof.* $V$ is bounded as a subset of the compact set $\mathbb{T} \times \mathbb{U}$. Let us prove it is closed. Let $\{\theta^t, t \geq 0\}$ be a $\mathcal{K}$-valued sequence converging to $\theta^* \in \mathcal{K}$, and let $\{v^t, t \geq 0\}$ be a sequence converging to $v^* \in \mathbb{U}$, such that $v^t \in \mathbb{U}[\theta^t]$; we prove that $v^* \in \mathbb{U}[\theta^*]$. Since $F$ and $G$ are continuous functions (see A3-c and Proposition 12), we have

$$ F(\theta^*) = \lim_{t} F(\theta^t) = \lim_{t} G(\theta^t; v^t) = G(\theta^*; v^*), $$

thus showing that $v^* \in \mathbb{U}[\theta^*]$.

<figure><img src="image_10.png" /></figure>

We apply Theorem 5 with $\mathcal{L} \leftarrow \mathcal{L}^+$.

**Step 1.** We first prove that $\mathcal{L}^+$ is closed. Let $\{\theta^t, t \geq 0\}$ be a $\mathcal{L}^+$-valued sequence, converging to $\theta^*$; let us show that $\theta^* \in \mathcal{L}^+$.

There exists a sequence $\{v^t, t \geq 0\}$ such that $v^t \in \mathbb{U}[\theta^t]$ and $T(v^t) = \theta^t$ for all $t \geq 0$. Since
Lange, K. (2016). *MM Optimization Algorithms*. Philadelphia: SIAM.

Lange, K., Won, J.-H., Landeros, A., & Zhou, H. (2021). *Nonconvex Optimization via MM Algorithms: Convergence Theory*, (pp. 1–22). John Wiley & Sons, Ltd.

Lei, Y. & Zhou, D.-X. (2020). Convergence of online mirror descent. *Applied and Computational Harmonic Analysis*, 48(1), 343–373.

Lin, Z., Li, H., & Fang, C. (2020). Accelerated optimization for machine learning. *Nature Singapore: Springer*.

Lions, P. L. & Mercier, B. (1979). Splitting algorithms for the sum of two nonlinear operators. *SIAM Journal on Numerical Analysis*, 16(6), 964–979.

Liu, A., Lau, V. K., & Kananian, B. (2019). Stochastic successive convex approximation for non-convex constrained stochastic optimization. *IEEE Transactions on Signal Processing*, 67(16), 4189–4203.

Liu, A., Lau, V. K., & Zhao, M.-J. (2018). Online successive convex approximation for two-stage stochastic nonconvex optimization. *IEEE Transactions on Signal Processing*, 66(22), 5941–5955.

Liu, J., Cui, Y., & Pang, J.-S. (2022). Solving nonsmooth and nonconvex compound stochastic programs with applications to risk measure minimization. *Mathematics of Operations Research*, 47(4), 3051–3083.

Liu, J. & Pang, J.-S. (2023). Risk-based robust statistical learning by stochastic difference-of-convex value-function optimization. *Operations Research*, 71(2), 397–414.

Lupu, D. & Necoara, I. (2023). Convergence analysis of stochastic higher-order majorization-minimization algorithms. *Optimization Methods and Software*, (pp. 1–30).

Mairal, J. (2013). Stochastic majorization-minimization algorithm for large-scale optimization. In *Advances in Neural Information Processing Systems* (pp. 2283–2291).

Mairal, J. (2015). Incremental majorization-minimization optimization with application to large-scale machine learning. *SIAM Journal of Optimization*, 25, 829–855.

McLachlan, G. J. & Krishnan, T. (2008). *The EM Algorithm And Extensions*. New York: Wiley.

McLachlan, G. J. & Peel, D. (2000). *Finite Mixture Models*. New York: Wiley.

Meng, X.-L. & Rubin, D. B. (1993). Maximum likelihood estimation via the ECM algorithm: a general framework. *Biometrika*, 80, 267–278.

Meyn, S. (2022). *Control systems and reinforcement learning*. Cambridge University Press.
$\{v^t, t \ge 0\}$ is a $\mathbb{U}$-valued sequence, there exists $v^* \in \mathbb{U}$ and a subsequence $\{v^{\rho(t)}, t \ge 0\}$ such that $\lim_t v^{\rho(t)} = v^*$. It holds that

$$F(\theta^*) = \lim_t F(\theta^{\rho(t)}) = \lim_t G(\theta^{\rho(t)}; v^{\rho(t)}) = G(\lim_t \theta^{\rho(t)}; \lim_t v^{\rho(t)}) = G(\theta^*; v^*),$$

where we used that $F$ and $G$ are continuous on $\mathbb{T}$ and $\mathbb{T} \times \mathbb{U}$, respectively (see A3-c and Proposition 12). In addition,

$$\theta^* = \lim_t \theta^{\rho(t)} = \lim_t \mathbb{T}(v^{\rho(t)}) = \mathbb{T}(\lim_t v^{\rho(t)}) = \mathbb{T}(v^*),$$

where we used that $\mathbb{T}$ is continuous on $\mathbb{U}$ (see Proposition 13). Hence, there exists $v^* \in \mathbb{U}[\theta^*]$ such that $\mathbb{T}(v^*) = \theta^*$; i.e., $\theta^* \in \mathcal{L}^+$.

**Step 2.** By A3-b and A3-c, $\mathbb{T}$ is a point-to-point map and $F$ is continuous.

**Step 3.** The condition H-i follows from A1 (see (7)).

**Step 4.** Let $\mathcal{K}$ be a compact subset of $\mathbb{T} \setminus \mathcal{L}^+$ and set $\mathbb{V} := \{(\theta, v) : \theta \in \mathcal{K}, v \in \mathbb{U}[\theta]\}$. By Lemma 17, $\mathbb{V}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$. For $(\theta, v) \in \mathbb{V}$, $F(\theta) - F(\mathbb{T}(v)) > 0$, since $\theta \notin \mathcal{L}^+$ (see (7) and A3-b). In addition, the function $(\theta, v) \mapsto F(\theta) - F(\mathbb{T}(v))$ is continuous on $\mathbb{V}$. Hence, $\inf_{(\theta,v) \in \mathbb{V}} F(\theta) - F(\mathbb{T}(v)) > 0$ and this concludes the verification of H-ii.

**Step 5.** By Proposition 7, H-iii holds whenever $\lim_t G(\theta^{t+1}; v^t) - G(\mathbb{T}(v^t); v^t) = 0$ and the condition (9) holds. The first limit holds by Item i. Let us prove (9). Applying Lemma 17 with $\mathcal{K} := \mathbb{T}$ shows that $\{(\theta, v) : \theta \in \mathbb{T}, v \in \mathbb{U}[\theta]\}$ is a compact subset of $\mathbb{T} \times \mathbb{U}$. Therefore, since $\mathbb{T}$ is continuous on $\mathbb{U}$, the set $\mathcal{K}_\delta := \{(\theta, \theta') \in \mathbb{T} \times \mathbb{T}, v \in \mathbb{U}[\theta] : \|\theta' - \mathbb{T}(v)\| \ge \delta\}$ is compact. On $\mathcal{K}_\delta$, A 3-b implies that $G(\theta'; v) - G(\mathbb{T}(v); v) > 0$. Since $G$ and $\mathbb{T}$ are continuous, condition (9) is verified.

## 6.7 Technical results of Section 4

**Proof of Lemma 10** Under MD1 and MD2, the function $G$ is continuous on $\mathbb{T} \times \mathbb{U}$; then, the continuity of $\mathbb{T}$ is proved along the same lines as the proof of Proposition 13-item i.

Let $\gamma \in (0, \gamma_*)$ and $\theta \in \mathbb{T}$. Since $\mathbb{T}(\theta, \gamma)$ minimizes the convex function $x \mapsto \langle \gamma \nabla F(\theta), x \rangle + \psi(x) - \psi(\theta) - \langle \nabla \psi(\theta), x - \theta \rangle$ on the convex set $\mathbb{T}$, we have

$$\langle \gamma \nabla F(\theta) - \nabla \psi(\theta) + \nabla \psi(\mathbb{T}(\theta, \gamma)), \theta - \mathbb{T}(\theta, \gamma) \rangle \ge 0. \quad (31)$$
Mokhtari, A. & Koppel, A. (2020). High-dimensional nonconvex stochastic optimization by doubly stochastic successive convex approximation. *IEEE Transactions on Signal Processing*, 68, 6287-6302.

Naderi, S., He, K., Aghajani, R., Sclaroff, S., & Felzenszwalb, P. (2019). Generalized majorization-minimization. In *International Conference on Machine Learning* (pp. 5022–5031).: PMLR.

Nedić, A. & Lee, S. (2014). On stochastic subgradient mirror-descent algorithm with weighted averaging. *SIAM Journal on Optimization*, 24(1), 84–107.

Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. *SIAM Journal on Optimization*, 19(4), 1574–1609.

Nemirovskii, A. & Yudin, D. B. (1983). *Problem complexity and method efficiency in optimization*. Wiley.

Nguyen, H. D., Forbes, F., Fort, G., & Cappé, O. (2022). An online minorization-maximization algorithm. In *Conference of the International Federation of Classification Societies* (pp. 263–271).: Springer.

Nitanda, A. (2014). Stochastic proximal gradient descent with acceleration techniques. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, & K. Weinberger (Eds.), *Advances in Neural Information Processing Systems*, volume 27: Curran Associates, Inc.

Polyak, R. A. (2021). *Introduction to Continuous Optimization*. Springer Cham.

Razaviyayn, M., Hong, M., & Luo, Z.-Q. (2013). A unified convergence analysis of block successive minimization methods for nonsmooth optimization. *SIAM Journal of Optimization*, 23, 1126–1153.

Razaviyayn, M., Sanjabi, M., & Luo, Z. (2016). A stochastic successive minimization method for nonsmooth nonconvex optimization with applications to transceiver design in wireless communication networks. *Mathematical Programming Series B*, (pp. 515–545).

Robbins, H. & Siegmund, D. (1971). A convergence theorem for non negative almost supermartingales and some applications. In J. S. Rustagi (Ed.), *Optimizing Methods in Statistics* (pp. 233–257). Academic Press.

Rosasco, L., Villa, S., & Vü, B. C. (2020). Convergence of stochastic proximal gradient algorithm. *Applied Mathematics & Optimization*, 82.

Rossignol, C., Sureau, F., Chouzenoux, É., Comtat, C., & Pesquet, J.-C. (2022). A bregman majorization-minimization framework for pet image reconstruction. In *2022 IEEE International Conference on Image Processing (ICIP)* (pp. 1736–1740).: IEEE.
Using $F(T(\theta, \gamma)) \le G(T(\theta, \gamma); (\theta, \gamma))$, we write:

$$
\begin{align*}
F(\theta) - F(T(\theta, \gamma)) &\ge F(\theta) - G(T(\theta, \gamma); (\theta, \gamma)) \\
&\ge -\langle \nabla F(\theta), T(\theta, \gamma) - \theta \rangle - \frac{1}{\gamma}\psi(T(\theta, \gamma)) + \frac{1}{\gamma}\psi(\theta) + \frac{1}{\gamma}\langle \nabla\psi(\theta), T(\theta, \gamma) - \theta \rangle \\
&\ge \frac{1}{\gamma}\psi(\theta) - \frac{1}{\gamma}\psi(T(\theta, \gamma)) - \frac{1}{\gamma}\langle \nabla\psi(T(\theta, \gamma)), \theta - T(\theta, \gamma) \rangle,
\end{align*}
$$

where we used Equation (31) in the last inequality. Since $\psi$ is $\mu$-strongly convex, this yields

$$
F(\theta) - F(T(\theta, \gamma)) \geq \frac{1}{\gamma} D_{\psi}(T(\theta, \gamma); \theta) \geq \frac{\mu}{2\gamma} \|T(\theta, \gamma) - \theta\|^2.
$$

**6.8 Technical results of Section 5**

**Lemma 18.** Let $q \in (0, 1)$. For all $y, u \in \mathbb{R}$, $|\rho_q(y+u) - \rho_q(y)| \le |u|$.

Proof. Set $\Delta := \rho_q(y+u) - \rho_q(y)$. Assume that $y+u \ge 0$ and $y \ge 0$. Then $\Delta = q(y+u) - qy = qu$
and $|\Delta| \le |u|$. Assume that $y+u < 0$ and $y < 0$. Then $\Delta = (q-1)(y+u-y) = (q-1)u$
and $|\Delta| \le |u|$. Assume that $y+u \ge 0$ and $y < 0$. This implies that $u > 0$ and $y \ge -u$. Then
$\Delta = q(y+u) - (q-1)y = y+qu \in [(q-1)u, qu]$, and $|\Delta| \le |u|$. Assume that $y+u < 0$ and $y \ge 0$.
This implies that $u < 0$ and $y < -u$. Then $\Delta = (q-1)(y+u) - qy = -y+(q-1)u \in [qu, (q-1)u]$,
and $|\Delta| \le |u|$.
□

**Proof of Proposition 11** Recall that $\overline{W} := (1, W) \in \mathbb{R}^l$. For any $\tau \in \mathbb{R}^l$, we write

$$
\langle \theta, \overline{W} \rangle = \langle \tau, \overline{W} \rangle + \frac{1}{\ell} \sum_{j=1}^{\ell} (\ell(\theta_j - \tau_j) \overline{W}_j),
$$

so that $Y - \langle \theta, \overline{W} \rangle = \frac{1}{\ell} \sum_{j=1}^{\ell} (Y - \langle \tau, \overline{W} \rangle - \ell(\theta_j - \tau_j) \overline{W}_j)$. Since the function $u \mapsto \rho_q(u)$ is convex, this yields

$$
\rho_q \left( Y - \langle \theta, \overline{W} \rangle \right) \le \frac{1}{\ell} \sum_{j=1}^{\ell} \rho_q \left( Y - \langle \tau, \overline{W} \rangle - \ell (\theta_j - \tau_j) \overline{W}_j \right).
$$

Set

$$
f_{\eta}(\theta, X) := \rho_{q}(Y - \langle \theta, \overline{W} \rangle) - \rho_{q}(Y) + \eta \mathrm{pen}(\theta),
$$

where pen $(\theta) := \sum_{j=1}^{\ell} \varphi(|\theta_j|)$. We obtain $f_{\eta}(\theta, \cdot) \le g_{\eta}(\theta, \cdot; \tau)$ for any $\theta, \tau \in \mathbb{R}^{\ell}$. When $\tau = \theta$, it is easily checked that $g_{\eta}(\theta, x; \theta) = f_{\eta}(\theta, x)$, and thus $\theta \in \mathbb{U}[\theta]$, for each $\theta \in \mathbb{T}$. This concludes the
Schraudolph, N. N., Yu, J., & Günter, S. (2007). A stochastic quasi-newton method for online convex optimization. In *Artificial intelligence and statistics* (pp. 436–443).: PMLR.

Serfling, R. J. (1980). *Approximation Theorems Of Mathematical Statistics*. New York: Wiley.

Shalev-Shwartz, S. & Ben-David, S. (2014). *Understanding Machine Learning: From Theory to Algorithms*. Cambridge: Cambridge University Press.

Shapiro, A., Dentcheva, D., & Ruszczynski, A. (2021). *Lectures on Stochastic Programming: Modeling and Theory, Third Edition*. Philadelphia, PA: Society for Industrial and Applied Mathematics.

Vaida, F. (2005). Parameter convergence for EM and MM algorithms. *Statistica Sinica*, 15, 831–840.

van der Vaart, A. & Wellner, J. (2023). *Weak Convergence and Empirical Processes: With Applications to Statistics*. Springer Science & Business Media.

Vapnik, V. N. (1998). *Statistical Learning Theory*. New York: Wiley.

Vidyasagar, M. (2003). *Learning and generalisation: with applications to neural networks*. London: Springer.

Yuille, A. L. & Rangarajan, A. (2003). The concave-convex procedure. *Neural Computation*, 15, 915–936.

Zhang, H., Zhou, P., Yang, Y., & Feng, J. (2019). Generalized majorization-minimization for non-convex optimization. In *IJCAI* (pp. 4257–4263).

Zhang, S. & He, N. (2018). *On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization*. Technical report, arXiv 1806.04781.

Zheng, S. (2011). Gradient descent algorithms for quantile regression with smooth approximation. *International Journal of Machine Learning and Cybernetics*, 2(3), 191–207.

Ziegler, K. (2001). Uniform laws of large numbers for triangular arrays of function-indexed processes under random entropy conditions. *Results in Mathematics*, 39, 374–389.
proof of A1. By Lemma 18 it holds

$$|g_{\eta}(\theta, X; \tau)| \leq (2\|\tau\| + \|\theta\|) \|\overline{W}\| + \eta \text{pen}(\theta).$$

Since $\mathbb{T}$ is a compact set, A3-a is therefore satisfied with $p = p_\star$. A3-b holds since $\rho_q$ is strictly convex. Finally, since $u \mapsto \rho_q(u)$ is continuous, the functions $\theta \mapsto f_\eta(\theta, x)$ and $(\theta, \tau) \mapsto g_\eta(\theta, x; \tau)$ are continuous on $\mathbb{T}$ and $\mathbb{T} \times \mathbb{T}$, respectively, for all $x \in \mathbb{R}^\ell \times \mathbb{R}$. The proof of A3 is concluded by the dominated convergence theorem.

**The optimization step** Let $q \in (0, 1)$ and $\eta \geq 0$. The SAM2 update (5) in Algorithm 2, reduces to solving $\ell$ independent optimization problems in 1D (see Proposition 11):

$$\arg\min_{u \in \mathbb{R}} \frac{1}{N_{t+1}} \sum_{i=1}^{N_{t+1}} \left\{ \rho_q \left( Y^{t+1,i} - \left\langle \tau, \overline{W}^{t+1,i} \right\rangle + \ell \overline{W}_j^{t+1,i} \tau_j - \ell \overline{W}_j^{t+1,i} u \right) - \rho_q(Y^{t+1,i}) + \ell \eta \varphi(|u|) \right\}.$$

Let us observe that the 1D optimization problems can be written in the form

$$\arg\min_{u \in \mathbb{R}} g_{N,\eta}(u), \text{ with } g_{N,\eta}(u) := \frac{1}{N} \sum_{i=1}^{N} \rho_q (a_i - b_i u) + \ell \eta \varphi(|u|),$$

where $(a_i, b_i) \in \mathbb{R}^2$ with $b_i$ different from 0 (without loss of generality), for each $i \in [N]$. For each $i \in [N]$, set $\mu_i = a_i/b_i$ and $\mu_{N+1} = 0$, and denote the $i$th order statistic of $\mu_1, \dots, \mu_{N+1}$ by $\mu_{(i)}$, so that $\mu_{(1)} \le \dots \le \mu_{(N+1)}$ and $0 \in [\mu_{(1)}, \mu_{(N+1)}]$. By definition of $\rho_q$, it holds that

$$u \le \mu_i \implies \rho_q (a_i - b_i u) = |b_i| (\mu_i - u) [q1_{b_i>0} + (1-q) 1_{b_i<0}],$$

and

$$u \ge \mu_i \implies \rho_q (a_i - b_i u) = |b_i| (\mu_i - u) [(1-q) 1_{b_i>0} + q1_{b_i<0}].$$

Furthermore, by the properties of $\varphi$, we have the fact that if $u \le \mu_{(1)} \le 0$ then $\varphi(|u|)$ is concave and strictly decreasing, and if $u \ge \mu_{(N+1)} \ge 0$ then $\varphi(|u|)$ is concave and strictly increasing. These observations imply that $g_{N,\eta}$ is decreasing when $u \le \mu_{(1)}$ and increasing when $u \ge \mu_{(N+1)}$, is continuous, and that $g_{N,\eta}$ is concave on the interval $[\mu_{(i)}, \mu_{(i+1)}]$. Thus the minimizer of $g_{N,\eta}$ can only be realized on the boundary of one of the intervals $[\mu_{(i)}, \mu_{(i+1)}]$. We thus have the closed form

$$\arg\min_{u \in \mathbb{R}} g_{N,\eta}(u) = \arg\min_{i \in [N+1]} g_{N,\eta}(\mu_i),$$

as required.
# 7 Conclusion

We have proposed a new SAM2 algorithm that extends the applicability of MM algorithms in a stochastic optimization context where the objective majorizers cannot be observed or computed exactly but can be estimated through stochastic simulations. When compared to gradient approaches, MM algorithms are interesting because their progress toward the target does not critically depend on the tuning of hyperparameters such as step-sizes. In a stochastic context, combining MM with sample averaging, SAM2 uses Monte-Carlo approximations of the majorizers constructed from samples of data. The setting of step-sizes is then replaced by successive samples of increasing sizes, whose exact values are not critical as illustrated numerically in our experiments. Another advantage of SAM2 is that no smoothness assumptions are made on the objective and majorizers, which covers a much larger number of situations than gradient-based approaches. Nevertheless, when compared to gradient update, the sample averaging update links successive estimates only through a warm-start-like relationship that may result in a more variable sequence of estimations. One standard way to reduce this variability is to use Polyak averaging. With our framework, another possibility is to add a Bregman term between two successive estimates. Such addition leads to a minor change in the majorizers definition while penalizing departure from the previous parameter value and producing much smoother sequences. Similarly sparsity constraints through sparsity-inducing norms can easily be added without changing the applicability of SAM2 that can handle even significantly non-convex penalties. In practice, this could be of great practical interest to handle datasets both large in size and dimension.

# Acknowledgments

All authors acknowledge funding from the Australian Research Council grant DP230100905, and from Inria Project WOMBAT.

# References

* Amemiya, T. (1985). *Advanced Econometrics*. Cambridge: Harvard University Press.

* Andrews, D. W. K. (1992). Generic Uniform Convergence. *Econometric Theory*, 8, 241–257.

* Atchadé, Y. F., Fort, G., & Moulines, E. (2017). On Perturbed Proximal Gradient Algorithms. *Journal of Machine Learning Research*, 18(10), 1–33.

* Audet, C. & Hare, W. (2017). Derivative-Free and Blackbox Optimization. *Springer Series in Operations Research and Financial Engineering*.
Azizan, N. & Hassibi, B. (2019). Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization. In *International Conference on Learning Representations*.

Bauschke, H. & Combettes, P. (2011). *Convex Analysis and Monotone Operator Theory in Hilbert Spaces*. CMS Books in Mathematics. Springer New York.

Beck, A. & Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. *Oper. Res. Lett.*, 31(3), 167–175.

Beck, A. & Teboulle, M. (2009). *Gradient-based algorithms with applications to signal-recovery problems*, (pp. 42–88). Cambridge University Press.

Bickel, P. J. & Doksum, K. A. (2015). *Mathematical Statistics: Basic Ideas and Selected Topics*, volume 1. CRC Press.

Bohning, D. & Lindsay, B. R. (1988). Monotonicity of quadratic-approximation algorithms. *Annals of the Institute of Mathematical Statistics*, 40, 641–663.

Bonnans, J. F. (2019). *Convex and Stochastic Optimization*. Springer.

Bubeck, S. (2015). Convex Optimization: Algorithms and Complexity. *Found. Trends Mach. Learn.*, 8(3–4), 231–357.

Byrd, R. H., Hansen, S. L., Nocedal, J., & Singer, Y. (2016). A Stochastic Quasi-Newton Method for Large-Scale Optimization. *SIAM Journal on Optimization*, 26(2), 1008–1031.

Byrne, C. L. (2014). *Iterative Optimization in Inverse Problems*. CRC Press.

Cadoni, S., Chouzenoux, E., Pesquet, J.-C., & Chaux, C. (2016). A block parallel majorize-minimize memory gradient algorithm. In *2016 IEEE International Conference on Image Processing (ICIP) (pp. 3194–3198)*.: IEEE.

Cappé, O. & Moulines, E. (2009). On-line expectation-maximization algorithm for latent data models. *Journal of the Royal Statistical Society B*, 71, 593–613.

Celeux, G. & Diebolt, J. (1992). A stochastic approximation type EM algorithm for the mixture problem. *Stochastics and Stochastic Reports*, 41, 119–134.

Chalvidal, M., Chouzenoux, E., Fest, J.-B., & Lefort, C. (2023). Block delayed Majorize-Minimize subspace algorithm for large scale image restoration. *Inverse Problems*, 39(4), 044002.

Chen, G. & Teboulle, M. (1993). Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions. *SIAM Journal on Optimization*, 3(3), 538–543.
Chen, X., Liu, W., Mao, X., & Yang, Z. (2020). Distributed High-dimensional Regression Under a Quantile Loss Function. *Journal of Machine Learning Research*, 21, 1–43.

Chen, X., Liu, W., & Zhang, Y. (2019). Quantile Regression under memory constraint. *Annals of Statistics*, 47, 3244–3273.

Chouzenoux, E. & Fest, J.-B. (2022). SABRINA: A Stochastic Subspace Majorization-Minimization Algorithm. *Journal of Optimization Theory and Applications*, 195(3), 919–952.

Chouzenoux, E. & Pesquet, J.-C. (2016). Convergence Rate Analysis of the Majorize-Minimize Subspace Algorithm. *IEEE Signal Processing Letters*, 23(9), 1284–1288.

Combettes, P. L. & Pesquet, J.-C. (2015). Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping. *SIAM Journal on Optimization*, 25(2), 1221–1248.

Combettes, P. L. & Wajs, V. R. (2005). Signal Recovery by Proximal Forward-Backward Splitting. *Multiscale Modeling & Simulation*, 4(4), 1168–1200.

Cui, Y. & Pang, J. (2022). *Modern Nonconvex Nondifferentiable Optimization*. Philadelphia: SIAM.

Dacunha-Castelle, D. & Duflo, M. (1986). *Probability and Statistics: Volume II*. Springer.

Davidson, J. (2021). *Stochastic Limit Theory: An Introduction for Econometricians*. Oxford University Press.

Delyon, B., Lavielle, M., & Moulines, E. (1999). Convergence of a Stochastic Approximation Version of the EM Algorithm. *Annals of Statistics*, 27, 94–128.

Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. *Journal of the Royal Statistical Society Series B*, 39, 1–38.

Dieuleveut, A., Fort, G., Moulines, E., & Robin, G. (2021). Federated-EM with heterogeneity mitigation and variance reduction. *Advances in Neural Information Processing Systems*, 34, 29553–29566.

D'Orazio, R., Loizou, N., Laradji, I. H., & Mitliagkas, I. (2023). Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize. *Transactions on Machine Learning Research*.

Dragomir, R. A., Even, M., & Hendrikx, H. (2021). Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction. In M. Meila & T. Zhang (Eds.), *Proceedings of the 38th International Conference on Machine Learning*, volume 139 of *Proceedings of Machine Learning Research* (pp. 2815–2825): PMLR.
Fort, G., Gach, P., & Moulines, E. (2021a). Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence. *Statistics and Computing*, 31(48), 1–24.

Fort, G. & Moulines, E. (2003). Convergence of the Monte Carlo Expectation Maximization for Curved Exponential Families. *The Annals of Statistics*, 31(4), 1220–1259.

Fort, G. & Moulines, E. (2023). Stochastic variable metric proximal gradient with variance reduction for non-convex composite optimization. *Statistics and Computing*, 33.

Fort, G., Moulines, E., & Wai, H.-T. (2021b). Geom-Spider-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization. In *ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)* (pp. 3135–3139).: IEEE.

Ghadimi, S., Lan, G., & Zhang, H. (2016). Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. *Math. Program.*, 155.

Gourieroux, C. & Monfort, A. (1995). *Statistics And Econometrics Volume 2: Testing, Confidence Regions, Model Selection, And Asymptotic Theory*. Cambridge: Cambridge University Press.

Guilmeau, T., Chouzenoux, E., & Elvira, V. (2025). Regularized Rényi divergence minimization through Bregman proximal gradient algorithms. To appear in *Journal of Machine Learning Research*.

Hall, P. & Heyde, C. (1980). *Martingale Limit Theory and Its Application*. Elsevier Science.

Hong, M., Wang, X., Razaviyayn, M., & Luo, Z.-Q. (2017). Iteration complexity analysis of block coordinate descent methods. *Mathematical Programming*, 163(1), 85–114.

Hu, T., Moricz, F., & Taylor, R. (1989). Strong laws of large numbers for arrays of rowwise independent random variables. *Acta Math Hung.*, 54, 153–162.

Hunter, D. R. & Lange, K. (2000). Quantile Regression via an MM Algorithm. *Journal of Computational and Graphical Statistics*, 9, 60–77.

Hunter, D. R. & Lange, K. (2004). A Tutorial on MM Algorithms. *The American Statistician*, 58, 30–37.

Ichinose, T., Yukawa, M., & Cavalcante, R. L. G. (2023). Online Kernel-Based Quantile Regression Using Huberized Pinball Loss. In *2023 31st European Signal Processing Conference (EUSIPCO)* (pp. 1803–1807).

Ilandarideva, S., Bekri, Y., Juditsky, A. B., & Perchet, V. (2023). Stochastic Mirror Descent for Large-Scale Sparse Recovery. In *AISTATS*, volume 206 of *Proceedings of Machine Learning Research* (pp. 1–27). Valencia, Spain.
Jiang, R. & Yu, K. (2022). Renewable quantile regression for streaming data sets. *Neurocomput.*, 508(C), 208–224.

Karimi, B. & Li, P. (2021). Two-Timescale Stochastic EM Algorithms. In *2021 IEEE International Symposium on Information Theory (ISIT)* (pp. 890–895).: IEEE.

Karimi, B., Miasojedow, B., Moulines, E., & Wai, H.-T. (2019a). Non-Asymptotic Analysis of Biased Stochastic Approximation Scheme. *Proceedings of Machine Learning Research*, 99, 1–31.

Karimi, B., Wai, H.-T., Moulines, E., & Li, P. (2022). Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems. In *International Conference on Algorithmic Learning Theory* (pp. 606–637).: PMLR.

Karimi, B., Wai, H.-T., Moulines, R., & Lavielle, M. (2019b). On the Global Convergence of (Fast) Incremental Expectation Maximization Methods. In *Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS)*.

Khanh Hien, L. T., Phan, D. N., Gillis, N., Ahookhosh, M., & Patrinos, P. (2022). Block Bregman majorization minimization with extrapolation. *SIAM Journal on Mathematics of Data Science*, 4(1), 1–25.

Lai, T. (1989). Extended stochastic lyapunov functions and recursive algorithms in linear stochastic systems. In K. H. N. Christopeit & N. Kohlmann (Eds.), *Stochastic Differential Systems: Proceedings of the 4th Bad Honnef Conference, June, 20–24, 1988* (pp. 206–220).: Springer New-York.

Lan, G. (2020). *First-Order and Stochastic Optimization Methods for Machine Learning*. Springer Nature Switzerland AG.

Lan, G., Nemirovski, A., & Shapiro, A. (2012). Validation analysis of mirror descent stochastic approximation method. *Mathematical Programming*, 134, 425–458.

Lange, K. (2013). *Optimization*. New York: Springer.

Lange, K. (2016). *MM Optimization Algorithms*. Philadelphia: SIAM.

Lange, K., Won, J.-H., Landeros, A., & Zhou, H. (2021). *Nonconvex Optimization via MM Algorithms: Convergence Theory*, (pp. 1–22). John Wiley & Sons, Ltd.

Lei, Y. & Zhou, D.-X. (2020). Convergence of online mirror descent. *Applied and Computational Harmonic Analysis*, 48(1), 343–373.

Lin, Z., Li, H., & Fang, C. (2020). Accelerated Optimization for Machine Learning. *Nature Singapore: Springer*.
Lions, P. L. & Mercier, B. (1979). Splitting Algorithms for the Sum of Two Nonlinear Operators. *SIAM Journal on Numerical Analysis*, 16(6), 964–979.

Liu, A., Lau, V. K., & Kananian, B. (2019). Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization. *IEEE Transactions on Signal Processing*, 67(16), 4189–4203.

Liu, A., Lau, V. K., & Zhao, M.-J. (2018). Online Successive Convex Approximation for Two-Stage Stochastic Nonconvex Optimization. *IEEE Transactions on Signal Processing*, 66(22), 5941–5955.

Liu, J., Cui, Y., & Pang, J.-S. (2022). Solving Nonsmooth and Nonconvex Compound Stochastic Programs with Applications to Risk Measure Minimization. *Mathematics of Operations Research*, 47(4), 3051–3083.

Liu, J. & Pang, J.-S. (2023). Risk-Based Robust Statistical Learning by Stochastic Difference-of-Convex Value-Function Optimization. *Operations Research*, 71(2), 397–414.

Lupu, D. & Necoara, I. (2023). Convergence analysis of stochastic higher-order majorization-minimization algorithms. *Optimization Methods and Software*, (pp. 1–30).

Mairal, J. (2013). Stochastic Majorization-Minimization Algorithm for Large-Scale Optimization. In *Advances in Neural Information Processing Systems* (pp. 2283–2291).

Mairal, J. (2015). Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning. *SIAM Journal of Optimization*, 25, 829–855.

McLachlan, G. J. & Krishnan, T. (2008). *The EM Algorithm And Extensions*. New York: Wiley.

McLachlan, G. J. & Peel, D. (2000). *Finite Mixture Models*. New York: Wiley.

Meng, X.-L. & Rubin, D. B. (1993). Maximum Likelihood Estimation via the ECM Algorithm: A General Framework. *Biometrika*, 80, 267–278.

Meyn, S. (2022). *Control Systems and Reinforcement Learning*. Cambridge University Press.

Mokhtari, A. & Koppel, A. (2020). High-Dimensional Nonconvex Stochastic Optimization by Doubly Stochastic Successive Convex Approximation. *IEEE Transactions on Signal Processing*, 68, 6287–6302.

Naderi, S., He, K., Aghajani, R., Sclaroff, S., & Felzenszwalb, P. (2019). Generalized majorization-minimization. In *International Conference on Machine Learning* (pp. 5022–5031).: PMLR.

Nedić, A. & Lee, S. (2014). On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging. *SIAM Journal on Optimization*, 24(1), 84–107.
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009). Robust Stochastic Approximation Approach to Stochastic Programming. *SIAM Journal on Optimization*, 19(4), 1574–1609.

Nemirovskii, A. & Yudin, D. B. (1983). *Problem Complexity and Method Efficiency in Optimization*. Wiley.

Nguyen, H. D., Forbes, F., Fort, G., & Cappé, O. (2022). An Online Minorization-Maximization Algorithm. In *Conference of the International Federation of Classification Societies* (pp. 263–271).: Springer.

Nguyen, H. D., Forbes, F., & McLachlan, G. J. (2020). Mini-batch learning of exponential family finite mixture models. *Statistics and Computing*, 30, 731–748.

Nitanda, A. (2014). Stochastic Proximal Gradient Descent with Acceleration Techniques. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, & K. Weinberger (Eds.), *Advances in Neural Information Processing Systems*, volume 27: Curran Associates, Inc.

Polyak, B. T. & Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. *SIAM journal on control and optimization*, 30(4), 838–855.

Polyak, R. A. (2021). *Introduction to Continuous Optimization*. Springer Cham.

Razaviyayn, M., Hong, M., & Luo, Z.-Q. (2013). A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization. *SIAM Journal of Optimization*, 23, 1126–1153.

Razaviyayn, M., Sanjabi, M., & Luo, Z. (2016). A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in wWireless Communication Networks. *Mathematical Programming Series B*, (pp. 515–545).

Robbins, H. & Siegmund, D. (1971). A convergence theorem for non negative almost supermartingales and some applications. In J. S. Rustagi (Ed.), *Optimizing Methods in Statistics* (pp. 233–257). Academic Press.

Rosasco, L., Villa, S., & Vü, B. C. (2020). Convergence of Stochastic Proximal Gradient Algorithm. *Applied Mathematics & Optimization*, 82.

Rossignol, C., Sureau, F., Chouzenoux, É., Comtat, C., & Pesquet, J.-C. (2022). A Bregman Majorization-Minimization Framework for PET Image Reconstruction. In *2022 IEEE International Conference on Image Processing (ICIP)* (pp. 1736–1740).: IEEE.

Schraudolph, N. N., Yu, J., & Günter, S. (2007). A Stochastic Quasi-Newton Method for Online Convex Optimization. In M. Meila & X. Shen (Eds.), *Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics*, volume 2 (pp. 436–443).: PMLR.
Serfling, R. J. (1980). *Approximation Theorems Of Mathematical Statistics*. New York: Wiley.

Shalev-Shwartz, S. & Ben-David, S. (2014). *Understanding Machine Learning: From Theory to Algorithms*. Cambridge: Cambridge University Press.

Shapiro, A., Dentcheva, D., & Ruszczynski, A. (2021). *Lectures on Stochastic Programming: Modeling and Theory, Third Edition*. Philadelphia, PA: Society for Industrial and Applied Mathematics.

Vaida, F. (2005). Parameter Convergence for EM and MM Algorithms. *Statistica Sinica*, 15, 831–840.

van der Vaart, A. & Wellner, J. (2023). *Weak Convergence and Empirical Processes: With Applications to Statistics*. Springer Science & Business Media.

Vapnik, V. N. (1998). *Statistical Learning Theory*. New York: Wiley.

Vidyasagar, M. (2003). *Learning and Generalisation: With Applications to Neural Networks*. London: Springer.

Yuille, A. L. & Rangarajan, A. (2003). The Concave-Convex Procedure. *Neural Computation*, 15, 915–936.

Zhang, H., Zhou, P., Yang, Y., & Feng, J. (2019). Generalized Majorization-Minimization for Non-Convex Optimization. In *IJCAI* (pp. 4257–4263).

Zhao, Y.-B. (2018). *Sparse Optimization Theory and Methods*. CRC Press, 1st edition.

Zheng, S. (2011). Gradient descent algorithms for quantile regression with smooth approximation. *International Journal of Machine Learning and Cybernetics*, 2(3), 191–207.

Ziegler, K. (2001). Uniform Laws of Large Numbers for Triangular Arrays of Function-indexed Processes under Random Entropy Conditions. *Results in Mathematics*, 39, 374–389.