More Like this

1. Second Order Adjoints in Optimization

   https://doi.org/10.1007/978-3-030-72040-7_10  

   Petra, Noemi; Sachs, Ekkehard W. (January 2022, Numerical Analysis and Optimization)

   Al-Baali, Mehiddin; Purnama, Anton; Grandinetti, Lucio (Ed.)

   Second order, Newton-like algorithms exhibit convergence properties superior to gradient-based or derivative-free optimization algorithms. However, deriving and computing second order derivatives--needed for the Hessian-vector product in a Krylov iteration for the Newton step--often is not trivial. Second order adjoints provide a systematic and efficient tool to derive second derivative infor- mation. In this paper, we consider equality constrained optimization problems in an infinite-dimensional setting. We phrase the optimization problem in a general Banach space framework and derive second order sensitivities and second order adjoints in a rigorous and general way. We apply the developed framework to a partial differential equation-constrained optimization problem. 

   more » « less
2. First-Order Minimax Bilevel Optimization

   Yang, Yifan; Si, Zhaofeng; Lyu, Siwei; Ji, Kaiyi (December 2024, Advances in Neural Information Processing Systems)

   Multi-block minimax bilevel optimization has been studied recently due to its great potential in multi-task learning, robust machine learning, and few-shot learning. However, due to the complex three-level optimization structure, existing algorithms often suffer from issues such as high computing costs due to the second-order model derivatives or high memory consumption in storing all blocks’ parameters. In this paper, we tackle these challenges by proposing two novel fully first-order algorithms named FOSL and MemCS. FOSL features a fully single-loop structure by updating all three variables simultaneously, and MemCS is a memory-efficient double-loop algorithm with cold-start initialization. We provide a comprehensive convergence analysis for both algorithms under full and partial block participation, and show that their sample complexities match or outperform those of the same type of methods in standard bilevel optimization. We evaluate our methods in two applications: the recently proposed multi-task deep AUC maximization and a novel rank-based robust meta-learning. Our methods consistently improve over existing methods with better performance over various datasets. 

   more » « less
3. Self-Healing First-Order Distributed Optimization

   https://doi.org/10.1109/CDC45484.2021.9683487  

   Donato Ridgley, Israel L.; Freeman, Randy A.; Lynch, Kevin M. (December 2021, 2021 60th IEEE Conference on Decision and Control (CDC))
4. Private Zeroth-Order Nonsmooth Nonconvex Optimization

   Zhang, Qinzi; Tran, Hoang; Cutkosky, Ashok (May 2024, International Conference on Learning Representations)
5. Zeroth-Order Optimization Finds Flat Minima

   Zhang, Liang; Li, Bingcong; Thekumparampil, Kiran_Koshy; Oh, Sewoong; Muehlebach, Michael; He, Niao (June 2025, https://doi.org/10.48550/arXiv.2506.05454)

   Zeroth-order methods are extensively used in machine learning applications where gradients are infeasible or expensive to compute, such as black-box attacks, reinforcement learning, and language model fine-tuning. Existing optimization theory focuses on convergence to an arbitrary stationary point, but less is known about the implicit regularization that provides a fine-grained characterization of which particular solutions are reached. This paper shows that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian, a measure widely used to distinguish between sharp and flat minima. The authors provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions, defining flat minima as minimizers that achieve the smallest trace of Hessian among all optimal solutions. Experiments on binary classification tasks with convex losses and language model fine-tuning support the theoretical findings. 

   more » « less