13

I graduated from my PhD last November and as I get along super well with my PhD supervisors, I decided to pursue research with them on my free time alongside my postdoctoral position.

We all have spent a large amount of working time (I can't say if it's months or years!) to make an idea concrete.

However, things did not go as planned.

Numerical experiments of our work shows that it can only remain theoretical.

Most specifically, our model works for very tiny instances (up to 15 nodes, in graph theory) and can not scale up at all. It already takes between one hour and two hours to solve such instances.

For real life size instances (starting at 50 nodes), the model would take far longer than hours to solve.

How should we proceed with such failing idea?

As my professor wanted me to think of a detailed plan of action, here are my thoughts to be improved, corrected and completed:

A theoretical model is still interesting to publish as eventually, computers performances will improve over time and maybe this model will serve on real life instances some day. Still this is disappointing to say it cannot scale up. Maybe some other researches will find ideas to make it applicable once it has been published? Another possibility is to try improving the theoretical model but how could we know if this would last six months or 10 more years? We are currently out of ideas to make the model better after having tested a tons of ideas (some of them improved the model performances by 10%, some small ideas were thrown up, etc.) A final possibility is to give up the research we conducted but to me, this is unacceptable with respect to the amount of quality work on this research topic. This is a year a half of my thesis and several months after.

10
  • 18
    Have you consulted with an algorithms expert? Does your model require solving an NP-hard problem? The right computer scientist could perhaps tell why your model is slow without even touching a computer. That might inform next steps. Feb 18 at 0:23
  • 3
    @AlexanderWoo, thank you for your comment. I believe my professor is an algorithm expert. Indeed we are solving a NP-Hard problem, we are working with knowledges on computer science and operations research. This is an interesting suggestion to ask for another expert's opinion
    – JKHA
    Feb 18 at 0:38
  • 5
    @AlexanderWoo I strongly disagree with your suggestion to close, since I think folks run into this sort of dilemma frequently. I'd suggest that you put your advice in an answer instead.
    – jakebeal
    Feb 18 at 13:03
  • 2
    In my field months of computing hours are common, why is it a problem in your field that it can take many hours or days to solve real life size instances? Ps: I suggest you to make your question more concise, I don't see why your relationship with your previous supervisors matters to the question.
    – The Doctor
    Feb 18 at 13:54
  • 9
    @AlexanderWoo: this question strongly depends on the norms and values of your research community – … and as such it is on-topic here, because it is about the norms and values of academia (as opposed to the content of research). Sure, at the end of the day, the asker needs to evaluate whether further pursuing this path is worth the effort. But that’s exactly what the question is about (in my understanding): how to make the decision and not what to decide.
    – Wrzlprmft
    Feb 18 at 15:36

6 Answers 6

26

You did not have a failing idea. You just had an idea that did not scale (if I understood you correctly). These are two very different things.

Your approach brings a model to the table and a proof-of-concept study. That's the novelty. Maybe at some point, it is possible to scale it, via better computers, clever classical or quantum algorithms or possibly suitable approximations or probabilistic algorithms that do not guarantee results 100%.

There are instances where there is a cool idea that scales horribly, and then, after some time, people find excellent, and highly performative algorithms that scale much better; maybe with some compromise, such as approximation, random sampling or other. I know of a model for which no good approximation for around 6 years was known, scaling horribly, for which no obvious route to improvement was conceivable. The following years saw a spate of reasonable, if not gargantuan improvements. 15 years later a highly effective and elegant approximation was discovered. This is a very fast rate of improvement.

Even in the well-known realm of matrix multiplication, the naive O(n^3) algorithm can be substantially improved (I believe it's around O(n^2.372) now.

In short, the fact that it cannot be computed now, does not mean it cannot be computed in the future. If you have an interesting question, model and theory, it's definitely worth publishing.

7
  • 1
    The last paragraph is unknown here - there could be known theoretical reasons why this cannot be computed, ever. Assuming P<>NP, there are indeed theoretical bounds on how well and how quickly solutions to NP-hard problems can be approximated. Feb 18 at 20:39
  • 1
    @MarcGlisse: Indeed, they're "galactic algorithms", only faster with ridiculous problem sizes. Strassen's is useful in practice (n>100). en.wikipedia.org/wiki/… , O(n^2.807). Same with BigInt multiply: Did the 2019 discovery of O(N log(N)) multiplication have a practical outcome? - no, Toom-Cook and Schönhage-Strassen are still the best practical algorithms for big problem sizes that fit on real computers (at least that anyone's interested in actually computing.) Feb 18 at 22:01
  • 1
    @PeterCordes Of course, but for instance Shannon codes show that you may have excellent feasible approximations where the asymptotically precise calculation is galactic. The point is that, in general, you do not know if all good complexity calculations are galactic. Feb 18 at 23:23
  • 2
    Even things that don't scale can have value. For example, the typical person wanting a traveling salesman solver is looking to optimize a couple dozen stops at most.
    – Mark
    Feb 20 at 23:48
  • 1
    Interestingly, TSP can actually be solved for much bigger problems than required in practice. For example “shortest path to visit all US cities with a population over 100,000”. This can be solved but the tour will take weeks or months.
    – gnasher729
    Feb 21 at 9:59
33

Negative results are still results!

In my career, I've had a lot of ideas that have worked out, and also a lot of ideas that have not worked out. But when you've spent a lot of time on a project, you've almost always learned some things, even if they weren't the things you hoped for. Share that knowledge with others!

I always think that the saddest possible fate for a piece of work you've poured a lot of time and effort into is to have it die quietly in the dark. Instead, you can at least write a paper as a grave marker to mourn its passing:

Let me tell you about the life of my friend, Nifty New Graph Model (NNGM). NNGM was a bright and promising idea, full of energy and wanting to help people with [relevant application here]. When NNGM was young, it seemed full of promise, all the way up to around 15 nodes. But as it scaled, everything seemed to go wrong. And when we did tests, we got the fatal diagnosis: Bad Big O. Well, we knew then that NNGM didn't have the future we'd all hoped for, and so we're putting it into cryogenic storage. But we wanted to tell its story here: maybe others can learn from our experiences, or maybe even figure out how to cure NNGM's problems and bring it out of storage in the future.

Silly? A little, maybe, but I find that publishing a story like this (in more professional language, of course) really helps me to let go and move on. You won't put it in a glamour journal, but there's always solid society-level publications or megajournals that are happy to accept results that are true but not exciting.

And sometimes these articles really can be helpful to others too! Some of my own "gravestone" publications have dozens of citations, clearly having picked up an afterlife that I had never envisioned for them.

Bottom line: publish the sad things that you've learned, and then move on.

10
  • 11
    +1. This is a vital idea. Research isn't to prove our initial guesses but to arrive at knowledge and truth. Knowing something doesn't work can be as (more) important than knowing it does. Hydroxychloroquine.
    – Buffy
    Feb 18 at 13:22
  • 6
    In theoretical mathematics, if you are aiming for a research-oriented job, then I think writing this up is at best a waste of time. Researchers who have several such papers in fact LOSE prestige for this work - people wonder why they're wasting their time with it. And - no - the research community doesn't gain from the paper because we just won't find it; I still think there's a good chance that a determinantal identity that would solve the conjectures in my dissertation is in some 19th century paper somewhere, but no one will ever find it. Feb 18 at 20:48
  • 1
    I agree @AlexanderWoo. Negative results are not usually published in mathematics (though I agree with Captain Emacs on the nature of this work). They're at best a good candidate for something in a blog post, but most mathematicians don't keep up a math blog, so it is likely not to gain any real attention. Feb 18 at 21:54
  • 1
    @Trunk - as opposed to applied mathematics. Some of us are staying away from the term 'pure mathematics' because the notion of 'purity' has unfortunate historical connotations (that are in fact historically related to the origins of the usage of the term 'pure mathematics'). Feb 21 at 0:34
  • 2
    @AlexanderWoo Which may be true but is actually quite idiotic. So OP and his colleagues had this great idea which didn’t work out. If nobody writes it down, it will still look like a great idea, and the next guy will look at it, and waste another year of time. And another one in two years time.
    – gnasher729
    Feb 21 at 9:54
11

Generally if there is a good method that doesn't scale well, it is sometimes possible to develop a scalable algorithm that approximates the method well. Of course you can collaborate with people who have the expertise for this, but even without such a thing, I think that a publication is realistic that in its conclusion clearly says that right now scalability is an issue and finding an approximation that improves scalability is a worthwhile project for future research. This may not fly in a strong impact journal, but there are many journals that would be keen to publish something that is original, correct, and presented with insight even if scalability is an issue. I have seen such papers. And somebody may later dig it out and develop a better algorithm or do something new inspired by this.

2
  • Something that I forgot to mention in my question is that my former PhD director nearly only publish on top journals with high impact and, if I understood their working habits well, would not let our work to be submitted to a "middle" journal and will continue try to make the model as good as possible
    – JKHA
    Mar 10 at 1:34
  • @JKHA Well, if you can get it into a top journal, fine. If you can't, but are personally interested in having it published at a somewhat lower level (for a fresh PhD with academic ambitions every publication counts), better than making assumptions talk with them! Mar 10 at 11:40
9

First, stop berating yourself! You worked hard, you achieved a result ... and you have discovered the limits to which your results can be applied with current technology or, perhaps, pushed using current methods.

This is how much of mathematics proceeds. The work is incremental. One need only look at the history of the Fast Fourier Transform (FFT) algorithm to see that it took 160 years to get from Gauss's initial approach to the Cooley-Tukey publication in 1965. Tukey and Cooley had the significant advantage of having at their disposal a object that only came into being around 1940 ... a computer! Prior to that, the possibility of applying the FFT to siginficant problems was largely beyond reach ... the same scaling issue as is staring at you. Should Gauss have been embarrassed?

Consider also the paper by Terrence Tao on what constitutes good mathematics in which he presents a very incomplete list and even then, concludes "As the above list demonstrates, the concept of mathematical quality is a high-dimensional one and lacks an obvious canonical total ordering."

My advice: if you have not already done so, consult with someone who is an expert in relevant algorithms; they might have an insight that would lead to an improvement in scaling. But then, irrespective of the outcome of the consultation, write up what you have without feeling that it was a failed idea. Then move on.

Appendix: As an aside, although I have put in references to the history of the FFT, a more personal view is evident in the paper by Cooley that you can find here.

5

Firstly, thank your lucky stars for having a sympathetic research milieu. Few enjoy such bounties.

Others have clarified the need to publish what you have (originally at least) done, regardless of its limitations as a tool with a practical future.

The question of where to go from here with this is the one I'll answer.

Regardless of whether you intend to have another crack at this matter, i.e. to devise a new model or to seek ways to make the existing one more computation-efficient, I think your conscious mind needs a rest from this topic right now.

A change is as good as a rest, they say. And looking at other topics and their challenges may well throw up the odd idea on how to advance the old intractable one.

Sometimes it is only when we accept "defeat" with a challenge that our mind is freed of those trammelled patterns of thought that led us nowhere and the real path forward starts to dawn on us.

0

From what I understand, the result of your research is that you have indeed solved a mathematical problem, just that it is not applicable to real life scenarios.

Are you aware that most of what makes our computers work, is based on papers from the '50s when it was also entirely unfeasible to make practical use of them ?

So my suggestion is to publish. You don't know what the future brings.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .