# American Institute of Mathematical Sciences

• 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

 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.

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:

show all references

##### References:
 [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