Stochastic Framework

[epapoutsellis]

This is a poll for the design of

• FunctionNumberGenerator
• ApproximateGradientSumFunction

that are currently implemented in the latest commit of #1345.

Apart from the names of the generator FunctionNumberGenerator and the most important class for our stochastic framework ApproximateGradientSumFunction, we need to decide on their signatures.

FunctionNumberGenerator

At the moment the FunctionNumberGenetator implements three different sampling methods and basically wraps the
numpy.random.choice.

• 1st sampling method: selects a function randomly, with replacement and uniformly (p=None)
• 2nd sampling method: selects a function randomly, without replacement and uniformly (p=None). At the end of each epoch, i.e., after selected all functions, the list of functions is permuted again.
• 3rd sampling method: selects a function randomly, without replacement and uniformly (p=None). The list of functions is permuted only once is used for all epochs.

from here.

ApproximateGradientSumFunction

This represents a sum of nfunctions and the differences from the SumFunction are

• all functions are expected to be smooth (.gradient) is implemented for each function
• the .gradient method is implemented in a stochastic mode and is determined by its children, e.g., SGFunction, SAG(A)Function, etc

At the moment the ApproximateGradientSumFunction accepts

• list of functions and
• selection=string, accepted strings are: random (1st sampling method), random _permutation(2nd sampling method),
  fixed_permutation (3rd sampling method), or
• selection = FunctionNumberGenetator(...)

Note: Please propose alternative names for the generator/class and their arguments in the poll options below and I can add them

[KrisThielemans]

• I asked what conventions are used for "functions" or something that returns a "generator". Maybe this is the first time CIL has something like this, but it could be considered to need the same convention as "factories". It is not a class. I'd call it function_num_generator (which sticks to Python terminology) or function_num_selector (as you call it "selection process"). I also don't know if you stick to "num" or "number".
• I proposed 2 other sampling methods in ApproximateGradientSumFunction and SGFunction #1345 (comment)

[KrisThielemans]

The above poll isn't useful as it only allows selecting one of them.

[paskino]

My preference would be to use a staticmethod of a class, which is a more complex form of a function.
I developed something similar in a class that creates the subsets of the data using static methods, see #1344

In this case the name FunctionNumberGenerator is not correct as it is a function that generates an index within a min and a max [0, N]. How we use that index is totally irrelevant. In SPDGH we select the number of the subset with an hard-coded line:

CIL/Wrappers/Python/cil/optimisation/algorithms/SPDHG.py

Lines 190 to 191 in 76e5014

	# Choose subset
	i = int(np.random.choice(len(self.sigma), 1, p=self.prob))

SPDHG would also benefit from being able to call a generator as discussed here, so I would definitely drop the term function from the name of the method.

My proposal is something like

class IndexGenerator(object):
    @staticmethod
     def random(num_subsets):
          return IndexGenerator.FunctionNumberGenerator(num_subsets, replacement=True)
    @staticmethod
     def random_shuffle(num_subsets):
          return IndexGenerator.FunctionNumberGenerator(num_subsets, replacement=False, shuffle='random')

    @staticmethod
     def single_shuffle(num_subsets):
          return IndexGenerator.FunctionNumberGenerator(num_subsets, replacement=False, shuffle='single' )

    @staticmethod
    def FunctionNumberGenerator(num_functions, sampling_method):
         '''This is the function at https://github.com/TomographicImaging/CIL/blob/a81b01f59d786cf0c7163f65aa39482569eb379c/Wrappers/Python/cil/optimisation/utilities/FunctionNumberGenerator.py#L20'''

Personally I understand better the terms random_permutation and fixed_permutation with respect to random_shuffle and single_shuffle.

Finally, I wonder if it would be more advantageous to be able to specify the interval [min, max] rather than just their difference as num_subsets = max - min.

[KrisThielemans]

that sounds good to me!

[epapoutsellis]

Thank you @paskino @KrisThielemans . Polls in github do not allow multiple questions and answers so I will create a poll using mentimeter, but I would like to know all the questions. So far we have the following:

Q1: The name of a function that returns an index number refering to the selected $f_{i}$ function:

• Option 1: FunctionNumberGenerator
• Option 2: IndexGenerator

Q2 The design of such a function:

• Option 1: Class
• Option 2: Function/Generator

Q3 Arguments of this function are a) integer:number_of_subsets and b) string: sampling method.

• Option 1: number_of_subsets, sampling_method

Q4 names for sampling_methods:

• 1st sampling method: Selects a random index with replacement uniformly

  • Option 1: random
  • Option 2: uniform

• 2nd sampling method: Selects a random index without replacement and at the end of each epoch, the list of numbers/function is permuted again

  • Option 1: random_permutation
  • Option 2: random_shuffle

• 3rd sampling method: Selects a random index without replacement where the list of numbers/function is permuted only one time. The same order is used for all epochs.

  • Option 1: fixed_permutation
  • Option 2: single_shuffle

• 4th sampling method: Selects an index sequentially, e.g., 0,1,2,3,

  • Option 1: fixed_sequential

• 5th sampling method: Selects an index with a step_size=number_of_subsets with , e.g., n=4 , subset 1 = 0,3,6,9, subset 2 = 1,4,8,12, etc

  • Option 1: fixed_staggered

Q5: Base class for stochastic framework
- Option 1: ApproximateGradientSumFunction

Q6: Signature of base class for stochastic framework
- Option 1: arg1: list_of_functions, arg2 = selection=

• either a string with the above sampling methods
• or an instance of the function that generates an index.

@zeljkozeljko, @jakobsj, @gfardell, @BillyTang , @ClaireDelplancke, @mehrhardt, @Imraj-Singh , @samdporter in case you want to add another question, option etc please leave a comment below and I will add them in the poll. If you agree with questions/options, please 👍 and I will create the poll.

[paskino]

My opinion is resumed in #1377 (comment)

Q1 Q2: a factory with the name IndexGenerator, better detailed in the above comment.

Q3, I suggest to make available several factory method to create the required generator. The only argument would then be the number of subsets. Would it make sense to make the generator generate indices in a range [a,b], so that the factory will need to know a and b?

Q4 random, random_permutation, fixed_permutation, sequential, stagger.

Q5 and Q6 we have discussed at length, and what you write is the consensus reached.

[epapoutsellis]

In terms of Q5, Q6, I have changed the base class in the last 5 months 4 times:

1. AverageSumFunction, and SubsetSumFunction to
2. only SubsetSumFunction with 1/n to
3. SubsetSumFunction without 1/n to
4. ApproximateGradientSumFunction

I think we need to be sure of the design, reach a final decision that we all agree and implement.

[epapoutsellis]

@paskino why do we need min, max?

[paskino]

the generator could generate indices in a range [a,b], so that the factory will need to know a and b.
Currently by passing only the number of subsets the generator generates indices in the interval [0, N].

Mine is just a proposal to make the generator more general, if it may turn out to be useful.

[epapoutsellis]

Fine with me, but we need to add checks that a>=0 and b<=N-1, because the index that is randomly selected is an integer $i\in{{0,1,\cdots,N-1}}$, since we have $$\sum_{i=0}^{N-1}f_{i}$$

[KrisThielemans]

I'd stick to just providing N for now. It'd be easy enough to add the option [a,b] later if we need it.

[paskino]

Let's forget the [a,b] then

[KrisThielemans]

@paskino, I'd modify your proposal to hide the IndexGenerator.FunctionNumberGenerator member (e,g. call it IndexGenerator._index_generator_from_string` or so) or even get rid of it completely.

[paskino]

With version 24.0.0 SGD was introduced and with the merge of #1624 and #1625 the stochastic framework has been added to CIL.