1. Sublinear-Time and Sublinear-Space Geometric Approximate Optimization for Some Problems Arising in Machine Learning and its Relatives


    Ken Clarkson
    IBM Almaden Research

    joint with Elad Hazan and David Woodruff

  2. Some Geometric Optimization Problems

  3. Our Results

  4. MEB Formulation

  5. Max `p` vs. Min `x`

    For rounds `t=1,\ldots T`, two players respond to each other.
  6. A Primal-Dual Algorithm

    The resulting algorithm, in pseudo-code:
    `p_1\leftarrow (\frac{1}{n}, \frac{1}{n}, \ldots, \frac{1}{n})`
    `x_1 \leftarrow A^\top p_1`
    for `t=1,2,\ldots ,T`:
      for each `i`: `p_t(i) \leftarrow p_{t-1}(i)\exp(\eta||x_{t-1} - A_i^\top||^2)`
      `p_t\leftarrow p_t/||p_t||_1`
      `x_t \leftarrow (1-\frac{1}{t})x_{t-1} + \frac{1}{t}A^\top p_t`
        // So `x_t = \frac{1}{t}\sum_{\tau\in [t]} A^\top p_{\tau}`
  7. The Primal-Dual Algorithm is Not Too Bad

  8. Randomizing the Primal-Dual Algorithm

  9. The Randomized Primal-Dual Algorithm is
    Not Too Bad


  10. Randomized vs. Deterministic

  11. Randomized vs. Deterministic for "real" data

  12. Kernelization

  13. Remaining Questions

  14. Ingredients of the Analysis:
    Regret Bounds and Concentration


  15. Concentration Bounds

  16. Concentrated Estimators via Variance Bounds

  17. Digression: Other Concentrated Estimators
    from only Variance Bounds


  18. Related Work: Coresets,
    Low-Rank Approximation


  19. Related Work: Prior Primal-Dual Algorithms

  20. `\ell_2` Sampling vs. Sketches

  21. `\ell_2` Sampling as Low-Rent Feature Selection

  22. Matrix Product via `\ell_2` Sampling

  23. Concluding Remarks


    Thank you for your attention