Aryan Mokhtari

The optimistic gradient method has seen increasing popularity as an efficient first-order method for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [A. Mokhtari, A. E. Ozdaglar, and S. Pattathil, SIAM J. Optim., 30 (2020), pp. 3230–3251] proposed an interesting perspective that interprets the optimistic gradient method as an approximation to the proximal point method. In this paper, we follow this approach and distill the underlying idea of optimism to propose a generalized optimistic method, which encompasses the optimistic gradient method as a special case. Our general framework can handle constrained saddle point problems with composite objective functions. Moreover, we also develop a backtracking line search scheme to select the step sizes without knowledge of the smoothness coefficients. By instantiating our general framework with a second-order oracle, we propose a second-order optimistic method and prove a complexity bound of [Formula: see text] in terms of the primal-dual gap in the convex-concave setting and a complexity bound of [Formula: see text] in terms of the distance to the optimal solution in the strongly-convex-strongly-concave setting, where [Formula: see text] is the Lipschitz constant of the Jacobian, [Formula: see text] is the strong convexity parameter, and [Formula: see text] is the initial Euclidean distance to the saddle point. We also establish convergence rates in terms of the tangent residual, which generalizes the operator norm as a metric in the unconstrained setting. Moreover, our line search scheme provably only requires a constant number of calls to a subproblem solver per iteration on average.

In this paper, we explore the non-asymptotic global convergence rates of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method implemented with exact line search. Notably, due to Dixon’s equivalence result, our findings are also applicable to other quasi-Newton methods in the convex Broyden class employing exact line search, such as the Davidon-Fletcher-Powell (DFP) method. Specifically, we focus on problems where the objective function is strongly convex with Lipschitz continuous gradient and Hessian. Our results hold for any initial point and any symmetric positive definite initial Hessian approximation matrix. The analysis unveils a detailed three-phase convergence process, characterized by distinct linear and superlinear rates, contingent on the iteration progress. Additionally, our theoretical findings demonstrate the trade-offs between linear and superlinear convergence rates for BFGS when we modify the initial Hessian approximation matrix, a phenomenon further corroborated by our numerical experiments.

The performance of an optimizer on large-scale deep learning models depends critically on fine-tuning the learning rate, often requiring an extensive grid search over base learning rates, schedules, and other hyperparameters. In this paper, we propose a principled framework called GALA (Gradient Alignment-based Learning rate Adaptation), which dynamically adjusts the learning rate by tracking the alignment between consecutive gradients and using a local curvature estimate. Guided by the convergence analysis, we formulate the problem of selecting the learning rate as a one-dimensional online learning problem. When paired with an online learning algorithm such as Follow-the-Regularized-Leader, our method produces a flexible, adaptive learning rate schedule that tends to increase when consecutive gradients are aligned and decrease otherwise. We establish a data-adaptive convergence rate for normalized SGD equipped with GALA in the smooth, nonconvex setting. Empirically, common optimizers such as SGD and Adam, when augmented with GALA, demonstrate robust performance across a wide range of initial learning rates and perform competitively without the need for tuning.