Accelerating ADMM for Efficient Simulation and Optimization The alternating direction method of multipliers (ADMM) is a popular approach for solving optimization problems that are potentially nonsmooth and with hard constraints. It has been applied to various computer graphics applications, including physical simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve nonconvex optimization, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, an established technique for accelerating fixedpoint iterations. We show that in the general case, ADMM is a fixedpoint iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixedpoint iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular nonconvex problem structure that is common in computer graphics, and prove the convergence of ADMM on such problems under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.

Sharp Characterization of Optimal Minibatch Size for Stochastic Finite Sum Convex Optimization The minibatching technique has been extensively adopted to facilitate stochastic firstorder methods because of their computational efficiency in parallel computing for largescale machine learning and data mining. However, the optimal minibatch size determination for accelerated stochastic gradient methods is not completely understood. Actually, there appears tradeoff between the iteration complexity and the total computational complexity; that is, the number of iterations (minibatch queries) can be decreased by increasing the minibatch size, but too large minibatch size would result in an unnecessarily large total computational cost. In this study, we give a sharp characterization of the minimax optimal minibatch size to achieve the optimal iteration complexity by providing a reachable lower bound for minimizing finite sum of convex functions and, surprisingly, show that the optimal method with the minimax optimal minibatch size can achieve both of the optimal iteration complexity and the optimal total computational complexity simultaneously. Finally, this feature is verified experimentally.