The yielding transition of amorphous solids is a phase transition with a special type of universality. Critical exponents and scaling relations have been defined and proposed near the yield stress. We show here that, even in the initial stage of shear far below the yield stress, the stress-strain curve of amorphous solids also shows critical scaling with universal exponents. The key point is to remove the elastic part of the strain, and the shear stress exhibits a sublinear scaling with the plastic strain. We show how this critical scaling is related to the finite size effect of the minimum strain to trigger the first plastic avalanche after a quench. We point out that this sublinear scaling between the stress and the plastic strain implies the divergence of a high-order shear modulus. A scaling relation is derived between two exponents characterizing the stress-strain curve and the density distribution of the local stabilities, respectively. We test the critical scaling of the stress-strain curve using both mesoscopic and atomistic simulations and get satisfying agreement in two and three dimensions.