Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimization
We consider the problem of minimizing the sum of an average function of a large number of smooth convex components and a general, possibly non-differentiable, convex function. Although many methods have been proposed to solve this problem with the assumption that the sum is strongly convex, few methods support the non-strongly convex case. Adding a small quadratic regularization is a common devise used to tackle non-strongly convex problems; however, it may cause loss of sparsity of solutions or weaken the performance of the algorithms. Avoiding this devise, we propose an accelerated randomized mirror descent method for solving this problem without the strongly convex assumption. Our method extends the deterministic accelerated proximal gradient methods of Paul Tseng and can be applied even when proximal points are computed inexactly. We also propose a scheme for solving the problem when the component functions are non-smooth.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Explicit Regularization of Stochastic Gradient Methods through Duality
We consider stochastic gradient methods under the interpolation regime where a perfect fit can be obtained (minimum loss at each observation). While previous work highlighted the implicit regularization of such algorithm…
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorit…
Stochastic OptimizationAn Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems
In this work, we revisit the problem of solving large-scale semidefinite programs using randomized first-order methods and stochastic smoothing. We introduce two oblivious stochastic mirror descent algorithms based on a …
Accelerated Mirror Descent in Continuous and Discrete Time
We study accelerated mirror descent dynamics in continuous and discrete time. Combining the original continuous-time motivation of mirror descent with a recent ODE interpretation of Nesterov's accelerated method, we prop…
Mirror Descent Search and its Acceleration
In recent years, attention has been focused on the relationship between black-box optimiza- tion problem and reinforcement learning problem. In this research, we propose the Mirror Descent Search (MDS) algorithm which is…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)