Runtime guarantees for regression problems

DOI10.1145/2422436.2422469zbMath1361.68108arXiv1110.1358OpenAlexW1968307589MaRDI QIDQ2986877

Richard Peng, Aleksander Mądry, Hui Han Chin, Gary Lee Miller

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.1358

zbMATH Keywords

optimizationimage processingregression

Mathematics Subject Classification ID

Ridge regression; shrinkage estimators (Lasso) (62J07) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Hardness Results for Structured Linear Systems ⋮ A Laplacian approach to \(\ell_1\)-norm minimization

Uses Software

• LASSO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Runtime guarantees for regression problems