-
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
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 |
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.
References:
| [1] |
F. Bach,
Self-concordant analysis for logistic regression, Electronic Journal of Statistics, 4 (2010), 384-414.
doi: 10.1214/09-EJS521. |
| [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. |
| [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. |
| [4] |
J. Diakonikolas and C. Guzmán, Lower bounds for parallel and randomized convex optimization, In Conference on Learning Theory, 2019, 1132-1157. |
| [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. |
| [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. |
| [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. |
| [8] |
A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983. |
| [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. |
| [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. |
| [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. |
| [12] |
B. E Woodworth and N. Srebro, Tight complexity bounds for optimizing composite objectives, In Advances in Neural Information Processing Systems, 2016, 3639-3647. |
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. |
| [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. |
| [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. |
| [4] |
J. Diakonikolas and C. Guzmán, Lower bounds for parallel and randomized convex optimization, In Conference on Learning Theory, 2019, 1132-1157. |
| [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. |
| [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. |
| [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. |
| [8] |
A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983. |
| [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. |
| [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. |
| [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. |
| [12] |
B. E Woodworth and N. Srebro, Tight complexity bounds for optimizing composite objectives, In Advances in Neural Information Processing Systems, 2016, 3639-3647. |
| [1] |
Hedy Attouch, Jalal Fadili, Vyacheslav Kungurtsev. On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping. Evolution Equations and Control Theory, 2022 doi: 10.3934/eect.2022022 |
| [2] |
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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101 |
| [3] |
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 |
| [4] |
Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial and Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945 |
| [5] |
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 |
| [6] |
Sylvia Anicic. Existence theorem for a first-order Koiter nonlinear shell model. Discrete and Continuous Dynamical Systems - S, 2019, 12 (6) : 1535-1545. doi: 10.3934/dcdss.2019106 |
| [7] |
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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 |
| [8] |
Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022003 |
| [9] |
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 |
| [10] |
Adolfo Damiano Cafaro, Simone Fiori. Optimization of a control law to synchronize first-order dynamical systems on Riemannian manifolds by a transverse component. Discrete and Continuous Dynamical Systems - B, 2022, 27 (7) : 3947-3969. doi: 10.3934/dcdsb.2021213 |
| [11] |
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 |
| [12] |
Mohammed Al Horani, Angelo Favini. First-order inverse evolution equations. Evolution Equations and Control Theory, 2014, 3 (3) : 355-361. doi: 10.3934/eect.2014.3.355 |
| [13] |
Afaf Bouharguane, Pascal Azerad, Frédéric Bouchette, Fabien Marche, Bijan Mohammadi. Low complexity shape optimization & a posteriori high fidelity validation. Discrete and Continuous Dynamical Systems - B, 2010, 13 (4) : 759-772. doi: 10.3934/dcdsb.2010.13.759 |
| [14] |
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 |
| [15] |
Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 |
| [16] |
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 |
| [17] |
R. P. Gupta, Peeyush Chandra, Malay Banerjee. Dynamical complexity of a prey-predator model with nonlinear predator harvesting. Discrete and Continuous Dynamical Systems - B, 2015, 20 (2) : 423-443. doi: 10.3934/dcdsb.2015.20.423 |
| [18] |
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 |
| [19] |
Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334 |
| [20] |
Yuhki Hosoya. First-order partial differential equations and consumer theory. Discrete and Continuous Dynamical Systems - S, 2018, 11 (6) : 1143-1167. doi: 10.3934/dcdss.2018065 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]