Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations

2015/08/04 by Anikin, Anton, Dvurechensky, Pavel, Gasnikov, Alexander +5
Computer Science · Engineering · #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1508.00858

openalex publication_date 2015/08/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

In this work we collect and compare to each other many different numerical methods for regularized regression problem and for the problem of projection on a hyperplane. Such problems arise, for example, as a subproblem of demand matrix estimation in IP- networks. In this special case matrix of affine constraints has special structure: all elements are 0 or 1 and this matrix is sparse enough. We have to deal with huge-scale convex optimization problem of special type. Using the properties of the problem we try "to look inside the black-box" and to see how the best modern methods work being applied to this problem.

Citations

• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Smooth minimization of non-smooth functions

Related

• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• Robust Regularized Low-Rank Matrix Models for Regression and Classification
• Path Following and Empirical Bayes Model Selection for Sparse Regression
• The Geometry and Well-Posedness of Sparse Regularized Linear Regression
• Relaxed Sparse Eigenvalue Conditions for Sparse Estimation via Non-convex Regularized Regression