9 papers
M-duality in fixed-point problems for general normed spaces
Jongmin Lee, Sangyeop Woo, Ernest K. Ryu
Solving fixed-point problems by reducing residual bounds is one of the central approaches in fixed-point iteration, and, in particular, the Halpern iteration is known to effectivel…
Higher-Order Derivatives Do Not Accelerate the Computation of Fixed Points
Uijeong Jang, Ernest K. Ryu
The Picard iteration converges to the unique fixed point of a -contractive operator at a linear rate , and a lower bound with an affine construction shows that no determini…
Optimal Acceleration for Proximal Minimization of the Sum of Convex and Strongly Convex Functions
Govind M. Chari, Uijeong Jang, Ernest K. Ryu +1
When minimizing the sum of a convex and a strongly convex function, or when finding the zero of the sum of a monotone operator and a strongly monotone operator, Chambolle and Pock…
Nesterov Acceleration with Operator Decomposition
Jaewook Lee, Ernest K. Ryu, Chulhee Yun
We propose Nesterov acceleration with Operator Decomposition (NOD), which extends Nesterov's accelerated gradient descent (NAG) from smooth strongly convex optimization to the broa…
Nesterov Flow May Travel Infinitely Long to Converge to a Minimizer
Ernest K. Ryu
Recent work has established that the trajectory of the Nesterov ODE, a the continuous-time model of Nesterov's accelerated gradient method, exhibits point convergence towards a min…
ALiA: Adaptive Linearized ADMM
Uijeong Jang, Kaizhao Sun, Wotao Yin +1
We propose ALiA, a novel adaptive variant of the alternating direction method of multipliers (ADMM). Specifically, ALiA is a variant of function-linearized proximal ADMM (FLiP ADMM…
H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms
TaeHo Yoon, Ernest K. Ryu, Benjamin Grimmer
For nonexpansive fixed-point problems, Halpern's method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all…
Point Convergence of Nesterov's Accelerated Gradient Method: An AI-Assisted Proof
Uijeong Jang, Ernest K. Ryu
The Nesterov accelerated gradient method, introduced in 1983, has been a cornerstone of optimization theory and practice. Yet the question of its point convergence had remained ope…
Sharpness-Aware Minimization Can Hallucinate Minimizers
Chanwoong Park, Uijeong Jang, Ernest K. Ryu +1
Sharpness-Aware Minimization (SAM) is widely used to seek flatter minima -- often linked to better generalization. In its standard implementation, SAM updates the current iterate u…