This article investigates the phenomenon of barren plateaus in shallow parametrized quantum circuits (PQCs) used in variational quantum algorithms (VQAs). It proves that defining the cost function $ C $ in terms of global observables leads to exponentially vanishing gradients, resulting in barren plateaus even for shallow circuits. In contrast, defining $ C $ with local observables results in at most polynomially vanishing gradients, making the cost function trainable when the circuit depth is $ \mathcal{O}(\log n) $. The study establishes a connection between locality and trainability of VQAs. The paper demonstrates that global cost functions, which compare states or operators in exponentially large Hilbert spaces, lead to barren plateaus. However, local cost functions, which compare objects on individual qubits, avoid this issue. The results are illustrated with large-scale simulations of a quantum autoencoder, showing that the global cost function proposed in the literature leads to barren plateaus, while a novel local cost function is trainable. The paper also discusses the implications of these findings for various applications of VQAs, including quantum data compression, quantum error correction, and quantum simulation. It highlights the importance of choosing appropriate cost functions to ensure the trainability of VQAs, especially for shallow circuits. The results provide a theoretical foundation for understanding the scalability of VQAs and guide the development of more efficient and practical quantum algorithms.This article investigates the phenomenon of barren plateaus in shallow parametrized quantum circuits (PQCs) used in variational quantum algorithms (VQAs). It proves that defining the cost function $ C $ in terms of global observables leads to exponentially vanishing gradients, resulting in barren plateaus even for shallow circuits. In contrast, defining $ C $ with local observables results in at most polynomially vanishing gradients, making the cost function trainable when the circuit depth is $ \mathcal{O}(\log n) $. The study establishes a connection between locality and trainability of VQAs. The paper demonstrates that global cost functions, which compare states or operators in exponentially large Hilbert spaces, lead to barren plateaus. However, local cost functions, which compare objects on individual qubits, avoid this issue. The results are illustrated with large-scale simulations of a quantum autoencoder, showing that the global cost function proposed in the literature leads to barren plateaus, while a novel local cost function is trainable. The paper also discusses the implications of these findings for various applications of VQAs, including quantum data compression, quantum error correction, and quantum simulation. It highlights the importance of choosing appropriate cost functions to ensure the trainability of VQAs, especially for shallow circuits. The results provide a theoretical foundation for understanding the scalability of VQAs and guide the development of more efficient and practical quantum algorithms.