{
  "id": "1711.04734",
  "version": "v1",
  "published": "2017-11-13T18:03:15.000Z",
  "updated": "2017-11-13T18:03:15.000Z",
  "title": "Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso",
  "authors": [
    "Roberto I. Oliveira",
    "Philip Thompson"
  ],
  "comment": "28 pages",
  "categories": [
    "math.OC"
  ],
  "abstract": "We present exponential finite-sample nonasymptotic deviation inequalities for the SAA estimator's near-optimal solution set over the class of \\emph{convex} stochastic optimization problems with heavy-tailed random H\\\"older continuous functions in the objective and constraints. Such setting is better suited for problems where a sub-Gaussian data generating distribution is less expected, e.g., in stochastic portfolio optimization. One of our contributions is to exploit \\emph{convexity} of the perturbed objective and the perturbed constraints as a property which entails \\emph{localized} deviation inequalities for joint feasibility and optimality guarantees. This means that our bounds are significantly tighter in terms of diameter and metric entropy since they depend only on the near-optimal solution set but not on the whole feasible set. As a result, we obtain a much sharper sample complexity estimate when compared to a general nonconvex problem. In our analysis, we derive some localized deterministic perturbation error bounds for convex optimization problems which are of independent interest. To obtain our results, we only assume a metric regular convex feasible set, possibly not satisfying the Slater condition and not having a metric regular solution set. In this general setting, joint near feasibility and near optimality are guaranteed. If in addition the set satisfies the Slater condition, we obtain finite-sample simultaneous exact feasibility and near optimality guarantees. Another contribution of our work is to present, as a proof of concept of our localized techniques, a persistent result for a variant of the LASSO estimator under very weak assumptions on the data generating distribution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-13T18:03:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sample average approximation",
      "stochastic convex optimization",
      "persistence results",
      "finite-sample nonasymptotic deviation inequalities",
      "deterministic perturbation error bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}