 |
ML Newsnew | past | best | rss | submit | about |
| Minimizing a sum of clipped convex functions (arxiv.org) | |
| 3 points by LolWolf on Jun 2, 2020 | hide | past | pdf | 1 comment on HN | |
|
In plain words: Some problems minimize a total of costs capped at a maximum, so extreme values stop mattering; exactly solving this is very hard. Their quick approximations find good answers, and a second formulation proves those answers sit close to the best possible. Abstract · Minimizing a Sum of Clipped Convex FunctionsWe consider the problem of minimizing a sum of clipped convex functions; applications include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped convex functions is NP-hard, we present some heuristics for approximately solving instances of these problems. These heuristics can be used to find good, if not global, solutions and appear to work well in practice. We also describe an alternative formulation, based on the perspective transformation, which makes the problem amenable to mixed-integer convex programming and yields computationally tractable lower bounds. We illustrate one of our heuristic methods by applying it to various examples and use the perspective transformation to certify that the solutions are relatively close to the global optimum. This paper is accompanied by an open-source implementation. | |
| add comment on HN |
We thought this paper might be of interest to people in data analysis or machine learning for fitting problems which have many outliers in data (in relatively simple ways). We a few examples where most common heuristics fail pretty badly, yet this approach does surprisingly well (see Section 6.1).
We also show an application in autonomous vehicle control for lane-changing and such, which may also be of interest to a slightly different crowd! :)
There is also an open source implementation, for those interested in using this package: https://www.github.com/cvxgrp/sccf