More Like this

1. Online Convex Optimization with Stochastic Constraints

   Yu, Hao; Neely, Michael J (January 2017, Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.)

   This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich’s OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environ- ments or deterministic environments with noisy observations. It also includes many important problems as special case, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained con- vex optimization. To solve this problem, this paper proposes a new algorithm that achieves O(√T ) expected regret and constraint violations and O(√T log(T )) high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm. 

   more » « less
2. Online Convex Optimization with Stochastic Constraints

   Yu, Hao; Neely, Michael J; Wei, Xiaohan (January 2017, 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.)

   This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich’s OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environ- ments or deterministic environments with noisy observations. It also includes many important problems as special case, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained con- vex optimization. To solve this problem, this paper proposes a new algorithm that achieves O(√T ) expected regret and constraint violations and O(√T log(T )) high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm. 

   more » « less
3. Nonsmooth Projection-Free Optimization with Functional Constraints

   K. Asgari; M. J. Neely (November 2023, arXiv:2311.11180v1)

   arXiv:2311.11180v1 (Ed.)

   This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank-Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In con- trast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an ϵ-suboptimal solution in O(ϵ^−2) iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle (LMO) call and a (possibly inexact) subgra- dient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projection-free method designed for constraint-free problems. Our approach uti- lizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule. 

   more » « less
4. ActiveHedge: Hedge meets Active Learning. ICML 2022: 11694-11709

   Bhuvesh Kumar, Jacob D. (August 2022, ICML)

   We consider the classical problem of multi-class prediction with expert advice, but with an active learning twist. In this new setting the learner will only query the labels of a small number of examples, but still aims to minimize regret to the best expert as usual; the learner is also allowed a very short "burn-in" phase where it can fast-forward and query certain highly-informative examples. We design an algorithm that utilizes Hedge (aka Exponential Weights) as a subroutine, and we show that under a very particular combinatorial constraint on the matrix of expert predictions we can obtain a very strong regret guarantee while querying very few labels. This constraint, which we refer to as ζ -compactness, or just compactness, can be viewed as a non-stochastic variant of the disagreement coefficient, another popular parameter used to reason about the sample complexity of active learning in the IID setting. We also give a polynomial-time algorithm to calculate the ζ -compactness of a matrix up to an approximation factor of 3. 

   more » « less
5. Parameter-Free Locally Differentially Private Stochastic Subgradient Descent

   Jun, Kwang-Sung; Orabona, Francesco (January 2019, Workshop on Privacy in Machine Learning at NeurIPS'19)

   null (Ed.)

   We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing $$\epsilon$$-locally differentially private ($$\epsilon$$-LDP). While it has been shown that stochastic optimization is possible with $$\epsilon$$-LDP via the standard SGD, its convergence rate largely depends on the learning rate, which must be tuned via repeated runs. Further, tuning is detrimental to privacy loss since it significantly increases the number of gradient requests. In this work, we propose BANCO (Betting Algorithm for Noisy COins), the first $$\epsilon$$-LDP SGD algorithm that essentially matches the convergence rate of the tuned SGD without any learning rate parameter, reducing privacy loss and saving privacy budget. 

   more » « less