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 or for the more general formulation Efficiency of coordinate descent methods on huge-scale optimization problems)

The analysis given here 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). 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.

  • 1
    $\begingroup$ 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 and Koufogiannakis & Young, A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs and subsequent works by Kent Quanrud et al. (discussed here). $\endgroup$
    – Neal Young
    Jan 20, 2021 at 16:15
  • $\begingroup$ @NealYoung thank you for the pointers. Will look into that $\endgroup$ Jan 20, 2021 at 17:27
  • $\begingroup$ (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. $\endgroup$
    – Neal Young
    Jan 21, 2021 at 1:20
  • $\begingroup$ @NealYoung, Some preliminary calculations show that if we execute $O(log(1/\epsilon))$ such random descent step, then we can get $(2+\epsilon)$ approximation $\endgroup$ Jan 21, 2021 at 5:59


Your Answer

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