American Institute of Mathematical Sciences

Advanced
doi: 10.3934/ipi.2020047

Some worst-case datasets of deterministic first-order methods for solving binary logistic regression

Yuyuan Ouyang , and  Trevor Squires

School of Mathematical and Statistical Sciences, Clemson University, Clemson, SC 29634, USA

* Corresponding author: Yuyuan Ouyang

Received  December 2019 Revised  April 2020 Published  August 2020

Fund Project: The authors are supported by National Science Foundation grant DMS-1913006 and Office of Naval Research grant N00014-19-1-2295

We present in this paper some worst-case datasets of deterministic first-order methods for solving large-scale binary logistic regression problems. Under the assumption that the number of algorithm iterations is much smaller than the problem dimension, with our worst-case datasets it requires at least $ {{{\mathcal O}}}(1/\sqrt{\varepsilon}) $ first-order oracle inquiries to compute an $ \varepsilon $-approximate solution. From traditional iteration complexity analysis point of view, the binary logistic regression loss functions with our worst-case datasets are new worst-case function instances among the class of smooth convex optimization problems.

Keywords: Binary Logistic Regression, Nonlinear Optimization, First-Order Methods, Lower Complexity Bound, Information-Based Complexity.
Mathematics Subject Classification: Primary: 90C06, 90C25, 90C30.
Citation: Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems & Imaging, doi: 10.3934/ipi.2020047
References:
[1]

F. Bach, Self-concordant analysis for logistic regression, Electronic Journal of Statistics, 4 (2010), 384-414.  doi: 10.1214/09-EJS521.  Google Scholar

[2]

Y. Carmon, J. C Duchi, O. Hinder and A. Sidford, Lower bounds for finding stationary points Ⅰ, Mathematical Programming, 2019, 1-50. doi: 10.1007/s10107-019-01406-y.  Google Scholar

[3]

Y. Carmon, J. C Duchi, O. Hinder and A. Sidford, Lower bounds for finding stationary points Ⅱ: First-order methods, Mathematical Programming, 2019, 1-41. doi: 10.1007/s10107-019-01431-x.  Google Scholar

[4]

J. Diakonikolas and C. Guzmán, Lower bounds for parallel and randomized convex optimization, In Conference on Learning Theory, 2019, 1132-1157. Google Scholar

[5]

Y. Drori, The exact information-based complexity of smooth convex minimization, Journal of Complexity, 39 (2017), 1-16.  doi: 10.1016/j.jco.2016.11.001.  Google Scholar

[6]

C. Guzmán and A. Nemirovski, On lower complexity bounds for large-scale smooth convex optimization, Journal of Complexity, 31 (2015), 1-14.  doi: 10.1016/j.jco.2014.08.003.  Google Scholar

[7]

A. Juditsky and Y. Nesterov, Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization, Stochastic Systems, 4 (2014), 44-80.  doi: 10.1214/10-SSY010.  Google Scholar

[8]

A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983.  Google Scholar

[9]

A. S. Nemirovski, Information-based complexity of linear operator equations, Journal of Complexity, 8 (1992), 153-175.  doi: 10.1016/0885-064X(92)90013-2.  Google Scholar

[10]

Y. E. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Massachusetts, 2004. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[11]

Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Mathematical Programming, 2019, 1-35. doi: 10.1007/s10107-019-01420-0.  Google Scholar

[12]

B. E Woodworth and N. Srebro, Tight complexity bounds for optimizing composite objectives, In Advances in Neural Information Processing Systems, 2016, 3639-3647. Google Scholar

show all references

References:
[1]

F. Bach, Self-concordant analysis for logistic regression, Electronic Journal of Statistics, 4 (2010), 384-414.  doi: 10.1214/09-EJS521.  Google Scholar

[2]

Y. Carmon, J. C Duchi, O. Hinder and A. Sidford, Lower bounds for finding stationary points Ⅰ, Mathematical Programming, 2019, 1-50. doi: 10.1007/s10107-019-01406-y.  Google Scholar

[3]

Y. Carmon, J. C Duchi, O. Hinder and A. Sidford, Lower bounds for finding stationary points Ⅱ: First-order methods, Mathematical Programming, 2019, 1-41. doi: 10.1007/s10107-019-01431-x.  Google Scholar

[4]

J. Diakonikolas and C. Guzmán, Lower bounds for parallel and randomized convex optimization, In Conference on Learning Theory, 2019, 1132-1157. Google Scholar

[5]

Y. Drori, The exact information-based complexity of smooth convex minimization, Journal of Complexity, 39 (2017), 1-16.  doi: 10.1016/j.jco.2016.11.001.  Google Scholar

[6]

C. Guzmán and A. Nemirovski, On lower complexity bounds for large-scale smooth convex optimization, Journal of Complexity, 31 (2015), 1-14.  doi: 10.1016/j.jco.2014.08.003.  Google Scholar

[7]

A. Juditsky and Y. Nesterov, Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization, Stochastic Systems, 4 (2014), 44-80.  doi: 10.1214/10-SSY010.  Google Scholar

[8]

A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983.  Google Scholar

[9]

A. S. Nemirovski, Information-based complexity of linear operator equations, Journal of Complexity, 8 (1992), 153-175.  doi: 10.1016/0885-064X(92)90013-2.  Google Scholar

[10]

Y. E. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Massachusetts, 2004. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[11]

Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Mathematical Programming, 2019, 1-35. doi: 10.1007/s10107-019-01420-0.  Google Scholar

[12]

B. E Woodworth and N. Srebro, Tight complexity bounds for optimizing composite objectives, In Advances in Neural Information Processing Systems, 2016, 3639-3647. Google Scholar

[1]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[2]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[3]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045
[4]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269
[5]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[6]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247
[7]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216
[8]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049
[9]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[10]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[11]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[12]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[13]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026
[14]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[15]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322
[16]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[17]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[18]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[19]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[20]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020  doi: 10.3934/fods.2020017

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (24)
  • HTML views (155)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences