{"action":"created","comment":{"url":"https://api.github.com/repos/scalanlp/breeze/pulls/comments/24848414","id":24848414,"diff_hunk":"@@ -1 +1,17 @@\n Breeze is distributed under an Apache License V2.0 (See LICENSE)\n+\n+===============================================================================\n+\n+Proximal algorithms outlined in Proximal.scala (package breeze.optimize.quadratic)\n+are based on https://github.com/cvxgrp/proximal (see LICENSE for details) and distributed with \n+Copyright (c) 2014 by Debasish Das (Verizon), all rights reserved.\n+\n+===============================================================================\n+\n+QuadraticMinimizer class in package breeze.optimize.proximal is distributed with Copyright (c)\n+2014, Debasish Das (Verizon), all rights reserved.","path":"NOTICE","position":12,"original_position":12,"commit_id":"ce8638fb697880158971e1dd70b94841e066e166","original_commit_id":"ce8638fb697880158971e1dd70b94841e066e166","user":{"login":"debasish83","id":510896,"avatar_url":"https://avatars.githubusercontent.com/u/510896?v=3","gravatar_id":"","url":"https://api.github.com/users/debasish83","html_url":"https://github.com/debasish83","followers_url":"https://api.github.com/users/debasish83/followers","following_url":"https://api.github.com/users/debasish83/following{/other_user}","gists_url":"https://api.github.com/users/debasish83/gists{/gist_id}","starred_url":"https://api.github.com/users/debasish83/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debasish83/subscriptions","organizations_url":"https://api.github.com/users/debasish83/orgs","repos_url":"https://api.github.com/users/debasish83/repos","events_url":"https://api.github.com/users/debasish83/events{/privacy}","received_events_url":"https://api.github.com/users/debasish83/received_events","type":"User","site_admin":false},"body":"I read the PQN paper and it is possible to stick all the proximal operators inside PQN...I have tested bounds with PQN already and it works well compared to default ADMM. \r\n\r\nIf it holds for ProximalL1() compared to OWLQN then I am good to use PQN as the core of NonlinearMinimizer...PQN right now accepts closure of form DenseVector[Double] => DenseVector[Double]. Would it be fine if I change the signature to (x: DenseVector[Double], rho: Double) => DenseVector[Double] ? \r\n\r\nThis is in-tune to generic proximal algorithms:\r\nminimize g(x) + rho||x - v||_{2}^{2}\r\n\r\ng(x) can be constraints here: x \\in C\r\ng(x) can be L1 here as well through soft-thresholding I think","created_at":"2015-02-17T20:01:09Z","updated_at":"2015-02-17T20:01:09Z","html_url":"https://github.com/scalanlp/breeze/pull/364#discussion_r24848414","pull_request_url":"https://api.github.com/repos/scalanlp/breeze/pulls/364","_links":{"self":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/comments/24848414"},"html":{"href":"https://github.com/scalanlp/breeze/pull/364#discussion_r24848414"},"pull_request":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/364"}}},"pull_request":{"url":"https://api.github.com/repos/scalanlp/breeze/pulls/364","id":29072999,"html_url":"https://github.com/scalanlp/breeze/pull/364","diff_url":"https://github.com/scalanlp/breeze/pull/364.diff","patch_url":"https://github.com/scalanlp/breeze/pull/364.patch","issue_url":"https://api.github.com/repos/scalanlp/breeze/issues/364","number":364,"state":"open","locked":false,"title":"[WIP] NonlinearMinimizer using ADMM based Proximal Algorithm","user":{"login":"debasish83","id":510896,"avatar_url":"https://avatars.githubusercontent.com/u/510896?v=3","gravatar_id":"","url":"https://api.github.com/users/debasish83","html_url":"https://github.com/debasish83","followers_url":"https://api.github.com/users/debasish83/followers","following_url":"https://api.github.com/users/debasish83/following{/other_user}","gists_url":"https://api.github.com/users/debasish83/gists{/gist_id}","starred_url":"https://api.github.com/users/debasish83/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debasish83/subscriptions","organizations_url":"https://api.github.com/users/debasish83/orgs","repos_url":"https://api.github.com/users/debasish83/repos","events_url":"https://api.github.com/users/debasish83/events{/privacy}","received_events_url":"https://api.github.com/users/debasish83/received_events","type":"User","site_admin":false},"body":"@dlwh @mengxr @dbtsai \r\n\r\nThis PR introduces ADMM based Proximal algorithm to solve problems of the following structure\r\nminimize f(x) + g(z)\r\ns.t x = z\r\nFISTA is also a candidate to solve this problem but we used ADMM since FISTA can't handle affine constraints natively. \r\n\r\nCurrently f(x) can be convex/nonlinear function. So far my stress tests are using convex functions (least square regression and logistic regression) but down the line we will come to nonlinear loss (DSGD formulation from matrix factorization or sigmoid function from neural net). We call it centralized ADMM since ADMM loop is still maintained on the Master node. Once centralized ADMM works, we will generalize it to Proximal Server (Parameter server with Proximal Algorithms).\r\n\r\nParameter Server with Proximal Algorithms is motivated by Mu's comparison of Blocked Proximal Gradient with Google's Distributed BFGS code:\r\nhttp://www.cs.cmu.edu/~muli/file/parameter_server_osdi14.pdf\r\n\r\nWe have two variants of ADMM iterations right now (experimentations are ongoing). One hot-starts on x from previous ADMM iterations while the other hot-starts on both x and BFGS history from previous ADMM iteration. New LBFGS API is added that returns state to facilitate BFGS history preservation.\r\n\r\nrunMain breeze.optimize.proximal.NonlinearMinimizer 200 0.4 0.99\r\n\r\nWe generate random data matrix (A) of size 200x200 from normal gaussian (0 mean 1 stddev). Label vector is generated from normal gaussian as well. If label > 0.5 we assign it to 1.0 else 0.0\r\n\r\nLambda = 0.4 ElasticNet beta = 0.99\r\nlambdaL1 = 0.4*0.99\r\nlambdaL2 = 0.4*0.01\r\n\r\nLinear Regression:\r\n\r\nComparison 1: NonlinearMinimizer (nl) vs QuadraticMinimizer (qp)\r\n\r\nNonlinearMinimizer takes f(x) = ||Ax - b||_2^{2} df/dx = 2(Ax - b)*A \r\nQuadraticMinimizer takes gram=A'A, linear term= A'b\r\n\r\nSolution quality:\r\n||qp - nl|| norm 0.16799969531758605 max-norm 0.034283192270685436\r\n||bfgs - nl|| norm 0.25715611616302037 max-norm 0.04888455483124021\r\n\r\nObjective:\r\n\r\nObjective qp -55.00000000000021 nl -54.999725074409454 bfgs -54.99983413525827\r\n\r\nnl and bfgs are both using BFGS for the primal solve\r\n\r\nComparison 2: NonlinearMinimizer with g(z)=ProximalL1 (nlSparse/nlSparseHistory) vs OWLQN vs QuadraticMinimizer with g(z)=ProximalL1 (sparseQp)\r\n\r\nRuntime:\r\nowlqn 165.178 ms iters 143 sparseQp 32.87 ms iters 59\r\n\r\nSolution Quality:\r\n||sparseQp - owlqn|| norm 0.14861916579656498 inf-norm 0.03034052809134663\r\nowlqnObj -47.42068811893944 sparseQpObj -47.45927392747443\r\n\r\nnlSparse 1479.666 ms iters 195 nlSparseHistory 407.347 ms iters 429\r\n||owlqn - nlSparse|| norm 0.1460259470192177 inf-norm 0.029597210620735503\r\n||owlqn - nlSparseHistory|| norm 0.14649731508771383 inf-norm 0.030278923124194383\r\nnlSparseObj -47.457604531534805 nlSparseHistoryObj -47.45480418795271\r\n\r\nNonlinearMinimizer is ~2X slower than OWLQN but if you look at objective, it converges to better solution.\r\n\r\nComparison 3: NonlinearMinimizer with g(z) = ProximalBounds(0 <= z <= 1.0) (nlBox) vs PQN vs QuadraticMinimizer with g(z) = ProximalBounds (qpBox)\r\n\r\nqpBox 6.769 ms iters 57\r\nnlBox 10182.424 ms iters 2282 nlBoxHistory 1269.134 ms 2271\r\npqnBox 272.064 ms iters 28\r\n\r\n||qpBox - nlBox|| norm 0.0022824265880237215 inf-norm 4.694687018757908E-4\r\n||qpBox - nlBoxHistory|| norm 0.0023190292089652767 inf-norm 4.773077547529439E-4\r\n||qpBox - nlBox|| norm 0.0021390982826103347 inf-norm 5.634071605518931E-4\r\n\r\nqpBoxObj -31.130008148965725 nlBoxObj -31.209892573229023 nlBoxHistoryObj -31.20915524772166 pqnBoxObj -31.127492181959255\r\n\r\nHere also we are 5X slower than PQN but our solution is better compared to PQN.\r\n \r\nLogistic Regression:\r\n\r\nComparison 1: ElasticNet formulation with OWLQN and NonlinearMinimizer with g(z)=ProximalL1 (nlLogistic)\r\n\r\nRuntime:\r\n\r\nowlqn 59.57 ms iters 62 nlLogistic 185.436 ms iters 33\r\n\r\nSolution difference:\r\n\r\n||owlqn - nlLogistic|| norm 0.41682550361219334 inf-norm 0.10509790307392614\r\n\r\nowlqnLogistic objective 30.83266520992968\r\nnlLogistic objective 30.817377544996752\r\n\r\nWe are ~3X compared to OWLQN but again the objective is better. So NonlinearMinimizer is producing better solution. Also see that the solutions are completely different. I have looked at the solutions. Both are sparse.\r\n\r\nComparison 2: Logistic Regression + L2 regularization with Bounds using PQN and NonlinearMinimizer with g(z) = ProximalBox (nlBox) \r\n\r\npqnBox 226.606 ms iters 29 nlBox 1283.92 ms iters 263\r\npqn loss 57.56457339692869\r\nnl loss 57.50013311157119\r\n\r\nWe are ~ 5X slower than PQN but producing better solution quality.\r\n\r\nNext steps:\r\n\r\n1. Runtime optimization to bring centralized ADMM closer to projected gradient algorithms (OWLQN, PQN)\r\n2. Add proximal algorithm for probability simplex 1'x = 1, x >=0 (Centralized ADMM can solve it but not OWLQN/PQN)\r\n3. Formulate MLE loss in mllib ALS and solve it using NonlinearMinimizer for PLSA formulation\r\n4. Code refactoring and use Iterator pattern.\r\n5. Test-cases showing up the objective improvement compared to OWLQN/PQN.\r\n\r\nI wanted to open it up for early reviews. QuadraticMinimizer as mentioned here is the following PR:\r\nhttps://github.com/scalanlp/breeze/pull/321","created_at":"2015-02-11T07:48:38Z","updated_at":"2015-02-17T20:01:10Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/scalanlp/breeze/pulls/364/commits","review_comments_url":"https://api.github.com/repos/scalanlp/breeze/pulls/364/comments","review_comment_url":"https://api.github.com/repos/scalanlp/breeze/pulls/comments/{number}","comments_url":"https://api.github.com/repos/scalanlp/breeze/issues/364/comments","statuses_url":"https://api.github.com/repos/scalanlp/breeze/statuses/ce8638fb697880158971e1dd70b94841e066e166","head":{"label":"debasish83:nlqp","ref":"nlqp","sha":"ce8638fb697880158971e1dd70b94841e066e166","user":{"login":"debasish83","id":510896,"avatar_url":"https://avatars.githubusercontent.com/u/510896?v=3","gravatar_id":"","url":"https://api.github.com/users/debasish83","html_url":"https://github.com/debasish83","followers_url":"https://api.github.com/users/debasish83/followers","following_url":"https://api.github.com/users/debasish83/following{/other_user}","gists_url":"https://api.github.com/users/debasish83/gists{/gist_id}","starred_url":"https://api.github.com/users/debasish83/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debasish83/subscriptions","organizations_url":"https://api.github.com/users/debasish83/orgs","repos_url":"https://api.github.com/users/debasish83/repos","events_url":"https://api.github.com/users/debasish83/events{/privacy}","received_events_url":"https://api.github.com/users/debasish83/received_events","type":"User","site_admin":false},"repo":{"id":18274015,"name":"breeze","full_name":"debasish83/breeze","owner":{"login":"debasish83","id":510896,"avatar_url":"https://avatars.githubusercontent.com/u/510896?v=3","gravatar_id":"","url":"https://api.github.com/users/debasish83","html_url":"https://github.com/debasish83","followers_url":"https://api.github.com/users/debasish83/followers","following_url":"https://api.github.com/users/debasish83/following{/other_user}","gists_url":"https://api.github.com/users/debasish83/gists{/gist_id}","starred_url":"https://api.github.com/users/debasish83/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debasish83/subscriptions","organizations_url":"https://api.github.com/users/debasish83/orgs","repos_url":"https://api.github.com/users/debasish83/repos","events_url":"https://api.github.com/users/debasish83/events{/privacy}","received_events_url":"https://api.github.com/users/debasish83/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/debasish83/breeze","description":"Breeze is a numerical processing library for Scala.","fork":true,"url":"https://api.github.com/repos/debasish83/breeze","forks_url":"https://api.github.com/repos/debasish83/breeze/forks","keys_url":"https://api.github.com/repos/debasish83/breeze/keys{/key_id}","collaborators_url":"https://api.github.com/repos/debasish83/breeze/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/debasish83/breeze/teams","hooks_url":"https://api.github.com/repos/debasish83/breeze/hooks","issue_events_url":"https://api.github.com/repos/debasish83/breeze/issues/events{/number}","events_url":"https://api.github.com/repos/debasish83/breeze/events","assignees_url":"https://api.github.com/repos/debasish83/breeze/assignees{/user}","branches_url":"https://api.github.com/repos/debasish83/breeze/branches{/branch}","tags_url":"https://api.github.com/repos/debasish83/breeze/tags","blobs_url":"https://api.github.com/repos/debasish83/breeze/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/debasish83/breeze/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/debasish83/breeze/git/refs{/sha}","trees_url":"https://api.github.com/repos/debasish83/breeze/git/trees{/sha}","statuses_url":"https://api.github.com/repos/debasish83/breeze/statuses/{sha}","languages_url":"https://api.github.com/repos/debasish83/breeze/languages","stargazers_url":"https://api.github.com/repos/debasish83/breeze/stargazers","contributors_url":"https://api.github.com/repos/debasish83/breeze/contributors","subscribers_url":"https://api.github.com/repos/debasish83/breeze/subscribers","subscription_url":"https://api.github.com/repos/debasish83/breeze/subscription","commits_url":"https://api.github.com/repos/debasish83/breeze/commits{/sha}","git_commits_url":"https://api.github.com/repos/debasish83/breeze/git/commits{/sha}","comments_url":"https://api.github.com/repos/debasish83/breeze/comments{/number}","issue_comment_url":"https://api.github.com/repos/debasish83/breeze/issues/comments/{number}","contents_url":"https://api.github.com/repos/debasish83/breeze/contents/{+path}","compare_url":"https://api.github.com/repos/debasish83/breeze/compare/{base}...{head}","merges_url":"https://api.github.com/repos/debasish83/breeze/merges","archive_url":"https://api.github.com/repos/debasish83/breeze/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/debasish83/breeze/downloads","issues_url":"https://api.github.com/repos/debasish83/breeze/issues{/number}","pulls_url":"https://api.github.com/repos/debasish83/breeze/pulls{/number}","milestones_url":"https://api.github.com/repos/debasish83/breeze/milestones{/number}","notifications_url":"https://api.github.com/repos/debasish83/breeze/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/debasish83/breeze/labels{/name}","releases_url":"https://api.github.com/repos/debasish83/breeze/releases{/id}","created_at":"2014-03-30T21:16:03Z","updated_at":"2014-09-30T22:52:52Z","pushed_at":"2015-02-16T08:11:14Z","git_url":"git://github.com/debasish83/breeze.git","ssh_url":"git@github.com:debasish83/breeze.git","clone_url":"https://github.com/debasish83/breeze.git","svn_url":"https://github.com/debasish83/breeze","homepage":"www.scalanlp.org","size":25041,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"scalanlp:master","ref":"master","sha":"0f82f3648a609326200fc666a3ae240fdaf220c9","user":{"login":"scalanlp","id":103090,"avatar_url":"https://avatars.githubusercontent.com/u/103090?v=3","gravatar_id":"","url":"https://api.github.com/users/scalanlp","html_url":"https://github.com/scalanlp","followers_url":"https://api.github.com/users/scalanlp/followers","following_url":"https://api.github.com/users/scalanlp/following{/other_user}","gists_url":"https://api.github.com/users/scalanlp/gists{/gist_id}","starred_url":"https://api.github.com/users/scalanlp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scalanlp/subscriptions","organizations_url":"https://api.github.com/users/scalanlp/orgs","repos_url":"https://api.github.com/users/scalanlp/repos","events_url":"https://api.github.com/users/scalanlp/events{/privacy}","received_events_url":"https://api.github.com/users/scalanlp/received_events","type":"Organization","site_admin":false},"repo":{"id":246644,"name":"breeze","full_name":"scalanlp/breeze","owner":{"login":"scalanlp","id":103090,"avatar_url":"https://avatars.githubusercontent.com/u/103090?v=3","gravatar_id":"","url":"https://api.github.com/users/scalanlp","html_url":"https://github.com/scalanlp","followers_url":"https://api.github.com/users/scalanlp/followers","following_url":"https://api.github.com/users/scalanlp/following{/other_user}","gists_url":"https://api.github.com/users/scalanlp/gists{/gist_id}","starred_url":"https://api.github.com/users/scalanlp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scalanlp/subscriptions","organizations_url":"https://api.github.com/users/scalanlp/orgs","repos_url":"https://api.github.com/users/scalanlp/repos","events_url":"https://api.github.com/users/scalanlp/events{/privacy}","received_events_url":"https://api.github.com/users/scalanlp/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scalanlp/breeze","description":"Breeze is a numerical processing library for Scala.","fork":false,"url":"https://api.github.com/repos/scalanlp/breeze","forks_url":"https://api.github.com/repos/scalanlp/breeze/forks","keys_url":"https://api.github.com/repos/scalanlp/breeze/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scalanlp/breeze/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scalanlp/breeze/teams","hooks_url":"https://api.github.com/repos/scalanlp/breeze/hooks","issue_events_url":"https://api.github.com/repos/scalanlp/breeze/issues/events{/number}","events_url":"https://api.github.com/repos/scalanlp/breeze/events","assignees_url":"https://api.github.com/repos/scalanlp/breeze/assignees{/user}","branches_url":"https://api.github.com/repos/scalanlp/breeze/branches{/branch}","tags_url":"https://api.github.com/repos/scalanlp/breeze/tags","blobs_url":"https://api.github.com/repos/scalanlp/breeze/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scalanlp/breeze/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scalanlp/breeze/git/refs{/sha}","trees_url":"https://api.github.com/repos/scalanlp/breeze/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scalanlp/breeze/statuses/{sha}","languages_url":"https://api.github.com/repos/scalanlp/breeze/languages","stargazers_url":"https://api.github.com/repos/scalanlp/breeze/stargazers","contributors_url":"https://api.github.com/repos/scalanlp/breeze/contributors","subscribers_url":"https://api.github.com/repos/scalanlp/breeze/subscribers","subscription_url":"https://api.github.com/repos/scalanlp/breeze/subscription","commits_url":"https://api.github.com/repos/scalanlp/breeze/commits{/sha}","git_commits_url":"https://api.github.com/repos/scalanlp/breeze/git/commits{/sha}","comments_url":"https://api.github.com/repos/scalanlp/breeze/comments{/number}","issue_comment_url":"https://api.github.com/repos/scalanlp/breeze/issues/comments/{number}","contents_url":"https://api.github.com/repos/scalanlp/breeze/contents/{+path}","compare_url":"https://api.github.com/repos/scalanlp/breeze/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scalanlp/breeze/merges","archive_url":"https://api.github.com/repos/scalanlp/breeze/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scalanlp/breeze/downloads","issues_url":"https://api.github.com/repos/scalanlp/breeze/issues{/number}","pulls_url":"https://api.github.com/repos/scalanlp/breeze/pulls{/number}","milestones_url":"https://api.github.com/repos/scalanlp/breeze/milestones{/number}","notifications_url":"https://api.github.com/repos/scalanlp/breeze/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scalanlp/breeze/labels{/name}","releases_url":"https://api.github.com/repos/scalanlp/breeze/releases{/id}","created_at":"2009-07-08T23:22:52Z","updated_at":"2015-02-17T05:40:23Z","pushed_at":"2015-02-17T05:40:23Z","git_url":"git://github.com/scalanlp/breeze.git","ssh_url":"git@github.com:scalanlp/breeze.git","clone_url":"https://github.com/scalanlp/breeze.git","svn_url":"https://github.com/scalanlp/breeze","homepage":"www.scalanlp.org","size":28669,"stargazers_count":879,"watchers_count":879,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":236,"mirror_url":null,"open_issues_count":54,"forks":236,"open_issues":54,"watchers":879,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/364"},"html":{"href":"https://github.com/scalanlp/breeze/pull/364"},"issue":{"href":"https://api.github.com/repos/scalanlp/breeze/issues/364"},"comments":{"href":"https://api.github.com/repos/scalanlp/breeze/issues/364/comments"},"review_comments":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/364/comments"},"review_comment":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/scalanlp/breeze/pulls/364/commits"},"statuses":{"href":"https://api.github.com/repos/scalanlp/breeze/statuses/ce8638fb697880158971e1dd70b94841e066e166"}}}}