Multi-task learning (MTL) is effective in solving multiple related tasks simultaneously by sharing knowledge. However, a key challenge hindering its applications is the task interference problem where different tasks compete with each other, leading to the gradients conflicts during optimization and suffering from negative transfer. One thread is to manipulate task gradients by adjusting conflicting directions, ignoring architecture learning. Another thread is to learn architectures by generating task-exclusive modules, ignoring all-task balances. We address the problem by proposing a novel Multi-task Architecture learning model via Multi-Objective (MAMO) optimization. It achieves the goal in two steps. First, for the competing tasks detected during architecture learning, MAMO automatically generates a new module of gradient mediative kernel (GMK). Second, MAMO finds a Pareto optimal solution that balances all tasks during model parameter learning. MAMO outperforms various MTL baselines on benchmarks with an effective model size. It is model-agnostic and can be integrated into other SOTA methods to promote their performance. Extensive ablation study is conducted to understand the working of MAMO.