American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Stochastic greedy algorithms for multiple measurement vectors
  • IPI Home
  • This Issue
  • Next Article
    Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data
February  2021, 15(1): 63-77. 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, 2021, 15 (1) : 63-77. 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]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[2]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[3]

Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028
[4]

Hong Yi, Chunlai Mu, Guangyu Xu, Pan Dai. A blow-up result for the chemotaxis system with nonlinear signal production and logistic source. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2537-2559. doi: 10.3934/dcdsb.2020194
[5]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[6]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[7]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169
[8]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565
[9]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[10]

Jumpei Inoue, Kousuke Kuto. On the unboundedness of the ratio of species and resources for the diffusive logistic equation. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2441-2450. doi: 10.3934/dcdsb.2020186
[11]

Meiqiao Ai, Zhimin Zhang, Wenguang Yu. First passage problems of refracted jump diffusion processes and their applications in valuing equity-linked death benefits. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021039
[12]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[13]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[14]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[15]

Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017
[16]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[18]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[19]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[20]

Wei Wang, Degen Huang, Haitao Yu. Word sense disambiguation based on stretchable matching of the semantic template. Mathematical Foundations of Computing, 2021, 4 (1) : 1-13. doi: 10.3934/mfc.2020022

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (71)
  • HTML views (239)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences