Optimality of the Subgradient Algorithm in the Stochastic Setting
We show that the Subgradient algorithm is universal for online learning on the simplex in the sense that it simultaneously achieves $O(\sqrt N)$ regret for adversarial costs and $O(1)$ pseudo-regret for i.i.d costs. To the best of our knowledge this is the first demonstration of a universal algorithm on the simplex that is not a variant of Hedge. Since Subgradient is a popular and widely used algorithm our results have immediate broad application.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonsmooth Analysis and Subgradient Methods for Averaging in Dynamic Time Warping Spaces
Time series averaging in dynamic time warping (DTW) spaces has been successfully applied to improve pattern recognition systems. This article proposes and analyzes subgradient methods for the problem of finding a sample …
Dynamic Time WarpingTime SeriesTime Series AnalysisTime Series AveragingRevisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity
The subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. The existing complexity and convergence results for this method are mainly derived for Lipschitz continuous objective …
Subgradient Method for System Identification with Non-Smooth Objectives
This paper investigates a subgradient-based algorithm to solve the system identification problem for linear time-invariant systems with non-smooth objectives. This is essential for robust system identification in safety-…
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
We develop model-based methods for solving stochastic convex optimization problems, introducing the approximate-proximal point, or aProx, family, which includes stochastic subgradient, proximal point, and bundle methods.…
Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization
We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradi…