4 ms·

Can you elaborate a bit on the applicability of those methods for general optimization? Are they significantly better than [stochastic] Gradient descent or Sadd

Can you elaborate a bit on the applicability of those methods for general optimization? Are they significantly better than [stochastic] Gradient descent or Saddle free newtons method? For what kinds of landscapes/dimensions it does well?

zzleeper 11y ago
Well their paper that I'm reading is about solving systems of equations (Ax=b) where the matrix has a special form (diagonally dominant), which is also a huge contribution. It also uses a similar idea to the convex optimization paper (to find the "dual" problem and try to solve it) so I would guess it has similar issues: - Very very VERY complex to code, compared to e.g. PCG - Although it is asymptotically faster, the constant terms that you have to amortize might be very large. For instance, imagine you can sort on O(n) instead of on O(n log n) but the constant on the first case is a thousand times larger than on the second. All in all, I am very interested about it, but you will need some valiant efforts in order to implement it efficiently.
- darkmighty 11y ago
  Thanks. I don't have much knowledge on the field; I was wondering what important problems involve large linear systems and/or convex optimization. Here's an expert from the wiki if anyone's interested: "Convex minimization has applications in a wide range of disciplines, such as automatic control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, statistics (optimal design), and finance." I wonder if we could use convex optimization techniques to solve non convex problems (and occasionally jump out of local minima traps?)
- petra 11y ago
  Maybe spiral can automate much of this work ? http://spiral.net/ http://spiral.net/ http://www.spiralgen.com/ http://www.spiralgen.com/
  - zzleeper 11y ago
    Seems interesting but after spending 5 minutes on the site, I have no idea how to set it up or use it..
    - petra 11y ago
      I don't think they have a free version.
jules 11y ago
These are algorithms for convex optimization whereas stochastic gradient descent and saddle free newton are generally used for nonconvex optimization (neural nets in particular).

zzleeper 11y ago

Well their paper that I'm reading is about solving systems of equations (Ax=b) where the matrix has a special form (diagonally dominant), which is also a huge contribution. It also uses a similar idea to the convex optimization paper (to find the "dual" problem and try to solve it) so I would guess it has similar issues: - Very very VERY complex to code, compared to e.g. PCG - Although it is asymptotically faster, the constant terms that you have to amortize might be very large. For instance, imagine you can sort on O(n) instead of on O(n log n) but the constant on the first case is a thousand times larger than on the second. All in all, I am very interested about it, but you will need some valiant efforts in order to implement it efficiently.

darkmighty 11y ago
Thanks. I don't have much knowledge on the field; I was wondering what important problems involve large linear systems and/or convex optimization. Here's an expert from the wiki if anyone's interested: "Convex minimization has applications in a wide range of disciplines, such as automatic control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, statistics (optimal design), and finance." I wonder if we could use convex optimization techniques to solve non convex problems (and occasionally jump out of local minima traps?)
petra 11y ago
Maybe spiral can automate much of this work ? http://spiral.net/ http://spiral.net/ http://www.spiralgen.com/ http://www.spiralgen.com/
- zzleeper 11y ago
  Seems interesting but after spending 5 minutes on the site, I have no idea how to set it up or use it..
  - petra 11y ago
    I don't think they have a free version.

jules 11y ago

These are algorithms for convex optimization whereas stochastic gradient descent and saddle free newton are generally used for nonconvex optimization (neural nets in particular).