6
$\begingroup$

This question is prompted by this post on genetic algorithms, but I think the matter applies more generally as well to other metaheuristic methods like annealing, neural networks and the like.

Are these reasonable topics for discussion on this site ? They are weak on pure theoretical content, but they do crop up "when the theory fails", and there's been a fair amount of discussion on theory blogs (see Michael Mitzenmacher, and myself) on whether these should be taught in algorithms classes, which would make them fair game.

$\endgroup$
9
  • $\begingroup$ disagree with the [apparent widely shared] bias that heuristic methods in TCS are "weak on pure theoretical content", whatever that means, to me some of them are stronger on theory than much of other "mainstream" TCS subjs. & feel the tiein to "when the theory fails" is defn a nonsequitur. but am indeed attempting to understand this perspective more .. can anyone articulate it better via refs etc? to me it seems like a concept bordering on academic folklore or even stigma/taboo.. also, plz forgive the question if basic, but what is the difference between a heuristic & a metaheuristic? $\endgroup$
    – vzn
    Sep 2, 2012 at 22:11
  • 1
    $\begingroup$ When I say "weak on pure theoretical content", I mean "weak on formal guarantees of quality/running time". This is not controversial - most heuristic methods are some kind of local search that deal with local optima and have weak convergence bounds. There is a formal treatment of such heuristics in the work on PLS, PPAD and the like. "Meta"-heuristics are techniques that apply generically to many different problems and are 'parametrized' for each problem: this is also not my term, it's used in the Encyclopedia of approximations $\endgroup$
    – Suresh Venkat
    Sep 3, 2012 at 1:34
  • $\begingroup$ thx for clarification yet feels like sleight of hand or moving goalposts to me =( .. two different concepts & seems there is a strong case there are many algorithms weak on formal guarantees yet still chock full of theory (some even more so than some algorithms with guarantees, because of emergent complexity involved). have never seen literature arguing otherwise & but am open to suggestions. moreover sometimes so-called "weak" algorithms deliver superior even extraordinary results in practice based on domain specific quality measurements. but agree your pov is defn not unique on this site. $\endgroup$
    – vzn
    Sep 3, 2012 at 2:32
  • $\begingroup$ @vzn: You and Suresh are talking about different kinds of "theory". TCS is about what we can prove about abstract computation. This is not controversial. $\endgroup$
    – Jeffε
    Sep 3, 2012 at 14:37
  • $\begingroup$ @JɛffE .. think your defn is unnec limiting & not unanimous, see 1st answer below which seems to directly contradict it, & measures last/current? group consensus on subj unless theres been sig. drift since posted. there is clearly sig. controversy over the scope of this site across many discussions in meta, easy to find it. there is no strict defn given in the FAQ of what TCS actually constitutes. that is not surprising because moreoever the field of TCS does not have such a consensus either. there are however many individuals in the field with strong but nonuniform opinions on the subj... $\endgroup$
    – vzn
    Sep 3, 2012 at 15:22
  • $\begingroup$ No, the first answer does not contradict my claim. "Rigorous theoretical analysis" means proof. $\endgroup$
    – Jeffε
    Sep 3, 2012 at 18:44
  • $\begingroup$ ps not all GAs seem to be provably within PLS or PPAD although it works as a rough approximation. some issues are that the fitness functions can have very high complexity, and also many of the algorithms are not really terminating. they are just run for very long and stopped in practice when improvement becomes negligible. proof is only one tool of rigorous theoretical analysis, admittedly one of the best & most unequivocal. proof is preferred where possible but often unattainable and sig. areas of TCS do not focus on it... in GAs "proof" is in fact discovered and computed by fitness fns! $\endgroup$
    – vzn
    Sep 3, 2012 at 18:51
  • $\begingroup$ (this is not sarcastic) Can you provide an example of "rigorous theoretical analysis" that doesn't involve a proof ? $\endgroup$
    – Suresh Venkat
    Sep 4, 2012 at 16:41
  • $\begingroup$ ?! dude, how about this? there is mass research on P vs NP and NP complete problems even though there is no proof that $\mathsf{ P \ne NP}$, and the problem has been open for four decades. or maybe you dont think it has any "rigorous theoretical analysis"? reading your original question above you came out as favoring scope that includes metaheuristics.... scratching my head over here.... $\endgroup$
    – vzn
    Sep 13, 2012 at 2:25

2 Answers 2

Reset to default
15
$\begingroup$

Please keep in mind that there are people who actually do rigorous theoretical analyses on metaheuristics. I cannot think of a good reason to just exclude everything related to metaheuristics. I would propose to decided it on a case by case basis depending on the theoretical merit of the question.

$\endgroup$
4
  • 2
    $\begingroup$ I agree. I can think of several questions relating to metaheuristics that I would think are interesting and in scope: what rigorous analysis has been done? Do we have any theoretical explanation for why rigorous analysis of metaheuristics seems so difficult? etc. $\endgroup$
    – Joshua Grochow
    Aug 24, 2010 at 1:45
  • $\begingroup$ ok fair enough. so what do you feel about this particular case then ? i.e genetic algorithms $\endgroup$
    – Suresh Venkat
    Aug 24, 2010 at 4:04
  • 4
    $\begingroup$ I fail to see any relation to theory in this particular question. $\endgroup$
    – Matthias
    Aug 24, 2010 at 8:57
  • $\begingroup$ ?? the answers to the genetic algorithms question seem all [including but not limited to] rigorous theoretical analyses on metaheuristics, written up in scientific papers and references $\endgroup$
    – vzn
    Sep 4, 2012 at 15:11
1
$\begingroup$

These questions are actually in-scope on the data analysis site. See this discussion on scope for that site.

I would argue that the CS Theory site should focus on more theoretical questions, and the given question was applied.

$\endgroup$

You must log in to answer this question.

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