arXiv research

This paper improves online learning algorithms for LP problems, achieving better regret bounds.

New algorithm reduces online decision-making regret with efficient LP re-solving and parallel first-order method.

Optimized algorithms for online learning with linear constraints improve performance and provide worst-case analysis.

The paper tackles online resource allocation with uncertain coefficients and chance constraints.

Unified approach for optimizing predictions in linear programming and inverse problems.

Develops an online method for solving constrained optimization problems with debiasing techniques.

Fast algorithm for online optimization on transport polytopes.

New MIP approach for efficient change-point detection.

New method for identifying best arm in batched multi-armed bandit problems.

In this paper, we consider the problem of preserving privacy in the online learning setting. We study the problem in the online convex programming (OCP) framework---a popular online learning setting with several interesting theoretical and practical implications---while using differential privacy as the formal privacy …

Algorithm reduces episode count for CMDPs with constraints.

We describe an approximate dynamic programming (ADP) approach to compute approximations of the optimal strategies and of the minimal losses that can be guaranteed in discounted repeated games with vector-valued losses. Such games prominently arise in the analysis of regret in repeated decision-making in adversarial env…

Unified LP framework for offline reward learning from human demonstrations and feedback.

New method solves nonseparable stochastic control problems.

Determining the programming language of a source code file has been considered in the research community; it has been shown that Machine Learning (ML) and Natural Language Processing (NLP) algorithms can be effective in identifying the programming language of source code files. However, determining the programming lang…

New OLO algorithms use Stein's method for better performance tradeoffs.

Framework learns linear programs from optimal decisions.

We study the task of online boosting--combining online weak learners into an online strong learner. While batch boosting has a sound theoretical foundation, online boosting deserves more study from the theoretical perspective. In this paper, we carefully compare the differences between online and batch boosting, and pr…

New method for online inference of constrained optimization problems.

New algorithms robust to adversarial data achieve optimal performance.

Framework optimizes battery storage for markets by separating long-term degradation from short-term market dynamics.

Solving linear programs by using entropic penalization has recently attracted new interest in the optimization community, since this strategy forms the basis for the fastest-known algorithms for the optimal transport problem, with many applications in modern large-scale machine learning. Crucial to these applications h…

This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two…

Online advertising in E-commerce platforms provides sellers an opportunity to achieve potential audiences with different target goals. Ad serving systems (like display and search advertising systems) that assign ads to pages should satisfy objectives such as plenty of audience for branding advertisers, clicks or conver…

Real-world problems of operations research are typically high-dimensional and combinatorial. Linear programs are generally used to formulate and efficiently solve these large decision problems. However, in multi-period decision problems, we must often compute expected downstream values corresponding to current decision…

Approximate linear programming (ALP) represents one of the major algorithmic families to solve large-scale Markov decision processes (MDP). In this work, we study a primal-dual formulation of the ALP, and develop a scalable, model-free algorithm called bilinear $π$ learning for reinforcement learning when a sampling or…

This paper proposes an online tree-based Bayesian approach for reinforcement learning. For inference, we employ a generalised context tree model. This defines a distribution on multivariate Gaussian piecewise-linear models, which can be updated in closed form. The tree structure itself is constructed using the cover tr…

Graph-based approach repairs programs from diagnostic feedback.

Paper generalizes VB-FTRL for online learning of quantum states with logarithmic loss.

Quantum algorithms improve regret bounds for bandits with knapsacks.

New method solves constrained stochastic optimization problems efficiently.

We resolve the fundamental problem of online decoding with general $n^{th}$ order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation vi…

Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.

New bounds on hyperbolic surfaces' properties using linear programming.

Algorithm balances online and offline data for linear bandits.

FPML algorithm reduces regret by limiting the number of arms chosen per round.

We formalize the notion of nesting probabilistic programming queries and investigate the resulting statistical implications. We demonstrate that while query nesting allows the definition of models which could not otherwise be expressed, such as those involving agents reasoning about other agents, existing systems take …

Faster algorithms for structured SVMs reduce computation time.

New method for natural policy gradients converges linearly.

Max-linear regression problem solved with convex programming.

We study online prediction where regret of the algorithm is measured against a benchmark defined via evolving constraints. This framework captures online prediction on graphs, as well as other prediction problems with combinatorial structure. A key aspect here is that finding the optimal benchmark predictor (even in hi…

We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, wi…

GLCB uses Gated Linear Networks for online contextual bandits.

Extends online linear regression to handle multivariate data.

Bayesian rating system for large competitions improves prediction and efficiency.

OOMP selects features online for sparse linear regression.

Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and…

Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.