{"action":"created","issue":{"url":"https://api.github.com/repos/scalanlp/breeze/issues/633","repository_url":"https://api.github.com/repos/scalanlp/breeze","labels_url":"https://api.github.com/repos/scalanlp/breeze/issues/633/labels{/name}","comments_url":"https://api.github.com/repos/scalanlp/breeze/issues/633/comments","events_url":"https://api.github.com/repos/scalanlp/breeze/issues/633/events","html_url":"https://github.com/scalanlp/breeze/pull/633","id":218427644,"number":633,"title":"Fix lbfgsb linesearch out of bound and findAlpha method","user":{"login":"WeichenXu123","id":19235986,"avatar_url":"https://avatars0.githubusercontent.com/u/19235986?v=4","gravatar_id":"","url":"https://api.github.com/users/WeichenXu123","html_url":"https://github.com/WeichenXu123","followers_url":"https://api.github.com/users/WeichenXu123/followers","following_url":"https://api.github.com/users/WeichenXu123/following{/other_user}","gists_url":"https://api.github.com/users/WeichenXu123/gists{/gist_id}","starred_url":"https://api.github.com/users/WeichenXu123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/WeichenXu123/subscriptions","organizations_url":"https://api.github.com/users/WeichenXu123/orgs","repos_url":"https://api.github.com/users/WeichenXu123/repos","events_url":"https://api.github.com/users/WeichenXu123/events{/privacy}","received_events_url":"https://api.github.com/users/WeichenXu123/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":6,"created_at":"2017-03-31T08:07:35Z","updated_at":"2017-07-20T23:46:03Z","closed_at":"2017-04-18T04:50:29Z","pull_request":{"url":"https://api.github.com/repos/scalanlp/breeze/pulls/633","html_url":"https://github.com/scalanlp/breeze/pull/633","diff_url":"https://github.com/scalanlp/breeze/pull/633.diff","patch_url":"https://github.com/scalanlp/breeze/pull/633.patch"},"body":"# What to solve\r\nAfter a deep check to the LBFGS-B in breeze, I found two serious bug in LBFGS-B:\r\n- line search is wrong in this implementation. \r\n- `LBFGSB.findAlpha` method is also wrong.\r\n\r\n# Fix Line search with bound\r\nAccording to the LBFGS-B paper\r\nhttp://users.iems.northwestern.edu/~nocedal/PDFfiles/limited.pdf\r\nThe line search in LBFGS-B should be restricted in the bound, but the implementation in breeze do not,\r\nthis will cause the optimizer run out of bound, it will cause wrong result or cause line search fail, in some case.\r\nThis is the root cause of issue #572, and a series of features is blocking because of this bug:  \r\n- Huber loss: https://github.com/apache/spark/pull/14326\r\n- Bounded LiR: https://github.com/apache/spark/pull/17360\r\n- Bounded LoR: https://issues.apache.org/jira/browse/SPARK-20047\r\n\r\nSo that it should be fixed ASAP.  \r\ncc @yanboliang \r\n\r\n## Strong wolfe line search with bound restriction\r\nAs mentioned in paper, the best linesearch method for LBFGS-B is strong wolfe line search with bound restriction, this require some modification based on `StrongWolfeLineSearch` in breeze:\r\n\r\n### modified strong wolfe condition with bound\r\nWe know that strong wolfe condition is to satisfy **sufficient decrease condition** and **curvature condition**, BUT according to the paper, the strong wolfe line search in LBFGS-B, the condition should be modified as following:\r\n- satisfy **sufficient decrease condition**\r\n- satisfy **curvature condition** OR **new point X(k + 1) hit the bound**\r\n\r\n### Algorithm for strong wolfe condition with bound\r\nWithout bound, we already have the following algos (Nodecal & Wright Numerical Optimization p58)\r\n![lbfgsb-1](https://cloud.githubusercontent.com/assets/19235986/24540092/43cbda84-1624-11e7-929b-2d2cd2e1af1c.png)\r\nSo that, with bound, we can modify this algo into following:\r\n![lbfgsb-2](https://cloud.githubusercontent.com/assets/19235986/24541690/0f87c6fa-162b-11e7-8c68-6dcb2d2599e7.png)\r\n\r\n## modification in LBFGS-B\r\n- In method `determineStepSize`, first calculate the max step size which won't exceed bound box, then use it as the step bound, call `StrongWolfeLineSearch.minimizeWithBound`\r\n- override `takeStep` method, in this method check whether the `newX` exceed bound and correct it. (This is used to avoid numerical error that cause the `newX` run out of bound)\r\n\r\n# Fix `findAlpha` method\r\nUnfortunately, the `findAlpha` method here is also wrong, the wrong implementation cause the `subspaceMin` point walk out of bound and so that in some case it will also cause the algos crash.\r\nI trace to the code here through several failed testcases with `Huber loss`.\r\nIn summary, there are at least 2 mistakes in this method, let me explain what the method should do first:\r\n\r\nfind the maximum `alpha`, satisfiy `0.0 <= alpha <= 1.0`, and, for each dimension `i`, should satisfy:\r\n```\r\nlowerBound_i - xCauchy_i <= alpha * du_i <= upperBound_i - xCauchy_i\r\n```\r\n\r\n`xCauchy` is the Cauchy point inside the bound box which will satisfy\r\n```\r\nlowerBound_i - xCauchy_i <= 0\r\nupperBound_i - xCauchy_i >= 0\r\n```\r\nand `du` is the direction vector (details please refer to the paper), the key point is ,  **for each `i`, the condition above should be satisfied**, so that the `subspace minimum point` computed will be restricted in the bound box.\r\n\r\nSo that the algo to find the maximum alpha should be:\r\n```\r\nminimize i: 0 -> dimensionSize  {\r\n  if (du_i < 0) (lowerBound_i - xCauchy_i) / du_i\r\n  else if (du_i > 0) (upperBound_i - xCauchy_i) / du_i\r\n  else Double.Infinity\r\n}\r\n```\r\nNote that we should handle the case `du_i == 0` carefully, otherwise it may generate `NaN` in computation and will cause the whole algo crash.\r\n\r\nThen we can check the implementation in breeze, the logic in `findAlpha` is wrong. The place where it should use `math.min` it use `math.max`. And the code write `(ub_i - xc_i) / du_i` to be the wrong code `ub_i - xc_i / du_i`\r\n\r\nThe second mistake in `findAlpha` is that it do not handle the case that components of `du` is zero. This may cause computation run into `NaN`. We should skip the zero components of `du`.\r\n\r\n# Numerical error handling\r\nIn theory, the `cauchy point`, the `subspaceMin point`, the `X` point, in the computation, should all be restricted in the bound box. BUT because of floating point error, it may slightly exceed the bound, so I add a `adjustWithinBound` method to correct it. So that it can avoid the point step out of bound which may cause other bugs.\r\n\r\n# Test\r\nThe following typical algos have been tested:\r\n- huber loss regression\r\n- bounded LOR\r\n- bounded LIR\r\n"},"comment":{"url":"https://api.github.com/repos/scalanlp/breeze/issues/comments/316861141","html_url":"https://github.com/scalanlp/breeze/pull/633#issuecomment-316861141","issue_url":"https://api.github.com/repos/scalanlp/breeze/issues/633","id":316861141,"user":{"login":"dlwh","id":9633,"avatar_url":"https://avatars2.githubusercontent.com/u/9633?v=4","gravatar_id":"","url":"https://api.github.com/users/dlwh","html_url":"https://github.com/dlwh","followers_url":"https://api.github.com/users/dlwh/followers","following_url":"https://api.github.com/users/dlwh/following{/other_user}","gists_url":"https://api.github.com/users/dlwh/gists{/gist_id}","starred_url":"https://api.github.com/users/dlwh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dlwh/subscriptions","organizations_url":"https://api.github.com/users/dlwh/orgs","repos_url":"https://api.github.com/users/dlwh/repos","events_url":"https://api.github.com/users/dlwh/events{/privacy}","received_events_url":"https://api.github.com/users/dlwh/received_events","type":"User","site_admin":false},"created_at":"2017-07-20T23:46:02Z","updated_at":"2017-07-20T23:46:02Z","body":"i think it's more that you're ignoring the passed in value of init\n\nOn Thu, Jul 20, 2017 at 4:35 PM, WeichenXu <notifications@github.com> wrote:\n\n> *@WeichenXu123* commented on this pull request.\n> ------------------------------\n>\n> In math/src/main/scala/breeze/optimize/StrongWolfe.scala\n> <https://github.com/scalanlp/breeze/pull/633#discussion_r128655226>:\n>\n> > @@ -58,12 +58,18 @@ class StrongWolfeLineSearch(maxZoomIter: Int, maxLineSearchIter: Int) extends Cu\n>    val c1 = 1e-4\n>    val c2 = 0.9\n>\n> +  def minimize(f: DiffFunction[Double], init: Double = 1.0): Double = {\n> +    minimizeWithBound(f, init = 1.0, bound = Double.PositiveInfinity)\n>\n> In LBFGS-B, we can use 1 as the init value, according to paper, or do you\n> have some better init value ?\n>\n> —\n> You are receiving this because you modified the open/close state.\n> Reply to this email directly, view it on GitHub\n> <https://github.com/scalanlp/breeze/pull/633#discussion_r128655226>, or mute\n> the thread\n> <https://github.com/notifications/unsubscribe-auth/AAAloepiOk2B2kTaPR896BT-RmplS8gFks5sP-RbgaJpZM4MvWUO>\n> .\n>\n"}}
{"actor":{"display_login":"dlwh"}}