Fetching the paper…
Reading the bibliography…
We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness.
A. Nemirovski and D. Yudin, Problem complexity and method efficiency in optimization , 1st ed. Wiley -Interscience, 1983
1983
Earlier work this paper cites.
G. Pisier, The Volume of Convex Bodies and Banach Space Geometry , 1st ed. Cambridge University Press, 1989
1989
Earlier work this paper cites.
A. Nemirovski, “Efficient methods in convex programming,” 1994, lecture notes. [Online]. Available: http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
1994
Earlier work this paper cites.
A. Ben-Tal, T. Margalit, and A. Nemirovski, “The ordered subsets mirror descent optimization method with applications to tomography,” SIAM J. Optim , vol. 12, p. 2001, 2001
2001
Earlier work this paper cites.
Y. Nesterov, Introductory lectures on convex optimization: a basic course , 1st ed. Springer Netherlands, 2004
2004
Earlier work this paper cites.
T. Cover and J. Thomas, Elements of information theory . Wiley-interscience, 2006
2006
Earlier work this paper cites.
F. A. Chudak and K. Nagano, “Efficient solutions to relaxations of combinatorial problems with submodular penalties via the lovász extension and non-smooth convex optimization,” in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms . Society for Industrial and Applied Mathematics, 2007, pp. 79–88
2007
Earlier work this paper cites.
A. Beck and M. Teboulle, “Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems,” IEEE Transactions on Image Processing , vol. 18, no. 11, pp. 2419–2434, 2009
2009
Earlier work this paper cites.
A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM J. Img. Sci. , vol. 2, no. 1, pp. 183–202, Mar. 2009
2009
Earlier work this paper cites.
G. Goel, C. Karande, P. Tripathi, and L. Wang, “Approximability of combinatorial problems with multi-agent submodular cost functions,” in Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on . IEEE, 2009, pp. 755–764
2009
Earlier work this paper cites.
S. Iwata and K. Nagano, “Submodular function minimization under covering constraints,” in Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on . IEEE, 2009, pp. 671–680
2009
Earlier work this paper cites.
S. Arora and B. Barak, Computational complexity . Cambridge: Cambridge University Press, 2009
2009
Cited alongside, same era.
M. Zhu, S. J. Wright, and F. T. Chan, “Duality-based algorithms for total-variation-regularized image restoration,” Comput. Optim. Appl. , vol. 47, no. 3, pp. 377–400, Nov. 2010
2010
Cited alongside, same era.
M. Braverman and A. Rao, “Information equals amortized communication,” in Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on . IEEE, 2011, pp. 748–757
2011
Cited alongside, same era.
M. Pǎtraşcu, “Unifying the landscape of cell-probe lower bounds,” SIAM Journal on Computing , vol. 40, no. 3, pp. 827–847, 2011
2011
Cited alongside, same era.
Z. Svitkina and L. Fleischer, “Submodular approximation: Sampling-based algorithms and lower bounds,” SIAM Journal on Computing , vol. 40, no. 6, pp. 1715–1737, 2011
S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher, “Block-coordinate Frank-Wolfe optimization for structural SVMs,” in Proceedings of the 30th International Conference on Machine Learning (ICML-13) , 2013, pp. 53–61
2013
Later among the works it cites.
Y. Nesterov and A. Nemirovski, “On first-order algorithms for ℓ 1 \ell_{1} /nuclear norm minimization,” Acta Numerica , vol. 22, pp. 509–575, 4 2013
2013
Later among the works it cites.
G. Braun and S. Pokutta, “Common information and unique disjointness,” Proceedings of FOCS , 2013
2013
Later among the works it cites.
A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor, “Information cost tradeoffs for augmented index and streaming language recognition,” SIAM Journal on Computing , vol. 42, no. 1, pp. 61–83, 2013
2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2011
Cited alongside, same era.
M. Raginsky and A. Rakhlin, “Information-based complexity, feedback and dynamics in convex programming,” IEEE Transactions on Information Theory , vol. 57, no. 10, pp. 7036–7056, 2011
2011
Cited alongside, same era.
M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, “From information to exact communication,” in Electronic Colloquium on Computational Complexity (ECCC) , vol. 19, 2012, p. 171
2012
Cited alongside, same era.
A. Dasgupta, R. Kumar, and D. Sivakumar, “Sparse and lopsided set disjointness via information theory,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer, 2012, pp. 517–528
2012
Cited alongside, same era.
M. Braverman and A. Moitra, “An information complexity approach to extended formulations,” in Proceedings of STOC , Jun. 2013, pp. 161–170. [Online]. Available: https://eccc.weizmann.ac.il/report/2012/131/
2012
Cited alongside, same era.
A. Agarwal, P. L. Bartlett, P. D. Ravikumar, and M. J. Wainwright, “Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization,” IEEE Transactions on Information Theory , vol. 58, no. 5, pp. 3235–3249, 2012
2012
Cited alongside, same era.
N. Srebro and K. Sridharan, “On convex optimization, fat shattering and learning,” Unpublished, 2012. [Online]. Available: http://ttic.uchicago.edu/~karthik/optfat.pdf
2012
Cited alongside, same era.
2013
Later among the works it cites.
D. Garber and E. Hazan, “Playing Non-linear Games with Linear Oracles,” Proceedings of FOCS , 2013
2013
Later among the works it cites.
H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, and A. Sprock, “The string guessing problem as a method to prove lower bounds on the advice complexity,” Theoretical Computer Science , vol. 554, pp. 95–108, Oct. 16 2014
2014
Closest in time.
C. Guzmán, “Information, complexity and structure in convex optimization,” Ph.D. dissertation, Georgia Institute of Technology, May 2015
2015
Closest in time.
C. Guzmán and A. Nemirovski, “On lower complexity bounds for large-scale smooth convex optimization,” Journal of Complexity , vol. 31, no. 1, pp. 1–14, Feb. 2015
2015
Closest in time.
G. Braun, S. Fiorini, and S. Pokutta, “Average case polyhedral complexity of the maximum stable set problem,” Mathematical Programming , vol. 160, pp. 407–431, Mar. 2016
2016
Closest in time.
G. Lan, “The complexity of large-scale convex programming under a linear optimization oracle,” 2013. [Online]. Available: https://bpb-us-w2.wpmucdn.com/sites.gatech.edu/dist/f/330/files/2016/02/OptCndG6-26.pdf
2016
Closest in time.