The beginning of the tenancy is defined in section 45(2) of the Housing Act 1988 as:
the day on which the tenancy is entered into or, if it is later, the day on which, under the terms of any lease, agreement or other document, the tenant is entitled to possession under the tenancy.
(This applies to the statutory instrument because it is made under section 21B of the 1988 Act, and definitions carry over from primary to secondary legislation in this way.) The definition probably matches what people would expect.
Section 21B, and the 2015 Regulations, just say that the landlord has to give this information to their tenant. But it follows that if the tenancy has begun, then the landlord's obligation also begins. It binds from day 1. Therefore, the government is justified in saying in the booklet:
The landlord, or the letting agent, should give the current version of this guide to the tenant when a new assured shorthold tenancy starts.
Because of all the other paperwork involved, it's most common for the booklet to be given as part of the bundle of documents when the tenancy agreement is signed - so, along with the inventory and so on. This is typically not too distant in time from when the tenant is entitled to actually move in, and landlords will often only sign on the day itself even if the tenant has completed their part of the formalities earlier.
Perhaps your doubt is about whether it is "OK" for the landlord to provide the booklet before the actual start date of the tenancy, as opposed to waiting until the tenancy is in effect. In the same way, we could imagine a prospective tenant wanting to see the energy performance certificate well before agreeing to sign anything. Does the landlord have to give them another copy on day 1 of the tenancy, even though it's the same as the copy they already have?
In fact, there are specific different rules for those other items of information.
- The most recent gas safety certificate must normally be given "to any new tenant of premises ... before that tenant occupies those premises" (SI 1998/2451 reg.36(6)(b))
- The EPC must be given to any prospective tenant at the earliest opportunity, and in any event must have been given to "the person who ultimately becomes the buyer or tenant" (SI 2012/3118 reg.6, and compare the definition of "prospective tenant" in regulation 3).
- The EICR must similarly be given to new and prospective tenants before they occupy the premises (SI 2022/312 reg.3(e)).
So these are meant to be given before the tenancy begins. They are part of what the prospective tenant should know before deciding whether to sign the agreement. The government's model tenancy agreement has checklists for landlord and tenant in relation to these documents, plus the "How to rent" booklet. That is consistent with the idea that the tenant is meant to have this information on the day that the tenancy is to begin, whether that's because they're just being given it now, or because they've already seen it. Armed with all the knowledge, they can now proceed to signing the agreement.
Indeed, the content of the "How to rent" booklet makes it less useful if it's provided after the agreement has started. A lot of the material is about searching for a property, making sure that you are prepared to sign, and avoiding bad behaviour by potential landlords. Even though it would meet the letter of the law to only get this information after signing (but still on the day), it also meets letter and spirit to get it on the day, before signing. Or if you had it even earlier, it would be a bold argument to say that the landlord hadn't given you the information just because they emailed it to you a week before the tenancy actually began - especially if you have checked the appropriate little box on the tenancy agreement to say you received it.
Nonetheless, because the only practical consequence for landlords is their ability to serve a s.21 notice, it's also common for them to play it safe and send another copy of the booklet before sending the notice itself. They will also often send updated copies as they arise, even though the regulation doesn't require it; some insurers ask for this just to really cement the chance of making a proper s.21 notice.
I'm not aware of judicial precedent on early delivery of the booklet, but we can get some guidance from a recent Court of Appeal decision on s.21A, Trecarrell House v Rouncefield  EWCA Civ 760. This case examined the nature of breaches and remedies that prevent serving an eviction notice. The conclusion was that if the tenant received a gas safety certificate "before or with" the s.21 notice, then the landlord has fulfilled their obligation - they are not irreparably in breach just becuse they did not give that information at the beginning. What matters for the Housing Act is that the tenant received it by the time that it was needed for the s.21 process. Likewise, it would seem that if the tenant had the "How to rent" booklet from the landlord before the beginning of their tenancy, then the landlord is not in breach - because the tenant has the information the whole time even though the act of giving the booklet predated the tenancy itself.