混合測地凸優化及其應用

Hybrid Geodesically Convex Optimization with Applications

王冠人(Guan-Ren Wang)

指導教授 ： 李彥寰

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2024年)

https://doi.org/10.6342/NTU202404042

摘要

我們提出了一種混合測地凸優化框架，該框架的動機來自於計算對數最優投資組合問題和計算Augustin信息問題。我們的框架考慮了相對於一種黎曼度量測地凸且相對於另一種黎曼度量測地Lipschitz梯度的目標函數。在這種混合條件下，我們為黎曼梯度下降提供了非漸近收斂性證明，證明其以O(1/T)的速度收斂。我們將此框架應用於原先作為動機的應用。

關鍵字

最佳化 ； 測地凸優化 ； 黎曼優化 ； 黎曼梯度下降法

並列摘要

We introduce a hybrid geodesically convex optimization framework, which is motivated by the problems of computing the log-optimal portfolio and computing the Augustin information. Our framework considers objective functions that are geodesically convex with respect to one Riemannian metric and have geodesically Lipschitz gradients with respect to another Riemannian metric. Under this hybrid condition, we provide a non-asymptotic convergence guarantee for Riemannian gradient descent, proving that it converges at a rate of O(1/T). We apply this framework to the original motivating problems.

並列關鍵字

Optimization ； Geodesically convex optimization ； Riemannian optimization ； Riemannian gradient descent

參考文獻

Kimon Antonakopoulos, Elena Veronica Belmega, and Panayotis Mertikopoulos. Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach. In Int. Conf. Learning Representations (ICLR), 2020.

Suguru Arimoto. On the converse to the coding theorem for discrete memoryless channels (corresp.). IEEE Trans. Inf. Theory, 19(3):357–359, 1973.

Udo Augustin. Error estimates for low rate codes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 14(1):61–88, 1969.

Udo Augustin. Noisy channels. Habilitation Thesis, Universität Erlangen-Nürnberg, 1978.

Rajendra Bhatia, Tanvi Jain, and Yongdo Lim. On the Bures–Wasserstein distance between positive definite matrices. Expo. Math., 37(2):165–191, 2019.