Manish Purohit

ICLR Conference 2025 Conference Paper

Descent with Misaligned Gradients and Applications to Hidden Convexity

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We consider the problem of minimizing a convex objective given access to an oracle that outputs "misaligned" stochastic gradients, where the expected value of the output is guaranteed to be correlated with, but not necessarily equal to the true gradient of the objective. In the case where the misalignment (or bias) of the oracle changes slowly, we obtain an optimization algorithm that achieves the optimum iteration complexity of $\tilde O(\epsilon^{-2})$; for the more general case where the changes need not be slow, we obtain an algorithm with $\tilde O(\epsilon^{-3})$ iteration complexity. As an application of our framework, we consider optimization problems with a "hidden convexity" property, and obtain an algorithm with $O(\epsilon^{-3})$ iteration complexity.

ICML Conference 2023 Conference Paper

Bandit Online Linear Optimization with Hints and Queries

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We study variants of the online linear optimization (OLO) problem with bandit feedback, where the algorithm has access to external information about the unknown cost vector. Our motivation is the recent body of work on using such “hints” towards improving regret bounds for OLO problems in the full-information setting. Unlike in the full-information OLO setting, with bandit feedback, we first show that one cannot improve the standard regret bounds of $\tilde{O}(\sqrt{T})$ by using hints, even if they are always well-correlated with the cost vector. In contrast, if the algorithm is empowered to issue queries and if all the responses are correct, then we show $O(\log T)$ regret is achievable. We then show how to make this result more robust—when some of the query responses can be adversarial—by using a little feedback on the quality of the responses.

SODA Conference 2022 Conference Paper

Learning-Augmented Weighted Paging

• Nikhil Bansal 0001
• Christian Coester
• Ravi Kumar 0001
• Manish Purohit
• Erik Vee

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging [45, 50, 52] to the weighted setting. For the case of perfect predictions, we provide an ℓ -competitive deterministic and an O (log ℓ )-competitive randomized algorithm, where ℓ is the number of distinct weight classes. Both these bounds are tight, and imply an O (log W )- and O (log log W )-competitive ratio, respectively, when the page weights lie between 1 and W. Previously, it was not known how to use these predictions in the weighted setting and only bounds of k and O (log k ) were known, where k is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from O ( ℓ ) and O (log ℓ ) to O ( k ) and O (log k ), respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.

ICML Conference 2022 Conference Paper

Parsimonious Learning-Augmented Caching

• Sungjin Im
• Ravi Kumar 0001
• Aditya Petety
• Manish Purohit

Learning-augmented algorithms—in which, traditional algorithms are augmented with machine-learned predictions—have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally when the predictions are accurate yet retain certain worst-case guarantees irrespective of the accuracy of the predictions. This framework has been successfully applied to online problems such as caching where the predictions can be used to alleviate uncertainties. In this paper we introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously. We consider the caching problem—which has been extensively studied in the learning-augmented setting—and show that one can achieve quantitatively similar results but only using a sublinear number of predictions.

ICML Conference 2021 Conference Paper

Dynamic Balancing for Model Selection in Bandits and RL

• Ashok Cutkosky
• Christoph Dann
• Abhimanyu Das
• Claudio Gentile
• Aldo Pacchiano
• Manish Purohit

We propose a framework for model selection by combining base algorithms in stochastic bandits and reinforcement learning. We require a candidate regret bound for each base algorithm that may or may not hold. We select base algorithms to play in each round using a “balancing condition” on the candidate regret bounds. Our approach simultaneously recovers previous worst-case regret bounds, while also obtaining much smaller regret in natural scenarios when some base learners significantly exceed their candidate bounds. Our framework is relevant in many settings, including linear bandits and MDPs with nested function classes, linear bandits with unknown misspecification, and tuning confidence parameters of algorithms such as LinUCB. Moreover, unlike recent efforts in model selection for linear stochastic bandits, our approach can be extended to consider adversarial rather than stochastic contexts.

NeurIPS Conference 2021 Conference Paper

Logarithmic Regret from Sublinear Hints

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar
• Manish Purohit

We consider the online linear optimization problem, where at every step the algorithm plays a point $x_t$ in the unit ball, and suffers loss $\langle c_t, x_t \rangle$ for some cost vector $c_t$ that is then revealed to the algorithm. Recent work showed that if an algorithm receives a _hint_ $h_t$ that has non-trivial correlation with $c_t$ before it plays $x_t$, then it can achieve a regret guarantee of $O(\log T)$, improving on the bound of $\Theta(\sqrt{T})$ in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at _every_ time step. Somewhat surprisingly, we show that an algorithm can obtain $O(\log T)$ regret with just $O(\sqrt{T})$ hints under a natural query model; in contrast, we also show that $o(\sqrt{T})$ hints cannot guarantee better than $\Omega(\sqrt{T})$ regret. We give two applications of our result, to the well-studied setting of {\em optimistic} regret bounds, and to the problem of online learning with abstention.

NeurIPS Conference 2021 Conference Paper

Online Knapsack with Frequency Predictions

• Sungjin Im
• Ravi Kumar
• Mahshid Montazer Qaem
• Manish Purohit

There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms. In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.

TCS Journal 2020 Journal Article

Approximation algorithms for connected maximum cut and related problems

• MohammadTaghi Hajiaghayi
• Guy Kortsarz
• Robert MacDavid
• Manish Purohit
• Kanthi Sarpatwar

An instance of the Connected Maximum Cut problem consists of an undirected graph G = ( V, E ) and the goal is to find a subset of vertices S ⊆ V that maximizes the number of edges in the cut δ ( S ) such that the induced graph G [ S ] is connected. We present the first non-trivial Ω ( 1 log ⁡ n ) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs.

SODA Conference 2020 Conference Paper

Interleaved Caching with Access Graphs

• Ravi Kumar 0001
• Manish Purohit
• Zoya Svitkina
• Erik Vee

ICML Conference 2020 Conference Paper

Online Learning with Imperfect Hints

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a “hint” vector before choosing the action for that round. Rather surprisingly, it was shown that if the hint vector is guaranteed to have a positive correlation with the cost vector, then the online player can achieve a regret of $O(\log T)$, thus significantly improving over the $O(\sqrt{T})$ regret in the general setting. However, the result and analysis require the correlation property at \emph{all} time steps, thus raising the natural question: can we design online learning algorithms that are resilient to bad hints? In this paper we develop algorithms and nearly matching lower bounds for online learning with imperfect hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case. Our results also generalize, simplify, and improve upon previous results on optimistic regret bounds, which can be viewed as an additive version of hints.

NeurIPS Conference 2020 Conference Paper

Online Linear Optimization with Many Hints

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar
• Manish Purohit

We study an online linear optimization (OLO) problem in which the learner is provided access to $K$ ``hint'' vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the $K$ hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case $K=1$. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.

NeurIPS Conference 2019 Conference Paper

Efficient Rematerialization for Deep Networks

• Ravi Kumar
• Manish Purohit
• Zoya Svitkina
• Erik Vee
• Joshua Wang

When training complex neural networks, memory usage can be an important bottleneck. The question of when to rematerialize, i. e. , to recompute intermediate values rather than retaining them in memory, becomes critical to achieving the best time and space efficiency. In this work we consider the rematerialization problem and devise efficient algorithms that use structural characterizations of computation graphs---treewidth and pathwidth---to obtain provably efficient rematerialization schedules. Our experiments demonstrate the performance of these algorithms on many common deep learning models.

ICML Conference 2019 Conference Paper

Hiring Under Uncertainty

• Manish Purohit
• Sreenivas Gollapudi
• Manish Raghavan

In this paper we introduce the hiring under uncertainty problem to model the questions faced by hiring committees in large enterprises and universities alike. Given a set of $n$ eligible candidates, the decision maker needs to choose the sequence of candidates to make offers so as to hire the $k$ best candidates. However, candidates may choose to reject an offer (for instance, due to a competing offer) and the decision maker has a time limit by which all positions must be filled. Given an estimate of the probabilities of acceptance for each candidate, the hiring under uncertainty problem is to design a strategy of making offers so that the total expected value of all candidates hired by the time limit is maximized. We provide a 2-approximation algorithm for the setting where offers must be made in sequence, an 8-approximation when offers may be made in parallel, and a 10-approximation for the more general stochastic knapsack setting with finite probes.

NeurIPS Conference 2018 Conference Paper

Improving Online Algorithms via ML Predictions

• Manish Purohit
• Zoya Svitkina
• Ravi Kumar

In this work we study the problem of using machine-learned predictions to improve performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.

SODA Conference 2014 Conference Paper

Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

• Samir Khuller
• Manish Purohit
• Kanthi K. Sarpatwar

We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem (P cds ), we are given an undirected graph G = ( V, E ) and an integer n′, and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n′ vertices. We obtain the first polynomial time algorithm with an O (lnΔ) approximation factor for this problem, thereby significantly extending the results of Guha and Khuller (Algorithmica, Vol. 20(4), Pages 374–387, 1998) for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem (B cds ), there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a “special” submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies a O (ln q ) approximation (where q denotes the quota) and an O (1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function.