A unified analysis of convex and non‑convex ‑ball projection problems.

Journal: Optimization letters
Published Date: Sep 4, 2022

Abstract

The task of projecting onto norm balls is ubiquitous in statistics and machine learning, yet the availability of actionable algorithms for doing so is largely limited to the special cases of . In this paper, we introduce novel, scalable methods for projecting onto the -ball for general . For , we solve the univariate Lagrangian dual via a dual Newton method. We then carefully design a bisection approach For , presenting theoretical and empirical evidence of zero or a small duality gap in the non-convex case. The success of our contributions is thoroughly assessed empirically, and applied to large-scale regularized multi-task learning and compressed sensing. The code implementing our methods is publicly available on Github.

Authors

  • Joong-Ho Won
    Department of Statistics, Seoul National University, Seoul, Republic of Korea.
  • Kenneth Lange
    Departments of Computational Medicine, Human Genetics and Statistics, University of California, Los Angeles, California, USA.
  • Jason Xu
    Department of Statistical Science, Duke University, Durham, North Carolina, USA.

Keywords

No keywords available for this article.

External Resources

Popular Topics
Recent Journals