Federated learning (FL) is a distributed machine learning architecture that\nleverages a large number of workers to jointly learn a model with decentralized\ndata. FL has received increasing attention in recent years thanks to its data\nprivacy protection, communication efficiency and a linear speedup for\nconvergence in training (i.e., convergence performance increases linearly with\nrespect to the number of workers). However, existing studies on linear speedup\nfor convergence are only limited to the assumptions of i.i.d. datasets across\nworkers and/or full worker participation, both of which rarely hold in\npractice. So far, it remains an open question whether or not the linear speedup\nfor convergence is achievable under non-i.i.d. datasets with partial worker\nparticipation in FL. In this paper, we show that the answer is affirmative.\nSpecifically, we show that the federated averaging (FedAvg) algorithm (with\ntwo-sided learning rates) on non-i.i.d. datasets in non-convex settings\nachieves a convergence rate $\\mathcal{O}(\\frac{1}{\\sqrt{mKT}} + \\frac{1}{T})$\nfor full worker participation and a convergence rate\n$\\mathcal{O}(\\frac{\\sqrt{K}}{\\sqrt{nT}} + \\frac{1}{T})$ for partial worker\nparticipation, where $K$ is the number of local steps, $T$ is the number of\ntotal communication rounds, $m$ is the total worker number and $n$ is the\nworker number in one communication round if for partial worker participation.\nOur results also reveal that the local steps in FL could help the convergence\nand show that the maximum number of local steps can be improved to $T/m$ in\nfull worker participation. We conduct extensive experiments on MNIST and\nCIFAR-10 to verify our theoretical results.\n