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  February 2021 Early access  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]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[2]

Matteo Ludovico Bedini, Rainer Buckdahn, Hans-Jürgen Engelbert. On the compensator of the default process in an information-based model. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 10-. doi: 10.1186/s41546-017-0017-4
[3]

Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945
[4]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[5]

Sylvia Anicic. Existence theorem for a first-order Koiter nonlinear shell model. Discrete & Continuous Dynamical Systems - S, 2019, 12 (6) : 1535-1545. doi: 10.3934/dcdss.2019106
[6]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[7]

William Guo. Unification of the common methods for solving the first-order linear ordinary differential equations. STEM Education, 2021, 1 (2) : 127-140. doi: 10.3934/steme.2021010
[8]

Adolfo Damiano Cafaro, Simone Fiori. Optimization of a control law to synchronize first-order dynamical systems on Riemannian manifolds by a transverse component. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021213
[9]

Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015
[10]

Mohammed Al Horani, Angelo Favini. First-order inverse evolution equations. Evolution Equations & Control Theory, 2014, 3 (3) : 355-361. doi: 10.3934/eect.2014.3.355
[11]

Afaf Bouharguane, Pascal Azerad, Frédéric Bouchette, Fabien Marche, Bijan Mohammadi. Low complexity shape optimization & a posteriori high fidelity validation. Discrete & Continuous Dynamical Systems - B, 2010, 13 (4) : 759-772. doi: 10.3934/dcdsb.2010.13.759
[12]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[13]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[14]

Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019
[15]

R. P. Gupta, Peeyush Chandra, Malay Banerjee. Dynamical complexity of a prey-predator model with nonlinear predator harvesting. Discrete & Continuous Dynamical Systems - B, 2015, 20 (2) : 423-443. doi: 10.3934/dcdsb.2015.20.423
[16]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[17]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334
[18]

Yuhki Hosoya. First-order partial differential equations and consumer theory. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1143-1167. doi: 10.3934/dcdss.2018065
[19]

Ansgar Jüngel, Ingrid Violet. First-order entropies for the Derrida-Lebowitz-Speer-Spohn equation. Discrete & Continuous Dynamical Systems - B, 2007, 8 (4) : 861-877. doi: 10.3934/dcdsb.2007.8.861
[20]

Pierre Fabrie, Alain Miranville. Exponential attractors for nonautonomous first-order evolution equations. Discrete & Continuous Dynamical Systems, 1998, 4 (2) : 225-240. doi: 10.3934/dcds.1998.4.225

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (168)
  • HTML views (242)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences