Timeline for Minimize sum of $\ell_2$ norm and linear combination, on simplex
Current License: CC BY-SA 3.0
41 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jun 13, 2016 at 1:38 | history | edited | dohmatob | CC BY-SA 3.0 |
added 15 characters in body
|
| Jun 13, 2016 at 1:12 | history | edited | dohmatob | CC BY-SA 3.0 |
added 60 characters in body
|
| Jun 12, 2016 at 18:50 | history | edited | dohmatob | CC BY-SA 3.0 |
deleted 18 characters in body
|
| Jun 12, 2016 at 9:21 | history | edited | dohmatob | CC BY-SA 3.0 |
added 4 characters in body
|
| Jun 12, 2016 at 9:14 | history | edited | dohmatob | CC BY-SA 3.0 |
added 1 character in body
|
| Jun 12, 2016 at 8:57 | history | edited | dohmatob | CC BY-SA 3.0 |
added 1 character in body
|
| S Dec 26, 2015 at 11:30 | history | bounty ended | CommunityBot | ||
| S Dec 26, 2015 at 11:30 | history | notice removed | CommunityBot | ||
| Dec 23, 2015 at 19:47 | history | edited | dohmatob | CC BY-SA 3.0 |
added 73 characters in body
|
| Dec 22, 2015 at 9:07 | history | edited | dohmatob | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Dec 22, 2015 at 9:04 | comment | added | dohmatob | Its more than just a "verbose version of @fedja's answer". It contains a rigorous proof of q-linear convergence of the iterates, in the small perturbation régime. Glad to hear this is all useful afterall :) | |
| Dec 21, 2015 at 23:39 | comment | added | Yi Liu | Thank you for writing up a verbose version of fedja's answer to make it easier to follow for folks like me | |
| Dec 21, 2015 at 20:35 | history | edited | dohmatob | CC BY-SA 3.0 |
added 29 characters in body
|
| Dec 21, 2015 at 15:08 | history | edited | dohmatob | CC BY-SA 3.0 |
added 70 characters in body
|
| Dec 21, 2015 at 15:01 | history | edited | dohmatob | CC BY-SA 3.0 |
deleted 15 characters in body
|
| Dec 21, 2015 at 14:52 | history | edited | dohmatob | CC BY-SA 3.0 |
deleted 7 characters in body
|
| Dec 21, 2015 at 14:42 | history | edited | dohmatob | CC BY-SA 3.0 |
added 490 characters in body
|
| Dec 20, 2015 at 17:38 | history | edited | dohmatob | CC BY-SA 3.0 |
added 2392 characters in body
|
| Dec 20, 2015 at 17:23 | history | edited | dohmatob | CC BY-SA 3.0 |
added 2392 characters in body
|
| Dec 20, 2015 at 17:17 | history | edited | dohmatob | CC BY-SA 3.0 |
added 2392 characters in body
|
| Dec 20, 2015 at 17:12 | history | edited | dohmatob | CC BY-SA 3.0 |
added 2392 characters in body
|
| Dec 20, 2015 at 5:17 | answer | added | fedja | timeline score: 9 | |
| S Dec 18, 2015 at 9:45 | history | bounty started | dohmatob | ||
| S Dec 18, 2015 at 9:45 | history | notice added | dohmatob | Canonical answer required | |
| Dec 18, 2015 at 9:41 | history | edited | dohmatob | CC BY-SA 3.0 |
added 13 characters in body
|
| Dec 10, 2015 at 7:50 | history | edited | dohmatob | CC BY-SA 3.0 |
added 260 characters in body
|
| Dec 7, 2015 at 19:14 | history | edited | dohmatob | CC BY-SA 3.0 |
added 12 characters in body
|
| Dec 6, 2015 at 17:11 | history | edited | dohmatob | CC BY-SA 3.0 |
deleted 6 characters in body
|
| Dec 6, 2015 at 16:05 | comment | added | Suvrit | I already noted this (worst-case median algo) in my 2nd comment. Also, I'll not ask you to make good on your offer of a \$ --- :-) | |
| Dec 6, 2015 at 15:53 | comment | added | dohmatob | Oops! Looks like I'm the one who needs to re-read the paper carefully. You're right. Algorithm 3 has linear worst-case running time if the pivot is computed with a mom's (median-of-medians) algorithm (see last paragraph of page 4). | |
| Dec 6, 2015 at 15:43 | comment | added | Suvrit | What do you say to the 4th row of Table 1 on page 7? That's where I read their worst case $O(n)$ claim. | |
| Dec 6, 2015 at 15:34 | comment | added | dohmatob | Please re-read the Condat paper carefully. The algorithm proposed in the paper (Algorithm 3) has linear expected running time, not linear worst-case running time. Even the authors of that paper admit this fact cautiously. I'll offer you a dollar if you can exhibit (of course, with proofs!) an algorithm for projecting onto the simplex with linear worst-case running time :) | |
| Dec 6, 2015 at 15:08 | comment | added | Suvrit | But there exist methods for worst-case linear time median finding (they might be empirically a bit slower, because of constants in the big-Oh) --- so the true complexity of this problem is $O(n)$ (using pivoting methods with worst-case linear time median finding routines). And to disprove your claim on "no method is likely to exist" have a look at: gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/… | |
| Dec 6, 2015 at 10:44 | comment | added | dohmatob | @Suvrit: For the problem of projecting onto a simplex, there are indeed randomized algorithms (for example based on randomized median-finding) with linear average running time, but no algorithm with linear worst-case running time is known, nor is likely to exist... | |
| Dec 6, 2015 at 3:08 | comment | added | Suvrit | btw, projection onto simplex is solvable in $O(n)$ also, no need of the extra $\log n$ in there.... | |
| Dec 5, 2015 at 22:36 | history | edited | dohmatob | CC BY-SA 3.0 |
added 25 characters in body
|
| Dec 5, 2015 at 21:48 | history | edited | dohmatob | CC BY-SA 3.0 |
added 212 characters in body
|
| Dec 5, 2015 at 21:33 | history | edited | dohmatob | CC BY-SA 3.0 |
added 811 characters in body
|
| Dec 5, 2015 at 21:30 | review | Low quality posts | |||
| Dec 5, 2015 at 21:35 | |||||
| Dec 5, 2015 at 21:12 | history | asked | dohmatob | CC BY-SA 3.0 |