Friday, November 30th, 2007
3:30pm
WEH 7220
Title: Efficient algorithms for agnostic learning (aka learning with arbitrary noise)
Adam Kalai
Georgia Tech
Abstract:
The talk will give an overview of theoretical results for learning from extremely n01sy data, including a boosting procedure and algorithms for learning decision trees, halfspaces, and parity functions.
Who: Kanat Tangwongsan
Where: NSH 1507
When: 2007-11-28 12:00
L_p-Norm Set Cover
Abstract:
In many optimization problems, a solution can be viewed as ascribing a “cost” to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize some $L_p$-norm (or some other symmetric convex function or norm) of the vector of costs—though different applications may suggest different norms to use. Ideally, we want to obtain a solution that optimizes several norms simultaneously.
We will examine a natural problem in this framework: the $L_p$ set-cover problem. Suppose we pick sets $S_1, S_2, ldots, S_t$ (in that order), and define the {em cover time} of an element $e$ to be $C_e = \min{i | e in S_i}$, the index of the first set that covers $e$. Minimizing the maximum cover time $|C|_infty$ gives us the classical min-set cover, for which the greedy algorithm is an $O(log n)$ approximation (which is the best possible). Minimizing the average (or total) cover time $\sum_e C_e = |C|_1$ gives the min-sum set-cover (mssc) problem, for which the greedy algorithm gives a 4-approximation (which also is tight). This leads us to a natural question:
How well does the greedy algorithm perform for the $L_p$ set-cover problem, where the objective function is $|C|_p = (\sum_e C_e^p)^{1/p}$ for $1 \leq p \leq \infty$?
In this talk, we will give tight results for this problem: the greedy algorithm \emph{simultaneously} gives an $O(p)$-approximation for $L_p$-Set-Cover for all values of $1 leq p < infty$ (even for the weighted version), and that there are simple examples where this is tight for all values of $p$. In fact, we also show that for every fixed value of $p$, no efficient algorithm can obtain an approximation guarantee better than $\Omega(p)$ under suitable complexity assumptions. We will show how to apply our analysis techniques to the more general {\em submodular set cover} and prove some results for the so-called {\em pipelined set cover} problem.
This is joint work with Daniel Golovin, Anupam Gupta, and Amit Kumar.
Title: Log-Concave Random Graphs
Speaker: Alan Frieze
When: November 29, 16:30-17:30
Where: Wean Hall 5302
Abstract:
We propose the following model of a random graph on $n$ vertices. Let $F$ be a distribution in $R_+^{n(n-1)/2}$ with a coordinate for every pair $ij$ with $1 \le i,j \le n$. Then $G_{F,p}$ is the distribution on graphs with $n$ vertices obtained by picking a random point $X$ from a distribution with a log-concave density $f$ and defining a graph on $n$ vertices whose edges
are pairs $ij$ for which $X_{ij} \le p$. The standard Erd\H{o}s-R\’{e}nyi model is the special case when $F$ is the indicator function for the We thus obtain an interesting connection between convex geometry and random graphs.
When $f$ is down-monotone we can determine the connectivity and matching thresholds up to a constant factor. When $f$ is the indicator function for a right simplex then we can obtain more precise results on connectivity and the diameter.
If $X$ is used to define weights for an optimization problem and $f$ is “column independent” then we can whp solve the ATSP asymptotically.
Joint work with Santosh Vempala and Juan Vera
Title: Optimization under Uncertainty (Thesis Proposal)
Speaker: Vineet Goyal
When: November 29, 10:30am
Where: Room 388, Tepper School
Abstract
Most optimization problems in real life do not have accurate estimates of the problem parameters at the optimization phase. Stochastic optimization models have been studied widely in the literature to address this problem. The expected value optimization is reasonable in a repeated decision making framework. However, it does not sufficiently guard against the worst case future in more risk averse or one-shot applications. The broad purpose of this thesis is to study optimization approaches under uncertainty that overcome this shortcoming of a traditional stochastic optimization model.
We consider new models of uncertainty namely, the “demand-robust” model and the “chance constrained” model and introduce these in the framework of general covering problems. Here, uncertainty is considered in the right hand side of the constraints and is referred to as the demand uncertainty. In the two-stage model of “demand-robustness”, motivated by recent work in two-stage stochastic optimization problems, we are interested in finding a solution such that the worst case cost over all realizations of uncertainty is minimized. We prove a general structural lemma about special types of first stage solutions and provide approximation algorithms for covering problems such as Steiner tree, min-cut, minimum multi-cut, vertex cover and facility location. While some of the algorithms draw from the rounding approaches developed recently for stochastic optimization problems, we also show new applications of the old metric rounding techniques and develop novel charging arguments using Gomory-Hu cut trees for cut problems.
The robust optimization approach guards against the worst case future but tends to be overly conservative if there are some outlier scenarios. To overcome this, we consider a chance constrained model where we are given a reliability level p and the idea is to select a “p fraction” of the scenarios and find a robust solution on the selected scenarios. The remaining (1-p) fraction of the scenarios are considered as outliers and can be ignored. We consider both one-stage and two-stage chance constrained covering problems with demand-uncertainty. When the demand-uncertainty follows an independent distribution, we show that one-stage chance constrained covering problems reduce to a weighted version of well studied partial covering problems and we obtain constant approximations for the Steiner tree and facility location problems in this model. We also show hardness results for both one-stage and two-stage chance constrained problem in a “correlated” demand-uncertainty model.
In both the above models, we consider uncertainty in the right hand side of the constraints. We extend our work to consider uncertainty in the constraint matrix referred to as data uncertainty and propose to study a chance constrained knapsack problem where the size of each item is random. Finally, we propose to use the theoretical framework to develop a practical solution methodology to solve the planning problem for post-disaster logistics. This problem combines
aspects of both demand and data uncertainty. We aim to implement our solution to solve the real-life problem of earthquake preparedness of Turkey and Israel where seismic risk is a major concern.
A month ago I wrote about how to install MiKTeX 2.5 concurrently with 2.6 so that I can run Ipe 6.0pre28 on my main production machine.
Well, Ipe 6.0pre30 has just been released yesterday. From the announcement email, the major features of this release include:
* Ipe now works with pdftex 1.40 (in MikTeX 2.6 and texlive 2007).
* Pascal-Nicolas Becker, Frederik Hermans, and Damian Schmidt
implemented the missing forms of intersection snapping (for arcs
and Bezier curves), with bug fix by Jonathan Backer.* Fixed the broken user interface (fields were too small to contain
the text) on Unix (removed a static QFont) (bug #191).* Figtoipe now distributed separately.
I note that the source and the windows packages are already available at the LuaForge download site.
Thanks Otfried!
