Geodesic
A dual active set algorithm for optimal sparse convex regression
Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 23 (2019) no. 1, pp. 113-130.

Voir la notice de l'article provenant de la source Math-Net.Ru

The shape-constrained problems in statistics have attracted much attention in recent decades. One of them is the task of finding the best fitting monotone regression. The problem of constructing monotone regression (also called isotonic regression) is to find best fitted non-decreasing vector to a given vector. Convex regression is the extension of monotone regression to the case of $2$-monotonicity (or convexity). Both isotone and convex regression have applications in many fields, including the non-parametric mathematical statistics and the empirical data smoothing. The paper proposes an iterative algorithm for constructing a sparse convex regression, i.e. for finding a convex vector $z\in \mathbb{R}^n$ with the lowest square error of approximation to a given vector $y\in \mathbb{R}^n$ (not necessarily convex). The problem can be rewritten in the form of a convex programming problem with linear constraints. Using the Karush–Kuhn–Tucker optimality conditions it is proved that optimal points should lie on a piecewise linear function. It is proved that the proposed dual active-set algorithm for convex regression has polynomial complexity and obtains the optimal solution (the Karush–Kuhn–Tucker conditions are fulfilled).
Keywords: dual active set algorithm, pool-adjacent-violators algorithm, isotonic regression
Mots-clés : monotone regression, convex regression. 
@article{VSGTU_2019_23_1_a6,
     author = {A. A. Gudkov and S. V. Mironov and S. P. Sidorov and S. V. Tyshkevich},
     title = {A dual active set algorithm for optimal sparse convex regression},
     journal = {Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences},
     pages = {113--130},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VSGTU_2019_23_1_a6/}
}
TY  - JOUR
AU  - A. A. Gudkov
AU  - S. V. Mironov
AU  - S. P. Sidorov
AU  - S. V. Tyshkevich
TI  - A dual active set algorithm for optimal sparse convex regression
JO  - Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
PY  - 2019
SP  - 113
EP  - 130
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VSGTU_2019_23_1_a6/
LA  - en
ID  - VSGTU_2019_23_1_a6
ER  - 
%0 Journal Article
%A A. A. Gudkov
%A S. V. Mironov
%A S. P. Sidorov
%A S. V. Tyshkevich
%T A dual active set algorithm for optimal sparse convex regression
%J Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
%D 2019
%P 113-130
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VSGTU_2019_23_1_a6/
%G en
%F VSGTU_2019_23_1_a6
A. A. Gudkov; S. V. Mironov; S. P. Sidorov; S. V. Tyshkevich. A dual active set algorithm for optimal sparse convex regression. Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 23 (2019) no. 1, pp. 113-130. http://geodesic.mathdoc.fr/item/VSGTU_2019_23_1_a6/

[1] Burdakov O., Sysoev O., “A Dual Active-Set Algorithm for Regularized Monotonic Regression”, J. Optim. Theory Appl., 172:3 (2017), 929–949 | DOI | MR | Zbl

[2] Brezger A., Steiner W. J., “Monotonic Regression Based on Bayesian P-Splines: An application to estimating price response functions from store-level scanner data”, J. Bus. Econ. Stat., 26:1 (2008), 90–104 | DOI | MR

[3] Chen Y., Aspects of Shape-constrained Estimation in Statistics, PhD Thesis, University of Cambridge, Cambridge, UK, 2013 https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.648300

[4] Balabdaoui F., Rufibach K., Santambrogio F., “Least-squares estimation of two-ordered monotone regression curves”, J. Nonparametric Stat., 22:8 (2010), 1019–1037 | DOI | MR | Zbl

[5] Hazelton M. L., Turlach B. A., “Semiparametric Regression with Shape-Constrained Penalized Splines”, Comput. Stat. Data Anal., 55:10 (2011), 2871–2879 | DOI | MR | Zbl

[6] Lu M., “Spline estimation of generalised monotonic regression”, J. Nonparametric Stat., 27:1 (2014), 19–39 | DOI | MR | Zbl

[7] Robertson T., Wright F. T. Dykstra R. L., Order Restricted Statistical Inference, Wiley Series in Probability and Mathematical Statistics, John Wiley Sons, Chichester (UK) etc., 1988, xix+521 pp. | MR | Zbl

[8] Barlow R. E. Brunk H. D., “The Isotonic Regression Problem and its Dual”, J. Amer. Stat. Assoc., 67:337 (1972), 140–147 | DOI | MR | Zbl

[9] Dykstra R. L., “An Isotonic Regression Algorithm”, J. Stat. Plan. Inf., 5:1 (1981), 355–363 | DOI | MR | Zbl

[10] Best M. J., Chakravarti N., “Active set algorithms for isotonic regression: A unifying framework”, Mathematical Programming, 47:3 (1990), 425–439 | DOI | MR | Zbl

[11] Best M. J., Chakravarti N., Ubhaya V. A., “Minimizing Separable Convex Functions Subject to Simple Chain Constraints”, SIAM J. Optim., 10:3 (2000), 658–672 | DOI | MR | Zbl

[12] Ahuja R. K., Orlin J. B., “A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints”, Operations Research, 49:1 (2001), 784–789 | DOI | MR | Zbl

[13] Strömberg U., “An Algorithm for Isotonic Regression with Arbitrary Convex Distance Function”, Comput. Stat. Data Anal., 11:2 (1991), 205–219 | DOI | MR | Zbl

[14] Hansohm J., “Algorithms and Error Estimations for Monotone Regression on Partially Preordered Sets”, J. Multivariate Analysis, 98:5 (2007), 1043–1050 | DOI | MR | Zbl

[15] Burdakow O., Grimvall A., Hussian M., “A Generalised PAV Algorithm for Monotonic Regression in Several Variables”, COMPSTAT, Proceedings in Computational Statistics, 16th Symposium Held in Prague, Czech Republic, v. 10, ed. J. Antoch, Springer-Verlag, New York, 2004, 761–767 http://users.mai.liu.se/olebu87/PAPERS/COMPSTAT04.pdf | MR

[16] Dykstra R. L., Robertson T., “An Algorithm for Isotonic Regression for Two or More Independent Variables”, Ann. Statist., 10:3 (1982), 708–716 | DOI | MR | Zbl

[17] Sidorov S. P., Faizliev A. R., Gudkov A. A., Mironov S. V., “Algorithms for Sparse $k$-Monotone Regression”, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, 10848, ed. W.-J. van Hoeve, Springer International Publishing, Cham, 2018, 546–556 | DOI | MR | Zbl

[18] Bach F. R., Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization, 2017, arXiv: [cs.LG] 1707.09157

[19] Altmann D., Grycko Eu., Hochstättler W., Klützke G., Monotone smoothing of noisy data, Technical Report feu-dmo034.15, FernUniversität in Hagen, 2014 https://www.fernuni-hagen.de/mathematik/DMO/pubs/feu-dmo034-14.pdf

[20] Gorinevsky D. M., Kim S.-J., Beard Sh., Boyd S. P., Gordon G., “Optimal Estimation of Deterioration From Diagnostic Image Sequence”, {IEEE} Transactions on Signal Processing, 57:3 (2009), 1030–1043 | DOI | MR | Zbl

[21] Hastie T. Tibshirani R. Wainwright M., Statistical Learning with Sparsity: The Lasso and Generalizations, Monographs on Statistics and Applied Probability, 143, Chapman and Hall/CRC, New York, 2015, xvi+351 pp. | DOI | MR

[22] Cai Y., Judd K. L., “Advances in Numerical Dynamic Programming and New Applications”, Handbook of Computational Economics, v. 3, eds. K. Schmedders, K. L. Judd, Elsevier, 2014, 479–516 | DOI

[23] Boytsov D. I., Sidorov S. P., “Linear approximation method preserving $k$-monotonicity”, Sib. Èlektron. Mat. Izv., 12 (2015), 21–27 | DOI | MR | Zbl

[24] Cullinan M. P., “Piecewise Convex-Concave Approximation in the Minimax Norm”, Abstracts of Conference on Approximation and Optimization: Algorithms, Complexity, and Applications (June 29–30, 2017, Athens, Greece), eds. I. Demetriou, P. Pardalos, National and Kapodistrian University of Athens, Athens, 2017, 4

[25] Shevaldin V. T., Approksimatciia lokalnymi splainami [Local approximation by splines], Ural Branch of RAS, Ekaterinburg, 2014, 198 pp. (In Russian)

[26] Leeuw J. Hornik K. Mair P., “Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods”, J. Stat. Softw., 32:5 (2009), 1–24 | DOI

[27] Li G., Pong T. K., “Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods”, Found. Comput. Math., 18:5 (2017), 1199–1232, arXiv: [math.OC] 1602.02915 | DOI | MR