3 ms·

Is it a groundbreaking better way to approximate continuous functions, or is it fundamentally impractical, like new algorithms with a good asymptotic time often

by kubb 5y ago

Is it a groundbreaking better way to approximate continuous functions, or is it fundamentally impractical, like new algorithms with a good asymptotic time often are? I'm curious to know, but my mathematical illiteracy prevents me from reading the paper.

kiengcan9999 5y ago
From abstract: "Our method is the first variant of Newton’s method that has both cheap iterations and provably fast global convergence". It seems interesting.
- rwilson4 5y ago
  "Cheap iterations" led me to expect a 1st order method, not requiring computing the matrix of 2nd derivatives, which is the bottleneck in large systems. But this does indeed rely on the Hessian, so I'm not sure what makes the iterations "cheap".
  - MauranKilom 5y ago
    If you don't want to compute the Hessian, you're at the wrong address with Newton's method. Quasi-Newton methods is where you want to look.
    - rwilson4 5y ago
      Sure, or Nesterov's accelerated gradient descent or something. I'm just not sure what the authors mean by "cheap iterations". Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.
rwilson4 5y ago
This is an approach for solving convex optimization problems. An optimization problem is when you want to find the best option, or the fastest, or the most profitable. If you're asking questions with superlatives (most, best, fastest), you may be working on an optimization problem. Many optimization problems are NP Hard and cannot be solved in a reasonable amount of time. Convex optimization problems are a special subclass which can typically be solved efficiently (meaning in polynomial time). This paper provides a new approach to solving Convex Optimization problems for systems where other methods struggle.
MauranKilom 5y ago
Newton's method is not for function approximation, but for optimization ("find the minimum"). Newton's method already has "good asymptotic time" (e.g. if you use it to compute a square root, you double the number of correct digits with each step!) - but only under certain conditions (e.g. "not too far from the solution"). This paper shows how to modify it so this sort of benefit is obtained under a wider range of conditions ("global"). There are other related methods with a similar goal, but some require more expensive computations. The method from the paper appears to fill a sweet spot in high-dimensional optimization by virtue of requiring "few" matrix inversions (or linear solves) while having very good convergence properties. When you are dealing with the kind of problem that this sort of method is applicable to, it appears to me that you might benefit from looking into using this method. But it's not a revolutionary improvement from what I can tell - there are many related methods, and chances are you could have used something similar for similar benefit already. And it's likely that someone already used more or less this method in practice. As the paper notes: > Our goal is twofold. On the one hand, we are interested in designing methods that are useful for applications and can be used without any change as black-box tools. On the other hand, we hope that our theory will serve as the basis for further study of globally-convergent second-order and quasi-Newton methods with superior rates. Although many of the ideas that we discuss in this paper are not new and have been observed by practitioners to help solve challenging optimization problems, our analysis, however, is the first of its kind. We hope that our theory will lead to appearance of new methods that are motivated by the theoretical insights of our work.
plafl 5y ago
(note: comments based on a superficial read) I would say "interesting" more than "groundbreaking", in the sense that you will not solve problems that you were not previously solving. The benchmarks provided show nice convergence. The interesting part is that the method will not fail, which is very good. The benchmarks seem to crush other methods but keep in mind that the plots do not show "time required" but "number of iterations required" and that with Newton's method you are doing much much more work per iteration: computing the Hessian instead of the gradient and solving a system of linear equations on every iteration.

by kubb 5y ago

kiengcan9999 5y ago

From abstract: "Our method is the first variant of Newton’s method that has both cheap iterations and provably fast global convergence". It seems interesting.

rwilson4 5y ago
"Cheap iterations" led me to expect a 1st order method, not requiring computing the matrix of 2nd derivatives, which is the bottleneck in large systems. But this does indeed rely on the Hessian, so I'm not sure what makes the iterations "cheap".
- MauranKilom 5y ago
  If you don't want to compute the Hessian, you're at the wrong address with Newton's method. Quasi-Newton methods is where you want to look.
  - rwilson4 5y ago
    Sure, or Nesterov's accelerated gradient descent or something. I'm just not sure what the authors mean by "cheap iterations". Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.

rwilson4 5y ago

This is an approach for solving convex optimization problems. An optimization problem is when you want to find the best option, or the fastest, or the most profitable. If you're asking questions with superlatives (most, best, fastest), you may be working on an optimization problem. Many optimization problems are NP Hard and cannot be solved in a reasonable amount of time. Convex optimization problems are a special subclass which can typically be solved efficiently (meaning in polynomial time). This paper provides a new approach to solving Convex Optimization problems for systems where other methods struggle.

MauranKilom 5y ago

Newton's method is not for function approximation, but for optimization ("find the minimum"). Newton's method already has "good asymptotic time" (e.g. if you use it to compute a square root, you double the number of correct digits with each step!) - but only under certain conditions (e.g. "not too far from the solution"). This paper shows how to modify it so this sort of benefit is obtained under a wider range of conditions ("global"). There are other related methods with a similar goal, but some require more expensive computations. The method from the paper appears to fill a sweet spot in high-dimensional optimization by virtue of requiring "few" matrix inversions (or linear solves) while having very good convergence properties. When you are dealing with the kind of problem that this sort of method is applicable to, it appears to me that you might benefit from looking into using this method. But it's not a revolutionary improvement from what I can tell - there are many related methods, and chances are you could have used something similar for similar benefit already. And it's likely that someone already used more or less this method in practice. As the paper notes: > Our goal is twofold. On the one hand, we are interested in designing methods that are useful for applications and can be used without any change as black-box tools. On the other hand, we hope that our theory will serve as the basis for further study of globally-convergent second-order and quasi-Newton methods with superior rates. Although many of the ideas that we discuss in this paper are not new and have been observed by practitioners to help solve challenging optimization problems, our analysis, however, is the first of its kind. We hope that our theory will lead to appearance of new methods that are motivated by the theoretical insights of our work.

plafl 5y ago

(note: comments based on a superficial read) I would say "interesting" more than "groundbreaking", in the sense that you will not solve problems that you were not previously solving. The benchmarks provided show nice convergence. The interesting part is that the method will not fail, which is very good. The benchmarks seem to crush other methods but keep in mind that the plots do not show "time required" but "number of iterations required" and that with Newton's method you are doing much much more work per iteration: computing the Hessian instead of the gradient and solving a system of linear equations on every iteration.