Short answer
Both start and begin are natural in the context of the example sentence in the question.
Long answer
Unless I am mistaken, they can always be freely exchanged when they are used as auxiliary verbs:
✔ The tree starts to move.
✔ The tree starts moving.
✔ The tree begins to move.
✔ The tree begins moving.
✔ Start writing.
✔ Begin writing.
Or when used after an auxiliary verb without a noun:
- ✔ I will start now.
- ✔ I will begin now.
However, they cannot always be freely exchanged when they are the only verb or they are followed by a particular noun:
The fact that begin doesn't work in the first two examples but does in the third, indicates that you can't determine what's acceptable from the grammar alone. Instead, context is extremely important.
They cannot be freely exchanged (without altering their spelling), when they are used as nouns:
However, their use as adjectives can alter this:
✔ It is a starting point.
? It is a beginning point. [This at least sounds odd to me.]
✔ They are starting writers.
✔ They are beginning writers.
While some conventions (if not actual rules) can be determined in general, some other uses are very much based on the context of the particular words in the rest of the sentence, as well as the overall construction.
In presenting these examples, it at least appears as if start and its variations can be used in more contexts than begin and its variations. However, there are still some sentences where begin is fine, but start is not.