More Like this

1. A unified approach for a 1D generalized total variation problem

   https://doi.org/10.1007/s10107-021-01633-2  

   Lu, Cheng; Hochbaum, Dorit S. (July 2021, Mathematical Programming)

   null (Ed.)

   Abstract We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush–Kuhn–Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem. 

   more » « less
2. CoCoA: A General Framework for Communication-Efficient Distributed Optimization

   Smith, Virginia; Forte, Simone; Ma, Chenxin; Takáč, Martin; Jordan, Michael I.; Jaggi, Martin (July 2018, Journal of machine learning research)

   The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets. 

   more » « less
3. Stable Conical Regularization by Constructible Dilating Cones with an Application to $$L^{p}$$-constrained Optimization Problems

   https://doi.org/10.11650/tjm/181103  

   Jadamba, Baasansuren; Khan, Akhtar A.; Sama, Miguel (January 2019, Taiwanese Journal of Mathematics)

   We study a convex constrained optimization problem that suffers from the lack of Slater-type constraint qualification. By employing a constructible representation of the constraint cone, we devise a new family of dilating cones and use it to introduce a family of regularized problems. We establish novel stability estimates for the regularized problems in terms of the regularization parameter. To show the feasibility and efficiency of the proposed framework, we present applications to some Lp-constrained least-squares problems. 

   more » « less
4. An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration

   https://doi.org/https://epubs.siam.org/doi/10.1137/17M1125157  

   Lin, Hongzhou; Mairal, Julien; Harchaoui, Zaid (January 2019, SIAM journal on optimization)

   We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental optimization algorithms. QNing is also compatible with composite objectives, meaning that it has the ability to provide exactly sparse solutions when the objective involves a sparsity-inducing regularization. When combined with limited-memory BFGS rules, QNing is particularly effective to solve high-dimensional optimization problems, while enjoying a worst-case linear convergence rate for strongly convex problems. We present experimental results where QNing gives significant improvements over competing methods for training machine learning methods on large samples and in high dimensions. 

   more » « less
5. Stochastic Variance-Reduced Cubic Regularized Newton Method

   Zhou, Dongruo; Xu, Pan; Gu, Quanquan (July 2018, International Conference on Machine Learning)

   We propose a stochastic variance-reduced cubic regularized Newton method (SVRC) for non-convex optimization. At the core of our algorithm is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. We show that our algorithm is guaranteed to converge to an $$(\epsilon,\sqrt{\epsilon})$$-approximate local minimum within $$\tilde{O}(n^{4/5}/\epsilon^{3/2})$$ second-order oracle calls, which outperforms the state-of-the-art cubic regularization algorithms including subsampled cubic regularization. Our work also sheds light on the application of variance reduction technique to high-order non-convex optimization methods. Thorough experiments on various non-convex optimization problems support our theory. 

   more » « less