论文标题
无投影的非平滑凸编程
Projection-Free Non-Smooth Convex Programming
论文作者
论文摘要
在本文中，我们提供了一种基于次级的算法来求解一般受约束的凸优化，而无需将投影投影到域集中。研究良好的Frank-Wolfe型算法也避免了预测。但是，它们仅旨在处理平稳的目标功能。所提出的算法可以治疗平滑和非平滑问题的问题，并达到$ O（1/\ sqrt {t}）$收敛率（与现有的下限匹配）。当确定性亚梯度被随机亚梯度取代时，该算法在预期中产生相似的性能。因此，所提出的算法是投影次级下降（PGD）和随机投影的亚梯度下降（SGD）算法的无投影替代品。
In this paper, we provide a sub-gradient based algorithm to solve general constrained convex optimization without taking projections onto the domain set. The well studied Frank-Wolfe type algorithms also avoid projections. However, they are only designed to handle smooth objective functions. The proposed algorithm treats both smooth and non-smooth problems and achieves an $O(1/\sqrt{T})$ convergence rate (which matches existing lower bounds). The algorithm yields similar performance in expectation when the deterministic sub-gradients are replaced by stochastic sub-gradients. Thus, the proposed algorithm is a projection-free alternative to the Projected sub-Gradient Descent (PGD) and Stochastic projected sub-Gradient Descent (SGD) algorithms.
