I have a problem which I'm looking to see if there is literature on:

Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator talks to multiple Followers. The director gives simple commands to the Aggregator, who then can portion out the commands to each Follower as she sees fit.

The question then is, how can the Director know whether or not an Aggregator can complete a given request at time step T? T+1? If T is now, then this is relatively easy as the Aggregator can simply sum up the capabilities of each of the Followers and return it, saying "this is what I can do in total." The problem then is, if the Director is doing her own optimization problem in deciding how to direct two different Aggregators, given each command she must be able to predict how the Aggregator will react. I.e., what are the Aggregator's capabilities in time step T+1 given a direction D in time step T?

Due to the complexity of the Aggregator, I think it's likely best to create an estimator across the current state of the Aggregator (or all of their followers). Further, the Aggregator can give whatever knowledge it wants to the Director, though ideally this would be of constant size no matter the size of the set of Followers. This is therefor an optimization problem on the Aggregator's side for creating an optimal estimator, which is well studied.

What I want to know: Is there any literature about creating an estimator when you know the exact function you are estimating? So if I am the aggregator, how can I tell the Director, in a constant space for the amount of information I give no matter the number of followers, the information require to best predict I would react to a given direction?

Put another way: How can I create an optimal estimator in which I have full knowledge of the shape and composition of the functions I am estimating?

I can think of a number of places where this might occur, potentially in networking, data compression, etc., though I think I don't have the necessary vocabulary. I've tried searching through aggregation, optimization, estimation, forecasting, prediction, which a number of different combinations of keywords relating to these. There is a ton of generalized work on making estimators and predictors, though none which target the assumption that they already have perfect knowledge of that which they're estimating.

  • $\begingroup$ I'm not sure why the three roles are necessary to describe your problem. If there aren't, it might be better to give a less complicated formulation and put the three roles in some background info. Otherwise, it might be a good idea to explain why the three roles are important to the question. $\endgroup$
    – Discrete lizard
    Feb 14, 2017 at 8:30

1 Answer 1


Is there any literature about creating an estimator when you know the exact function you are estimating?

I think streaming algorithms may be of interest to you. A streaming algorithm is an algorithm that operates on some model of a massive 'stream' of data that is simply impossible to completely store, but it is possible to traverse it and do some computations with bounded memory. Often, it is impossible to solve even simple computations with bounded memory, but answers that are correct with high probability can be found efficiently, with techniques as random sampling, aggregating medians or probabilistic data structures.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.