This article proposes a virtual leader-based coordinated controller for the nonlinear multiple autonomous underwater vehicles (multi-AUVs) with the system uncertainties. To achieve the coordinated formation, a virtual AUV is set as the leader, while the desired command is designed using the relative position between each AUV and the virtual leader. The controller is designed based on the back-stepping scheme, and the online data-based learning scheme is used for uncertainty approximation. The highlight is that compared with previous learning methods which mostly focus on stability, the learning performance index is constructed using the collected online data in this article. The index is further used in the composite update law of the neural weights. The closed-loop system stability is analyzed via the Lyapunov approach. The simulation test on the five AUVs under fixed formation shows that the proposed method can achieve higher tracking performance with improved approximation accuracy.