<p>Those are some very technical terms to be throwing around and although I'm familiar with some of the literature from either side, I don't think that I've ever seen them used together. What is the distinction between using a convex program and an LP? They are significantly different, and you refer to both in your question. What you are mentioning sounds really similar to cutting plane or column generation methods in optimization, so perhaps you want to check those out and see if any active learning approaches have been used. In most cutting plane methods, there is usually an efficient (but ad hoc) way to search for violated constraints, usually found by an optimization subproblem; that could be considered similar to active learning but I'm not sure how a canonical active learning approach would look different.</p>

CC BY-SA 3.0
2012-04-16T18:01:24.160Z
2012-04-16T18:01:24.160Z
Andrew Mao
<p>I was wondering if anybody knows of any relevant references on the general topic of <a href="http://en.wikipedia.org/wiki/Active_learning_%28machine_learning%29" rel="nofollow noreferrer">active learning</a> for gradually inferring/updating a convex opt. <strong>formulation</strong>.</p>
<p>As a specific example, I am thinking of a system where a learner can query an oracle the validity of the current best solution to incrementally learn constraints or coefficients of an LP cost function.</p>
<h3>Update</h3>
<p>I am interested in problems and methods where we don't have access to the full definition of the problem (e.g. in LP the constraints that define the polytope, or the cost coefficients are unknown). Yet we may be able to iteratively solve the problem by iteratively asking a sequence of questions to an oracle until the last query confirms we have reached an optimal solution (an optimal vertex in LP)</p>

CC BY-SA 3.0
2012-04-16T18:24:17.020Z
Andrew is right in that this is a very general question. For example, one view of the multiplicative weight update method for SDPs is as an "active" learning problem where you query an oracle to change the distribution over constraints that you're working with. Would that count ?
Suresh Venkat
CC BY-SA 3.0
2012-04-16T19:07:03.533Z
This doesn't seem as much active learning as query learning.  Querying the oracle with the validity of solutions makes me think of Statistical Queries (or even Correlational Statistical Queries).  Lots of work has been done in this area.
Lev Reyzin
CC BY-SA 3.0
2012-04-16T19:33:39.070Z
Thanks @SureshVenkat, yes I guess that would count as well. I guess I am interested in methods where we don't have access to the full definition of the problem (e.g. the constraints that define the polytope, or the cost coefficients of an LP problem are unknown). Yet we may be able to iteratively solve the LP problem by asking a sequence of questions to an oracle until the last query confirms we reached an optimal vertex.
Amelio Vazquez-Reina
CC BY-SA 3.0
2012-04-16T21:09:35.393Z
http://en.wikipedia.org/wiki/Ellipsoid_method ?
Jeffε
CC BY-SA 3.0
2012-04-17T02:00:24.287Z
The version where you don't know the cost might be interesting. The version where you don't have the constraints is one where methods like the ellipsoid come into play.
Suresh Venkat
<reference-request><machine-learning><lg.learning><convex-optimization>
Active learning for inferring a convex optimization formulation
Amelio Vazquez-Reina
# Active learning for inferring a convex optimization formulation

(Asked by: username_0 on 2011-09-06)

I was wondering if anybody knows of any relevant references on the general topic of [active learning](http://en.wikipedia.org/wiki/Active_learning_%28machine_learning%29) for gradually inferring/updating a convex opt. **formulation**.

As a specific example, I am thinking of a system where a learner can query an oracle the validity of the current best solution to incrementally learn constraints or coefficients of an LP cost function.

### Update

I am interested in problems and methods where we don't have access to the full definition of the problem (e.g. in LP the constraints that define the polytope, or the cost coefficients are unknown). Yet we may be able to iteratively solve the problem by iteratively asking a sequence of questions to an oracle until the last query confirms we have reached an optimal solution (an optimal vertex in LP)

**Tags:** reference-request, machine-learning, lg.learning, convex-optimization

> **Comments:**
> **username_1**: Andrew is right in that this is a very general question. For example, one view of the multiplicative weight update method for SDPs is as an "active" learning problem where you query an oracle to change the distribution over constraints that you're working with. Would that count ?  
> **username_2**: This doesn't seem as much active learning as query learning.  Querying the oracle with the validity of solutions makes me think of Statistical Queries (or even Correlational Statistical Queries).  Lots of work has been done in this area.  
> **username_0**: Thanks @SureshVenkat, yes I guess that would count as well. I guess I am interested in methods where we don't have access to the full definition of the problem (e.g. the constraints that define the polytope, or the cost coefficients of an LP problem are unknown). Yet we may be able to iteratively solve the LP problem by asking a sequence of questions to an oracle until the last query confirms we reached an optimal vertex.  
> **username_3**: http://en.wikipedia.org/wiki/Ellipsoid_method ?  
> **username_1**: The version where you don't know the cost might be interesting. The version where you don't have the constraints is one where methods like the ellipsoid come into play.  

---

## 1 answers

### Answer by username_4 on 2012-04-16. Score: 2

Those are some very technical terms to be throwing around and although I'm familiar with some of the literature from either side, I don't think that I've ever seen them used together. What is the distinction between using a convex program and an LP? They are significantly different, and you refer to both in your question. What you are mentioning sounds really similar to cutting plane or column generation methods in optimization, so perhaps you want to check those out and see if any active learning approaches have been used. In most cutting plane methods, there is usually an efficient (but ad hoc) way to search for violated constraints, usually found by an optimization subproblem; that could be considered similar to active learning but I'm not sure how a canonical active learning approach would look different.


---

