2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

Accepted

### Restriction of a convex function to {0, 1}^n

Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question ...
• 6,650
Accepted

### On complexity of linear programming with quadratic equality/inequality constraints?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove: Let $G$ be ...
• 5,712
Accepted

### Gradient descent-like optimization on a convex landscape with noisy sampling

The problem you describe is called "stochastic convex optimization in the bandit setting". This is the problem considered and solved here: http://arxiv.org/pdf/1107.1744v2.pdf They show that after $k$...
• 9,800