IBM®
Skip to main content
    United States [change]    Terms of use
  
 
 
    Home    Products    Services & solutions    Support & downloads    My account    
IBM Research

(none)

Activity Report


  Activity Report, January - June 2008
clear image

Highlights

An Efficient Algorithm for Bandit Linear Optimization
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin introduced an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal O*(T1/2) regret. The setting is a natural generalization of the non-stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of recent papers. They showed how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function. The work was published in COLT 2008.

Corruption and Recovery-Efficient Locally Decodable Codes
A locally decodable code (LDC) allows one to encode messages into codewords such that individual bits of the message can be recovered from a corrupted codeword y by probing only a few positions of y. This is in contrast to standard error-correcting codes which require first decoding the entire codeword, even if one is only interested in a single bit of the message. If the encoding is a linear transformation, the LDC is called linear. In RANDOM 2008, David Woodruff constructed the first non-linear LDCs, and showed that if only two positions in y are queried to recover message bits, then non-linear LDCs are provably shorter than linear LDCs, answering a question of Kerenidis and de Wolf. The work gives a general transformation from linear LDCs into non-linear LDCs which achieve the best known tradeoffs between the fraction of codeword bits that can be corrupted and the probability of recovering a bit of the message.

Epistemic Privacy
Most known definitions of privacy are focused either on theoretical soundness, or on practical usefulness, but not on both. In an attempt to reduce the gap between these two aspects, Alexandre Evfimievski, Ronald Fagin, and David Woodruff introduced and studied a novel privacy definition, set in the framework of offline (retroactive) database query auditing. According to this definition, an audited property A is private, given the disclosure of a fact B, if no user can gain confidence in A by learning B, subject to prior knowledge constraints. Database users are modeled as either possibilistic agents whose knowledge is a set of possible databases, or as probabilistic agents whose knowledge is a probability distribution on possible databases. The new privacy notion is shown to be significantly more flexible than earlier approaches, and criteria are derived that allow an auditor to test privacy efficiently in some important cases. A paper describing these results was presented at the 27th ACM Symposium on Principles of Database Systems (PODS 2008); the full version of this paper was subsequently invited to a special issue of the Journal of the ACM for selected papers from PODS 2008.

Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs
The problem of prediction from expert advice is fundamental in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds. Cesa-Bianchi, Mansour and Stoltz posed the question whether it is possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper Elad Hazan and Satyen Kalen resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization.

Power of Membership Queries in Agnostic Learning
Vitaly Feldman studied the properties of the agnostic learning framework of Haussler (1992) and Kearns, Schapire and Sellie (1992). In particular, he addressed the question: is there any situation in which membership queries are useful in agnostic learning? He showed that the answer is negative for distribution-independent agnostic learning and positive for agnostic learning with respect to a specific marginal distribution. Namely, he gives a proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries. This resolves an open problem posed by Kearns et al. (1992). For agnostic learning with respect to the uniform distribution over {0,1}n, he shows a concept class that is learnable with membership queries but computationally hard to learn from random examples alone (assuming that one-way functions exist). These results were presented at Conference on Learning Theory (COLT), 2008.

Sparse Approximate Solutions to Semidefinite Programs
Elad Hazan analyzed a generalization of the Frank-Wolfe algorithm for approximately maximizing a concave function over the bounded semi-definite cone which produces sparse solutions (sparsity for SDP corresponds to low rank matrices). This work appeared in LATIN 2008.

Streaming Numerical Linear Algebra Problems
Ken Clarkson and David Woodruff found one-pass algorithms for some approximate matrix operations, including the computation of matrix products and the estimation of best low-rank projections. These algorithms maintain small "sketches" of the input matrices; with high probability, the product of the sketches is close to the true matrix product. Specifically, the Frobenius norm of the error is proportional to the product of the Frobenius norms of the input matrices. This upper bound result sharpens and simplifies prior work on this problem, and our matching lower bounds show that little improvement is possible.

Tight Lower Bounds for Selection in Randomly Ordered Streams
The model of data streams where the data arrives in a random order arises in several scenarios. It is also motivated by the attempt to overcome the barrier of pessimistic lower bounds on space and/or number of passes that can be shown with the usual (adversarial) order. Recently, there has a been a resurgence of interest in this model although historically, random-order data streams were considered even in the seminal paper of data streams by Munro and Paterson from FOCS 1978. In a joint SODA, 2008 paper with Amit Chakrabarti (Dartmouth) and Mihai Pătraşcu (MIT), T.S. Jayram resolves an open question from their paper on computing the median, a fundamental aggregate in order statistics. In particular, the paper show that any algorithm computing the median of a stream presented in random order, using polylog(n) space, requires an optimal Omega(log log n) passes.

Towards a Theory of Schema-Mapping Optimization
A schema mapping is a high-level specification that describes the relationship between two database schemas. Even though several different aspects of schema mappings have been explored in considerable depth, the study of schema-mapping optimization remains largely uncharted territory to date. In this work, Ron Fagin, Phokion Kolaitis, Alan Nash, and Lucian Popa lay the foundation for the development of a theory of schema-mapping optimization. They introduce several useful notions of "equivalence" between schema mappings. They show under what conditions a more complex schema mapping is equivalent to a much simpler schema mapping. A paper describing these results was presented at the 27th ACM Symposium on Principles of Database Systems (PODS 2008).

Awards and Honors

Elad Hazan received the best student co-authored paper in COLT 2008. Joint work with Jacob Abernethy and Alexander Rakhlin.

N. Megiddo received the IBM Bravo Award, January 15, 2008.

N. Megiddo and D. Modha received the Suppelemental Patent Issue Award, April 15, 2008.

A. Amir and N. Megiddo received the Invention Achievement Award, May 30, 2008.

N. Megiddo et al., received the Patent Issue Award, June 30, 2008.

Phokion G. Kolaitis and Moshe Y. Vardi were awarded the 2008 ACM PODS Alberto O. Mendelzon Test-of-Time Award for the paper "Conjunctive Query Containment and Constraint Satisfaction" published in the proceedings of the 1998 PODS conference.

Ron Fagin and Phokion Kolaitis won IBM Outstanding Technical Achievement Awards for "Schema mappings: theory and practice". This was joint with Lucian Popa, Howard Ho, Laura Haas, and Mauricio A. Hernandez.


Publications and Conferences

J. Abernethy, E. Hazan, and A. Rakhlin, “An Efficient Algorithm for Bandit Linear Optimization”, Proceedings of Conference on Learning Theory (COLT), 2008.

F. Afrati and Ph.G. Kolaitis, “Answering Aggregate Queries in Data Exchange”, Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS), 129-138, 2008.

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis, “Exponential Separation of Quantum and Classical One-Way Communication Complexity”, SIAM J. Comput. 38(1): 366-384, 2008.

Amit Chakrabarti, T. S. Jayram, Mihai Pătraşcu, “Tight lower bounds for selection in randomly ordered streams”, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 720-729, January, 2008: 720-729

L. Chiticariu, Ph.G. Kolaitis, and L. Popa, “Interactive generation of integrated schema”, Proceedings of the 28th ACM Conference on Management of Data (SIGMOD), 833-846, 2008.

Ken Clarkson, “Coresets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm”, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January, 2008.

Ken Clarkson, “Tighter Bounds for Random Projections of Manifolds”, Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry (SoCG), June 2008.

K. Clarkson and C. Seshadhri, “Self-Improving Algorithms for Delaunay Triangulations”, Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry (SoCG), June, 2008.

A. Evfimievski, R. Fagin, and D. Woodruff, “Epistemic Privacy”, Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS), Vancouver, 2008, pp. 171-180.

R. Fagin, Ph.G. Kolaitis, L. Popa, and W.C. Tan, “Quasi-Inverses of Schema Mappings", ACM Transactions on Database Systems (TODS), Vol. 33, No. 2, June, 2008 (Special issue for selected papers from the 2007 ACM Symposium on Principles of Database Systems).

R. Fagin, Ph.G. Kolaitis, A. Nash, and L. Popa, “Towards a theory of schema-mapping optimization”, Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS), 33-42, 2008.

Vitaly Feldman, “Evolvability from Learning Algorithms”, Proceedings of the ACM Symposium on Theory of Computing (STOC), 619-628, May, 2008.

Vitaly Feldman, “On The Power of Membership Queries in Agnostic Learning”, Proceedings of Conference on Learning Theory (COLT), 147-156, 2008.

Vitaly Feldman and Leslie Valiant, “The Learning Power of Evolution”, Open Problems/New Directions session of Conference on Learning Theory (COLT), 513-514, 2008.

Elad Hazan, “Sparse Approximate Solutions to Semidefinite Programs”, Proceedings of LATIN, 2008.

E. Hazan and S. Kale, “Regret Bounded by Variation in Costs”, Proceedings of Conference on Learning Theory (COLT), 2008.

David Woodruff, “Corruption and Recovery-Efficient Locally Decodable Codes”, Proceedings of APPROX-RANDOM, 584-595, 2008.

Patents and Patent Applications

D. Dash, G. Lohman, N. Megiddo, and J. Rao, "Discovering Interestingness in Advanced Faceted Search," U.S. 7,392,250, issued 6/24/2008.

M. Kutsch, V. Markl, N. Megiddo, and T.M. Tran, "Selectivity Estimation for Conjunctive Predicates in the Presences of Partial Knowledge About Multivariate Data Distributions," U.S. 7,376,639, issued 5/20/2008.

H. Jin, J. Lotspiech, N. Megiddo and M.J. Nelson, "Adaptive Traitor Tracing," Docket ARC920080024US1, filed June 20, 2008.

A. Amir and N. Megiddo, "A Method for Dynamically Freeing Up Computer Resources," Docket ARC920070102US1, filed May 20, 2008.

E. Hazan and N. Megiddo, "Method for Machine Learning wtih State Information," Docket ARC920070023US2, filed June 5, 2008.

G. Lohman, N. Megiddo and J. Rao, "Discovering Interestingness in Advanced Faceted Search," Docket ARC920070042US@, filed May 9, 2008.

N. Megiddo, "Method for Operating and Managing a Re-Fueling Business,” Docket ARC920070026, filed March 26, 2008.

R. Krauthgamer and N. Megiddo, "Computer System Management and Throughput Maximization Under Peak Power Constraints," Docket ARC920060053US2, filed May 29, 2008.

W. Fan, G. Lohman, V. Markl, N. Megiddo, L. Rao, and D. Simmen, “Automatically and Adaptively Determining Execution Plans for Queries with Parameter Markers," Docket ARC920060085US2, filed May 22, 2008.

M. Kutsch, V. Markl, N. Megiddo and T.M. Tran, "Selectivity Estimation for Conjunctive Predicates in the Presence of Partial Knowledge About Multivariate Data Distributions," Docket ARC920050041US2, filed March 4, 2008.

G. Lohman, N. Megiddo, J. Rao, and C. ZHANG, "System and Method for Automating Data Partitioning in a Parallel Database," Docket ARC920020042US2, filed April 28, 2008.

Presentations and Seminars

    About IBM    Privacy    Contact