{
  "id": "2012.15361",
  "version": "v1",
  "published": "2020-12-30T23:16:34.000Z",
  "updated": "2020-12-30T23:16:34.000Z",
  "title": "Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning",
  "authors": [
    "Haoyue Wang",
    "Haihao Lu",
    "Rahul Mazumder"
  ],
  "comment": "29 pages, 2 figures",
  "categories": [
    "math.OC"
  ],
  "abstract": "The Frank-Wolfe (FW) method is a popular algorithm for solving large-scale convex optimization problems appearing in structured statistical learning. However, the traditional Frank-Wolfe method can only be applied when the feasible region is bounded, which limits its applicability in practice. Motivated by two applications in statistical learning, the $\\ell_1$ trend filtering problem and matrix optimization problems with generalized nuclear norm constraints, we study a family of convex optimization problems where the unbounded feasible region is the direct sum of an unbounded linear subspace and a bounded constraint set. We propose two new Frank-Wolfe methods: unbounded Frank-Wolfe method (uFW) and unbounded Away-Step Frank-Wolfe method (uAFW), for solving a family of convex optimization problems with this class of unbounded feasible regions. We show that under proper regularity conditions, the unbounded Frank-Wolfe method has a $O(1/k)$ sublinear convergence rate, and unbounded Away-Step Frank-Wolfe method has a linear convergence rate, matching the best-known results for the Frank-Wolfe method when the feasible region is bounded. Furthermore, computational experiments indicate that our proposed methods appear to outperform alternative solvers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-30T23:16:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C25",
      "90C06",
      "90C90"
    ],
    "keywords": [
      "unbounded feasible region",
      "large-scale convex optimization problems",
      "unbounded away-step frank-wolfe method",
      "convex optimization problems appearing",
      "applications"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}