<p>Let us consider the following optimization problem.</p>
<p><span class="math-container">$\mathcal{P} =\{P_1,\cdots,P_n\}$</span>, where <span class="math-container">$P_i\subset\mathbb{R}^d$</span>. Let <span class="math-container">$m = max_i\lvert P_i\rvert$</span>. The goal is to find a point <span class="math-container">$c$</span> such that following function is minimized.</p>
<p><span class="math-container">$F(c) = \sum_{P_j\in \mathcal{P}}max_{p\in P_j}\Vert p-c\Vert^2$</span>. The following observations can be drawn</p>
<ol>
<li>F(.) is convex.</li>
<li>Given a point <span class="math-container">$c\in\mathbb{R}^d$</span>, let <span class="math-container">$p_j$</span> be the farthest point in <span class="math-container">$P_j$</span> from <span class="math-container">$c$</span>. Then <span class="math-container">$G(c) =\sum_{P_j\in\mathcal{P}}2(c-p_j)$</span> is a &quot;subgradient&quot; of <span class="math-container">$F$</span> at <span class="math-container">$c$</span>.</li>
</ol>
<p>Note that computing <span class="math-container">$G(c)$</span> requires <span class="math-container">$O(nmd)$</span> time. Instead if we uniformly sample an index <span class="math-container">$j\in[n]$</span> and define a random variable <span class="math-container">$X(c,j) = 2(c-p_j)$</span>, then <span class="math-container">$\mathbb{E}_j[X(c,j)] = \frac{G(c)}{n}$</span> and computing the random variable requires time <span class="math-container">$O(n+md)$</span>.</p>
<p>Now instead of doing the &quot;full&quot; gradient descent(using <span class="math-container">$G(c)$</span>), I am trying to use the random variable <span class="math-container">$X(c,j)$</span>. So one step of this &quot;randomized&quot; gradient descent looks something like</p>
<p><span class="math-container">$c^\prime = c -\alpha X(c,j)$</span>. Here <span class="math-container">$\alpha$</span> is some step size.</p>
<p>The above step is similar to &quot;randomized coordinate descent&quot; (see Algorithm 3 <a href="https://arxiv.org/pdf/1502.04759.pdf" rel="nofollow noreferrer">Coordinate Descent Algorithms</a> or for the more general formulation <a href="http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf" rel="nofollow noreferrer">Efficiency of coordinate descent methods
on huge-scale optimization problems</a>)</p>
<p>The analysis given <a href="https://arxiv.org/pdf/1502.04759.pdf" rel="nofollow noreferrer">here</a> depends on the fact that only a single coordinate is sampled during a single iterarion( more generally, if the underlying space can be partitioned into &quot;disjoint&quot; &quot;block&quot;s, then a single block is sampled, see <a href="https://arxiv.org/pdf/1305.4723.pdf" rel="nofollow noreferrer">here</a>). This can not be applied here in a straight forward manner(I think).</p>
<p>Does this variant of gradient descent appear in the literarure? More formally if the (sub)gradient is sum of a finite number of vectors, then can we use one uniformly sampled vector in the &quot;descent&quot; step?</p>
<p>Thanks you.</p>

CC BY-SA 4.0
2021-01-20T16:15:59.900Z
FWIW random sampling of individual coordinates to increase efficiency is also used e.g. in [Grigoriadis & Khachiyan,
A sublinear-time randomized approximation algorithm for matrix games](https://doi.org/10.1016/0167-6377(95)00032-0) and [Koufogiannakis & Young, A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs](https://doi.org/10.1007/s00453-013-9771-6) and subsequent works by Kent Quanrud et al. (discussed [here](https://doi.org/10.1137/1.9781611976014.11)).
Neal Young
CC BY-SA 4.0
2021-01-20T17:27:16.910Z
@NealYoung thank you for the pointers. Will look into that
Sudipta Roy
CC BY-SA 4.0
2021-01-21T01:20:45.470Z
(i) I think the answer to your question (about using vectors instead of individual coordinates) is probably "yes, you can" at least for some suitable step size.  The main reason for sampling a single coordinate in the existing literature is for efficiency.. but as long as the expectations are as they should be for your random choice, and the increment stays within the "trust region", it should work.  (ii) I wonder if you can reduce your case to a single-coordinate scenario by some appropriate change of variables.
Neal Young
CC BY-SA 4.0
2021-01-21T05:59:55.903Z
@NealYoung, Some preliminary calculations show that if we execute $O(log(1/\epsilon))$ such random descent step, then we can get $(2+\epsilon)$ approximation
Sudipta Roy
<reference-request><optimization><randomized-algorithms><convex-optimization>
A variant of randomized co-ordinate descent
Sudipta Roy
# A variant of randomized co-ordinate descent

(Asked by: username_0 on 2021-01-17)

Let us consider the following optimization problem.

$\mathcal{P} =\{P\_1,\cdots,P\_n\}$, where $P\_i\subset\mathbb{R}^d$. Let $m = max\_i\lvert P\_i\rvert$. The goal is to find a point $c$ such that following function is minimized.

$F(c) = \sum\_{P\_j\in \mathcal{P}}max\_{p\in P\_j}\Vert p-c\Vert^2$. The following observations can be drawn

1. F(.) is convex.
2. Given a point $c\in\mathbb{R}^d$, let $p\_j$ be the farthest point in $P\_j$ from $c$. Then $G(c) =\sum\_{P\_j\in\mathcal{P}}2(c-p\_j)$ is a "subgradient" of $F$ at $c$.

Note that computing $G(c)$ requires $O(nmd)$ time. Instead if we uniformly sample an index $j\in[n]$ and define a random variable $X(c,j) = 2(c-p\_j)$, then $\mathbb{E}\_j[X(c,j)] = \frac{G(c)}{n}$ and computing the random variable requires time $O(n+md)$.

Now instead of doing the "full" gradient descent(using $G(c)$), I am trying to use the random variable $X(c,j)$. So one step of this "randomized" gradient descent looks something like

$c^\prime = c -\alpha X(c,j)$. Here $\alpha$ is some step size.

The above step is similar to "randomized coordinate descent" (see Algorithm 3 [Coordinate Descent Algorithms](https://arxiv.org/pdf/1502.04759.pdf) or for the more general formulation [Efficiency of coordinate descent methods
on huge-scale optimization problems](http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf))

The analysis given [here](https://arxiv.org/pdf/1502.04759.pdf) depends on the fact that only a single coordinate is sampled during a single iterarion( more generally, if the underlying space can be partitioned into "disjoint" "block"s, then a single block is sampled, see [here](https://arxiv.org/pdf/1305.4723.pdf)). This can not be applied here in a straight forward manner(I think).

Does this variant of gradient descent appear in the literarure? More formally if the (sub)gradient is sum of a finite number of vectors, then can we use one uniformly sampled vector in the "descent" step?

Thanks you.

**Tags:** reference-request, optimization, randomized-algorithms, convex-optimization

> **Comments:**
> **username_1**: FWIW random sampling of individual coordinates to increase efficiency is also used e.g. in [Grigoriadis & Khachiyan, A sublinear-time randomized approximation algorithm for matrix games](https://doi.org/10.1016/0167-6377(95)00032-0) and [Koufogiannakis & Young, A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs](https://doi.org/10.1007/s00453-013-9771-6) and subsequent works by Kent Quanrud et al. (discussed [here](https://doi.org/10.1137/1.9781611976014.11)).  
> **username_0**: @NealYoung thank you for the pointers. Will look into that  
> **username_1**: (i) I think the answer to your question (about using vectors instead of individual coordinates) is probably "yes, you can" at least for some suitable step size.  The main reason for sampling a single coordinate in the existing literature is for efficiency.. but as long as the expectations are as they should be for your random choice, and the increment stays within the "trust region", it should work.  (ii) I wonder if you can reduce your case to a single-coordinate scenario by some appropriate change of variables.  
> **username_0**: @NealYoung, Some preliminary calculations show that if we execute $O(log(1/\epsilon))$ such random descent step, then we can get $(2+\epsilon)$ approximation  

---

## 0 answers

