Inexact Online Proximal-gradient Method for Time-varying Convex Optimization
This paper considers an online proximal-gradient method to track the minimizers of a composite convex function that may continuously evolve over time. The online proximal-gradient method is inexact, in the sense that: (i) it relies on an approximate first-order information of the smooth component of the cost; and, (ii) the proximal operator (with respect to the non-smooth term) may be computed only up to a certain precision. Under suitable assumptions, convergence of the error iterates is established for strongly convex cost functions. On the other hand, the dynamic regret is investigated when the cost is not strongly convex, under the additional assumption that the problem includes feasibility sets that are compact. Bounds are expressed in terms of the cumulative error and the path length of the optimal solutions. This suggests how to allocate resources to strike a balance between performance and precision in the gradient computation and in the proximal operator.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Inexact Proximal Gradient Methods for Non-convex and Non-smooth Optimization
In machine learning research, the proximal gradient methods are popular for solving various optimization problems with non-smooth regularization. Inexact proximal gradient methods are extremely important when exactly sol…
BIG-bench Machine LearningOnline Joint Topology Identification and Signal Estimation from Streams with Missing Data
Identifying the topology underlying a set of time series is useful for tasks such as prediction, denoising, and data completion. Vector autoregressive (VAR) model-based topologies capture dependencies among time series a…
DenoisingTime SeriesTime Series AnalysisA New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval
This paper considers the robust phase retrieval problem, which can be cast as a nonsmooth and nonconvex optimization problem. We propose a new inexact proximal linear algorithm with the subproblem being solved inexactly.…
RetrievalConvergence Analysis of the Wasserstein Proximal Algorithm beyond Geodesic Convexity
The proximal algorithm is a powerful tool to minimize nonlinear and nonsmooth functionals in a general metric space. Motivated by the recent progress in studying the training dynamics of the noisy gradient descent algori…
Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks
In decentralized learning, a network of nodes cooperate to minimize an overall objective function that is usually the finite-sum of their local objectives, and incorporates a non-smooth regularization term for the better…