Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for different purposes?
I couldn't find any exact definition for this term, though I have found examples of meta-algorithms such as Boosting in machine learning.
I interpret it as meaning "algorithmic technique". It's a general framework that can be used to solve a number of problems.
Don't worry too much about the meaning of that phrase. It's not something with an accepted definition, and you don't need to understand it to gain the value from that survey paper; it's just a passing phrase. Instead, focus on understanding the ideas and technical results in the survey paper.
The term "meta-algorithm" has a fairly well-accepted meaning in the context of learning theory, which is the field of research from which multiplicative weights originates.
Specifically, a meta-algorithm, in the context of learning theory, is an algorithm that decides how to take a set of other (typically, though not necessarily non-meta) "algorithms" (which might be as dumb as a constant output, for example), and constructs a new algorithm out of those, often by combining or weighting the outputs of the component algorithms. (Don't take this to be a canonical definition though.) Typically those component algorithms are viewed as black-boxes taking input and producing their output, with the inner workings hidden/irrelevant.
There are a number of examples of meta-algorithms. The referenced Multiplicative Weighting algorithm is one example. A particularly simple example is majority voting for an ensemble of binary classifiers: Suppose you have a bunch of binary classification algorithms, and you don't know how to pick a good one. You can just compute them all, and let them vote. Voting in this case is the meta-algorithm. Of course, this may not work very well, and you might want to do something like weighted voting, where the weight somehow scales with observed performance.
Just a few examples of meta-algorithms that I can think of at the moment:
As always, you can find examples that blur the line between meta and not meta. For example, K-nearest neighbors could be considered a weighted voting/averaging of component algorithms, where every potential neighbor (i.e. the labeled points in the dataset) is its own component algorithm, having a constant output, and the weighting is a function of distance from the algorithm input.
