Runtime guarantees for regression problems

DOI10.1145/2422436.2422469zbMATH Open1361.68108arXiv1110.1358OpenAlexW1968307589MaRDI QIDQ2986877FDOQ2986877

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

Publication date: 16 May 2017

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

Abstract: We study theoretical runtime guarantees for a class of optimization problems that occur in a wide variety of inference problems. these problems are motivated by the lasso framework and have applications in machine learning and computer vision. Our work shows a close connection between these problems and core questions in algorithmic graph theory. While this connection demonstrates the difficulties of obtaining runtime guarantees, it also suggests an approach of using techniques originally developed for graph algorithms. We then show that most of these problems can be formulated as a grouped least squares problem, and give efficient algorithms for this formulation. Our algorithms rely on routines for solving quadratic minimization problems, which in turn are equivalent to solving linear systems. Finally we present some experimental results on applying our approximation algorithm to image processing problems.

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

zbMATH Keywords

optimizationregressionimage processing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

Uses Software

• LASSO

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986877)