The paper investigates the cost function-dependent barren plateaus in shallow parametrized quantum circuits used in variational quantum algorithms (VQAs). The authors rigorously prove two main results: (1) defining the cost function in terms of global observables leads to exponentially vanishing gradients, even for shallow circuits, while (2) defining the cost function with local observables results in at worst polynomially vanishing gradients for circuits with depth $\mathcal{O}(\log n)$. These findings establish a connection between locality and trainability. The authors illustrate these ideas through large-scale simulations of a quantum autoencoder, showing that the global cost function exhibits a barren plateau, whereas a novel local cost function is trainable, making quantum autoencoders a scalable application. The results highlight the importance of choosing appropriate cost functions to avoid barren plateaus and improve the trainability of VQAs.The paper investigates the cost function-dependent barren plateaus in shallow parametrized quantum circuits used in variational quantum algorithms (VQAs). The authors rigorously prove two main results: (1) defining the cost function in terms of global observables leads to exponentially vanishing gradients, even for shallow circuits, while (2) defining the cost function with local observables results in at worst polynomially vanishing gradients for circuits with depth $\mathcal{O}(\log n)$. These findings establish a connection between locality and trainability. The authors illustrate these ideas through large-scale simulations of a quantum autoencoder, showing that the global cost function exhibits a barren plateau, whereas a novel local cost function is trainable, making quantum autoencoders a scalable application. The results highlight the importance of choosing appropriate cost functions to avoid barren plateaus and improve the trainability of VQAs.