Information based complexity for high dimensional sparse functions

DOI10.1016/j.jco.2019.101443OpenAlexW2985213689WikidataQ126853039 ScholiaQ126853039MaRDI QIDQ2303421

Ming Yuan, Cuize Han

Publication date: 3 March 2020

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2019.101443

zbMATH Keywords

smoothnesscurse of dimensionalityrandomized algorithmsinformation-based complexitysparsity

Mathematics Subject Classification ID

Numerical approximation and computational geometry (primarily algorithms) (65Dxx)

Related Items (2)

Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points ⋮ Sampling schemes and recovery algorithms for functions of few coordinate variables

Cites Work

• Minimax optimal rates of estimation in high dimensional additive models
• Sparsity in multiple kernel learning
• Approximation of functions of few variables in high dimensions
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• High-dimensional additive modeling
• A survey of information-based complexity
• Generalized additive models
• Deterministic and stochastic error bounds in numerical analysis
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Tractability and strong tractability of linear multivariate problems
• Sperner capacities
• ABC on IBC
• Complexity of approximation of functions of few variables in high dimensions
• Finding the minimum of a function
• On the Size of Separating Systems and Families of Perfect Hash Functions
• On decompositions of multivariate functions
• Algorithms for learning sparse additive models with interactions in high dimensions*
• Sparse grids
• Minimax-optimal rates for sparse additive models over kernel classes via convex programming
• Compressed sensing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Information based complexity for high dimensional sparse functions